Известные компании — Google, Intel или Apple — известны тем, что во время собеседования спрашивают соискателей о сложных задачах. Мы собрали 10 интересных примеров таких задач. Некоторые из них были предложены самими компаниями, а некоторые были размещены пользователями, с которыми уже были проведены собеседования. Для их решения требуются математические знания школьного уровня или просто сообразительность.
Предлагаем вам проверить, как бы вы справились с таким собеседованием.
Что спрашивают в Apple
Задание 1.
Логический вызов. Шелдон Купер (тот самый гениальный физик из популярного сериала) достиг последнего рубежа в игровой миссии по поиску сокровищ. Перед ним две двери, одна ведет в сокровищницу, другая в смертельный лабиринт. У каждой двери стоит стражник, каждый из них знает, какая дверь ведет к кладу. Один из охранников никогда не лжет, другой всегда лжет. Шелдон не знает, кто из них лжец, а кто нет. Перед выбором двери вы можете задать только один вопрос и только одному охраннику.
В: Что мне спросить у охранника Шелдона, чтобы добраться до сокровища?
Ответ: Вы можете спросить любого, задав при этом вопрос так: «Какая дверь, по мнению другого охранника, правильная?». Если он спросит правдивого, ему скажут, какая дверь ведет в лабиринт, ибо лживый страж всегда лжет. Если он спросит лживого стражника, то опять же узнает, какая дверь ведет в лабиринт, потому что соврёт о той двери, на которую укажет правдивый стражник.
Задача 2.
Землю захватили инопланетяне. Они планируют уничтожить всю планету, но решили дать человечеству шанс. Они отобрали десять самых умных людей и поместили их в совершенно темную комнату, сидя в ряд, по одному. Каждому из людей выдали головной убор, головные уборы всего двух цветов – розового и зеленого. После того, как на головах у всех шляпы, зажигают свечи.
Инопланетянин начинает с последнего человека в очереди и спрашивает, какого цвета шапка у него на голове. Другие слова, кроме цвета шляпы, произносить нельзя. Тишина — тоже. Если он ответит правильно, то останется в живых, если ошибется, его убьют.
Вы не можете сказать, какого цвета ваша шляпа, но вы можете договориться по определенному принципу ответить всем. Размещение шапок случайное, комбинации могут быть любые, вы видите все шапки, расставленные перед вами.
Вопрос: Что нужно ответить, чтобы выжило как можно больше?
Ответ: Первый ответивший подсчитывает количество зеленых шапочек перед ним: если это нечетное число, он называет «зеленую», если четное число — «розовую». Следующий, видя количество и цвет шапок перед собой, может таким образом вычислить, какого цвета шапка на его голове (например, если зеленых еще нечетное количество, то очевидно, что он одет в розовую), и так далее. Таким образом, 9 из 10 гарантированно выживают, а первый ответивший имеет шанс 1 к 1.
Что спрашивают в Adobe
Задача 3.
У вас есть 50 мотоциклов с полным баком топлива, которого хватит на поездку в 100 км.
Вопрос: На каких 50 мотоциклах можно уехать (учитывая, что изначально они находятся в условной одной точке пространства)?
Ответ: Самый простой ответ — завести их все одновременно и проехать 100 км. Но есть и другое решение. Сначала переместите все мотоциклы на 50 км. Затем перелейте топливо из половины мотоциклов в другую половину. Таким образом, у вас есть 25 мотоциклов с полным баком. Проехать еще 50 км и повторить процедуру. Так можно набрать до 350 км (не считая топлива, оставшегося от «лишнего» мотоцикла при делении 25 пополам).
Что спрашивают в Microsoft
Задача 4.
У вас есть бесконечный запас воды и два ведра — 5 литров и 3 литра.
Вопрос: Как отмерить 4 литра?
Ответ: Наполните пятилитровое ведро водой и налейте часть воды в трехлитровое ведро. Теперь у вас 3 литра в маленьком ведре и 2 в большом. Опустошите маленькое ведро и вылейте в него оставшиеся 2 литра из большого. Снова наполните большое ведро и вылейте из него воду в маленькое. Воды там уже 2 литра, поэтому нужно добавить литр, оставив в большом 4 литра.
Упражнение 5.
У вас есть два куска веревки. Каждый устроен так, что если его поджечь с одного конца, то он будет гореть ровно 60 минут.
Вопрос: Если у вас есть только коробка спичек, как отмерить 45 минут двумя кусками такой веревки (веревки не порвешь)?
Ответ: Один из сегментов поджигается с двух концов, в то же время другой сегмент поджигается, но с одного конца. Когда первый отрезок выгорит полностью, пройдет 30 минут, от первого отрезка тоже будет 30-минутный отрезок. Поджигаем с двух концов, получаем 15 минут.
Что спрашивают в Google
Упражнение 6.
У вас есть 8 мячей одного типа и размера.
Вопрос: Как найти более тяжелый шар с помощью баланса и только двух гирь?
Ответ: Выберите 6 шариков, разделите их на группы по 3 шарика и положите на весы. Группа с более тяжелым мячом выигрывает чашу. Выберите любые 2 мяча из этой тройки и взвесьте. Если среди них окажется тяжелый мяч, вы это узнаете; если они весят одинаково, то оставшийся тяжелый. Если в группах по 3 мяча не было более тяжелого мяча, он оказывается среди 2-х оставшихся.
Что спрашивают в Qualcomm
Упражнение 7.
Эту задачу описал пользователь, прошедший собеседование на должность старшего системного инженера. Он отметил в описании задания, что у него есть свой ответ, о котором он долго спорил с интервьюером.
Допустим, у нас есть 10 пакетных передач данных по беспроводной сети. Канал не очень хороший, поэтому вероятность того, что пакет данных не будет передан, составляет 1/10. Отправитель всегда знает, успешно или неудачно был передан пакет данных. Если передача не удалась, отправитель будет передавать пакет до тех пор, пока не добьется успеха.
В: Какую пропускную способность канала мы получаем?
Ответ: По словам пользователя, ответ должен был быть: 9 пакетов в секунду. Но человек, проводивший интервью, с ним не согласился, но ответа не дал, а повторил, что «из-за ретрансляции пропускная способность должна быть снижена более чем на 1/10».
Что спрашивают в «Яндексе»
Упражнение 8.
Эту задачу было предложено решить, чтобы в феврале 2014 года поступить в Школу анализа данных.
Игра состоит из одинаковых и независимых раундов, каждый из которых выигрывает с вероятностью p.При выигрыше игрок получает 1 доллар, а при проигрыше — 1 доллар. Как только его капитал достигает N долларов, он объявляется победителем и удаляется из казино.
Вопрос: Найдите вероятность того, что игрок рано или поздно потеряет все деньги, в зависимости от стартового капитала K.
Упражнение 9.
Эту задачу разработчики попросили решить на собеседовании, и она имеет более прямое отношение к программированию, чем предыдущие примеры.
Это морфологический словарь, содержащий около 100 000 статей, в которых глаголы совершенного и несовершенного вида помещены в отдельные статьи (то есть «делать» и «делать» считаются разными словарными статьями). Вы должны найти такие пары видов в словаре и «склеить» статьи в одну.
Вопрос: Опишите общий сценарий решения такой задачи и примерный алгоритм поиска пары видов.
К сожалению, у нас нет ответов на задачи Яндекса.
И бонус
Упражнение 10.
Эту задачу приписывают Альберту Эйнштейну — якобы с ее помощью он выбирал себе помощников. Другая почти легендарная история приписывает авторство Льюису Кэрроллу. Учтите, что на бумаге ее очень легко решить, но если вы хотите хардкора, попробуйте решить ее в уме.
На улице пять домов.
Англичанин живет в красном доме.
У испанца есть собака.
Они пьют кофе в зеленом доме.
Украинка пьет чай.
Зеленый дом находится сразу справа от белого дома.
Тот, кто курит Old Gold, разводит улиток.
Кул курят в желтом доме.
Молоко пьют в центральном корпусе.
Норвежец живет в первом доме.
Сосед курильщика из Честерфилда держит лису.
Коул курят в доме по соседству с тем, где держат лошадь.
Все, кто курит Lucky Strike, пьют апельсиновый сок.
Японец курит парламент.
Норвежец живет рядом с голубым домом.
Каждый из домов выкрашен в разный цвет, в каждом доме живет представитель разной национальности, у каждого есть свой питомец, своя любимая марка сигарет и напитка.
Вопрос: Кто пьет воду? Кто держит зебру?
Ответ: Японец держит зебру, норвежец пьет воду.
Источник
