Хотите узнать, какую задачку подкидывают в Microsoft соискателям на должность Software Engineering Intern? Спойлер: забудьте об интегралах и высшей математике. Вам понадобится умение считать до девяти и немного понимать по-английски. Готовы?
Microsoft Stone Puzzle
You have 9 stones, one of them is heavier than the others and all other 8 are equally heavy. You are allowed only 2 measurements in scales to determine which stone is the heaviest.
Пока вы ломаете голову над поиском решения, расскажу, где наткнулась на эту загадку. По утрам я обычно читаю новости на английском на medium.com и там мне попалась статья Eliran Turgeman, который пытался устроиться стажёром на должность разработчика ПО в Microsoft.
У меня решение созрело сразу, но оно оказалось неправильным. 😐Хотя я была на верном пути. Если бы подумала ещё чуток, пришла бы к правильному ответу. Если вам, как и мне тогда, не терпится узнать, как только двумя взвешиваниями выявить самый тяжёлый из 9 камней, читайте решение ниже. Если хотите ещё немного пораскинуть мозгами, можете посмотреть на то, как я вырабатываю витамин Д, греясь в лучах сентябрьского солнышка на травке. 😎
Ну, давай, не томи уже
Решение выглядит так. Делим наши девять камней на три равные части: А (A1, A2, A3), B (B1, B2, B3), C (C1, C2, C3).
Взвешиваем на весах камушки из группы А с камушками из группы В. Помните, что все камни, кроме одного, равны по весу и только один тяжелее остальных? Это значит, что во время первого взвешивания мы уже можем определить, в какой из групп находится интересующий нас камушек. Если чаши весов уравновесятся, значит искомый камень находится в группе С. Если же А перевесит В или наоборот, откладываем три камня из этой группы и производим повторное взвешивание. Принцип тот же. Два камня либо будут равны, тогда третий камень и будет самым тяжёлым, либо этот камень перевесит на чаще весов во время второго взвешивания.
Вот и всё!
Получилось ли у вас самостоятельно раскусить эту задачку? Оставляйте комментарии. Ставьте лайк, если было интересно. Теперь вы знаете, есть ли у вас шанс попасть на работу стажёром в Microsoft. 😉 Меня бы не взяли.
