В Apple соискателями могут задать вопросы не только технического плана, но и о сокровищах и пиратах (интересно, связано ли это с позицией компании в отношении нелегального контента?). Вопросы и задачи, как всегда, разного уровня сложности. В целом, нужно отметить, что доля логических задач вытесняется чисто техническими вопросами, но тем не менее, головоломки на собеседованиях все ещё встречаются.
Вопросы
- 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-го пирата и снова попробовали разделить сокровище, и снова остался один камень. Так же было и когда они разбудили пятого и шестого пиратов. Лишь когда они разбудили седьмого пирата, им удалось разделить все камни без остатка.
Сколько (минимум) драгоценных камней составили добычу пиратов?
- 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 монеты:
* Одна из них — неправильная монета, с решками на обеих сторонах.
* Вторая монета — идеальная монета (орел на одной стороне, и решка на обратной).
Я, с завязанными глазами, беру монету и подбрасываю её на стол. Видимая часть монеты — решка.
Какова вероятность, что на обратной стороне — тоже решка?
Задачи
- 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”.
- Car assembly task
A car factory has two assembly lines, each with n stations. A station is denoted by Si,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 ai,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 Si,j, it will continue to station Si,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 ti,j. Each assembly line takes an entry time ei and exit time xi 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 станций. Станция определяется Si,j, где i, могущая принимать значения 1 или 2, обозначает линию, на которой находится станция, а j — обозначает номер станции. Время затрачиваемое станцией обозначается как ai,j. Каждая станция предназначена для выполнения определенного вида работы — подгонки двигателя, подгонки корпуса, покраски и т.д. Так, ходовая часть машины должна пройти через все n станций в определенном порядке, прежде чем будет выпущена с завода. Параллельные станции на обеих сборочных линиях выполняют одинаковую задачу. После того, как деталь пройдёт станцию Si,j, она продолжит движение через Si,j+1, если не будет принято решение перевести её на другую линию. Переход от станции к станции на одной линии не требует дополнительного времени, но перевод со станции j-i на станцию j на другой линии — требует времени ti,j. Каждая сборочная линия также имеет входное время ei и выходное время xi, которое может быть различным для обеих линий. Предложите алгоритм с минимальным временем сборки машины.
- 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, где каждая строка и столбец отсортированы по возрастанию. Дано ключевое значение. Напишите программу для определения, где в матрице находится это ключевое значение.
Ответы будут даны в течение следующей недели — успейте решить. Удачи!
Комментарии (55)
yar3333
17.04.2018 16:42Про пиратов — 7*7 = 49 (нам нужен множитель к семёрке, но не ниже 7-ки же, т.к. мы знаем, что результат не делился на [2..6]).
Про монеты — 50/50. По сути у нас спросили является ли монета поддельной.
Snusmumrick97
17.04.2018 16:59Остаток от деления 49 на 5 — 4, а у нас по условию всегда остаётся лишней только 1 монета
Nikles
17.04.2018 17:461. Не подходит, так как когда их было 5 у них остался 1! камень, а при 49 осталось бы 4.
vmt88
17.04.2018 17:4649 не соответствует условию 5n+1
С вероятностью 0,5 согласен, но считаю что надо смотреть с точки зрения условной вероятности.
Р(2-я решка)= P(фальшивая монета)*Р(решка на фальшивой монете) = 0.5*1=0.5
Rsa97
17.04.2018 20:35А какова, по вашему, будет вероятность того, что внизу решка, если сверху орёл? Тоже 50%? Ведь по сути это вопрос о том, является ли монета настоящей…
yar3333
17.04.2018 21:00Думаю, что если взять высказывание и поменять в нём несколько слов на противоположные, истинность полученного высказывания не обязана совпадать с истинностью исходного :)
yar3333
18.04.2018 10:33Про монеты: был неправ. Ответ: 2/3. jsfiddle.net/shdqse5z/6
tashihu
18.04.2018 15:52С вероятностями проще расматривать все варианты. У нас 4 варинта событий.2 монеты по 2 стороны. 1 орел к верху, 1 решка к верху, 2 решка(А) к верху, 2 решка(Б) к верху. 1 случай не подходит. В оставшихся 3 вариантах снизу 1 орел и 2 решки. 2/3
urtow
18.04.2018 16:00Спасибо.
Я все так и подумал, но не учел, что один вариант надо исключить — результат уже известен.
Rsa97
17.04.2018 20:08+3Вопрос 1Поскольку для 2, 3, 4, 5 и 6 пиратов оставался один камень, то значит необходимо найти число вида НОК(2, 3, 4, 5, 6)*n+1 = 60*n+1, нацело делящееся на 7.
Признак делимости на 7 — число без последней цифры минус удвоенная последняя цифра делится на 7. Последняя цифра всегда 1, получаем что 6*n-2 должно делиться на 7. Ближайшее n = 5, значит число камней 60*5+1 = 301.mbait
18.04.2018 06:52От задач по терверу нужно отказаться, как когда-то отказались от логических задач, потому что ответ может меняться значительно от положения фразы "какова вероятность, что" в постановке задачи. В данном случае ответ 50%, потому что монеты всего две, выбираются они равновероятно, а значит две решки появятся только в половине случаев. Но вот если спросить иначе: какова вероятность, что после случайного выбора и подбрасывания будет решка с обоих сторон, от ответ уже получится другой.
mbait
18.04.2018 06:56В последнем предложении написал ерунду, но мысль должна быть понятна — переформулировав задачу, можно получить правильный ответ, отличный от "50%".
Dr_Dash
18.04.2018 07:06Вы берёте случайную моннту. Какова вероятность что после 2х подбрасываний случайно выбранной монеты выпадет решка. как-то так
mbait
18.04.2018 07:12Всё зависит от того, из чего формируется множество элементарных исходов. Допустим, мы равновероятно выбираем монету. Если после подбрасывания выпал орёл, то такой исход мы не считаем, а во всех остальных — считаем. Тогда у "неправильной" монеты больше шансов попасть в выборку, а значит и шанс получить решку после переворота не 50%. Но если нам ничего не известно про возможные выпадения орла, то всё таки шанс остаётся 50%.
Rsa97
18.04.2018 08:11Здесь в задаче два выбора — равновероятный выбор одной из двух монет и равновероятный выбор положения монеты. Они дают нам четыре равновероятных исхода. Один из этих исходов (настоящая монета орлом вверх) отсеивается условием. Остаётся три, из них только два с решкой внизу. 2/3.
Dr_Dash
18.04.2018 06:58+1Пираты —
Ещё Евклид считал очевидным, что с помощью умножения только простых чисел можно получить все натуральные числа, причем каждое натуральное число представимо в виде произведения простых чисел единственным образом. Поэтому искомое число камней состоит из числа 7(НОД) и ещё какого-то числа Dimonds_X
При этом Dimonds_X не делится ни на 2 ни на 3 ни 5. То есть оно состоит из простых чисел >= 7. Фактически поиск таких чисел это задача факторизации, т.е. требуется пробовать и проверять. Поскольку нужно минимальное, предположим что оно состоит из 1 простого сомножителя. И оно будет минимально до тех пор, пока искомый простой сомножитель не превысит 47 ( максимальное простое число меньшее чем 7*7 = 49, а это в свою очередь минимальное число состоящее их 2х простых чисел, которые оба >=7, напомню, что числа с 2 по 5 не подходят)
Перебираем простые числа от 7 до 47 и проверяем на калькуляторе.
Суть проверки, поскольку у тех ребят всё время оставался один камень, то 7*Dimonds_X — 1 должно делиться на 2(дважды) 3 и 5. Поскольку числа кратные 5 будут встречаться реже(их просто меньше) пусть это будет первый маркер.
7*7 -> 48 fail
7*11-1 -> 76 fail
7*13-1 -> 90 win? нет fail потому что не делится на 4.
Перебирая подобным незамысловатым способом остальне простые числа в диапазоне 7 до 47
неожиданно наткнулся насундук с пиастрамина число 43. 43*7-1 -> 300 то есть общее число камней которое полностью удовлетворяет условию задачи 301BarabashkaS
18.04.2018 13:33+1перебор можно было упростить, если заметить, что остаток от деления на 5 дает 1, а значит число должно заканчиваться на 1 (6-ку естественно отбрасываем), а значит число, на которое нужно умножить 7 должно оканчиваться на 3, тогда в перебор войдут только числа 13, 23 и 43
leshabirukov
18.04.2018 15:15Можно проще: чтобы выполнить первое условие, необходимо
Х % НОК(2,3,4,5,6) == 1 (%-остаток от деления, НОК(2,3,4,5,6)==60)
итого Х = 60n +1.
Заметив, что 60 % 7 = 4, ищем число вида
4+4+...+4+1 = 7n
А найдя, заменяем все 4+4+… на 60+60+..., и получаем 301
Dr_Dash
18.04.2018 07:26Монета — ответ 50% неверный.
Такой вариант не учитывает того, что мы уже произвели одно испытание и имеем некоторую информацию на этот счёт и в то же время наши знания на этот счёт ограничены. О чём я?
Всего у нас имеется 4 стороны монет(2 одной и 2 другой), для ясности проименуем их
a b c d/ из них a орёл, а остальные решки.
после испытания мы видим одну из b c d но не знаем которая из них. И нет никаких запретов на то, чтобы на противоположной стороне оказалась a либо две любые из b c d
иными словами, образно выражаясь, в мешке есть один орёл и две решки с равной вероятностью. Следовательно, вероятность того что на той стороне тоже решка — 2/3Funix
18.04.2018 13:33Как раз-таки 50% — верный ответ.
Раз уж мы уже видим решку, то варианта возможно только 2 (и вероятность у них одинаковая): выбранная монета или «настоящая» или фальшивая. И этим определяется содержимое обратной стороны (т.е. 50/50). Если бы речь шла о нескольких случаях бросания монет и вероятностях тех или иных событий, то определенно вероятности могли бы быть иными. Но для отдельного определенного случая с фактическим раскладом «решка» вверху — есть только два (равнозначных) варианта.Rsa97
18.04.2018 15:53Нет, мы видим либо первую решку фальшивой монеты, либо вторую её решку, либо решку настоящей монеты.
bogotoff
19.04.2018 20:38Всего вариантов может быть 2, т.к. монет только 2. Либо окажется что это правильная монета, либо фальшивая. Если вариантов исхода 2 то и ответ 1/2.
Rsa97
19.04.2018 23:32Вы забыли, что кроме выбора монет было и второе действие — выбор стороны.
bogotoff
20.04.2018 02:06Выбора монет не было. Мы не подкидываем монеты 2 раза. Мы не считаем количество разных подбросов чтобы получить текущую ситуацию. По условию мы имеем уже подброшенную монету и уже видим решку и от этого отталкиваемся. Нам осталось лишь перевернуть и увидеть что на обратной стороне.
Чтобы посчитать вероятность нужно знать количество возможных исходов, а исходов у нас может быть только 2, потому что мы уже подбросили какую-то монету и мы уже знаем что выпала решка, и когда мы перевернем монету там будет либо решка либо орел.Rsa97
20.04.2018 07:04Первый выбор — выбор монеты. Мы можем выбрать либо фальшивую (Ф), либо настоящую (Н). Выбор равновероятен.
Второй выбор — выбор стороны, он тоже равновероятен. В случае Ф мы можем выбрать либо одну решку (ФР1), либо вторую (ФР2). В случае Н — либо решку (НР), либо орла (НО).
Таким образом до получения информации имеем четыре равновероятных исхода — ФР1, ФР2, НР, НО. Открыв глаза видим, что сверху решка, значит исход НО не выпал. Остаются три варианта, в двух из которых снизу вторая решка.bogotoff
20.04.2018 14:34Я понял Вашу мысль :)
Но мне все-таки кажется, что независимо от того какая именно сторона выпала в случае с фальшивой монетой, это не влияет на исход, т.е. не важно для нас.
Давайте подождем ответы от автора статьи. Думаю кто-то из нас сильно удивиться :)
bogotoff
20.04.2018 15:13Думаю я оказался не прав)
Я решил практическим путем проверить и накидал код: cpp.sh/8ibyj
У меня получается 1/3 в ответе. Я где-то допустил ошибку?
Detlev
18.04.2018 13:33+1Вторая задача = 2/3. Классическая задача на теорему Байеса.
andyudol
18.04.2018 15:43Байес вас бы в угол поставил.
Выбирается монета. Одна из двух. Решка вверху по условию задачи. Всё, выбора больше нет.Detlev
18.04.2018 19:22События H1 и H2 — соответственно выбор первой и второй монеты. Их вероятности(априорные) P(H1) и P(Н2) по условию равны 0,5. Событие A — появление решка. Условные вероятности события A равны P(A/Н1) = 1(если выбрана первая монета) и P(A/Н2) = 0,5(если выбрана вторая монета). Событие А произошло, необходимо пересчитать априорную вероятность выбора первой монеты. По формуле Байеса находим = 0,5 * 1 / (0,5 * 1 + 0,5 * 0,5) = 0,67 (или 2/3)
Байес в чистом виде)) в одно действиеandyudol
19.04.2018 19:26Даже не близко. Решка вверху — это условие задачи, заданное ещё до того, как я выбрал монету. Если я выбрал качественную монету, то обратная сторона гарантированно не решка. Если выбрал бракованную — обратная сторона гарантированно тоже решка.
Detlev
19.04.2018 20:53Неправильно. Задача не в том, чтобы найти вероятность выпадение решки. А именно найти вероятность, что выбранная монета неправильная!!! При условии что мы видим решку. Повторюсь, это чисто Байесовская схема и постановка задачи. Т.е. сначала выбор монеты(гипотезы), потом результат(событие) и по результату пересчитать вероятность гипотезы.
Detlev
20.04.2018 10:52Чтобы понять суть вышесказанного, попробуйте решить немного усложненный вариант этой задачи. У вас на столе N правильных монет и M неправильных монет. Наугад, с закрытыми глазами выбираете одну. Подбрасываете ее K раз, и ровно K раз выпадает решка. Найти вероятность, что и в K+1 раз тоже выпадет решка.
neobuh
18.04.2018 13:33Про камни — условие делится на пять с остатком 1 соотв. только числа с окончанием на 6 (не подходит т.к. четное и 1), смотрим числа с 1 которые делятся на 7 = 21 + 7*10*nб если еще учесть остаток о деления на 3, то = 91 + 7*3*10*n, первое число такое 301
Про монеты вероятность выкинуть правильную монету решкой вверх = 25%, для неправильной 50%, т.о. вероятность при перевороте получить решку = 2/3
AndreyZabolotny
18.04.2018 13:33+1Задача 1for (int i = 0; i<1000; i++)
{
if (i%2==1&&i%3==1&&i%4==1&&i%5==1&&i%6==1&&i%7==0&&)
{
cout<<«Значение i»<<i;
}
}
ответ 301tashihu
19.04.2018 11:38по Задача 1. Прямой перебор достаточно долго выполняется, с 6 операциями деления в if. Подвести бы сюда математические выкладки и пропустить заведомо ложные варианты.
If ( ( 60 * i + 1) % 7 == 0 )
Ravaldini
18.04.2018 17:03Монеты
Мы имеем всего два варианта на старте:
1) Выпала монета орел-решка.
2) Выпала монета решка-решка.
Верхнюю решку можно не считать — это уже данность.
Таким образом, вероятность того что это монета решка-решка 50%.
Если добавить в условия еще одну монету решка-решка:
1) Выпала монета орел-решка.
2) Выпала монета1 решка-решка.
3) Выпала монета2 решка-решка.
Вот так уже вероятность обнаружения решки будет 2/3.
В двух случаях из трех мы найдем под решкой еще одну решку.
Иными словами, условие что мы на старте уже видим решку исключает ее из нашего расчета вероятности. Это уже свершившийся факт и нужно считать только те варианты, которые могут быть на скрытой стороне монеты.
CakeOfChaos
19.04.2018 16:23В условиях задачи 1 указано неверное бинарное дерево
20 / 8 22 / 4 12 / 10 14
10 > 8, но при этом находится слева от узла 8.
Projack
19.04.2018 17:09Первое: берем условно-рандомное число, чтобы понять, что к чему.
Выбираем 49 из логики, что множитель больше 6. При переборе получаем, что не подходит 5. Наводит на мысль, что это число имеет форму или *6 или *1, чтобы удовлетворить 5. Отсекаем вариант с *6, потому что оно будет кратно 2.
Имеем, что число должно быть в формате *1. В силу того, что при умножении 7 на числа [0..9] только один вариант дает на конце единицу (7*3=21). Перебираем множители: n*10+3.
7*13 = 91 [91 % 4 = 3]
7*23 = 161 [161 % 3 = 2]
7*33 = 231 [число 33 само по себе делится на 3]
7*43 = 301 — бинго.
Ответ: 301.
gotoxy
Про пиратов: 61.
2 * 3 * 4 * 5 * 6 + 1.
Сокращаем лишние простые множители, остаются 3 * 4 * 5 + 1
Snusmumrick97
kwasar
складываем на калькуляторе 7+7+7+… и отсекаем все результаты, которые делятся на 2, 3, 4, 5, 6 (это несложно).
у меня получилось 91
Rsa97
91%4 = 3 ? 1
kwasar
верно.
Пересчитал, действительно 301 правильный ответ.