Задания на собедованиях

[leviaphan]

Доброго времени суток. С какими заданиями на собеседованиях встречались форумчане? Независимо от компании, языка, фреймворка и т. п. Интересуют задания для разработчиков, тимлидов и проект менеджеров.


Особенно интересны всякие интересные задания вроде тех, что задают в Google.

[Journeyman]

Вот пример. Это был bittorrent.com. Ещё их задача:

There is an ant which can walk around on a planar grid. The ant can move one space at a time left, right, up or down. That is, from (x, y) the ant can go to (x+1, y), (x-1, y), (x, y+1), and (x, y-1). Points where the sum of the digits of the x coordinate plus the sum of the digits of the y coordinate are greater than 25 are inaccessible to the ant. For example, the point (59, 79) is inaccessible because 5 + 9 + 7 + 9 = 30, which is greater than 25. How many points can the ant access if it starts at (1000, 1000), including (1000, 1000) itself?

По моему мнению задача нетривиальная.

Ещё: есть последовательность чисел. В этой последовательности числа парные, т.е. каждое встречается два раза. Кроме одного, его и нужно найти (это задача MTV social gaming).

Или ещё вспомнилось: есть 6 шаров. Один из них тяжелее. За какое количество взвешиваний можно определить самый тяжёлый?

[Алекс26]

во 2й задаче вы видимо хотели наложить ограничения на обьем исп. памяти и/или количество проходов по последовательности?

[Journeyman]

во 2й задаче вы видимо хотели наложить ограничения на обьем исп. памяти и/или количество проходов по последовательности?

Они ничего такого не говорили. Самый простой способ - просто xor'ить числа. Думаю проще и эффективнее вряд ли выйдет.

[Прoхожий]

За какое количество взвешиваний можно определить самый тяжёлый?

За одно - едва ли, а вот за два - легко

[Journeyman]

За одно - едва ли, а вот за два - легко

Недавно обнаружил второе решение за два взвешивание, правда оно очень похоже.

Чтобы тут не офтопить, тут есть интересные задачки, которые вряд ли будут на собеседованиях. Сам пока решил только 4, принципиально не ищу ответов в интернетах. Если кому интересно - добро пожаловать.