?

Log in

No account? Create an account
   Journal    Friends    Archive    Profile    Memories
 

Интервью-клуб - morfizm


May. 27th, 2009 02:52 pm Интервью-клуб

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

Формат занятия:
Участники разбиваются на группы по три человека, среди которых как минимум один старший разработчик и один новичок. Каждая группа идёт заниматься в соседний свободный конференц-зал. Время занятия такое, что конференц-залы почти все свободные. В каждой группе по кругу меняются роли: интервьюируемый, интервьюирующий и наблюдатель. (Разумеется, надо приходить со своими подготовленными задачами.) Для каждого круга 20 минут отводится на интервью и 10 на отзыв, как между интервьюирующим и интервьюируемым, так и от наблюдателя к обоим.

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

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

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

42 comments - Leave a commentPrevious Entry Share Next Entry

Comments:

From:extesy
Date:May 28th, 2009 12:12 am (UTC)
(Link)
Что значит задача по индукции? Насколько я знаю, математическая индукция - это метод доказательств теорем. Как это применимо к программированию?
From:morfizm
Date:May 28th, 2009 01:01 am (UTC)
(Link)
From:extesy
Date:May 28th, 2009 01:37 am (UTC)
(Link)
Вот тебе список отличных задач на динамическое программирование: http://black-zorro.com/mediawiki/СДА_Док_часть_11
From:dennyrolling
Date:May 28th, 2009 04:42 am (UTC)
(Link)
ну там стандартное, факториал, числа фиббоначчи ;) ну ты знаешь
From:dennyrolling
Date:May 28th, 2009 04:48 am (UTC)
(Link)
есть лягушка которой надо пересечь прямоугольный пруд. В каждой клетке пруда по кувшинке, лягушка не может перепрыгнуть через кувшинку. Когда лягушка начинает прыгать то кувшинки тонут сразу за ней, причем сразу всем рядом, паралельным берегу. Соответственно, лягушка может прыгнуть только либо вперед, либо вперед-направо, либо вперед-налево. На каждой кувшинке какое-то количество мух (положительное число, заданое двухмерным массивом). Когда лягушка прыгает на кувшинку, то она съедает всех мух на ней. Задача: выбрать маршрут для лягушки, который максимизирует количество съеденых мух.
From:morfizm
Date:May 28th, 2009 04:56 am (UTC)
(Link)
А если она прыгает по диагонали, то какие кувшинки тонут? (оба ряда - сзади и сбоку?)
From:dennyrolling
Date:May 28th, 2009 05:55 am (UTC)
(Link)
только сзади, параллельно берегу. можно ограничить по другому - лягушка может сделать только N прыжков, где N это ширина болота и в конце она обязана находиться на другом берегу.
From:morfizm
Date:May 28th, 2009 04:58 am (UTC)
(Link)
Это слишком тривиально и не продемонстрирует всю мощь метода. Я хочу какие-нибудь генераторы показать (перестановки, разбиения). Особенно интересны примеры, когда рекурсия двумерная, и для решения задачи необходимо *ввести* этот дополнительный параметр. Потом какие-нибудь обходы деревьев. Чего ещё?
From:dennyrolling
Date:May 28th, 2009 05:59 am (UTC)
(Link)
калькулятор со скобками, например

а про Fn лучше сказать, что бы кому-нить не пришло в голову делать рекурсивную реализацию
From:morfizm
Date:May 28th, 2009 09:17 am (UTC)
(Link)
Fn - это ты про числа Фиббоначи?

У них *уже дано* рекурсивное определение. Мне кажется, более важно - развить способность самому "видеть" рекурсию и создавать рекурсивные определения там, где их нет. Если рассматривать примеры, в которых рекурсивные определения уже даны, это отвлечёт от подобной цели.


Калькулятор со скобками - что именно? Я могу представить себе множество задач, связанных с калькулятором со скобками.
From:extesy
Date:May 28th, 2009 04:19 pm (UTC)
(Link)
Еще мне нравится задача о красивом разбиении текста. Условия: есть массив слов, представляющий собой какой-либо текст (words[] = text.split(' ')) и задана желаемая длина строки L. При разбиении текста на строки длиной L в каждой строке справа остаётся 0 <= Si < L пробелов (пустых строк не бывает). Красивым называется разбиение, при котором сумма кубов Si минимальна: sum(0..n, Si^3) -> 0

Решение рекурсией элементарное за O(n^2), а вот ты попробуй решить без рекурсии и за O(n).
From:dennyrolling
Date:May 28th, 2009 05:15 pm (UTC)
(Link)
отставить намеки на то что нерекурсивные методы решения лучше, они не соответствуют теме поста! :)
From:dennyrolling
Date:May 28th, 2009 06:29 am (UTC)
(Link)
... и еще отлично тренирует рекурсию robozzle
From:morfizm
Date:May 28th, 2009 09:18 am (UTC)
(Link)
Да, это рульная вещь. Смотрел уже :)
Правда, времени нет играться. Вот дети подрастут, буду их учить