Собеседование в Яндексе.

[stpdqstns]

Здравствуйте. Недавно получил предложение пройти skype-собеседование от сотрудников Яндекса(проходить производственную практику), в своем письме они посоветовали подготовиться отвечать на вопросы о программировании на C++, структурах данных, алгоритмах. Из структур данных и алгоритмов читал только о стандартных в STL в справочнике Шилдта. О понятиях сложности, временной сложности не имею практически представления, и какие еще характеристики у алгоритмов есть. Вобщем, подскажите, пожалуйста, литературу или другие источники, где можно хорошо узнать о алгоритмах и структурах данных(на русском языке).

[Abstraction]

С. Скиена, "Алгоритмы";
Кормен-Лейзерсон-Ривест-Штайн, "Алгоритмы: построение и анализ";
Ахо-Хокпрофт-Ульман, "Структуры данных и алгоритмы".

[Darkwinged]

Из своего опыта могу сказать, что нужно знать сложность записи, чтения, удаления из стандартных контейнеров STL и на базе чего контейнеры построены. Сложность поиска по контейнерам. Слышал могут спросить про сложности/использование памяти различных сортировок.
Сам я учу алгоритмы по Седжвигу "Алгоритмы на С++", но это занятие не на неделю и не на две.
Ещё сайт полезный по алгоритмам http://e-maxx.ru/algo/
Стоит подтянуть синтаксис языка, правила создания/удаления объектов и прочее само собой.
Полезный псто http://habrahabr.ru/post/117996/

[waleri]

Если хотите серьезно этим заниматься - учите английский.
http://en.wikipedia.org/wiki/Big_O_notation

[Blondy]

Я, к сожалению, не знаю специфики тестовых заданий и вопросов от Яндекса. Но, как тут справедливо было замечено, алгоритмы и структуры данных тема очень обширная и чтобы ее освоить необходимо в течении нескольких месяцев и теорию читать, и кучу практических заданий перерешать.
Вот Вам ссылочка на стандартный академический базовый курс http://www.intuit.ru/department/algorithms/staldata/ Яндекс организация серьезная, поэтому наверняка предполагается что, как минимум, в пределах академического курсы Вы должны быть как рыба в воде.

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

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

Опять таки тонкость - в чем эти структуры данных попросят реализовать: классы, массивы или структуры. Несмотря на похожесть логики алгоритмов обработки данных, у каждой структуры будут свои ньюансы.

PS Когда Вы пройдете собеседование, обязательно расскажите - про что спрашивали. Интересно же!

[stpdqstns]

Итак, теперь могу отчитаться. У меня было 2 собеседования, первое skype, второе по телефону. На первом собеседовании у меня поинтересовались кто я, какой опыт имею и какими проектами занимался, далее предложили ответить на список теоретических вопросов по C++, очень помогла ссылка Darkwinged http://habrahabr.ru/post/117996/, многие вопросы были взяты оттуда. Например о назначении виртуального конструктора, о генерации исключений в конструкторе и деструкторе, как предотвратить копирование объекта, спросили что такое наследование, о private и public наследовании, абстрактных классах; спросили о назначении ключевых слов volatile, template, typename, отличие deque от vector, внутренне устройство deque. Спросили о RAII. Также поинтересовались имею ли я опыт в разработке сетевых приложений, в метапрограммировании и разработке под Linux. В целом я ответил неплохо и через день на ящик пришло еще одно письмо с предложением пройти второе skype-собеседование с видео и написанием кода.

В этот раз собеседование проходило по телефону(из-за проблем со skype) с использованием http://collabedit.com/, также поинтересовались моим опытом и проектами, над которыми работал. В этот раз я ответил только на один вопрос, к чему приведет попытка скомпилировать такую вот строчку:

printf("%d", (int*)2+3);

Ответил, что скомпилируется норм и выведет 14. Далее я все запорол на простых задачках. Было предложено написать код для удаления элементов из односвязного списка с хвоста списка. В общем я наверное сильно волновался, и не мог нормально сосредоточиться на задаче и сказал, что не знаю как это сделать, мне рассказали 3 способа как это можно сделать, два неэффективных и 3й эффективный, для чего нужно мне было предложено реверсировать этот список, этого я тоже, к своему стыду, не смог сделать. Последнее задание было найти медиану в отсортированном массиве чисел. В общем, этого я тоже не сделал, хотя задание наипростейшее. После этого со мной распрощались, посоветовав почитать алгоритмы Скиены и посетить topcoder.com. Через день на ящик пришло письмо с отказом, который я и ожидал, а также с солидным списком литературы, которую стоит изучить. Обидно конечно, что не смог решить те простые задачки, после собеседования я конечно с ними разобрался.. Но в целом, общение с людьми из Яндекса порадовало, попробую в следующий раз показать себя лучше.

[Abstraction]

Ответил, что скомпилируется норм и выведет 14.

Вообще говоря, зависит от размера типа int. Стандарт C++ не гарантирует, что sizeof(int)==4.

А так, поздравляю с интересным опытом

[Darkwinged]

В Яндексе вообще очень продуктивные собеседования.
Не могли бы вы поделиться списком литературы?

[stpdqstns]

Пожалуйста, список литературы:

Рекомендуем Вам поступить в ШАД (http://shad.yandex.ru/), почитать следующие книги:

По программированию:
* Б. Страуструп, Язык C++.
* Г. Саттер. Решение сложных задач на С++.
* Г. Саттер. Новые сложные задачи на С++.
* Г. Саттер. Стандарты программирования на С++.
* Э. Хант, Д. Томас. Программист-прагматик. Путь от подмастерья к мастеру.
* М. Фаулер. Рефакторинг. Улучшение существующего кода.
* Э. Гамма, Р. Хелм, Р. Джонсон, Дж. Влиссидес. Приемы объектно-ориентированного проектирования. Паттерны проектирования.
* Э. Таненбаум. Современные операционные системы.

По алгоритмам:
* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ.

[Darkwinged]

Спасибо!
Вот мой список. Может, пригодится

Рекомендуем Вам поступить в ШАД (http://shad.yandex.ru/), почитать следующие книги:
По программированию:
* Б. Страуструп, Язык C++.
* С. Мейерс. Эффективное использование С++. 50 рекомендаций по улучшению ваших программ и проектов.
* С. Мейерс. Эффективное использование С++. 35 новых способов улучшить стиль программирования.
* С. Мейерс. Эффективное использование STL.
* Э. Хант, Д. Томас. Программист-прагматик. Путь от подмастерья к мастеру.
* М. Фаулер. Рефакторинг. Улучшение существующего код.
* Э. Гамма, Р. Хелм, Р. Джонсон, Дж. Влиссидес Приемы объектно-ориентированного проектирования. Паттерны проектирования.
* Э. Таненбаум. Современные операционные системы.

Посмотрите сайты:
* http://e-maxx.ru
* http://algolist.ru