|
|
Интервью-клуб - morfizm
| May. 27th, 2009 02:52 pm Интервью-клуб Вчера сходил на интереснейшее мероприятие - собрание небольшого клуба по интересам для желающих потренировать свои способности инженерного интервью среди русскоязычных разработчиков в Microsoft.
Формат занятия:
Участники разбиваются на группы по три человека, среди которых как минимум один старший разработчик и один новичок. Каждая группа идёт заниматься в соседний свободный конференц-зал. Время занятия такое, что конференц-залы почти все свободные. В каждой группе по кругу меняются роли: интервьюируемый, интервьюирующий и наблюдатель. (Разумеется, надо приходить со своими подготовленными задачами.) Для каждого круга 20 минут отводится на интервью и 10 на отзыв, как между интервьюирующим и интервьюируемым, так и от наблюдателя к обоим.
Мы немного затянули, и успели провести лишь два круга. Я побывал интервьюируемым и наблюдателем, получил массу полезных отзывов и наблюдений, и...
...хотел было сразу поделиться, но потом понял, что пост будет большим. Так что пусть пока у вас потекут слюнки, а я пока обмозгую, как это правильно преподнести.
Кроме всего прочего, было предложено в начале встречи проводить 15-минутный доклад на тему методов решения интервьюшных задач, и я вызывался рассказать о методе индукции рекурсии к следующему разу. (Кому не лень, накидайте мне задач по индукции в комменты, спасибо!) 42 comments - Leave a comment   | |
 | | From: |  extesy |
|---|
| Date: | May 28th, 2009 12:12 am (UTC) |
|---|
| | | (Link) |
|
Что значит задача по индукции? Насколько я знаю, математическая индукция - это метод доказательств теорем. Как это применимо к программированию?
| | From: | extesy |
|---|
| Date: | May 28th, 2009 01:37 am (UTC) |
|---|
| | | (Link) |
|
ну там стандартное, факториал, числа фиббоначчи ;) ну ты знаешь
есть лягушка которой надо пересечь прямоугольный пруд. В каждой клетке пруда по кувшинке, лягушка не может перепрыгнуть через кувшинку. Когда лягушка начинает прыгать то кувшинки тонут сразу за ней, причем сразу всем рядом, паралельным берегу. Соответственно, лягушка может прыгнуть только либо вперед, либо вперед-направо, либо вперед-налево. На каждой кувшинке какое-то количество мух (положительное число, заданое двухмерным массивом). Когда лягушка прыгает на кувшинку, то она съедает всех мух на ней. Задача: выбрать маршрут для лягушки, который максимизирует количество съеденых мух.
А если она прыгает по диагонали, то какие кувшинки тонут? (оба ряда - сзади и сбоку?)
только сзади, параллельно берегу. можно ограничить по другому - лягушка может сделать только N прыжков, где N это ширина болота и в конце она обязана находиться на другом берегу.
Это слишком тривиально и не продемонстрирует всю мощь метода. Я хочу какие-нибудь генераторы показать (перестановки, разбиения). Особенно интересны примеры, когда рекурсия двумерная, и для решения задачи необходимо *ввести* этот дополнительный параметр. Потом какие-нибудь обходы деревьев. Чего ещё?
калькулятор со скобками, например
а про Fn лучше сказать, что бы кому-нить не пришло в голову делать рекурсивную реализацию
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).
отставить намеки на то что нерекурсивные методы решения лучше, они не соответствуют теме поста! :)
... и еще отлично тренирует рекурсию robozzle
Да, это рульная вещь. Смотрел уже :)
Правда, времени нет играться. Вот дети подрастут, буду их учить
|
|
