Идею этого поста предложил Эмилбек -emli- Сулайманов. Спасибо тебе!

Напоминаю, что жду ваши предложения о новостях в личные сообщения :)

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

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

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

Кроме того, олимпиады, к сожалению, часто развивают навыки написания плохо читаемого кода, отчасти потому что вряд ли придётся возвращаться к этому коду после получения OK по задаче. Этот фактор тоже, скорее, играет отрицательную роль на собеседованиях, если писать код в том же стиле, что и на контестах.

Действительно, задачи на собеседованиях в крупные компании (МС, ФБ, гугл...) обычно на уровне див 2 B, C так что олимпиаднику их решить ничего не стоит)) плюс кроме самой идеи решения как правило нужно закодить на доске ( в блокноте) и на все это минут 25-30. Как мне кажеться, чтобы успешно пройти собеседование достаточно знать: указатели, динамику, сортировки, бинпоиск, структуры данных (set, map, hash_set, hash_map, queue, stack, Segment tree), обработка строк.

в небольших компаниях чаще спрашивают по тонкостям языка, по алгоритмам очень слабо... например, меня пробовали завалить вопросом: "Что такое бинарный поиск"))

Как уже написали выше, есть два типа компаний:

• Крупные компании уровня Google, Facebook, Yandex и компании, где важны алгоритмические навыки.

• Остальные, т.е. те, где именно алгоритмические навыки важны не так сильно (больше важно знание конкретных языков, паттернов проектирования, опыт работы в команде и т.п.).

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

Сложность задач в компаниях первого типа — что-то на уровне Div1 A/B, Div 2 B/C. Но надо понимать, что время ограничено еще сильнее чем на олимпиаде, к тому же, часто приходится писать решение не на компьютере, а на листочке/доске/... Еще важный аспект — в отличие от олимпиады, обычно требуется обосновать корректность решения.

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

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

P.S. Все написанное — из личного опыта прохождения собеседований в Яндекс/Google/несколько менее известных компаний.

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

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

Или же наоборот, однажды на собеседовании я получил задачу с ограничениями на все int32, и единственный алгоритм, до которого я смог додуматься был O(n^3). Я быстро набросал это решение на доску и провел больше 40 минут разговаривая с собеседником (который при этом быстро все происходящее записывал на своем ноуте), пытаясь догадаться до лучшего решения. В конце собеседования я спросил его, существует ли решение лучше, а он ответил, что не знает, и что вообще он видит эту задачу впервые.

При этом большое значение играет, собеседуетесь ли вы с BigCorp или с SmallCorp.

Допустим, это BigCorp. Тогда:

1. Опыт участия в спортивном программировании реально поможет пройти собеседование. Задача BigCorp-а — найти людей, которые соображуют. У них часто свой собственный закрытый стек технологий, и им в принципе все равно, с какими технологиями человек работал раньше. Проверка людей с помощью собеседований на алгоритмические задачи — далеко не идеальный, но достаточно хороший способ отсеять людей.

2. Популярные темы при этом: binary search, trees, graphs, sort-related algorithms, linked lists, string-related algorithms.

3. Знание O(n) ассимптотики обязательно, включая time complexity & memory complexity. С этим у спортивных программистов проблем нет.

4. Общение и простота решения имеет важнейшую роль. Как-то я решил задачу с помощью RMQ вместо двух binary search, и я не смог доказать O(log n) сложность RMQ, в итоге "послав" человека читать википедию. Результат: не смог донести идею решения, не смог донести простое решение, показался заносчивым — не командный игрок, не взяли.

5. По мере написания алгоритма на доске, можно показывать знание паттернов, можно писать псевдоязыком, во многих случаях просто допуская, что подобная функция имеется.

