Михаил Денисов
начальник управления разработки приложений в БКС «Мир инвестиций»
Предлагаемая задача позволяет определить, насколько соискатель умеет строить алгоритмы и системно искать решения.
Условие задачи
Представьте, что у Вас есть 8 металлических шариков, которые выглядят одинаково. Один из них — более тяжелый. И представьте, что у Вас есть весы с двумя чашами.
Эти весы настолько старые, что выдержат только два измерения, после которых сломаются. Как с помощью весов за два измерения найти один тяжелый шарик?
Разбор задачи
Делаем первое измерение: на обе чаши весов кладем по 3 шарика. 2 оставшихся шарика откладываем в сторону и не взвешиваем на данном измерении.
Возможны два варианта результата первого измерения:
Вариант 1. Ни одна из чаш весов не перевесила другую. Значит искомый шарик находится среди двух отложенных. В этом случае второе измерение делаем положив по 1 шарику на каждую чашу весов. Тот, который оказался в перевесившей чаше и есть наш искомый шарик.
Вариант 2. Одна из чаш весов перевесила другую (значит искомый шарик находится среди трех шариков этой чаши), в следующее измерение включаем только три шарика из этой чаши. Делаем второе измерение: на каждую чашу весов кладем по 1 шарику, а третий откладываем в сторону. Если одна из чаш весов перевесила, значит искомый шарик находится в ней. Если ни одна из чаш весов не перевесила другую, значит искомый шарик — тот, что мы отложили перед вторым измерением.
Оценка решения задачи
В идеальном случае соискателю следует уточнить, являются ли 7 из 8 шариков одинаковыми по весу. Наличие этого и других вопросов с уточнениями требований дают понимание об уровне соответствующей компетенции.
Доступность объяснения решения задачи (визуализация, или связный логический рассказ) — демонстрация навыков коммуникации.
Если соискатель затрудняется в решении задачи, то можно дать ему подсказку — «в измерении могут участвовать не все шарики».
Дополнительно задача позволяет оценить и спроектировать на рабочие ситуации следующие аспекты:
- как соискатель подходит к уточнению условий/требований;
- проявляет ли критическое мышление в адрес условий/требований;
- как выполняет поиск решения;
- что соискатель предпринимает, когда заходит в тупик при решении;
- к какой категории восприятия можно отнести соискателя (визуал, аудиал, кинестетик, дискрет).
Эту задачу мне прислал подписчик с комментарием, что она была на олимпиаде у его сына и, по его словам, её никто не решил. “Никто” я бы не воспринимал буквально, скорее всего, это значит, что её не решил его сын и тот, с кем он общался после олимпиады.
У нас есть 8 одинаковых на вид и размер шариков. Семь из них весят одинаково, а один тяжелее других. Как найти его с помощью двух взвешиваний на чашечных весах?
Классические задачи на взвешивания и нахождения фальшивки у меня уже были (ссылки будет в конце), эта примерно такая же, но немного с подвывертом (совсем небольшим). Если мне не изменяет память, то что-то подобное было в сборнике задач, которые давали на собеседовании в Гугл.
Пока вы думаете, расскажу историю, которую рассказал один из эйчаров в Иннополисе. Они в то время искали разработчика C++ и рассматривали кандидатов из других городов.
Собеседование было в конце рабочего дня, а соискатель из Новосибирска, так что у него уже был глубокий вечер из-за 4-часовой разницы во времени.
Когда включилась камера, по ту сторону экрана перед ними (а там, кроме эйчара были ещё три человека, в том числе руководитель) появился человек с голым торсом, который хлебал борщ из огромной тарелки. Его нисколько не смутило то, что сейчас будет собеседование и, не отрываясь от позднего ужина, он спросил, хорошо ли его слышно и видно и просил начать собеседование.
На предложения отложить ложку в сторону или хотя бы перенести собеседование минут на 15, он ответил категорическим отказом. Более того, после того, как с борщом было покончено, он принялся пить чай с печеньками, отвечая на вопросы с набитым ртом.
Возможно он хотел привлечь к себе внимание и запомниться, но, к сожалению, он не справился с технической частью собеседования и был благополучно послан… повышать свои профессиональные навыки с предложением пройти собеседование ещё раз через год. Ну а теперь давайте вернемся к задаче.
Решение
Нужно произвольно выбрать 6 шариков, разделить их на две группы по 3 шарика в каждой и положить на весы. Если какая-то из чаш перевесит, значит, тяжелый шарик там.
Далее выбираем любые два шарика из тяжелой тройки и снова взвешиваем. Если какой-то шарик перевесит, то он и есть искомый. Если весы будут в равновесии, то искомый шарик тот, который мы не взвешивали.
Если же при первом взвешивании ни одна из троек шаров не перевесила, значит, тяжелый находится среди тех двух, что мы не взвесили. Вторым взвешиванием мы его легко найдём.
Как видим, всё решается по классике, лишь немного изменили условие и сделали задачу даже проще.
В общем, то, что “никто не решил” вовсе не показатель сложности, просто надо было немного подготовиться и полистать советские сборники, посерфить в интернете, подписаться на мой канал на крайняк. А ещё шоколадки на олимпиадах и экзаменах отвлекают, а не наоборот, как многие думают. Впрочем, как и борщ, по всей видимости. А вот обещанные задачи:
Думаю, что если в задаче разрешается использовать чашечные весы с двумя чашками, хотя бы и без гирь, то задачу можно решить в два этапа, то есть за два взвешивания.
Первый этап. Делим восемь шаров на три группы: три, три и два шара. Первые две группы, по три шарика в каждой, кладём на весы. Допустим, первую кучку на левую чашку, а вторую — на правую. Два шарика, то есть третью группу оставляем в стороне. Выполняем первое взвешивание. Возможны три случая: 1) перетянула левая чашка; 2) перетянула правая чашка; 3) весы пришли в равновесие. В первом случае тяжёлый шар заведомо лежит на левой чашке весов, во втором случае — на правой чашке, в третьем — остался в стороне в группке из двух шариков. Таким образом, после первого взвешивания у нас уменьшилось количество шаров-кандидатов с восьми либо до трёх, либо до двух.
Второй этап. Два варианта: нужно определить тяжёлый шар либо из трёх шариков, либо из двух. В первом случае первый шар кладём на левую чашу, второй — на правую, третий оставляем в стороне. Выполняем второе взвешивание. Если перетянула левая чашка — тяжёлый шар слева (первый), правая — справа (второй), если равновесие — то он в стороне (третий). Ну а в случае двух шаров всё ещё проще. Кладём по шарику на каждую чашку, и та чашка, которая перетянет, однозначно укажет нам на тяжёлый шар.
Вешаешь первый раз по 3 шара
1) в каждой тройке одикаковая масса, тогда этот шар — один из двух оставшихся, его определяем за второе взвешивание.
2) в одной тройке масса больше, тогда этот шар в этой тройке..
— выбираем 2 любых из тройки и вешаем, если одинаковая масса, тогда искомый шар — оставшийся, а если не одинаковая, то искомый тот который больше весит..)))
1 ое взвешивание:
на весах 4 шара с одной и другой стороны, более тяжелая кучка идет на 2-ое взвешивание
Задачи с собеседований: ищем самый тяжёлый шар за два измерения
Предлагаемая задача позволяет определить, насколько соискатель умеет строить алгоритмы и системно искать решения.
Условие задачи
Представьте, что у Вас есть 8 металлических шариков, которые выглядят одинаково. Один из них — более тяжелый. И представьте, что у Вас есть весы с двумя чашами.
Эти весы настолько старые, что выдержат только два измерения, после которых сломаются. Как с помощью весов за два измерения найти один тяжелый шарик?
Разбор задачи
Делаем первое измерение: на обе чаши весов кладем по 3 шарика. 2 оставшихся шарика откладываем в сторону и не взвешиваем на данном измерении.
Возможны два варианта результата первого измерения:
Вариант 1. Ни одна из чаш весов не перевесила другую. Значит искомый шарик находится среди двух отложенных. В этом случае второе измерение делаем положив по 1 шарику на каждую чашу весов. Тот, который оказался в перевесившей чаше и есть наш искомый шарик.
Вариант 2. Одна из чаш весов перевесила другую (значит искомый шарик находится среди трех шариков этой чаши), в следующее измерение включаем только три шарика из этой чаши. Делаем второе измерение: на каждую чашу весов кладем по 1 шарику, а третий откладываем в сторону. Если одна из чаш весов перевесила, значит искомый шарик находится в ней. Если ни одна из чаш весов не перевесила другую, значит искомый шарик — тот, что мы отложили перед вторым измерением.
Оценка решения задачи
В идеальном случае соискателю следует уточнить, являются ли 7 из 8 шариков одинаковыми по весу. Наличие этого и других вопросов с уточнениями требований дают понимание об уровне соответствующей компетенции.
Доступность объяснения решения задачи (визуализация, или связный логический рассказ) — демонстрация навыков коммуникации.
Если соискатель затрудняется в решении задачи, то можно дать ему подсказку — «в измерении могут участвовать не все шарики».
Дополнительно задача позволяет оценить и спроектировать на рабочие ситуации следующие аспекты:
Задача про шары от Google
У вас 8 шаров: 7 весят одинаково, а 1 чуть тяжелее остальных. Как определить с помощью весов, какой шар тяжелее, если у вас только 2 попытки?
Попробуйте сначала решить, а потом сравните с правильным ответом ниже 😉
Шаг 1. Берем 6 любых шаров из 8
Шаг 2. Кладем по 3 шара на две чаши весов (тем самым используем 1-ю попытку):
A) если чаши сравнялись, то более тяжелый шар нужно искать среди двух оставшихся
B) если одна чаша перевесила, то нужный шар находится среди этой тройки
Шаг 3. Используем 2-ю и последнюю попытку. При варианте A) все просто: нужно взвесить два оставшихся шара, чтобы выявить более тяжелый. При варианте B) взвешиваем 2 любых шара из оставшихся 3-х и тогда либо весы сразу покажут более тяжелый, либо чаши сравняются, а значит, 3-й, не взвешенный шар и есть самый тяжелый.
Моё мнение. номер 8 уже на весах, все остальные кроме номера 15(который прячет лицо), довольны и радостны.
Вывод, номер 15 самый тяжёлый.
как то сразу мысль пришла про «отложить два, и по три на весы»
это типо сложным должно быть?
про «кандидатов в гугл» — херня какая то.
Я бы предложил ронять шары на пол с одинаковой высоты тот, что отскачет меньше всего, тот самый тяжелый. Потом можно проверить взвесив его с любым из других.
В Гугле такие задачки давно не задают, потому что умение решать такие задачки показывает только умение решать такие задачки, но не прошраммировать
Эмм, не уверен, что это задача из гугла, разве что, на должность дворника. Такие задачки у нас в школе решали еще до 9 класса. Учительница говорила, что это на «сообразительность» и было это много лет назад, наверняка уже что-то сложнее придумали.
сравниваем по 3 шара за первую попытку. если вес равен — то сравниваем 2 оставшихся, если какая-то тройка тяжелей, то сравниваем 2 шара из этой тройки. если вес одинаковый — то тяжелей последний шар
З.Ы. что-то класс пятый, наверное, вспомнился
для физиков — за 1 попытку надо определить, вот и решайте кто сообразительней — программисты или физики.
Жрать меньше надо прост
Загадка про блендер
«Вас уменьшили до размеров 5-центовой монеты и бросили в блендер. Ваш вес уменьшился так, что плотность вашего тела осталась прежней. Лезвия начнут вращаться через 60 секунд. Ваши действия?»
Начнём с классификации наиболее популярных ответов, затем расскажем про тот, который считается лучшим среди интервьюверов в Google.
Многие соискатели выдают один забавный ответ: «Так как блендер очень скоро включат, можно предположить, что в него положат какие-то продукты, и поэтому мне, может быть, лучше подставить свою шею под лезвие, чем задохнуться из-за паров той жижи, которая скоро появится в блендере».Если же говорить о часто встречающихся серьезных ответах, то лидерами являются такие.
Первый. Лечь как можно плотнее к днищу, чтобы лезвия крутились надо мной.
Второй. Встать с той стороны блендера, где крепятся лезвия. Возможно, между стенкой и устройством крепления есть зазор шириной в 5-центовую монету.
Третий. Залезть по лезвию на ось вращения и найти такое место, где при вращении лезвий можно сохранять равновесие. Схватиться покрепче. Итоговая центростремительная сила в этом случае будет близка к нулю, что и позволит удержаться.
Первые три варианта дают некоторый шанс на выживание, но что если лезвия будут крутиться долго? Или конструкция такова, что вас всё таки заденет остриём? И вообще, если вдуматься, кто и зачем вас бросил в блендер? Если это какие-то враждебные существа, которые собираются приготовить соус из человека, то ваши долгосрочные шансы на выживание будут очень небольшими при любом варианте.
Вот стандартные ответы интервьюверов на уточняющие вопросы: «По поводу враждебных существ не беспокойтесь». «Никакой жидкости добавлено не будет». «Крышки у блендера нет». «Исходите из того, что лезвия будут вращаться до тех пор, пока вы не погибните».
Четвертый подход отличается — нужно выбраться во вне. Интервьювер поинтересуется, как вы будете это делать. Одним из самых ярких ответов был такой: при очень малом весе вы сможете взобраться по стенке примерно так же, как это делают мухи.
Пятый, не самый оптимистичный, вариант — воспользоваться телефоном и позвонить или отправить sms с просьбой о помощи. Тут всё зависит от того, уменьшился ли так же ваш телефон, сможет ли он работать с базовой станцией (которая осталась прежней) и какова будет скорость реакции службы спасения (и будет ли вообще?).
Шестой вариант: разорвать одежду на полосы, чтобы сделать из них верёрвку и воспользоваться её, чтобы выбраться. Но реально ли это сделать за одну минуту? Как крепить верёвку сверху? И даже если это удастся, как потом спуститься вниз?
Есть и седьмой: использовать одежду и собственные усилия, чтобы как-то заблокировать (или даже сломать) лезвия или работу мотора. Но и здесь могут возникнуть проблемы.
Ни один из перечисленных ответов не принесёт вам в Google много баллов. Интервьюверы рассказывали, что лучший ответ, который они слышали был таким — выпрыгнуть из блендера.
Ух ты? В вопросе даётся важный ключ — слово «плотность». Эта подсказка наводит на мысль, что важны вес и объем тела (а на другие «нереалистичности» можно не обращать внимания) и что подходящий ответ должен строиться на простейших законах физики.
Короче: интервьювер хочет, чтобы вы сфокусировались на последствиях, связанных с изменением размера. Вы, вероятно, слышали, что муравей способен поднять вес, в 50 раз превышающий вес его тела. Это объясняется не тем, что его мускулы лучше, чем у человека, а тем, что муравей маленький. Вес любого живого существа пропорционален кубу его высоты. Сила мускулов и скелета, поддерживающего их, зависит от площади их поперечного сечения, которая пропорциональна квадрату высоты. Если вас уменьшить до 1/10 вашего роста, сила ваших мускулов уменьшится в сто раз, но ваш вес уменьшится еще больше — в тысячу раз. Про прочих равных условиях небольшие существа «сильнее».
В середине 1600-х годов Джованни Альфонсо Борелли, современник Галилео, предположил, что всё, что прыгает, поднимается примерно на одинаковую высоту. Подумайте хорошенько об этом. Если вы физически здоровы, то, вероятно, сможете подпрыгнуть сантиметров на 70. Эта высота не преграда и для других живых существ: лошади, кролика, лягушки, кузнечика или блохи. Разумеется, есть вариации, но общее правило именно такое: самые крутые баскетболисты NBA могут поднять свой центр тяжести примерно на такую же высоту, как и блоха.
Мускульная энергия в конечном счёте определяется химическими процессами: глюкозой и водородом, циркулирующем в крови, а также АТФ, имеющимся в клетках мускул. Количество любых хим. веществ пропорционально объему вашего тела т.е. если вы уменьшитесь до 1/n вашего размера, то мускульная энергия сократится в n³ раз.
К счастью, вес уменьшится так же. Поэтому при размере в монетку, высота вашего прыжка (если не учитывать сопротивление воздуха) никак не изменится. Высота блендера примерно 30 см. Если вы можете сейчас перепрыгнуть через препятствие такой высоты, то удрать из блендера для вас не будет проблемой.
Возможно, вы спросите, как же упав потом с такой высоты вы не поломаете себе кости? Поверхность, которую вы теперь занимаете, составит 1/n² по сравнению с вами обычным, а вес сократится еще больше, до 1/n³ прежнего. Соотношение площади поверхности к весу возрастёт в n раз, поэтому когда вы приземлитесь, никаких поврежений у вас не будет. Это объясняет, почему любое существо размером с мышь и менее может не беспокоиться и падать с любой высоты.
22.12.2021
В наличии имеется внешне восемь одинаковых шаров, однако один из шариков по весу несколько тяжелее. Как, используя весы-чашки, всего лишь за два взвешивания найти это шар?
Правильный ответ
Берем любые шесть шариков и разделяем их на две равные кучки по три штуки в каждой. Производим взвешивание каждой из кучек и для этого кладем на каждой чашу весов по три шарика. Та чаша, которая перевесит, и включает более тяжелый шарик.
После этого из более тяжелой кучки выберем два шара и кладем на чаши весов, перевесившая чаша и покажет нам искомый шарик. Если же чаши будут уравновешены, то оставшийся третий шар, взвешивание которого не производили, и будет искомым.
В том случае, если в ходе первого взвешивания чаши весов будут находиться в равновесии друг относительно друга, то берем два оставшихся шара и взвешиваем их на чашах весов. В любом случае получается, что в при втором взвешивании мы точно узнаем более тяжелый по весу шар.
