Выпуск#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 “12 20”

   Перевод

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

   Рассмотрим дерево:

    
                                 20
                                /   
                               8    22
                             /   
                           4      12
                         /   
                       10    14
   

   Вход: target = указатель на узел 8; root = указатель на узел 20; k = 2.
   Выход: 10 14 22

   Если target = 14 и k = 3, тогда выход должен быть “12 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, где каждая строка и столбец отсортированы по возрастанию. Дано ключевое значение. Напишите программу для определения, где в матрице находится это ключевое значение.

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

Автор: reci

Источник ^[1]