6. Хеширование — скользкая тема, к которой нужно осторожно относится. Применение хеширования там, где можно применить КМП — не хорошо. Утверждение, что запросы к хэш сету имеют О(1) сложность — не хорошо. С другой стороны, написание алгоритма с O(n * log(n)) сложностью, в то время когда с помощью хэш сета можно добиться O(n) — тоже нехорошо.

7. На собеседованиях в BigCorp меня ни разу не спросили ни одного вопроса на многопоточность, но onsite interviews содержат 1-2 design problems, где может понадобиться знание distributed systems.

8. CV мало влияет на вероятность получения положительного ответа. Собеседник имеет не больше 2 минут, чтобы просмотреть резюме, и понять что от вас можно ожидать. Если CV будет указывать, что у вас есть хорошие результаты по спортивному программированию, то вероятно собеседник будет ожидать, что вы справитесь с алгоритмическими задачами на раз-два, и он наверно расстроится, если этого не произойдет. Поэтому, подавая CV в BigCorp, я рекомендую убирать любое упоминание о ACM или sports programming, а в идеале иметь отдельное CV для HR, и отдельное CV для инженеров.

Если же вы собеседуетесь со SmallCorp, то

1. Можете ожидать чего угодно. У каждой компании свои методы потбора сотрудников. И если вас не взяли, это не значит, что вы провалили собеседование. Это как правило значит, что в данным момент вы им не нужны.

2. Знание определенных технологий, языков и принципов разработки играет существенную роль.

3. Указание успехов в спортивном программировании в CV может играть существенную роль.

4. Многие SmallCorp-ы проводят собеседования на алгоритмические задачи. Параллельно они могут спрашивать нюансы языка и многопоточность.

5. Самой популярной темой при этом являются разные структуры данных для написания кэшей. Причем это прекрасный плацдарм для проверки знаний пареллелизма.

6. Бывают жутко неприятные казусы:

1) Собеседование прошло просто отлично. На следующий день сообщают regrettably... Спрашиваю, как это так, собеседование было ж на отлично. Ответ: ну да, собеседование было на отлично, но мы ищем человека со знаниями других технологий/с другим опытом. Вывод — HR плохо делают свою работу.

2) Получая некоторые специфичные вопросы от собеседников и видя довольные их лица, они наверно думают: "Ха-ха-ха, я знаю ответ на этот интересный вопрос, а он не знает". Ну да, я не могу написать сходу формулу для комбинаторного вопроса, которого никогда раньше не слышал, не знал что это имеет такое большое значение для компании, занимающейся разработкой internet of things. Еще этот вопрос: "Вам дам массив из n + 1 чисел от 1 до n, одно число повторяется 2 раза, как быстрое его найти", и затем сразу следующий: "n + 2 чисел, 2 числа повторяются 2 раза", и при этом ожидают ответа практически сразу, как на первый. Вроде как должны проверять умение догадаться до хорошего решения, а вместо этого проверяют знание ответа.

3) На одном собеседовании мне задали задачу, которая сводилась к рюкзаку с ограничением в миллион на все числа. Ну, ок, спросил, нужно ли им точное или приближенное решение. Спросил несколько раз, ответили, что нужно точное. Пришлось писать рекурсивный перебор с отсечением, которого собеседник понятное дело слабо понимал. Затем, он сказал скомпилировать это решение (оказывается, их онлайн редактор умел компилировать) и запустить на тестовом примере. Очень редкая вещь на собеседовании, я как правило пишу псевдокодом, стараясь показать и знание паттернов. К тому же я писал на Java, а я привык к Intellij IDEA, который фактически за меня все дописывает. В результате это свелось к жалким попыткам скомпилировать это чудо. В конце собеседования я спросил, где в их health-related web application они сталкиваются с такими задачами, на что получил ответ — Load Balancer. Ему повезло, что он был на другом стороне скайпа. Что-то я увлекся...

На Quora сравнивают сложность задач с собеседований в Google с задачами второго дивизиона и утверждают, что задачи с собеседований Facebook проще задач контестов.

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