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

Мы подготовили для Вас новый выпуск с интересными задачами с собеседований в Apple.



В Apple соискателями могут задать вопросы не только технического плана, но и о сокровищах и пиратах (интересно, связано ли это с позицией компании в отношении нелегального контента?). Вопросы и задачи, как всегда, разного уровня сложности. В целом, нужно отметить, что доля логических задач вытесняется чисто техническими вопросами, но тем не менее, головоломки на собеседованиях все ещё встречаются.

Вопросы

1. Gems and Pirates
   

   Seven pirates attacked the ship and looted some rare gems from them. They decided to rest for some time and then divide the gems later. While everyone was resting, two pirates wake up and planned to divide gems equally between the two. When they divided gems equally, one gem was left. So, they decided to wake up the third pirate and divide among three, but alas again one gem was left. They decide to wake up the fourth pirate to divide the gems and again one gem was left. The same happened again with the fifth and sixth. Finally, they woke up the 7th pirate and this time the gems were divided equally.
   How many minimum gems did they stole in total ?

   
   
   Перевод

   Семь пиратов захватили судно и добыли несколько драгоценных камней. Они решили отдохнуть и заняться дележём добычи позже. Пока все спали, 2 пирата проснулись и решили поделить камни между собой поровну. Когда они поделили, остался один камень. Тогда они решили разбудить ещё одного пирата и поделить камни поровну на троих, но когда они так и поступили — остался один камень. Они разбудили 4-го пирата и снова попробовали разделить сокровище, и снова остался один камень. Так же было и когда они разбудили пятого и шестого пиратов. Лишь когда они разбудили седьмого пирата, им удалось разделить все камни без остатка.
   Сколько (минимум) драгоценных камней составили добычу пиратов?
   
   
   
2. Faulty coin & perfect coin
   

   I have two coins.
   * One of the coin is a faulty coin having tail on both side of it.
   * The other coin is a perfect coin (heads on side and tail on other).
   
   I blind fold myself and pick a coin and put the coin on table. The face of coin towards the sky is tail.
   
   What is the probability that other side is also tail?
   

   
   
   Перевод

   У меня 2 монеты:
   * Одна из них — неправильная монета, с решками на обеих сторонах.
   * Вторая монета — идеальная монета (орел на одной стороне, и решка на обратной).
   
   Я, с завязанными глазами, беру монету и подбрасываю её на стол. Видимая часть монеты — решка.
   
   Какова вероятность, что на обратной стороне — тоже решка?
   
   
   

Задачи

1. Print all nodes at distance k
   

   Given a binary tree, a target node in the binary tree, and an integer value k, print all the nodes that are at distance k from the given target node. No parent pointers are available.
   
   Consider the tree shown in diagram:
   

    
                                 20
                                /   \
                               8    22
                             /   \
                           4      12
                                 /   \
                                10    14
   

   
   
   Input: target = pointer to node with data 8; root = pointer to node with data 20; k = 2.
   Output: 10 14 22
   
   If target is 14 and k is 3, then output should be “4 20”
   

   
   
   Перевод

   Дано бинарное дерево, выбранный узел дерева и целое число k. Напечатайте все узлы дерева, которые находятся на дистанции k от целевого узла. Родительские ссылки не доступны.
   
   Рассмотрим дерево:
   

    
                                 20
                                /   \
                               8    22
                             /   \
                           4      12
                                 /   \
                                10    14
   

   
   
   Вход: target = указатель на узел 8; root = указатель на узел 20; k = 2.
   Выход: 10 14 22
   
   Если target = 14 и k = 3, тогда выход должен быть “4 20”.
   
   
   
