Мы подготовили для вас новый сет задач и вопросов, задаваемых на собеседованиях в ведущих IT-компаниях.
В подборку вошли задачи для соискателей в Amazon. Вопросы задаются, в том числе и логистические, только не с дронами, а с верблюдами :)
Мы постарались подобрать задачи различного уровня сложости, но, в любом случае, их решение будет хорошим упражнением для мозга.
Pythagorean Triplet
Anti-clockwise rotated array
Ответы будут даны в течение следующей недели — успейте решить. Удачи!
В подборку вошли задачи для соискателей в Amazon. Вопросы задаются, в том числе и логистические, только не с дронами, а с верблюдами :)
Мы постарались подобрать задачи различного уровня сложости, но, в любом случае, их решение будет хорошим упражнением для мозга.
Вопросы
- Transport the bananas
A person has 3000 bananas and a camel. The person wants to transport maximum number of bananas to a destination which is 1000 KMs away, using only the camel as a mode of transportation. The camel cannot carry more than 1000 bananas at a time and eats a banana every km it travels. What is the maximum number of bananas that can be transferred to the destination using only camel (no other mode of transportation is allowed).
ПереводУ человека есть 3000 бананов и верблюд. Он хочет отвезти максимум бананов в пункт назначения, находящийся в 1000 км, используя верблюда в качестве транспорта. Верблюд не может перевозить более 1000 бананов за раз и ест по одному банану за каждый километр пути.
Какое наибольшее количество бананов удастся доставить таким способом (другие способы перевозки не разрешены)?
- Measure forty-five minutes using wires
How do we measure forty-five minutes using two identical wires, each of which takes an hour to burn. We have matchsticks with us. The wires burn non-uniformly. So, for example, the two halves of a wire might burn in 10 minute and 50 minutes respectively.
ПереводИмеется 2 идентичных шнура, каждый из которых сгорает за час. Спички у нас с собой, шнуры сгорают неравномерно. Так, например, половина может сгореть за 10 минут и оставшаяся половина за 50 минут. Как, используя эти шнуры, нам отсчитать 45 минут?
Задачи
- Elephants lifetime
Given life time of different elephants. Find the period when maximum number of elephants were alive.
Input: [2005, 2010], [2006, 2015], [2002, 2007]
Output: [2006, 2007] .ПереводДано время жизни нескольких слонов. Найти период, в который жило наибольшее количество слонов.
Вход: [2005, 2010], [2006, 2015], [2002, 2007]
Выход: [2006, 2007] .
Pythagorean Triplet
Given an array of integers, write a function that returns True if there is a triplet (a, b, c) that satisfies a^2 + b^2 = c^2.
Example:
Input: arr[] = {3, 1, 4, 6, 5}
Output: True
There is a Pythagorean triplet (3, 4, 5).
Input: arr[] = {10, 4, 6, 12, 5}
Output: False
There is no Pythagorean triplet.
Перевод
Дан массив целых чисел, нужно написать функцию, возвращающую True, если в массиве содержится тройка чисел (a, b, c), так, что a^2 + b^2 = c^2
Пример:
Вход: arr[] = {3, 1, 4, 6, 5}
Выход: True
Пифагорова тройка — (3, 4, 5).
Вход: arr[] = {10, 4, 6, 12, 5}
Выход: False
Пифагоровской тройки в массиве нет.
Пример:
Вход: arr[] = {3, 1, 4, 6, 5}
Выход: True
Пифагорова тройка — (3, 4, 5).
Вход: arr[] = {10, 4, 6, 12, 5}
Выход: False
Пифагоровской тройки в массиве нет.
Anti-clockwise rotated array
Consider an array of distinct integers sorted in increasing order. The array has been rotated (anti-clockwise) k number of times. Given such an array, find the value of k.
Array rotation:
* * 0 1 5 1 => 0 2 4 2 5 3 3 4
Examples:
Input: arr[] = {15, 18, 2, 3, 6, 12}
Output: 4
Initial array must be {2, 3, 6, 12, 15. 18}. We get the given array after rotating the initial array twice.
Input: arr[] = {7, 9, 11, 12, 5}
Output: 1
Input: arr[] = {7, 9, 11, 12, 15};
Output: 0
Перевод
Предположим, имеется массив целых чисел, отсортированный по возрастанию. Массив был «повернут» против часовой стрелки k раз. Найти k.
Поворот массива означает:
Примеры:
Вход: arr[] = {15, 18, 2, 3, 6, 12}
Выход: 4
Исходны массив должен быть — {2, 3, 6, 12, 15. 18}. Мы получим входной массив, если повернем исходный 2 раза.
Вход: arr[] = {7, 9, 11, 12, 5}
Выход: 1
Вход: arr[] = {7, 9, 11, 12, 15};
Выход: 0
Поворот массива означает:
* *
0 1
5 1 => 0 2
4 2 5 3
3 4
Примеры:
Вход: arr[] = {15, 18, 2, 3, 6, 12}
Выход: 4
Исходны массив должен быть — {2, 3, 6, 12, 15. 18}. Мы получим входной массив, если повернем исходный 2 раза.
Вход: arr[] = {7, 9, 11, 12, 5}
Выход: 1
Вход: arr[] = {7, 9, 11, 12, 15};
Выход: 0
Ответы будут даны в течение следующей недели — успейте решить. Удачи!
Решения
- Вопрос 1На первый взгляд кажется, что верблюд, могущий везти только 1000 бананов при расходе 1 банан/км, придёт пустым к 1000-километровой отметке. Однако ключ к решению — в промежуточных остановках. Будем исходить из предположения, что верблюд потребляет 1 банан/км будучи груженым и порожним. Тогда, остановки на расстоянии >=500 км не имеет смысла делать (минимум, 2 остановки), получается такой план маршрута:
===туда===> <===сюда==== ===туда===> И (исходная точка) ===туда===> А <===сюда==== Б ===туда===> Ц (цель) <===сюда==== ===туда===> ===туда===>
Обратим внимание, что стоимость километра на отрезке ИА — 5 бананов, на отрезке АБ — 3 банана, на отрезке БЦ — 1. Чтобы сохранить максимум бананов, мы должны постараться сократить наиболее затратные отрезки.
Из точки А верблюд сможет увезти максимум — 2000 бананов, следовательно в точку Б должно быть доставлено 2000 бананов, откуда можно получить длину ИА: 3000 — 5ИА = 2000, т.е. ИА = 200 км.
Расчёт АБ аналогичен. Поскольку, из Б верблюд увезёт максимум — 1000 бананов, длина АБ получается 2000-3АБ = 1000, т.е. АБ = 333⅓. Длина БЦ — 466⅔, а к цели будет доставлено 533⅓ бананов.
Правильный ответ также был предложен в комментариях.
- Вопрос 2В комментарии был дан верный ответ. Действительно, как бы неравномерно ни сгорал шнур, если зажечь его с двух сторон — он сгорит за полчаса. Следовательно, сначала нужно зажечь один шнур с двух сторон, один — только с одной. Когда первый догорит (значит прошло полчаса) — поджечь второй шнур со второго конца, он будет гореть еще 15 минут. Итого — 45 минут.
- Задача 1В комментариях были предложены верные алгоритмы, но не было примеров кода.
Вариант решения:
#include <iostream> #include <iomanip> #include <iterator> using namespace std; typedef struct{ int birthYear; int deathYear; }LIFE; typedef struct{ int startYear; int endYear; }PERIOD; int FindMinStartYear(LIFE* anmimals, int len) { int startYear = anmimals[0].birthYear; for(int i = 1; i < len; ++i){ if(anmimals[i].birthYear < startYear){ startYear = anmimals[i].birthYear; } } return startYear; } int FindMaxEndYear(LIFE* anmimals, int len) { int endYear = anmimals[0].deathYear; for(int i = 1; i < len; ++i){ if(anmimals[i].deathYear > endYear){ endYear = anmimals[i].deathYear; } } return endYear; } int FindPeriodOfMaxAnimal(LIFE* anmimals, int len, PERIOD& p) { int startYear = FindMinStartYear( anmimals, len); int endYear = FindMaxEndYear( anmimals, len); int* period = new int[endYear - startYear + 1]; for(int i = 0; i < endYear - startYear + 1; ++i){ period[i] = 0; } for(int i = 0; i < len; ++i){ for(int j = anmimals[i].birthYear; j <= anmimals[i].deathYear; ++j){ period[j - startYear]++; } } cout << endl; copy(period, period + endYear - startYear + 1, ostream_iterator<int>(cout, " ")); cout << endl; int maxAnimals = period[0]; int maxStart = 0; int maxEnd = 0; for(int i = 0; i <= endYear - startYear; ++i){ if(period[i] > maxAnimals){ maxStart = i; maxAnimals = period[i]; } if(period[i] == maxAnimals){ maxEnd = i; } } delete[] period; p.startYear = maxStart + startYear; p.endYear = maxEnd + startYear; return maxAnimals; } int main(int argc, char* argv[]) { LIFE testCases[] = { {5, 11}, {6, 18}, {2, 5}, {3, 12} }; PERIOD p; int maxAnimals = FindPeriodOfMaxAnimal(testCases, sizeof(testCases)/sizeof(testCases[0]), p); cout << "In the period " << p.startYear << " and "; cout << p.endYear << ", there are " << maxAnimals << endl; return 0;
- Задача 2Вариант решения с сортировкой:
// A C++ program that returns true if there is a Pythagorean // Triplet in a given array. #include <iostream> #include <algorithm> using namespace std; // Returns true if there is a triplet with following property // A[i]*A[i] = A[j]*A[j] + A[k]*[k] // Note that this function modifies given array bool isTriplet(int arr[], int n) { // Square array elements for (int i=0; i<n; i++) arr[i] = arr[i]*arr[i]; // Sort array elements sort(arr, arr + n); // Now fix one element one by one and find the other two // elements for (int i = n-1; i >= 2; i--) { // To find the other two elements, start two index // variables from two corners of the array and move // them toward each other int l = 0; // index of the first element in arr[0..i-1] int r = i-1; // index of the last element in arr[0..i-1] while (l < r) { // A triplet found if (arr[l] + arr[r] == arr[i]) return true; // Else either move 'l' or 'r' (arr[l] + arr[r] < arr[i])? l++: r--; } } // If we reach here, then no triplet found return false; } /* Driver program to test above function */ int main() { int arr[] = {3, 1, 4, 6, 5}; int arr_size = sizeof(arr)/sizeof(arr[0]); isTriplet(arr, arr_size)? cout << "Yes": cout << "No"; return 0; }
- Задача 3При внимательном рассмотрении задачи, можно заметить, что число поворотов массива равно длине массива — индекс минимального элемента, который можно найти бинарным поиском. Вариант решения:
// Binary Search based C++ program to find number // of rotations in a sorted and rotated array. #include<bits/stdc++.h> using namespace std; // Returns count of rotations for an array which // is first sorted in ascending order, then rotated int countRotations(int arr[], int low, int high) { // This condition is needed to handle the case // when array is not rotated at all if (high < low) return 0; // If there is only one element left if (high == low) return low; // Find mid int mid = low + (high - low)/2; /*(low + high)/2;*/ // Check if element (mid+1) is minimum element. // Consider the cases like {3, 4, 5, 1, 2} if (mid < high && arr[mid+1] < arr[mid]) return (mid+1); // Check if mid itself is minimum element if (mid > low && arr[mid] < arr[mid - 1]) return mid; // Decide whether we need to go to left half or // right half if (arr[high] > arr[mid]) return countRotations(arr, low, mid-1); return countRotations(arr, mid+1, high); } // Driver code int main() { int arr[] = {15, 18, 2, 3, 6, 12}; int n = sizeof(arr)/sizeof(arr[0]); int sizearr = n -1 ; int countr = sizearr -countRotations(arr, 0, sizearr); cout << countr; return 0; }