Мини-конкурс для программистов

Не секрет, что многие наши соотечественники, даже совсем далекие от компьютерного мира, после эмиграции на Запад начинают зарабатывать на жизнь, занимаясь программированием или чем-то близким. Менее известно, что при приеме на тамошнюю работу определяющим фактором, как правило, является вовсе не знание software (и, тем более, - не умение с завязанными глазами устранять неисправности в hardware), а гораздо более прозаическая штука: умение соображать. Для проверки этого умения на первом собеседовании (интервью) кандидату обычно предлагают одну-две-три классических программистских задачки. Говорят, что такой способ значительно эффективнее, чем вопросы типа "чем IDE отличается от SCSI".

Я предлагаю читателям-программистам (и непрограммистам тоже) порешать несколько заданий, предлагавшихся в реальных интервью в разное время и в разных фирмах. Многие из них хорошо известны и опубликованы в книжках вместе с решениями, но я надеюсь, что каждый читатель найдет для себя что-нибудь новенькое.

1.1 Web-игра

Программист Вася решил поиграть с Интернетом. Он начинает свое путешествие на какой-то произвольной Web-страничке, а затем переходит со странички на страничку - каждый раз внимательно читая страничку сверху вниз и уходя с нее на первую же гиперссылку. Цель игры - зациклиться, то есть вернуться на начальную страницу.

Вся проблема в том, что Вася не в состоянии упомнить все адреса, по которым он ходил. Да и браузер у него плохонький - помнит только два адреса (хотя может обращаться к любому из этих адресов). Как Васе определить, зацикливается ли его путешествие? Помогите ему найти "честное" решение, то есть, без использования как дополнительных возможностей операционной системы (типа clipboard'а), так и без обыкновенных ручки и блокнота.

1.2 Аргентина манит негра

Есть строка символов. Напишите программу, которая укажет, является ли эта строка палиндромом (то есть, совпадает ли она со своим обращением с точностью до пробелов). Изменять строку не разрешается и заводить какие-либо вспомогательные строки также нельзя.

1.3 Экономный обмен

Дана таблица X[1]…X[N]. Необходимо поменять местами ее куски X[1]…X[M] и X[M+1]…X[N]. Каждый элемент таблицы разрешается перемещать не более одного раза.

1.4 Двумерный поиск

Имеется двумерный массив MxN, элементы которого упорядочены по возрастанию слева направо и сверху вниз. Необходимо определить, встречается ли в нем элемент, равный X. (Постарайтесь при этом отыскать экономный алгоритм).

1.5 Среднестатистический китаец

В таблицу занесены данные о росте миллиарда китайцев. Требуется написать программу определения роста "среднего китайца" - то есть, такого, для которого примерно половина всех китайцев ниже его по росту, а другая половина - выше. (Для полной сортировки такой таблицы вам не хватит ни времени, ни памяти компьютера).

1.6 Казнь по кругу

По кругу расположено N человек. Начиная с некоторой позиции, мы считаем по часовой стрелке и казним каждого M-го (после казни круг смыкается теснее). Написать программу, определяющую, кто будет казнен последним.

1.7 Найти пропуск

В массиве длины N содержатся все целые числа от 0 до N, кроме какого-то одного. Найти пропущенное число, если использовать дополнительные массивы нельзя.

1.8 Плюс-минус

Дана сумма, слагаемые которой - квадраты натуральных чисел: S=1+4+9+16+25+…+10000. Напишите программу, которая определяет, какие из плюсов в этой сумме нужно заменить на минусы, чтобы в результате получился нуль.

* * *

В отличие от предыдущих заданий, в следующих не требуется вообще никакого программирования.

2.1 Переправа

На берегу реки стоят папа, мама, бабушка и младенец. Им надо перейти по мосту на другой берег. Дело происходит ночью, поэтому без фонарика не обойтись. У них на всех есть только один фонарик. Скорости передвижения по мосту разные: папа может пройти мост за одну минуту, мама - за две, бабушка - за 5, а младенец - за 10. К сожалению, мост выдерживает не более двух человек. Если по мосту идут двое, то они должны держаться за руки, поэтому двигаются они со скоростью более медленного пешехода. Как им всем переправиться за наименьшее возможное время?

2.2 Двенадцать монет

Из двенадцати монет - одиннадцать настоящих, а одна фальшивая (она отличается по весу от настоящей, но неизвестно, в какую сторону). Требуется за три взвешивания на двухчашечных весах без гирь найти фальшивую монету и выяснить, легче она или тяжелее настоящей.

2.3 Тринадцать монет

Из тринадцати монет - двенадцать настоящих, а одна фальшивая (она отличается по весу от настоящей, но неизвестно, в какую сторону). Требуется за три взвешивания на двухчашечных весах без гирь найти фальшивую монету.

2.4 Настоящая монета

Среди одиннадцати монет - не более пяти фальшивых. Все настоящие монеты весят одинаково (а фальшивые, возможно, нет). Можно ли за одиннадцать взвешиваний определить хотя бы одну из настоящих монет?

2.5 Пять предметов

Пять различных предметов требуется расположить в порядке возрастания их веса. Пользоваться можно только двухчашечными весами без гирь. Как это сделать за наименьшее число взвешиваний?

2.6 Размен доллара

В США используются монетки в 1, 5, 10, 25 и 50 центов, а также однодолларовая монета. Каким наименьшим числом монет невозможно заплатить один доллар?

2.7 Пропавший доллар

Трое путешественников, проведя ночь в отеле, заплатили 30 долларов за ночлег и отправились дальше. Через какое-то время администратор сообразил, что номер стоил всего 25 долларов, и отправил мальчишку-посыльного вернуть деньги. Посыльный решил, что пять долларов плохо делится на троих, поэтому, догнав путешественников, отдал каждому по доллару, а два доллара прикарманил.

Теперь подсчитаем: каждый из них заплатил по десять долларов и получил доллар сдачи. Следовательно, они заплатили по девять долларов - вместе 27. Еще два доллара осталось у мальчишки - итого 29. Куда же делся один доллар?

2.8 Три пловца

Адамс, Браун и Смит часто принимали участие в соревнованиях по плаванию. После окончания своей спортивной карьеры они встретились и выяснили, что Адамс чаще опережал Брауна, Браун чаще заканчивал дистанцию раньше Смита, а Смит чаще обгонял Адамса. Не было ли в их подсчетах ошибки?

P.S. Имейте в виду, что и в России потихоньку входят в моду вступительные собеседования при приеме на работу. Так что вполне может оказаться, что вашему новому работодателю эта статья попадется на глаза, после чего он решит попробовать мои задачки на вас. Поэтому лучше порешайте их загодя! А своими впечатлениями можете поделиться со мной: kk@knop.spb.ru