2. Car assembly task
   

   A car factory has two assembly lines, each with n stations. A station is denoted by S_i,j where i is either 1 or 2 and indicates the assembly line the station is on, and j indicates the number of the station. The time taken per station is denoted by a_i,j. Each station is dedicated to some sort of work like engine fitting, body fitting, painting and so on. So, a car chassis must pass through each of the n stations in order before exiting the factory. The parallel stations of the two assembly lines perform the same task. After it passes through station S_i,j, it will continue to station S_i,j+1 unless it decides to transfer to the other line. Continuing on the same line incurs no extra cost, but transferring from line i at station j – 1 to station j on the other line takes time t_i,j. Each assembly line takes an entry time e_i and exit time x_i which may be different for the two lines. Give an algorithm for computing the minimum time it will take to build a car chassis.

   
   
   Перевод

   Машинная фабрика имеет 2 сборочные линии, каждая с N станций. Станция определяется S_i,j, где i, могущая принимать значения 1 или 2, обозначает линию, на которой находится станция, а j — обозначает номер станции. Время затрачиваемое станцией обозначается как a_i,j. Каждая станция предназначена для выполнения определенного вида работы — подгонки двигателя, подгонки корпуса, покраски и т.д. Так, ходовая часть машины должна пройти через все n станций в определенном порядке, прежде чем будет выпущена с завода. Параллельные станции на обеих сборочных линиях выполняют одинаковую задачу. После того, как деталь пройдёт станцию S_i,j, она продолжит движение через S_i,j+1, если не будет принято решение перевести её на другую линию. Переход от станции к станции на одной линии не требует дополнительного времени, но перевод со станции j-i на станцию j на другой линии — требует времени t_i,j. Каждая сборочная линия также имеет входное время e_i и выходное время x_i, которое может быть различным для обеих линий. Предложите алгоритм с минимальным временем сборки машины.
   
   
   
3. Search in sorted matrix
   

   Given an n x n matrix, where every row and column is sorted in increasing order. Given a key, write a program finding whether this key is in the matrix.

   
   
   Перевод

   Дана матрица NxN, где каждая строка и столбец отсортированы по возрастанию. Дано ключевое значение. Напишите программу для определения, где в матрице находится это ключевое значение.
   
   
   

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

Решения

1. Вопрос 1

   У пиратов был 301 самоцвет, как верно подметили в комментарии.
   
   
   
2. Вопрос 2

   Вероятность — 2/3, почему можно посмотреть в этом комментарии.
   
   
   
3. Задача 1

   Вариант решения:
   
   

   // Java program to print all nodes at a distance k from given node
    
   // A binary tree node
   class Node 
   {
       int data;
       Node left, right;
     
       Node(int item) 
       {
           data = item;
           left = right = null;
       }
   }
     
   class BinaryTree 
   {
       Node root;
       /* Recursive function to print all the nodes at distance k in
          tree (or subtree) rooted with given root. */
     
       void printkdistanceNodeDown(Node node, int k) 
       {
           // Base Case
           if (node == null || k < 0)
               return;
     
           // If we reach a k distant node, print it
           if (k == 0) 
           {
               System.out.print(node.data);
               System.out.println("");
               return;
           }
     
           // Recur for left and right subtrees
           printkdistanceNodeDown(node.left, k - 1);
           printkdistanceNodeDown(node.right, k - 1);
       }
     
       // Prints all nodes at distance k from a given target node.
       // The k distant nodes may be upward or downward.This function
       // Returns distance of root from target node, it returns -1
       // if target node is not present in tree rooted with root.
       int printkdistanceNode(Node node, Node target, int k) 
       {
           // Base Case 1: If tree is empty, return -1
           if (node == null)
               return -1;
     
           // If target is same as root.  Use the downward function
           // to print all nodes at distance k in subtree rooted with
           // target or root
           if (node == target) 
           {
               printkdistanceNodeDown(node, k);
               return 0;
           }
     
           // Recur for left subtree
           int dl = printkdistanceNode(node.left, target, k);
     
           // Check if target node was found in left subtree
           if (dl != -1) 
           {
                 
               // If root is at distance k from target, print root
               // Note that dl is Distance of root's left child from 
               // target
               if (dl + 1 == k) 
               {
                   System.out.print(node.data);
                   System.out.println("");
               }
                 
               // Else go to right subtree and print all k-dl-2 distant nodes
               // Note that the right child is 2 edges away from left child
               else
                   printkdistanceNodeDown(node.right, k - dl - 2);
     
               // Add 1 to the distance and return value for parent calls
               return 1 + dl;
           }
     
           // MIRROR OF ABOVE CODE FOR RIGHT SUBTREE
           // Note that we reach here only when node was not found in left 
           // subtree
           int dr = printkdistanceNode(node.right, target, k);
           if (dr != -1) 
           {
               if (dr + 1 == k) 
               {
                   System.out.print(node.data);
                   System.out.println("");
               } 
               else
                   printkdistanceNodeDown(node.left, k - dr - 2);
               return 1 + dr;
           }
     
           // If target was neither present in left nor in right subtree
           return -1;
       }
     
       // Driver program to test the above functions
       public static void main(String args[]) 
       {
           BinaryTree tree = new BinaryTree();
     
           /* Let us construct the tree shown in above diagram */
           tree.root = new Node(20);
           tree.root.left = new Node(8);
           tree.root.right = new Node(22);
           tree.root.left.left = new Node(4);
           tree.root.left.right = new Node(12);
           tree.root.left.right.left = new Node(10);
           tree.root.left.right.right = new Node(14);
           Node target = tree.root.left.right;
           tree.printkdistanceNode(tree.root, target, 2);
       }
   }
   

   
   
   
   
