интервью программиста (интересно только программистам)

[avva]

— Расскажите о своей карьере до сих пор.

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

— Гм, ну а как насчет последнего проекта, которым вы занимались?

— Воспользоваться merge sort и разбить на N кусков, каждый из которых умещается в память.

— Какую роль вы играли в вашей рабочей группе на последнем месте работы?

— Сначала пройти один раз и переворачивать отдельно каждое слово, потом перевернуть всю строку еще раз.

— Расскажите подробнее о последнем баге, который вы починили.

— Чтобы имплементировать с их помощью Singleton pattern.

— Какие языки программирования вы предпочитаете и почему?

— Если использовать XOR, можно обойтись без временной переменной.

— Вы нам подходите. Когда вы можете начать работать?

(идея украдена из этой записи (англ.), рекомендую)

Comments

[a7sharp9.livejournal.com]

Прекрасно!

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

[dizzy57.livejournal.com]

Про сортировку слиянием не узнал.

[dimrub.livejournal.com]

Хе-хе. Дополню, скажем, так:

— Как вы предпочитаете изучать новую для вас технологию?

— В цикле меняем сохраненный элемент на текущий с вероятностью единица деленная на номер текущего элемента.

[dimrub.livejournal.com]

Кажется, надо отсортировать огромный список, не влезающий в память.

[vadimkle.livejournal.com]

всё правда, кроме последней фразы

[white-lee.livejournal.com]

Почему, я думаю, что авва действительно украл это из той записи, и он действительно ее рекомендует ;)

[vadimkle.livejournal.com]

в той записи так и есть, я видел.
я о своем опыте.

[white-lee.livejournal.com]

Вы не поняли :)

[tassadar-il.livejournal.com]

я наверное дико торможу и шутка юмора не достигает астральных высот, куда уплыло мое сознания. поясните! понимаю что все это ответы на задачки которые часто дают на интервью, но в чем смысл?

[kvakoshka.livejournal.com]

Верно. Применяется при сортировке больших файлов на диске.

[xfyre.livejournal.com]

у меня примерно такой же вопрос :)

mark

[(Anonymous)]

во-первых, первоисточник, все-таки, интереснее, поскольку не так прямолинеен, как аввовский вариант, и реально заслуживает оценку "nice";
во-вторых, если авве смешно, а вам - нет, то это не значит, что с вами что-то не так...

Re: mark

[avva.livejournal.com]

Дело не в прямолинейности, а просто в другом выборе типа вопросов. Но ваша язвительность меня порадовала, спасибо :)

mark

[(Anonymous)]

"меняя направление указателей в обратную сторону" - это, чтобы понятно было, что не в левую и не в правую ;)

[malaya-zemlya.livejournal.com]

— Вопрос, ответ на который невозможно проверить.
— Ответ, не имеющий отношения к реальной работе.

Re: mark

[ex-ex-annut.livejournal.com]

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

[scolar.livejournal.com]

Второе решение (с переворотом) я придумал на интервью году в 2000. Но интервьюер не понял. И был послан.

[a7sharp9.livejournal.com]

Респект. Я тоже придумал именно второе, но не в обстановке интервью.

[scolar.livejournal.com]

У меня, собственно, никаких идей не было, что со списком можно ещё делать, кроме как начать переворачивать - поэтому дальше было просто. А вот хотел бы я посмотреть на человека, который сам придумал решение с двумя пойнтерами.

[ex-ex-annut.livejournal.com]

В десткие года когда я была сиеснительным ребенком меня пригласили в какую-то семью, которую я жутко стеснялась, а с другой стороны хотелось показать себя почему-то именно остроумным человеком.
Прочитала пару книжек со смешными историями приямо к этой встрече.
Сидели за столом, разговаривали, так как от усилий потраченных на подготовку мое стеснение только увеличилось, то на любую фразу брошенную за столом я рассказывала очередной анекдот по порядку.

[ex-ex-annut.livejournal.com]

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

[migmit.livejournal.com]

Ни хрена не понял. Это вообще о чём?

[109.livejournal.com]

- да.
- это что?
- и это?
- static members?
- а можно просто складывать-вычитать, если гарантировано отсутствие переполнения.

[dimrub.livejournal.com]

Ага, именно так.

Re: mark

[dimrub.livejournal.com]

А какие более эффективные? Расскажите, пожалуйста, если не лень.

Re: mark

[ex-ex-annut.livejournal.com]

если нужно однородное распределение, то есть несколько методов примерно на том же принципе, что и стандартный, но немного более эффективных
это все называется reservoir sampling
вот неплохой обзорчик с доказательством что без резервуара никуда
http://www.cs.duke.edu/~jsv/Papers/Vit85.Reservoir.pdf
также посмотрите по ключевым словам
sampling window streaming так в дата стрим много работали с этим (Радж Мотвани)





зачастую задача бывает еще проще
входной поток у вас уже достаточно рандомизированный
вам нужно набрать N
до n_1 < N вы набираете все элементы
а потом с вероятностью которая зависит от выбранного числа элементов и некоторых предположений о распределении на начальном потоке подбираете до N
на больших потоках это дает перевес в сторону начальных данных
но опять же они могут быть изначально случайными или можно придумать (если есть контроль над потоком например из хранилища данных) как начальный поток поменять
это дает приближения но достаточно хорошее для многих задач уровня аналитика по продажам итд
если данные обрабатываются паралельно то немного усложняем

это уже чистая статистика могу рассказать более подробно для однородных распределений (завтра у нас уже час ночи)

[slobin.livejournal.com]

Ну, посмотрите. ;-) Я его сам придумал году в 84-85 (то есть первый либо второй курс университета).

... Только каков был вопрос, если это ответ? ...

[evgeniysharapov.livejournal.com]

Хаха. Первоисточник интереснее. Но смешно будет только тем, кто проходил интервью в американских компаниях. Сплошные отсылы к типичным вопросам на типичном интервью. Про лампочки до сих пор помню. Три лампочки, три выключателя. Какая из лампочек будет горячей.

[syarzhuk.livejournal.com]

Я придумал следующее: от первого элемента идём на 1 шаг, от следующего - на 2, от следующего - на 3 и т.д. В конце каждого шага проверяем, не попали ли в тот же элемент, с которого начинали итерацию. Таким образом, или упрёмся в конец списка, или на итерации, номер которой делится на (не обязательно равен) размер кольца, поймём, что есть кольцо. Но не на интервью, и не за 5 минут

[scolar.livejournal.com]

Самое смешное, что это является и решением для задачи про список с кольцом. Только что запостил: http://scolar.livejournal.com/254112.html

[dimrub.livejournal.com]

Ха, забавно!

[andreyvo.livejournal.com]

На мелкософтовских интервью все то же самое, в блумберге тоже подобные вопросы... шаблонно мыслят господа-интервьюеры последнее время, прям по книжке " "Programming interviews exposed" (http://www.amazon.com/Programming-Interviews-Exposed-Secrets-Landing/dp/0471383562)