avva | задачки и головоломки

Интересный ресурс: хранилище задач и головоломок, используемых во время интервьюирования программистов. Много знакомых и хорошо известных, но много и незнакомых. Большинство простые, но есть сложные и интересные.

Вот например забавная задачка, которая мне понравилась; не слишком сложная (хоть и из раздела hard):

Вражеская подводная лодка движется в одном измерении по числовой оси. Её движение дискретно: она всегда находится на каком-то целом числе, и местоположение меняется раз в минуту. Лодка движется с постоянной скоростью вдоль оси, скорость - сдвиг по числовой оси в каждую минуту - тоже целое число. Ни местоположение лодки, ни скорость вам неизвестны.

У вас есть возможность стрелять в лодку торпедами раз в минуту, всякий раз выбирая какую-нибудь целую координату, в которую попадает торпеда. Задача: пользуясь неограниченными временем и количеством торпед, описать алгоритм, который позволит вам гарантированно поразить вражескую подлодку.

Кстати, раз уж речь зашла о головоломках, вот незаменимый сайт, содержащий архив ньюсгруппы rec.puzzles: большое количество интересных головоломок на самые разные темы, с решениями. Там есть даже большой список загадок-"данеток" (иначе называемых "ситуации", а по-английски - Situation Puzzles).

P.S. А за ссылку на страницу компьютерных задачек спасибо горячему жирафу, а кому же ещё.