4. Задача 2

   Исходный вариант решения:
   

   // A C program to find minimum possible time by the car chassis to complete
   #include <stdio.h>
   #define NUM_LINE 2
   #define NUM_STATION 4
    
   // Utility function to find minimum of two numbers
   int min(int a, int b) { return a < b ? a : b; }
    
   int carAssembly(int a[][NUM_STATION], int t[][NUM_STATION], int *e, int *x)
   {
       int T1[NUM_STATION], T2[NUM_STATION], i;
    
       T1[0] = e[0] + a[0][0]; // time taken to leave first station in line 1
       T2[0] = e[1] + a[1][0]; // time taken to leave first station in line 2
    
       // Fill tables T1[] and T2[] using the above given recursive relations
       for (i = 1; i < NUM_STATION; ++i)
       {
           T1[i] = min(T1[i-1] + a[0][i], T2[i-1] + t[1][i] + a[0][i]);
           T2[i] = min(T2[i-1] + a[1][i], T1[i-1] + t[0][i] + a[1][i]);
       }
    
       // Consider exit times and retutn minimum
       return min(T1[NUM_STATION-1] + x[0], T2[NUM_STATION-1] + x[1]);
   }
    
   int main()
   {
       int a[][NUM_STATION] = {{4, 5, 3, 2},
                   {2, 10, 1, 4}};
       int t[][NUM_STATION] = {{0, 7, 4, 5},
                   {0, 9, 2, 8}};
       int e[] = {10, 12}, x[] = {18, 7};
    
       printf("%d", carAssembly(a, t, e, x));
    
       return 0;
   }
   

   
   
   
   
5. Задача 3

   Тут предложен интересный графический разбор задачи. Исходный вариант:
   

   // Java program for implementation of divide and conquer algorithm 
   // to find a given key in a row-wise and column-wise sorted 2D array
   class SearchInMatrix
   {
       public static void main(String[] args)
       {
           int[][] mat = new int[][] { {10, 20, 30, 40}, 
                                       {15, 25, 35, 45},
                                       {27, 29, 37, 48},
                                       {32, 33, 39, 50}};
           int rowcount = 4,colCount=4,key=50;
           for (int i=0; i<rowcount; i++)
             for (int j=0; j<colCount; j++)
                search(mat, 0, rowcount-1, 0, colCount-1, mat[i][j]);
       }
    
       // A divide and conquer method to search a given key in mat[]
       // in rows from fromRow to toRow and columns from fromCol to
       // toCol
       public static void search(int[][] mat, int fromRow, int toRow, 
                                 int fromCol, int toCol, int key)
       {
           // Find middle and compare with middle 
           int i = fromRow + (toRow-fromRow )/2;
           int j = fromCol + (toCol-fromCol )/2;
           if (mat[i][j] == key) // If key is present at middle
             System.out.println("Found "+ key + " at "+ i + 
                                  " " + j);
           else
           {
               // right-up quarter of matrix is searched in all cases.
               // Provided it is different from current call
               if (i!=toRow || j!=fromCol)
                search(mat,fromRow,i,j,toCol,key);
    
               // Special case for iteration with 1*2 matrix
               // mat[i][j] and mat[i][j+1] are only two elements.
               // So just check second element
               if (fromRow == toRow && fromCol + 1 == toCol)
                 if (mat[fromRow][toCol] == key)
                   System.out.println("Found "+ key+ " at "+ 
                                      fromRow + " " + toCol);
    
               // If middle key is lesser then search lower horizontal 
               // matrix and right hand side matrix
               if (mat[i][j] < key)
               {
                   // search lower horizontal if such matrix exists
                   if (i+1<=toRow)
                     search(mat, i+1, toRow, fromCol, toCol, key);
               }
    
               // If middle key is greater then search left vertical 
               // matrix and right hand side matrix
               else
               {
                   // search left vertical if such matrix exists
                   if (j-1>=fromCol)
                     search(mat, fromRow, toRow, fromCol, j-1, key);
               }
           }
       }
   }