Выпуск#9: ITренировка — актуальные вопросы и задачи от ведущих компаний

Мы подготовили для вас новый сет задач и вопросов, задаваемых на собеседованиях в ведущих IT-компаниях.

КДПВ

В подборку вошли задачи для соискателей в Amazon. Вопросы задаются, в том числе и логистические, только не с дронами, а с верблюдами 🙂
Мы постарались подобрать задачи различного уровня сложости, но, в любом случае, их решение будет хорошим упражнением для мозга.

Вопросы

  1. 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 бананов за раз и ест по одному банану за каждый километр пути.
    Какое наибольшее количество бананов удастся доставить таким способом (другие способы перевозки не разрешены)?
  2. 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 минут?

Задачи

  1. 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
Пифагоровской тройки в массиве нет.

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.

Поворот массива означает:

        *                     *         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. Вопрос 1

    На первый взгляд кажется, что верблюд, могущий везти только 1000 бананов при расходе 1 банан/км, придёт пустым к 1000-километровой отметке. Однако ключ к решению — в промежуточных остановках. Будем исходить из предположения, что верблюд потребляет 1 банан/км будучи груженым и порожним. Тогда, остановки на расстоянии >=500 км не имеет смысла делать (минимум, 2 остановки), получается такой план маршрута:

                        ===туда===>                   <===сюда====    ===туда===> И (исходная точка) ===туда===> А <===сюда==== Б ===туда===> Ц (цель)                   <===сюда====    ===туда===>                    ===туда===>	  

    Обратим внимание, что стоимость километра на отрезке ИА — 5 бананов, на отрезке АБ — 3 банана, на отрезке БЦ — 1. Чтобы сохранить максимум бананов, мы должны постараться сократить наиболее затратные отрезки.
    Из точки А верблюд сможет увезти максимум — 2000 бананов, следовательно в точку Б должно быть доставлено 2000 бананов, откуда можно получить длину ИА: 3000 — 5ИА = 2000, т.е. ИА = 200 км.
    Расчёт АБ аналогичен. Поскольку, из Б верблюд увезёт максимум — 1000 бананов, длина АБ получается 2000-3АБ = 1000, т.е. АБ = 333⅓. Длина БЦ — 466⅔, а к цели будет доставлено 533⅓ бананов.

    Правильный ответ также был предложен в комментариях.

  2. Вопрос 2

    В комментарии был дан верный ответ. Действительно, как бы неравномерно ни сгорал шнур, если зажечь его с двух сторон — он сгорит за полчаса. Следовательно, сначала нужно зажечь один шнур с двух сторон, один — только с одной. Когда первый догорит (значит прошло полчаса) — поджечь второй шнур со второго конца, он будет гореть еще 15 минут. Итого — 45 минут.

  3. Задача 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;

  4. Задача 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; } 

  5. Задача 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; } 

FavoriteLoadingДобавить в избранное

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *