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

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



В подборку попали вопросы, встречающиеся на собеседованиях в Adobe (да, вопрос про цвет включён в подборку :). Задачи различного уровня сложности, но все решаемые. Особенно, если Вы уже ответили на вопросы из прошлых выпусков.

Надеемся, что приведённые задачи помогут Вам качественно подготовиться к предстоящим собеседованиями.

Вопросы

1. 8 marbles
   

   Let’s say you have 8 marbles and a two-pan balance.
   All of the marbles look the same. Each marble weighs 2.0 grams except for one, which is slightly heavier at 2.05 grams.
   How would you find the heaviest marble if you are only allowed to weigh the marbles 2 times using the balance scale?
   

   
   
   Перевод

   Предположим, у вас 8 стеклянных шариков и чашечные весы. Все шарики выглядят одинаково. Каждый весит 2 грамма, за исключением одного, который чуть тяжелее — 2.05 грамма.
   Как найти самый тяжёлый шарик, если разрешено провести всего 2 взвешивания?
   
   
   
2. Falling bear
   

   A bear fell from a height of 10m on the ground in √2 seconds. But somehow, it didn’t get hurt. What is the colour of bear?

   
   
   Перевод

   Медведь, падая с высоты 10м, достигает земли за √2 seconds и, почему-то, остаётся без повреждений. Какого цвета медведь?
   
   Прим: Я некоторое время подумал, и всё-таки заглянул в ответ. Вопрос немного с подвохом, но ответить можно. Решил привести здесь, если такое на собеседованиях встречается.
   

Задачи

1. Product of max and min in 2 arrays
   

   Given two arrays of integers, the task is to calculate the product of max element of first array and min element of second array.
   
   Ex:
   Input: arr1[] = {5, 7, 9, 3, 6, 2},
   arr2[] = {1, 2, 6, -1, 0, 9}
   Output: max element in first array
   is 9 and min element in second array
   is -1. The product of these two is -9.
   
   Input: arr1[] = {1, 4, 2, 3, 10, 2},
   arr2[] = {4, 2, 6, 5, 2, 9}
   Output: 20.
   

   
   
   Перевод

   Даны 2 массива целых чисел. Задача — вычислить произведение максимального элемента из первого массива и минимального из второго массива.
   
   Примеры:
   Даны: arr1[] = {5, 7, 9, 3, 6, 2}, arr2[] = {1, 2, 6, -1, 0, 9}
   Ответ: максимальный элемент первого массива — 9, минимальный элемент второго -1. Произведение -9.
   
   Даны: arr1[] = {1, 4, 2, 3, 10, 2},
   arr2[] = {4, 2, 6, 5, 2, 9}
   Ответ: 20.
   
   
   
2. Maximum Chocolates
   

   You have $15 with you. You go to a shop and shopkeeper tells you price as $1 per chocolate. He also tells you that you can get a chocolate in return of 3 wrappers. How many maximum chocolates you can eat?
   
   Write a program to find solution for variable inputs. Given following three values, the task is to find the total number of maximum chocolates you can eat.
   
   money: Money you have to buy chocolates
   price: Price of a chocolate
   wrap: Number of wrappers to be returned for getting one extra chocolate.
   
   It may be assumed that all given values are positive integers and greater than 1.
   

   
   
   Перевод

   У Вас есть $15. В магазине у продавца Вы узнаёте цену за шоколадку — $1. Продавец также сообщает, что за 3 обертки выдаст вам ещё шоколадку. На какой максимум шоколадок Вы можете рассчитывать?
   
   Напишите программу для переменных входных данных, задачей которой будет найти максимум шоколадок:
   
   money: Имеющиеся деньги
   price: Цена за шоколадку
   wrap: Количество обёрток нужное, чтобы получить ещё одну шоколадку.
   
   Можно считать, что все входные данные являются целыми и больше 1.
   
   
   
