Подготовка к собеседованию в Microsoft
(Содержимое поста может меняться и дополняться со временем.)
Когда я узнал, что буду проходить собеседование в Microsoft, то решил, что не буду полагаться на удачу, а попытаюсь сделать все возможное, чтобы максимизировать свои шансы на успех. То есть, я действительно хотел собеседование пройти и шел туда не ради тренировки или оценки своих способностей. Времени на подготовку у меня было около месяца, но надо учитывать, что три недели из этого месяца я еще и работал, да и семья немало времени отнимала, хотя и прилагала все усилия, чтобы меня освободить от домашних дел. Получилось, что в день на подготовку мне удавалось тратить от 1 до 4 часов, а если посчитать среднее, то, скорее всего, получится что-то около 1.5 - 2 часов.
Изначально мои шансы были невелики из-за отсутствия практики: последнее собеседование я проходил много лет назад, и ничего общего с процессом собеседования в Microsoft оно не имело. (Мне не нравится идея, что для подготовки нужно сходить на десяток-другой собеседований, а потом уж все пойдет как по маслу. Что-то в этом есть противоестественное.) Кроме того, разговорная практика на английском у меня тоже была где-то в районе нуля: немногочисленные разговоры с местным населением в заграничных отпусках, пожалуй, составляли весь мой опыт. Тем не менее, я свободно читал технические и большинство художественных текстов и хорошо воспринимал американский английский на слух. Что касается технической подготовленности, то я товарищ любопытный и учиться люблю, Coursera уважаю, умные книжки читаю и перечитываю постоянно, плюс недавняя аспирантура не давала расслабляться, да и работа часто требует включать мозг. При этом всем опыт решения маленьких алгоритмических задач, да еще и на бумаге, отсутствовал у меня почти полностью (весь опыт - несколько SRM на Topcoder), да и решать что-то в спешке, толком не продумав все аспекты, я терпеть не могу. И вообще я слегка тормоз, в смысле, думаю медленно. Это все я пишу, чтобы читатели могли как-то соотнести свой уровень с моим планом подготовки и скорректировать его в нужную сторону.
При подготовке я, разумеется, искал и читал в интернете все, что только мог найти по поводу собеседований в MS, а равно и в Google, Amazon и Yahoo, поскольку их подходы во многом схожи. Большинство тех, кто проходил собеседования, обычно описывают сам процесс (что тоже представляет несомненную ценность), но не описывают подготовку, а если и описывают, то обычно в терминах прочитанных книг (названия которых и так все знают) или изученных/повторенных областей.
Дальнейший рассказ будет строиться так: сначала я расскажу в целом об организации собеседований в MS, потом о нетехнической подготовке, затем приведу теоретический минимум и метод его проработки, и под конец перечислю задачи, которые, как мне кажется, покрывают большинство областей.
Организация собеседований в MS
Из того, что пишут в интернете, я могу сделать вывод, что процесс отбора кандидатов, во-первых, немного меняется со временем и, во-вторых, в нем могут наблюдаться отклонения в зависимости от статуса кандидата (студент, свежий выпускник, человек с небольшим опытом, человек с большим опытом, ...). Я, разумеется, мог наблюдать только ход вещей только со своей колокольни, а именно с точки зрения человека со степенью магистра, полученной 4 года назад, и 7 годами опыта разработки.
Процесс отбора, каким я его наблюдал, происходит в несколько этапов:
Нетехническая подготовка
Решать задачки и учить теорию - это все, безусловно, полезно. Но есть ряд необходимых условий нетехнического характера, некоторые из которых, судя по разочарованным отзывам в интернете в духе "я решил все задачи, а меня не взяли", многими кандидатами игнорируются:
Размышления вслух, вниманием к деталям и навык "сначала пойми, потом сделай" замечательно прорабатываются во время решения задач, так что тут убиваем четырех зайцев одним выстрелом.
Возьмите задачу, решение которой вам неизвестно. Перед тем, как начинать решать, задайте себе вслух как можно больше вопросов, касающихся этой задачи (ограничения и представление входных данных, необходимость проверки входных данных, обработка ошибок и т. п.), и дайте самому себе ответы на них. Затем решайте задачу. Старайтесь не делать никаких неявных предположений ("здесь нам будет достаточно 32-битного целого"). В ходе решения размышляйте вслух по-английски и записывайте код на бумаге. Ключевой момент здесь - нужно действительно думать вслух, а не пытаться транслировать процесс мышления в слова. В последнем случае вы будете вынуждены работать в многопоточном режиме (в одном потоке думаем, в другом говорим), а это здорово снижает скорость мышления и концентрацию. Если вам тяжело сразу думать по-английски, начните с русского, а потом, когда этот процесс станет для вас естественным, постепенно переходите на использование сначала некоторых английских слов, а потом и полностью на английский. Хорошая новость: при решении задач вам не понадобится сложная грамматика, да и набор слов будет довольно ограничен.
После того, как задача решена, а ответ записан на бумажке, нужно тщательно его проверить, прогнать в уме при разных входных данных, проверить на наличие типичных для вас ошибок (незакрытые скобки, ошибки на 1 при вычислении индексов в массивах, приведения типов, ...). Затем получившуюся программу вбивайте в компьютер с точностью до символа и тестируйте. Почти наверняка что-то не будет работать, поэтому исправляйте ошибки и запоминайте, в чем именно они заключались и почему остались незамеченными.
Стремитесь к тому, чтобы у вас с момента выбора задачи и до завершения записи решения на бумаге проходило не больше 30 минут. На собеседовании обстановка будет сложнее, так что среднее время решения немного увеличится.
Это очень важное, практически ключевое упражнение, поскольку именно так вы будете решать задачи во время собеседования. Чем больше задач вы так решите, тем лучше. Конечно, это занимает уйму времени (поначалу у меня на каждую задачу легко уходило по 1.5 часа), поэтому можно часть задач решать по полной программе, а часть - только до момента "знаю, как надо решать".
Идем дальше. Спокойствие на собеседовании очень важно. Когда трясешься и обливаешься потом, тяжело думать о циклах в связных списках. Способ, который помог мне - перенервничать до собеседования. Я почитал все описания собеседований, какие нашел в блогах, и ставил себя на место кандидатов. Пытался имитировать свои ощущения, когда мне отказывают через 10 минут после начала собеседования и обзывают нехорошими словами за непроходимую тупость. Под конец мне это все стало сниться, и я перестал себя терзать. Но требуемый эффект был достигнут: я жутко нервничал до собеседования, но на самом собеседовании был спокоен, как удав.
Еще говорят, что когда пройдешь несколько собеседований, этот процесс становится рутиной и перестает вызывать какие-либо эмоции. Сам я собирался сходить на одно, но не успел, поэтому ничего не могу сказать.
Уверенность в себе и энтузиазм существенно натренировать в короткие сроки, увы, не удастся. Или они уже есть, или нет. В некотором смысле способствует уверенности в себе техническая подготовленность, доскональное знание всего, что приведено в резюме, и готовность обсуждать любой из своих проектов вплоть до мельчайших деталей реализации, возникших проблем и способов их преодоления, взаимодействия с коллегами и т. д. Возьмите список своих проектов и напишите для каждого описание на одну страничку, стараясь придерживаться позитивного тона. Описания одного-двух проектов имеет смысл выучить наизусть - вам почти наверняка скажут "Расскажите что-нибудь о своем последнем проекте". И собеседующий предполагает, что "что-нибудь" будет связным рассказом на 1-2 минуты.
Ответы на т. н. behavioral questions нужно подготовить заранее. Я себе выписал ответы на следующие вопросы, и вам рекомендую сделать то же.
Вопросы к собеседующему - тоже важная штука, но очень простая. Если вам предлагает задать вопросы разработчик, поспрашивайте его о его команде и проекте: на каких языках пишут, как контролируется качество, как организован процесс, какова свобода принятия решений разработчиками и т. д. Это ведь и правда интересно, да? Если нужно задать вопрос HRу, то можно поспрашивать о том, как в случае успеха организуется переезд, сколько лет в среднем работают в MS, какие карьерные перспективы - да что угодно. Я HRа спрашивал о погоде в Сиэтле, от которой мы плавно перешли к обсуждению погоды в Москве, а потом и к зимним видам спорта. Так бы и болтали, если бы время не кончилось.
В качестве дополнительной тренировки многие также рекомендуют организовать себе mock interviews, то есть попросить друзей сыграть для вас роль собеседующих. Хотя сам я такое не делал, но наслышан об эффективности этой процедуры.
Еще одна важная вещь: нужно понимать, что собеседование - процесс субьективный. Человек, который вас собеседует, задает себе вопрос: "Хотел бы я с этим парнем вместе работать?". Поэтому показать нужно не только то, что вы мегамозг, умеете решать задачки и отвечать на вопросы, но и что вы просто хороший человек.
Теоретическая подготовка
Я для себя сформулировал следующий теоретический минимум (пункты приведены в произвольном порядке).
Практическая подготовка
Хотя MS декларирует, что вы можете использовать на собеседовании любой язык программирования, от вас предполагается знание C, а лучше еще и C++. Нередко встречаются задачи, требующие ручных манипуляций со связными структурами данных (например, перевернуть связный список "на месте" или вставить узел в BST) и работы с битами (например, округлить число до ближайшей сверху степени 2). У программистов на C такие задачи обычно естественным образом отработаны. Поэтому если у вас это вызывает трудности, обратите особое внимание.
Для человека, который не обладает врожденным даром быстрого мышления (я, например, не обладаю), нахождение решения задачи на собеседовании во многом зависит от того, известен ли ему общий подход к решению задач такого класса. Sad but true. На мой взгляд, без соответствующей практики почти невозможно за полчаса решить задачу вроде нахождение минимального расстояния между двумя строками. Поэтому практика решения задач - ключевой элемент подготовки.
Я уже писал раньше, что задачи лучше решать "как на собеседовании", с мыслями вслух и кодом на бумажке. Но если при чтении условия задачи решение кажется очевидным, то такую задачу можно с чистой совестью пропустить.
Ниже я привожу подборку, на которой практиковался я. Они более-менее покрывают основные виды предлагаемых задач. Замечу, что в этот список не вошли задачи, которые я где-то увидел и сразу понял, как решать. Поэтому всегда невредно будет заглянуть на сайты с задачами вроде Careercup.
Заключение
Отмечу еще раз, что все вышесказанное является планом моей личной подготовки к собеседованию. Так как собеседование прошло удачно, я предположил, что план может быть небесполезным. Однако учитывайте, что я в вопросах собеседований абсолютно не авторитет, и может оказаться и так, что все это никуда не годится, а на собеседовании мне просто повезло. К тому же, у всех людей подготовка разная, и то, что окажется эффективно для одного, будет бесполезно для другого. И уж конечно не нужно считать следование этому плану гарантией успеха. Собеседующие будут изо всех сил стараться понять, кто вы есть на самом деле, а не насколько давно вы читали книжку по алгоритмам и решали задачи.
Также, возможно, вам поможет список некоторых ресурсов, которыми я пользовался при подготовке:
Удачи!
Когда я узнал, что буду проходить собеседование в Microsoft, то решил, что не буду полагаться на удачу, а попытаюсь сделать все возможное, чтобы максимизировать свои шансы на успех. То есть, я действительно хотел собеседование пройти и шел туда не ради тренировки или оценки своих способностей. Времени на подготовку у меня было около месяца, но надо учитывать, что три недели из этого месяца я еще и работал, да и семья немало времени отнимала, хотя и прилагала все усилия, чтобы меня освободить от домашних дел. Получилось, что в день на подготовку мне удавалось тратить от 1 до 4 часов, а если посчитать среднее, то, скорее всего, получится что-то около 1.5 - 2 часов.
Изначально мои шансы были невелики из-за отсутствия практики: последнее собеседование я проходил много лет назад, и ничего общего с процессом собеседования в Microsoft оно не имело. (Мне не нравится идея, что для подготовки нужно сходить на десяток-другой собеседований, а потом уж все пойдет как по маслу. Что-то в этом есть противоестественное.) Кроме того, разговорная практика на английском у меня тоже была где-то в районе нуля: немногочисленные разговоры с местным населением в заграничных отпусках, пожалуй, составляли весь мой опыт. Тем не менее, я свободно читал технические и большинство художественных текстов и хорошо воспринимал американский английский на слух. Что касается технической подготовленности, то я товарищ любопытный и учиться люблю, Coursera уважаю, умные книжки читаю и перечитываю постоянно, плюс недавняя аспирантура не давала расслабляться, да и работа часто требует включать мозг. При этом всем опыт решения маленьких алгоритмических задач, да еще и на бумаге, отсутствовал у меня почти полностью (весь опыт - несколько SRM на Topcoder), да и решать что-то в спешке, толком не продумав все аспекты, я терпеть не могу. И вообще я слегка тормоз, в смысле, думаю медленно. Это все я пишу, чтобы читатели могли как-то соотнести свой уровень с моим планом подготовки и скорректировать его в нужную сторону.
При подготовке я, разумеется, искал и читал в интернете все, что только мог найти по поводу собеседований в MS, а равно и в Google, Amazon и Yahoo, поскольку их подходы во многом схожи. Большинство тех, кто проходил собеседования, обычно описывают сам процесс (что тоже представляет несомненную ценность), но не описывают подготовку, а если и описывают, то обычно в терминах прочитанных книг (названия которых и так все знают) или изученных/повторенных областей.
Дальнейший рассказ будет строиться так: сначала я расскажу в целом об организации собеседований в MS, потом о нетехнической подготовке, затем приведу теоретический минимум и метод его проработки, и под конец перечислю задачи, которые, как мне кажется, покрывают большинство областей.
Организация собеседований в MS
Из того, что пишут в интернете, я могу сделать вывод, что процесс отбора кандидатов, во-первых, немного меняется со временем и, во-вторых, в нем могут наблюдаться отклонения в зависимости от статуса кандидата (студент, свежий выпускник, человек с небольшим опытом, человек с большим опытом, ...). Я, разумеется, мог наблюдать только ход вещей только со своей колокольни, а именно с точки зрения человека со степенью магистра, полученной 4 года назад, и 7 годами опыта разработки.
Процесс отбора, каким я его наблюдал, происходит в несколько этапов:
- Подача резюме. Можно подавать на общих основаниях, через сайт Microsoft Careers, или через знакомого в Microsoft. Я воспользовался вторым вариантом.
- Отбор резюме. Так как желающих очень много (тысячи), а мест мало, то ваше резюме должны сначала выбрать из большой кучи таких же. Для этого оно должно чем-то заинтересовать рекрутеров, но это отдельная большая тема, и в этом посте я ее рассматривать не буду. У меня есть подозрения, что если резюме подается через знакомого, то оно считается уже отобранным (по крайней мере, в Google так).
- Почтовый скрининг. Рекрутер свяжется по электронной почте и задаст, как минимум, несколько вопросов, касающихся профессионального опыта. Некоторые кандидаты пишут, что им также предлагалось решить несложную задачу (реальный пример: реализовать класс односвязного списка, в котором есть операция "получить N-ый с конца элемент", и тесты для него). В силу оффлайнового характера данного этапа он не заключает в себе никаких особых проблем.
- Телефонный скрининг. Вот тут уже начинается интересное. В заранее согласованное с рекрутером время раздается звонок, и некий человек с другой стороны планеты имеет с вами получасовую беседу. Насколько я понял из своего скрининга, у собеседующего есть некий список вопросов, которые предполагается задать кандидату, но он может задавать и любые другие вопросы и задачи. Полчаса - это очень немного, поэтому после нескольких теоретических вопросов времени на практику почти не остается. Теоретически могут попросить написать код в онлайн-редакторе, но в моем случае собеседующий довольствовался описанием подходов к решению. Целью данного этапа является проверка вашей вменяемости и шанса прохождения очного этапа.
- Очные собеседования. Обычно 3-5 собеседований, одно из которых с HR, а остальные - технические, с представителями команд. Каждое техническое собеседование длится обычно 40-50 минут, из которых несколько минут уходит на общение - рассказ собеседующего о своей команде и проектах, обсуждение вашего опыта работы, вопросы и ответы. Остается совсем немного времени, за которое надо решить хотя бы одну предлагаемую задачу.
Нетехническая подготовка
Решать задачки и учить теорию - это все, безусловно, полезно. Но есть ряд необходимых условий нетехнического характера, некоторые из которых, судя по разочарованным отзывам в интернете в духе "я решил все задачи, а меня не взяли", многими кандидатами игнорируются:
- Думать вслух (по-английски!).
- Демонстрировать внимание к деталям.
- Излучать спокойствие, уверенность и энтузиазм.
- Свободно ориентироваться в своем резюме и своих проектах.
- Иметь под рукой заранее подготовленные вопросы, когда собеседующий спрашивает "Do you have any questions for me?"
- Иметь под рукой заранее подготовленные ответы на типичные HR-вопросы.
- Не начинать отвечать на вопрос или решать задачу, пока не будет полного понимания, что именно требуется.
Размышления вслух, вниманием к деталям и навык "сначала пойми, потом сделай" замечательно прорабатываются во время решения задач, так что тут убиваем четырех зайцев одним выстрелом.
Возьмите задачу, решение которой вам неизвестно. Перед тем, как начинать решать, задайте себе вслух как можно больше вопросов, касающихся этой задачи (ограничения и представление входных данных, необходимость проверки входных данных, обработка ошибок и т. п.), и дайте самому себе ответы на них. Затем решайте задачу. Старайтесь не делать никаких неявных предположений ("здесь нам будет достаточно 32-битного целого"). В ходе решения размышляйте вслух по-английски и записывайте код на бумаге. Ключевой момент здесь - нужно действительно думать вслух, а не пытаться транслировать процесс мышления в слова. В последнем случае вы будете вынуждены работать в многопоточном режиме (в одном потоке думаем, в другом говорим), а это здорово снижает скорость мышления и концентрацию. Если вам тяжело сразу думать по-английски, начните с русского, а потом, когда этот процесс станет для вас естественным, постепенно переходите на использование сначала некоторых английских слов, а потом и полностью на английский. Хорошая новость: при решении задач вам не понадобится сложная грамматика, да и набор слов будет довольно ограничен.
После того, как задача решена, а ответ записан на бумажке, нужно тщательно его проверить, прогнать в уме при разных входных данных, проверить на наличие типичных для вас ошибок (незакрытые скобки, ошибки на 1 при вычислении индексов в массивах, приведения типов, ...). Затем получившуюся программу вбивайте в компьютер с точностью до символа и тестируйте. Почти наверняка что-то не будет работать, поэтому исправляйте ошибки и запоминайте, в чем именно они заключались и почему остались незамеченными.
Стремитесь к тому, чтобы у вас с момента выбора задачи и до завершения записи решения на бумаге проходило не больше 30 минут. На собеседовании обстановка будет сложнее, так что среднее время решения немного увеличится.
Это очень важное, практически ключевое упражнение, поскольку именно так вы будете решать задачи во время собеседования. Чем больше задач вы так решите, тем лучше. Конечно, это занимает уйму времени (поначалу у меня на каждую задачу легко уходило по 1.5 часа), поэтому можно часть задач решать по полной программе, а часть - только до момента "знаю, как надо решать".
Идем дальше. Спокойствие на собеседовании очень важно. Когда трясешься и обливаешься потом, тяжело думать о циклах в связных списках. Способ, который помог мне - перенервничать до собеседования. Я почитал все описания собеседований, какие нашел в блогах, и ставил себя на место кандидатов. Пытался имитировать свои ощущения, когда мне отказывают через 10 минут после начала собеседования и обзывают нехорошими словами за непроходимую тупость. Под конец мне это все стало сниться, и я перестал себя терзать. Но требуемый эффект был достигнут: я жутко нервничал до собеседования, но на самом собеседовании был спокоен, как удав.
Еще говорят, что когда пройдешь несколько собеседований, этот процесс становится рутиной и перестает вызывать какие-либо эмоции. Сам я собирался сходить на одно, но не успел, поэтому ничего не могу сказать.
Уверенность в себе и энтузиазм существенно натренировать в короткие сроки, увы, не удастся. Или они уже есть, или нет. В некотором смысле способствует уверенности в себе техническая подготовленность, доскональное знание всего, что приведено в резюме, и готовность обсуждать любой из своих проектов вплоть до мельчайших деталей реализации, возникших проблем и способов их преодоления, взаимодействия с коллегами и т. д. Возьмите список своих проектов и напишите для каждого описание на одну страничку, стараясь придерживаться позитивного тона. Описания одного-двух проектов имеет смысл выучить наизусть - вам почти наверняка скажут "Расскажите что-нибудь о своем последнем проекте". И собеседующий предполагает, что "что-нибудь" будет связным рассказом на 1-2 минуты.
Ответы на т. н. behavioral questions нужно подготовить заранее. Я себе выписал ответы на следующие вопросы, и вам рекомендую сделать то же.
- Расскажите о себе.
- Почему вы хотите работать в MS?
- Расскажите о ситуации, когда вы застряли на какой-то проблеме. Как вы ее решили?
- Почему вы собираетесь менять работу? Что в вашей нынешней работе вам нравится и не нравится?
- Каково ваше самое важное достижение?
- Кем вы видите себя через 3-5 лет?
- Каковы ваши сильные и слабые стороны?
- Каков был ваш самый большой challenge?
- Какой продукт MS вам нравится (не нравится) больше всего?
- Что бы вы изменили в одном из продуктов MS?
- Вы когда-нибудь пропускали дедлайн? Почему?
Вопросы к собеседующему - тоже важная штука, но очень простая. Если вам предлагает задать вопросы разработчик, поспрашивайте его о его команде и проекте: на каких языках пишут, как контролируется качество, как организован процесс, какова свобода принятия решений разработчиками и т. д. Это ведь и правда интересно, да? Если нужно задать вопрос HRу, то можно поспрашивать о том, как в случае успеха организуется переезд, сколько лет в среднем работают в MS, какие карьерные перспективы - да что угодно. Я HRа спрашивал о погоде в Сиэтле, от которой мы плавно перешли к обсуждению погоды в Москве, а потом и к зимним видам спорта. Так бы и болтали, если бы время не кончилось.
В качестве дополнительной тренировки многие также рекомендуют организовать себе mock interviews, то есть попросить друзей сыграть для вас роль собеседующих. Хотя сам я такое не делал, но наслышан об эффективности этой процедуры.
Еще одна важная вещь: нужно понимать, что собеседование - процесс субьективный. Человек, который вас собеседует, задает себе вопрос: "Хотел бы я с этим парнем вместе работать?". Поэтому показать нужно не только то, что вы мегамозг, умеете решать задачки и отвечать на вопросы, но и что вы просто хороший человек.
Теоретическая подготовка
Я для себя сформулировал следующий теоретический минимум (пункты приведены в произвольном порядке).
- Сортировка: insertion sort, quick sort, heap sort и merge sort должны отскакивать от зубов. Bucket sort, counting sort, radix sort. Сортировка односвязного списка с помощью merge sort.
- Двоичные деревья поиска: поиск, вставка, удаление, разные виды обходов, вращение. Сбалансированные деревья: red-black tree, splay tree, B-tree.
- Двоичные кучи.
- Хэш-таблицы: подходы к реализации, требования к хэш-функции. Преимущества и недостатки по сравнению со сбалансированными деревьями.
- Динамическое программирование: сама концепция и типичные представители - расстояние между строками, нахождение подмассива с наибольше суммой и т. д.
- Графы: BFS и DFS, нахождение MST, топологическая сортировка, определение связности и нахождение связных компонент, кратчайшие пути (Dijkstra, A*).
- Жадные алгоритмы: сама концепция и типичные представители - Prim, Kruskal, EDF scheduling.
- Tries.
- Суффиксные массивы и их типичные применения.
- Экзотические деревья: kd tree, interval tree, quad tree.
- Пространственные алгоритмы: выпуклая оболочка, нахождение точки, ближайшей к заданной, поиск точек, попадающих в диапазон, поиск пересечений отрезков.
- Комбинаторные алгоритмы: получение следующей перестановки, выбор всех подмножеств заданного размера.
- Теория вероятностей: основы и типовые задачи. Вероятностные алгоритмы: случайная выборка (в том числе из потока), перемешивание.
- Поиск подстроки в строке: KMP, Rabin-Karp, остальные по желанию.
- NP-complete. Знать, что это. Знать классические задачи.
- Многопоточность: deadlock и способы его обнаружения/предотвращения, livelock, starvation, примитивы синхронизации, классические задачи (читатели-писатели, производители-потребители, обедающие философы). Атомарные операции (compare-and-set) и их использование.
- Backtracking: решение судоку, расстановка ферзей.
Практическая подготовка
Хотя MS декларирует, что вы можете использовать на собеседовании любой язык программирования, от вас предполагается знание C, а лучше еще и C++. Нередко встречаются задачи, требующие ручных манипуляций со связными структурами данных (например, перевернуть связный список "на месте" или вставить узел в BST) и работы с битами (например, округлить число до ближайшей сверху степени 2). У программистов на C такие задачи обычно естественным образом отработаны. Поэтому если у вас это вызывает трудности, обратите особое внимание.
Для человека, который не обладает врожденным даром быстрого мышления (я, например, не обладаю), нахождение решения задачи на собеседовании во многом зависит от того, известен ли ему общий подход к решению задач такого класса. Sad but true. На мой взгляд, без соответствующей практики почти невозможно за полчаса решить задачу вроде нахождение минимального расстояния между двумя строками. Поэтому практика решения задач - ключевой элемент подготовки.
Я уже писал раньше, что задачи лучше решать "как на собеседовании", с мыслями вслух и кодом на бумажке. Но если при чтении условия задачи решение кажется очевидным, то такую задачу можно с чистой совестью пропустить.
Ниже я привожу подборку, на которой практиковался я. Они более-менее покрывают основные виды предлагаемых задач. Замечу, что в этот список не вошли задачи, которые я где-то увидел и сразу понял, как решать. Поэтому всегда невредно будет заглянуть на сайты с задачами вроде Careercup.
- Крестики-нолики на квадратном поле произвольного размера. Нужно написать функцию, которая делает ход за очередного игрока и проверяет, заканчивается ли игра на этом ходу. Конец игры - когда игрок заполнил строку/столбец или одну из двух диагоналей. Требуется сложность O(1).
- Реализовать malloc/free, которые выделяют память с заданным выравниванием. В решении можно использовать обычные malloc/free.
- Реализовать malloc/free в пределах 64КБ-массива.
- Реализовать циклический сдвиг массива на заданную величину.
- Определить, является ли один массив результатом циклического сдвига второго массива.
- Определить величину сдвига отсортированного массива.
- Перевернуть стек. Доступны операции pop, push, top, is_empty. Использовать только O(1) явно выделяемой памяти, но можно использовать рекурсию.
- Выбрать K наибольших элементов из входного потока чисел.
- Определить медиану массива чисел. Массив размером 10ГБ, доступно памяти 2ГБ.
- Найти подпоследовательность с максимальной суммой (или произведением).
- Найти непрерывную подпоследовательность с максимальной суммой (или произведением).
- Найти подпоследовательность с суммой, максимально близкой к 0.
- Определить, есть ли у двух односвязных списков общая часть.
- Дан массив чисел. На вход подаются пары (a, b). Для каждой пары нужно вывести все числа массива, находящиеся между a и b, как можно более эффективным образом. Допускается предварительная обработка.
- В комнате N людей, один из которых знаменитость. Знаменитость характерна тем, что она никого не знает, но ее знают все. У нас есть матрица NxN. Элемент n(i,j) равен 1, если человек i знает человека j, и равен 0 в противном случае. Нужно за линейное время найти знаменитость или показать, что ее в комнате нет.
- Определить, что одна последовательность символов получена из другой путем некоторой перестановки символов. Пробелы и знаки препинания игнорировать.
- Найти N-ый наименьший элемент в массиве.
- Найти общие элементы двух массивов. Повторы не выводить.
- Реализовать quick sort.
- Реализовать merge sort.
- Реализовать двоичную кучу.
- Используя функцию compare-and-set (а-ля InterlockedCompareExchange), реализовать мьютекс.
- Реализовать очередь с синхронизированным доступом.
- Дано несколько потоков. Сделать так, чтобы они выполнялись в определенном порядке: поток 2 выполняется после завершения потока 1, поток 3 - после завершения потока 2, и т. д.
- Решить проблему читателей и писателей: есть область памяти, разделяемая несколькими потоками. Бывают потоки-читатели и потоки-писатели. К памяти может обращаться одновременно несколько читателей, но только один писатель. Читатели и писатели не могут обращаться к памяти одновременно.
- Проверить правильность скобочного выражения.
- Найти минимальное расстояние между двумя заданными символами в заданной строке.
- Инвертировать строку символов UTF-8.
- Изменить порядок слов в строке на противоположный.
- Реализовать сопоставление с образцом: дана строка и образец. Образец может включать специальные символы: '?' означает "любой символ", '*' означает "любое количество любых символов". Определить, соответствует ли строка образцу.
- Отсортировать петабайт чисел.
- Есть много текстовых файлов. Пользователь вводит несколько слов. Нужно найти все файлы, каждый из которых содержит все введенные слова в любом порядке. Разработать необходимые структуры данных.
- Реализовать слияние отсортированных массивов.
- Реализовать слияние отсортированных односвязных списков.
- Даны два различных обхода BST. Построить третий.
- Переставить числа в массиве так, чтобы если их вывести подряд без пробелов, получилось бы наибольшее число.
- Два ровера высаживаются на одномерную планету на парашютах, которые остаются на месте посадки. Роверу доступны команды "влево", "вправо", "ничего не делать", "перейти на метку, если стою на парашюте". Написать программу поведения роверов, позволяющую им встретиться.
- Поменять местами биты на четных местах с битами на нечетных в 32-битном беззнаковом целом. 0-й бит меняется местами с 1-ым, 2-й с 3-им, и т. д.
- Подсчитать количество единичных битов в 32-битном беззнаковом целом.
- Поменять местами элементы на четных местах с элементами на нечетных местах в односвязном списке.
- Получить имя K-го столбца в Excel.
- Обход дерева "змейкой": по уровням сверху вниз, уровни обходятся то слева направо, то справа налево.
- Найти K-ый по величине элемент матрицы, в которой каждый столбец и каждая строка отсортированы по возрастанию.
- Найти заданное число в матрице, в которой каждый столбец и каждая строка отсортированы по возрастанию.
- Найти ближайшего общего предка двух узлов в BST.
- Найти в BST максимальный элемент на каждом уровне.
- Найти все общие элементы двух BST.
- Односвязный список содержит цикл. Найти узел, в котором начинается цикл, и размер цикла.
- В файле 4 млрд 32-битных беззнаковых чисел, каждое повторяется не более 1 раза. Найти все числа, отсутствующие в файле.
- Даны длины сторон треугольника. Определить его вид: обычный, равнобедренный, равносторонний или невозможный.
- Найти максимальную общую подстроку двух строк.
- Есть поток целых чисел. Более 50% последовательности составляет одно и то же число. Найти его с O(1) памяти.
- В BST найти элемент, следующий по порядку за заданным.
- Реализовать хэш-таблицу строк.
- Реализовать очередь, имея два стека.
- Реализовать стек, имея две очереди.
- Задан набор слов. Вывести все поднаборы, в каждом из которых все слова являются анаграммами друг друга.
- Найти первый символ строки, который не повторяется в ней два или более раз.
- Дан массив чисел. Найти в нем все тройки чисел a, b, c такие, что a^2 + b^2 = c^2. За время меньше O(N^2).
- Найти длиннейшую возрастающую подпоследовательность (не обязательно непрерывную).
- Получить все перестановки заданного массива.
- Есть генератор случайных чисел, с равной вероятностью выдающий числа от 1 до 5. Реализовать ГСЧ, равновероятно выдающий числа от 1 до 7.
- Перемешать числа в массиве. Все перестановки должны иметь равные вероятности.
- Случайным образом выбрать m чисел из n-элементного массива.
- Имеется набор слов. Даны два слова из этого набора. Нужно преобразовать первое слово во второе. На каждом шаге преобразования можно добавлять, удалять или изменять только одну букву. Каждое промежуточное слово также должно входить в набор.
- Даны два слова. Нужно преобразовать первое слово во второе. На каждом шаге преобразования можно добавлять, удалять или изменять только одну букву. Выполнить преобразование за наименьшее количество шагов.
- Найти подматрицу квадратной матрицы с наибольшей суммой элементов.
- Получить все k-элементные подмножества заданного множества.
- Имея набор достоинств монет, найти минимальное количество монет, требуемых для формирования заданной суммы (extra credit, если быстрое решение).
- В дереве (бинарном/не бинарном) все вершины - белые или черные. Найдите самый длинный полностью белый путь(корень может быть где угодно).
- Найти K-ую порядковую статистику в BST, когда а) у каждого узла есть ссылка на родителя или б) имеется только ссылка на корень дерева.
- Найти медиану в двух отсортированных массивов (одинакового/разного размеров).
- Найти наименьшее положительное число, пропущенное в отсортированном массиве.
- Найти дубликаты в массиве чисел (числа могут быть только от 0 до n-1).
- В отсортированном массиве все элементы имеют пары, за исключением одного. Найти его.
- Развернуть слова в строке (первое слово становится последним и т. д., сами слова сохраняются).
- Реализовать сопоставление с образцом: дан массив слов и образец. Образец может включать специальные символы: '?' означает "любой символ", '*' означает "любое количество любых символов". Определить, соответствует ли какое-либо слово образцу.
- Распечатайте массив NxM по спирали.
- Напишите алгоритм, проверяющий, является ли дерево сбалансированным (разница высот любых 2-х поддеревьев узла отличается не более чем на 1).
- Отсортировать массив, сдвигая дубликаты в конец массива.
- Напишите реализацию функции IndexOf.
- Составьте все правильные скобочные выражения заданной длины (длина 4: "(())" и "()()").
- Написать программу определения количества шестизначных 'счастливых' билетов, у которых сумма первых 3 десятичных цифр равна сумме 3 последних десятичных цифр.
- У покупателя есть n монет достоинством H(1),..., H(n). У продавца есть m монет достоинством B(1),...,B(m). Может ли купить покупатель вещь стоимости S так, чтобы у продавца нашлась точная сдача (если она необходима).
- Разделить не отсортированный массив на 2, сумма элементов которых будет самой близкой.
- Распечатайте последние N строчек текстового файла.
- Передвинуть все нули в начало массива, не нарушая порядок следования ненулевых чисел (О(n)).
- Найти самый длинный палиндром в строке (за время О(n) с использованием памяти O(n)).
- Клонировать дерево, у которого слиплись некоторые подкорни в правильное дерево (на картинке нагляднее: http://outcoldman.com/Library/2011/03/17/image_0168E3A9.png).
- Дано n. Выведите числа от 0 до 2^n-1 (включительно) так, чтобы двоичное представление соседних чисел отличалось ровно на 1 бит.
Заключение
Отмечу еще раз, что все вышесказанное является планом моей личной подготовки к собеседованию. Так как собеседование прошло удачно, я предположил, что план может быть небесполезным. Однако учитывайте, что я в вопросах собеседований абсолютно не авторитет, и может оказаться и так, что все это никуда не годится, а на собеседовании мне просто повезло. К тому же, у всех людей подготовка разная, и то, что окажется эффективно для одного, будет бесполезно для другого. И уж конечно не нужно считать следование этому плану гарантией успеха. Собеседующие будут изо всех сил стараться понять, кто вы есть на самом деле, а не насколько давно вы читали книжку по алгоритмам и решали задачи.
Также, возможно, вам поможет список некоторых ресурсов, которыми я пользовался при подготовке:
- 12 Interesting C Interview Questions and Answers
- Collection Of Puzzles For Programmers
- Get that job at Facebook
- How to Rock a Developer Phone Interview
- How to Rock an Algorithms Interview
- My Career Stack
- Get that job at Google
- Interview Programming Problems Done Right
- Скромное руководство по прохождению интервью: часть 1, часть 2
- Телефонное собеседование с гуглом онсайт собеседование с гуглом, часть первая, часть вторая, часть третья
- Задачи, загадки, логические игры - Игры разума
- Как устроиться на работу в Microsoft. Part 1, Part 2, Part 2.5
- 140 Google Interview Questions
- Microsoft Jobs Blog
- Careercup
- Собеседование в Microsoft. Как готовиться? (RSDN)
- Прохождение интервью в Microsoft. Часть 1, Часть 2
- Как я проходил собеседование в Microsoft
- Cracking the Coding Interview (Laakmann)
- Programming Interviews Exposed (Mongan et al)
- Introduction to Algorithms (Cormen et al)
- Algorithms (Sedgewick, Wayne)
- The Algorithm Design Manual (Skiena)
- Writing Solid Code (Maguire)
- How Would You Move Mount Fuji? (Poundstone)
- Algorithms For Interviews (Azis, Prakash)
- Programming Pearls (Bentley)
Удачи!