Заметки (1) с тэгом «задача»

Погасить свет в поезде

04.10.2015 21:36
Комментариев:  

Третьего дня В. прислал «типовую задачу с собеседования программистов»:

Есть циклический поезд, состоящий из неизвестного числа вагонов. Т.е. каждый вагон сцеплен с задним и передним вагоном. В каждом вагоне горит или не горит свет. И в этот поезд заходит человек, и идет по вагонам. И он должен выключить в каждом вагоне свет. И у человека есть только возможность включить\выключить свет, и перемещаться из вагона в вагон. Нужно определить, когда необходимо закончить.

Моё решение

  1. Присваиваем вагону, в котором мы сначала оказались, №1, и гасим в нём свет.
  2. Заходим в соседний, зажигаем в нём свет, называем его №0.
  3. Возвращаемся в вагон №1.
  4. Если в вагоне №1 свет горит, то в поезде всего один вагон, гасим свет, стоп. Если в вагоне №1 темно, то преходим к п.5
  5. Идём от нулевого вагона, т.е. во второй, третий и далее, пока не дойдём до вагона, в котором горит свет. Гасим свет.
  6. Возвращаемся в вагон №0. Когда мы из него уходили, свет горел. Если теперь он погас, то мы прошли весь поезд по кругу, задача выполнена, стоп. Если свет в вагоне №0 все ещё горит, снова переходим к п.5.

Забавные моменты

Решение оформилось у меня в голове в виде картины, как по горящему кольцу расползается чёрная дуга, на второй день, когда я утром шёл по подземному переходу под Волоколамским шоссе. На собеседовании я эту задачу, наверное, не решил бы.

Задачу видели несколько знакомых. Их них один вообще не понял сначала, чего от него хотят: «Когда необходимо закончить ЧТО? Жить, решать эту задачу? Хотеть устроиться к ним на работу?» Однако, узнав, что решение есть, быстро решил. На собеседовании, наверное, провалился бы.

Был интересный вариант ограничить количество вагонов сверху, ведь не может быть в жизни поезда с, например, миллиардом вагонов, и пробежать по этому миллиарду. Задача решена, т.к. и свет погашен, и момент остановки назван, но решение выглядит очень неэффективным. Интересно, возьмут ли в программисты с таким подходом.

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

Не могу пока придумать, что за должность лучше всего подойдёт автору идеи пометить первый вагон, нагадив в нём.

HyperComments