3. Sort array larger than RAM
   

   Given 2 machines, each having 64 GB RAM, containing all integers (8 byte). You need to sort the entire 128 GB data. You may assume a small amount of additional RAM.

   
   
   Перевод

   Имеются 2 компьютера, у каждого по 64 Гб ОЗУ, занятых целыми числами (8 байт). Вам необходимо отсортировать все 128 Гб данных. Можно использовать небольшое количество дополнительной памяти ОЗУ.
   
   
   

Ответы, как обычно, будут даны в течение следующей недели — успейте решить. Удачи!

Решения

1. Вопрос 1

   В комментариях нашли верный ответ:
   1. берем шесть шариков по 3 на каждую чашу
   2. если чаши равны, то искомый шарик в оставшихся двух
   3. если не равны, то выкидываем три самых легких
   4. взвешиваем 2 из оставшихся трех — задача решена :)
   
   
   
2. Вопрос 2

   В оригинале, цвет медведя — белый, поскольку он падал с ускорением 10 м/c2, что может быть на полюсах. Правильное решение было найдено, и предложено несколько альтернативных :)
   
   
   
3. Задача 1

   
   Решение с сортировкой массивов не является оптимальным. Простой проход по массивам в поисках min/max лучше:
   

   // C++ program to find the to calculate
   // the product of max element of first 
   // array and min element of second array
   #include <bits/stdc++.h>
   using namespace std;
    
   // Function to calculate the product
   int minMaxProduct(int arr1[], int arr2[], 
                            int n1, int n2)
   {
       // Initialize max of first array
       int max = arr1[0];
    
       // initialize min of second array
       int min = arr2[0];
    
       int i;
       for (i = 1; i < n1 && i < n2; ++i) {
    
           // To find the maximum element 
           // in first array
           if (arr1[i] > max)
               max = arr1[i];
    
           // To find the minimum element
           // in second array
           if (arr2[i] < min)
               min = arr2[i];
       }
     
       // Process remaining elements
       while (i < n1)
       {
           if (arr1[i] > max)
              max = arr1[i];  
           i++;
       }
       while (i < n2)
       {
           if (arr2[i] < min)
              min = arr2[i];  
           i++;
       }
    
       return max * min;
   }
    
   // Driven code
   int main()
   {
       int arr1[] = { 10, 2, 3, 6, 4, 1 };
       int arr2[] = { 5, 1, 4, 2, 6, 9 };
       int n1 = sizeof(arr1) / sizeof(arr1[0]);
       int n2 = sizeof(arr1) / sizeof(arr1[0]);
       cout << minMaxProduct(arr1, arr2, n1, n2) << endl;
       return 0;
   }

   
   
   
   
4. Задача 2

   Решение с рекурсией — не самое оптимальное в данном случае. В оригинальном решении путём наблюдения была выведена формула totalChoc = (choc-1)/(wrap-1) и программа в таком случае приняла вид:
   

   // Efficient C++ program to find maximum
   // number of chocolates
   #include <iostream>
   using namespace std;
    
   // Returns maximum number of chocolates we can eat
   // with given money, price of chocolate and number
   // of wrapprices required to get a chocolate.
   int countMaxChoco(int money, int price, int wrap)
   {
       // Corner case
       if (money < price)
          return 0;
    
       // First find number of chocolates that
       // can be purchased with the given amount
       int choc = money / price;
    
       // Now just add number of chocolates with the
       // chocolates gained by wrapprices
       choc = choc + (choc - 1) / (wrap - 1);
       return choc;
   }
    
   // Driver code
   int main()
   {
       int money = 15 ; // total money
       int price = 1; // cost of each candy
       int wrap = 3 ; // no of wrappers needs to be
       // exchanged for one chocolate.
    
       cout << countMaxChoco(money, price, wrap);
       return 0;
   }
   

   
   
   
   
5. Задача 3

   В качестве решения задачи предлагается External merge sort:
   
   

   // C++ program to implement external sorting using 
   // merge sort
   #include <bits/stdc++.h>
   using namespace std;
    
   struct MinHeapNode
   {
       // The element to be stored
       int element;
    
       // index of the array from which the element is taken
       int i;
   };
    
   // Prototype of a utility function to swap two min heap nodes
   void swap(MinHeapNode* x, MinHeapNode* y);
    
   // A class for Min Heap
   class MinHeap
   {
       MinHeapNode* harr; // pointer to array of elements in heap
       int heap_size;     // size of min heap
    
   public:
       // Constructor: creates a min heap of given size
       MinHeap(MinHeapNode a[], int size);
    
       // to heapify a subtree with root at given index
       void MinHeapify(int);
    
       // to get index of left child of node at index i
       int left(int i) { return (2 * i + 1); }
    
       // to get index of right child of node at index i
       int right(int i) { return (2 * i + 2); }
    
       // to get the root
       MinHeapNode getMin() {  return harr[0]; }
    
       // to replace root with new node x and heapify()
       // new root
       void replaceMin(MinHeapNode x)
       {
           harr[0] = x;
           MinHeapify(0);
       }
   };
    
   // Constructor: Builds a heap from a given array a[]
   // of given size
   MinHeap::MinHeap(MinHeapNode a[], int size)
   {
       heap_size = size;
       harr = a; // store address of array
       int i = (heap_size - 1) / 2;
       while (i >= 0)
       {
           MinHeapify(i);
           i--;
       }
   }
    
   // A recursive method to heapify a subtree with root
   // at given index. This method assumes that the
   // subtrees are already heapified
   void MinHeap::MinHeapify(int i)
   {
       int l = left(i);
       int r = right(i);
       int smallest = i;
       if (l < heap_size && harr[l].element < harr[i].element)
           smallest = l;
       if (r < heap_size && harr[r].element < harr[smallest].element)
           smallest = r;
       if (smallest != i)
       {
           swap(&harr[i], &harr[smallest]);
           MinHeapify(smallest);
       }
   }
    
   // A utility function to swap two elements
   void swap(MinHeapNode* x, MinHeapNode* y)
   {
       MinHeapNode temp = *x;
       *x = *y;
       *y = temp;
   }
    
   // Merges two subarrays of arr[].
   // First subarray is arr[l..m]
   // Second subarray is arr[m+1..r]
   void merge(int arr[], int l, int m, int r)
   {
       int i, j, k;
       int n1 = m - l + 1;
       int n2 = r - m;
    
       /* create temp arrays */
       int L[n1], R[n2];
    
       /* Copy data to temp arrays L[] and R[] */
       for(i = 0; i < n1; i++)
           L[i] = arr[l + i];
       for(j = 0; j < n2; j++)
           R[j] = arr[m + 1 + j];
    
       /* Merge the temp arrays back into arr[l..r]*/
       i = 0; // Initial index of first subarray
       j = 0; // Initial index of second subarray
       k = l; // Initial index of merged subarray
       while (i < n1 && j < n2)
       {
           if (L[i] <= R[j])
               arr[k++] = L[i++];
           else
               arr[k++] = R[j++];
       }
    
       /* Copy the remaining elements of L[], if there
          are any */
       while (i < n1)
           arr[k++] = L[i++];
    
       /* Copy the remaining elements of R[], if there
          are any */
       while(j < n2)
           arr[k++] = R[j++];
   }
    
   /* l is for left index and r is right index of the
      sub-array of arr to be sorted */
   void mergeSort(int arr[], int l, int r)
   {
       if (l < r)
       {
           // Same as (l+r)/2, but avoids overflow for
           // large l and h
           int m = l + (r - l) / 2;
    
           // Sort first and second halves
           mergeSort(arr, l, m);
           mergeSort(arr, m + 1, r);
    
           merge(arr, l, m, r);
       }
   }
    
   FILE* openFile(char* fileName, char* mode)
   {
       FILE* fp = fopen(fileName, mode);
       if (fp == NULL)
       {
           perror("Error while opening the file.\n");
           exit(EXIT_FAILURE);
       }
       return fp;
   }
    
   // Merges k sorted files.  Names of files are assumed
   // to be 1, 2, 3, ... k
   void mergeFiles(char *output_file, int n, int k)
   {
       FILE* in[k];
       for (int i = 0; i < k; i++)
       {
           char fileName[2];
    
           // convert i to string
           snprintf(fileName, sizeof(fileName), "%d", i);
    
           // Open output files in read mode.
           in[i] = openFile(fileName, "r");
       }
    
       // FINAL OUTPUT FILE
       FILE *out = openFile(output_file, "w");
    
       // Create a min heap with k heap nodes.  Every heap node
       // has first element of scratch output file
       MinHeapNode* harr = new MinHeapNode[k];
       int i;
       for (i = 0; i < k; i++)
       {
           // break if no output file is empty and
           // index i will be no. of input files
           if (fscanf(in[i], "%d ", &harr[i].element) != 1)
               break;
    
           harr[i].i = i; // Index of scratch output file
       }
       MinHeap hp(harr, i); // Create the heap
    
       int count = 0;
    
       // Now one by one get the minimum element from min
       // heap and replace it with next element.
       // run till all filled input files reach EOF
       while (count != i)
       {
           // Get the minimum element and store it in output file
           MinHeapNode root = hp.getMin();
           fprintf(out, "%d ", root.element);
    
           // Find the next element that will replace current
           // root of heap. The next element belongs to same
           // input file as the current min element.
           if (fscanf(in[root.i], "%d ", &root.element) != 1 )
           {
               root.element = INT_MAX;
               count++;
           }
    
           // Replace root with next element of input file
           hp.replaceMin(root);
       }
    
       // close input and output files
       for (int i = 0; i < k; i++)
           fclose(in[i]);
    
       fclose(out);
   }
    
   // Using a merge-sort algorithm, create the initial runs
   // and divide them evenly among the output files
   void createInitialRuns(char *input_file, int run_size,
                          int num_ways)
   {
       // For big input file
       FILE *in = openFile(input_file, "r");
    
       // output scratch files
       FILE* out[num_ways];
       char fileName[2];
       for (int i = 0; i < num_ways; i++)
       {
           // convert i to string
           snprintf(fileName, sizeof(fileName), "%d", i);
    
           // Open output files in write mode.
           out[i] = openFile(fileName, "w");
       }
    
       // allocate a dynamic array large enough
       // to accommodate runs of size run_size
       int* arr = (int*)malloc(run_size * sizeof(int));
    
       bool more_input = true;
       int next_output_file = 0;
    
       int i;
       while (more_input)
       {
           // write run_size elements into arr from input file
           for (i = 0; i < run_size; i++)
           {
               if (fscanf(in, "%d ", &arr[i]) != 1)
               {
                   more_input = false;
                   break;
               }
           }
    
           // sort array using merge sort
           mergeSort(arr, 0, i - 1);
    
           // write the records to the appropriate scratch output file
           // can't assume that the loop runs to run_size
           // since the last run's length may be less than run_size
           for (int j = 0; j < i; j++)
               fprintf(out[next_output_file], "%d ", arr[j]);
    
           next_output_file++;
       }
    
       // close input and output files
       for (int i = 0; i < num_ways; i++)
           fclose(out[i]);
    
       fclose(in);
   }
    
   // For sorting data stored on disk
   void externalSort(char* input_file,  char *output_file,
                     int num_ways, int run_size)
   {
       // read the input file, create the initial runs,
       // and assign the runs to the scratch output files
       createInitialRuns(input_file, run_size, num_ways);
    
       // Merge the runs using the K-way merging
       mergeFiles(output_file, run_size, num_ways);
   }
    
    
   // Driver program to test above
   int main()
   {
       // No. of Partitions of input file.
       int num_ways = 10;
    
       // The size of each partition
       int run_size = 1000;
    
       char input_file[] = "input.txt";
       char output_file[] = "output.txt";
    
       FILE* in = openFile(input_file, "w");
    
       srand(time(NULL));
    
       // generate input
       for (int i = 0; i < num_ways * run_size; i++)
           fprintf(in, "%d ", rand());
    
       fclose(in);
    
       externalSort(input_file, output_file, num_ways,
                   run_size);
    
       return 0;
   }