Denis Gladkikh

outcoldman

My personal blog about software development

  • 18 Mar 2011
  • outcoldman, Microsoft, Interview, USA
  • 0 comments

Продолжу свой героический рассказ о том, как я проходил собеседования в компанию Microsoft. В прошлый раз я рассказал, как я на это вообще попал, а так же как я прошел первые этапы: ответы письменно на вопросы, а так же телефонное интервью. Часть 1 можно найти тут Прохождение интервью в Microsoft. Часть 1.

Этап 4. Назначение собеседований.

Я вас еще не утомил? В общем, как Боб2 мне и обещал, мне позвонил Боб3, но позвонил он в пятницу в час ночи, когда я сидел и попивал пивко с друзьями, телефонный звонок я, конечно же, просто пропустил, а потом мучился до понедельника моего вечера (московского времени), чтобы позвонить по номеру (звонил я конечно же по skype), по которому я получил звонок, спросить кто это был. Там меня встретил голос Боба3, который говорил очень быстро, и я его просто не понимал, единственное, что я понял, это то, что телефонное интервью я прошел, и что он мне пришлет email c дальнейшими указаниями.

Бобу2 я говорил, что буду в Сиэтле в начале марта (моя первая поездка в США была, есть немного фотографий) на MVP Summit, и что, в принципе, если нужно будет провести дальше интервью (такой вот я самоуверенный был), то мы могли бы договориться на какой-то день. В общем, Боб3 про это уже знал и мне намекнул, чтобы я предложил какой-нибудь день, который я бы мог использовать для собеседований. Я оценил сразу же, что вряд ли можно выбрать выходной, так как ребята, кто будет меня собеседовать, это обычные разработчики, с которыми мне предстоит работать в будущем, и не очень-то хорошо сразу же вызывать у них такие нехорошие чувства, вызвав на работу в выходной день. Конечно, все могут пойти на уступки, но это не мой случай был. Не знаю, оплачивают ли поездку из России в штаты для прохождения интервью, ибо мне не пришлось их просить об этом, так как билет у меня уже был на руках, и в планах уже была поездка в Редмонд. Есть рассказ, про то Как меня не взяли работать в Microsoft, и там рекрутеры приезжали в Москву, интересно, кто в этом случае собеседовал, обычные разработчики или кто (ссылку на эту историю любезно предоставил dmodeus). Боб3 меня попросил еще раз прислать ему самую свежую копию резюме, а так же заполнить еще один онлайн документ, на который он дал ссылку, который очень был похож на резюме. Автоматизация в прогрессе, и многие поля уже были заполнены, видимо, как-то автоматически распарсив мое резюме.

В общем, заранее мы выбрали день собеседования (это с их стороны согласовывалось с людьми, у которых я собеседовался), Боб3 сказал мне, когда будет само собеседование, точнее первое и второе. Так совпало, что собеседование было в соседнем здании с тем, где у меня были сессии MVP саммита. Но я и не переживал, так как между зданиями Microsoft ходят шаттлы (машины, автобусы), поэтому, если мне нужно было бы, я могу бы бесплатно себе заказать машину до определенного здания, об этом я заранее уточнил и Боба3.

Перед самим собеседованием (за пару дней) были небольшие поправки в плане первого собеседования, просто его сделали собеседованием по телефону. Это только сейчас я понял (когда просматривал письма), что первый человек, с которым я общался (первое интервью в Редмонде), был тот самый Боб1.

Этап 5. Технические собеседования.

Первое что спрашивается, а что нужно делать, собственно, перед собеседованием? Насколько мне известно, как мне сказали, многие готовятся, читают книги, вспоминает алгоритмы. Не буду лукавить, я тоже решил освежить немного свои воспоминания относительно алгоритмов и структур. Сначала попытался начать со всем известной книги Introduction to Algorithms, хватило меня, правда, только на первую главу, все не было времени, да и особого желания (я до сих пор собираюсь ее осилить, третью редакцию, так как считаю, что после университета достаточно много всего выветрилось). Мне знакомые, кто уже работает в Редмонде, посоветовали другую книгу Cracking the Coding Interview. Времени было не много на покупку ее с amazon, потому я честно признаюсь, что ее где-то дернул в pdf (можете не просить, не дам), раскаиваюсь перед издательством, обещаю ее купить, если будет возможность. Но вот тут опять мне не хватило усердия, книга построена так, что сначала на 100 страниц идут вопросы, потом идут ответы. В общем-то, вопросы я прочитал почти все, а вот ходить смотреть ответы опять не было времени, да еще и разбираться в них. Тем более писать, по рекомендации книги, код на листочке у меня совсем не было времени и желания. Более того, пробегаясь по вопросам, не скажу, что там были такие вопросы, которые я бы не смог решить за час (я говорю о тех первых вопросах, которые я прочитал и понял суть).  По крайней мере, последняя книга мне напомнила о том, какие методы сортировки бывают – уже хорошо.

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

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

Первое интервью

Так получилось, что первое интервью у меня было по телефону с Бобом1 (это я сейчас понял, что это был он). Я думал и ожидал, что это будет так же техническое интервью, потому у девушки, которая проводила меня в офис, где я должен был пройти телефонное интервью, я попросил бумагу с ручкой, но как оказалось зря. Боб1 просто мне пожелал удачи, спросил как самочувствие и рассказал как будет проходить интервью. Я пошел дальше слушать MVP сессии на полчаса. Вообще, Боб1 отлично меня настроил на позитив. Я на этот момент до сих пор находился с идеей того, что не заманит меня эта корпорация зла, а тут я чисто ради того, чтобы получить интересный опыт в плане прохождения интервью. С этой мыслей проходил почти все собеседования. Я так и сказал Бобу1, что я не расстроюсь, если не пройду, я это просто оцениваю как интересный challenge.

Второе интервью

Практически каждое собеседования начинается со знакомства, и мне сначала представляются и рассказывают, кто они в этой компании. Все, с кем я собеседовался, работники MSFT с большим стажем, у всех много опыта, и я понимал, что в любой момент, если нужно будет, они смогут меня прихлопнуть на сложных вопросах. Практически всегда мне давали время на то, чтобы задать свои вопросы, часто у нас было немного времени пообсуждать отдаленные темы. Вообще, люди, кто собеседует, оценивают вас с разных сторон, поэтому им очень нравится, если вы сами идете на разговор, и сами готовы что-то поведать.  Теперь каждый человек, с которым я знакомился будет БобN.

В общем, мы хорошо поболтали с БобN, дальше он меня попросил обратить внимание на доску (у всех сотрудников свои кабинеты, как я понял во всех есть доска, где можно почертить), где уже была обозначена задача, которую мне нужно было решить:

image

На входе у нас, примерно, следующее:

Node Copy(Node node) 
{
 
}

Сначала, я просто, чтобы было ясно, написал на доске структуру, которую я ожидаю от Node:

class Node
{    object Value { get; set; }
 
    Node Left { get; set; }
 
    Node Right { get; set; }
}

Я так же намекнул, что я просто выбрал object, как тип для Value, как один из вариантов. Всегда можно подставить generic тип, либо другой тип, но тут я просто для экономии места и времени выбрал тип object. БобN был согласен.

Наверное, из-за того что сказывались смены временных зон, я начал задавать крайне тупые вопросы. Я видел в поставленной задаче только то, что мы должны разделить узел D на два. И я спросил, а в метод же мы должны как-то подставлять, какой узел мы хотим так разделить. На себе я ощутил взгляд, непонимающий моего вопроса, и я понял, что нужно взглянуть на задачу еще раз. Ну конечно! Все очень просто, нужно просто сделать нормальное дерево из проблемного (я не знаю терминологии, я говорил? что алгоритмы у меня вылетели из головы), чтобы у каждого узла был только один родитель. Тогда я задал еще вопрос – в новом дереве все узлы должны быть копиями или мы можем (или должны) использовать то, что у нас уже есть (существующие узлы). БобN сказал, что это хороший вопрос, и для начала пускай все будет копиями. Приступая писать код, я сразу же сказал, что буду использовать C# (я всегда на этом акцентировал внимание, во время всех собеседований, что C++ я помню намного хуже). БобN был не против, и даже за. Я приступил писать код, ошибался, поправлялся, все сопровождал своими комментариями (устными и без мата). На доске писал переменные с именами “p”, а вслух говорил, что это переменная имеет имя “parentNode”, намекаю просто, что экономлю место и время. В один из моментов мне пришло в голову, что будет, если дерево будет замкнуто (например, F ссылаться на A), задал вопрос, стоит ли мне это проверить, БобN сказал, что нет, и что мы предполагаем, что была уже до нас проверка на это. После написания кода, я начал прогонять тест, устно выполняя код, уже не помню, может, нашел пару ошибок, может что-то поправил. Не забыл про исключительные ситуации, вроде, мне передают в метод node, равную null, в этом случае я просто принял решения возвращать null.

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

Третье интервью

В холле предыдущий БобN познакомил меня со следующим БобN. Новый БобN предложил мне кинуть шмотки к нему в кабинет и спросил готов ли я пообедать? Ха, зачем спрашивать, в штатах хорошо кормят, я бы каждое собеседование провел бы за тарелкой чего-нибудь вкусного. В общем, мы пошли до столовой, БобN спросил дали ли мне какой-нибудь купон на еду (а мне не дали, думаю, что может быть забыли), и сказал, что не проблема, раньше просто давали, но он заплатит. Я, правда, сделал хитрее, нашел Pete Brown, ведь в данный момент совсем рядом проходили сессии для MVP по WPF/SL, а я точно знал, что MVP должны есть и их должны кормить, и он мне дал карточку на $10 (не поверите, но я поел на $6). Считайте решил небольшую задачку, как не потратить личные деньги БобаN. БобN мне рассказал, что в столовой есть около 5 разных кухней (черт, так это пишется правильно? upd: Александр говорит что не так, а правильно Кухонь), какую я предпочитаю? Ну, русской кухни там, конечно же, не было, поэтому я попросил его порекомендовать мне что-нибудь, и типа я возьму то же что и он, ибо я понятие не имею, чем тут кормят. Кстати, напитки в офисах Microsoft, думаю как и везде, бесплатны, поэтому платим только за еду. В общем, за едой в основном спрашивал я, БобN был не очень разговорчивым, точнее он с интересом отвечал на вопросы, но мало чего спрашивал. Оказалось, что он отец 3х детей, в Microsoft после колледжа работает более 10 лет, имеет супер-пупер-мега-архитектор-программист должность и борется за то, чтобы его не сделали лидом. Я как раз подумал, что это хорошо, что с ним меня отправили просто пообедать, ибо задачку бы он, наверное, задал не из простых (настоящий гик же). Но радовался я не долго, мы доели и БобN мне сказал, ну классно поели, пойдем ко мне в офис, решим еще одну задачку и я тебя отправлю дальше.  Я понял, что я попал.

Задача была следующая, нужно на примитивных функциях, поддерживаемых многопоточную конкуренцию, написать класс, при помощи которого можно реализовать OneWriterManyReader класс (что-то вроде ReaderWriterLockSlim). Я долго вникал в задачу, конечно же, пытался понять, что же это за примитивные функции, методы Mutex что ли или нечто другое. И тут мне ударила выпитая за день кока-кола, и я предложил прогуляться до restroom. Кстати, это было во время, небольшой перерыв не помешал.

Итак, вернулись к задаче, я попросил БобаN написать на доске эти примитивные функции (c/c++ программисты, наверное, усмехаются), он изобразил, примерно, следующие три функции:

1. int ConcurentIncrement(ref int val)
2. int ConcurentDecrement(ref int val)
3. int TrySetConcurentValue(ref int value, int setValue, int comparedValue)

Может кто-нибудь сможет в комментариях привести документацию, ссылку на MSDN, где про них можно прочитать (upd: в комментариях привел osmirnov ссылку на класс Interlocked, явно методы оттуда). А я попробую на пальцах объяснить. Первая функция добавляет единицу в val, а возвращает предыдущее значение, то есть если один поток выполняет эту функцию в данный момент, то если val = 0, то установится 1, а вернется 0. Если два потока выполняют эту функцию, то если val=0, то в обоих потоках на выходе будем иметь val=2, а вот вернут функции разные значения, для одного потока 1, а для другого 0. Соответственно, вторая функция работает так же как первая, только вычитает единицу. А вот третья выставляет новое значение setValue переменной value, только в случае, если value = comparedValue, ну и возвращает предыдущее значение. Сначала, я опять же для ясности накидал сигнатуру этого класса

class OneWriterManyReaderLocker
{    public void ReadLock()
    {
    }
     public void ReaderUnlock()
    {
    }
     public void WriterLock()
    {
    }
     public void WriterUnlock()
    {
    }
}

Ну и приступил к решению. Честно, я даже понятия не имел, смогу ли я ее решить. Но медленно и уверенно я шел к решению. Сначала думал использовать два поля с типом int, где одно будет подсчитывать количество читателей (их может быть много), а второе количество писателей (он может быть только один). Пытался реализовать, и понял, что тогда с примитивными функциями я не смогу решить эту задачу. Потом до меня дошло использовать всего одно поле, где положительные значения – это залочено читателями, причем, там их количество, 0 – это никто не лочил, а –1 – это залочено писателем. Приступил к решению задачи, ожидания читателей и писателей я решил реализовывать при помощи while. Под конец, когда я мучился с реализацией ReaderUnlock, БобN спросил, нужна ли мне подсказка, но я отказался, в общем-то, задачу я до конца так и не решил (осталось, наверное, минут 5), но БобN сказал, что увидел, что в итоге я смогу ее решить, просто по этапам моего развития было это видно, что я бы закончил и последний метод. 

В общем, по старой схеме, меня в холл на диванчик, БобN пошел за новым Бобом.

Четвертое интервью

С новым БобN мы пообщались на тему того, вижу ли я какие-нибудь улучшения для их продукта, а у меня была одна мысля, я ее и поведал. Не знаю, хороша она была или нет, но мы пообсуждали немного ее. Да, практически все спрашивали меня о том, как у нас происходит общение в команде, особенно с учетом того, что я работаю удаленно. В общем-то, они просто, как я понял, хотели понять, знаю ли я про Agile, Scrum, спецификации, тестирование и т.п. Простые и логичные вещи, как выпускают ПО.

Дальше опять задача. Я, кстати, утомился это писать уже, как тогда я так же утомился решать задачи. Считайте, время было уже между 15 и 16, а я лазил по собеседованиям с 11 часов (напомню, что первое было по телефону). В общем, тут задача была крайне простая – нужно было перевернуть стек. Понятное дело возвращать нужно тот же самый стек, а то задача была бы крайне простая, но я на всякий случай уточнил, и посмеялся, что задачка-то очень простая будет.

Кстати, я даже был рад, что не знал и никогда не решал подобные задачи, так как там я демонстрировал именно то, что я могу решить их сам, а не вспоминать то, как где-то находил решения. Кстати, только теперь я понял смысл вопроса “Как вы решаете проблемы?”, я всегда давал крайне тупые ответы “Я сначала гуглю, пытаюсь найти там, если нет, то спрошу кого-нибудь, потом может сам что-то попробую.”. Я могу просто поругать тех, кто задавал мне этот вопрос, я реально не понимал, что меня спрашивали. А тут, при решении задач, я продемонстрировал и себе и окружающим, как я решаю проблемы. Разбираю простые случаи, нахожу сначала крайне неудачные решения, и потом шаг за шагом иду к правильному и хорошему решению.

Я спросил у БобаN, что для нас важнее, скорость или размер используемой памяти во время переворачивания стека. БобN был хитрый, он сказал и то, и то. В общем, сначала я на доске пытался рисовать алгоритмы, а только потом приступить к коду. Первый алгоритм был самый ужасный, который можно только придумать, честно даже не помню какой и что я там использовал. Я даже и не помню, как я решил эту задачу, помню только, что я предложил алгоритм обратный к тому, что хотел услышать БобN, работал просто с разных концов, но по трудоемкости был такой же, наверное. В итоге, как только мы пришли к решению, нарисовали алгоритм, БобN попросил меня написать этот код на доске. Было сделано без проблем. Потом БобN попросил немного порефакторить, предложив, что убрать и что подправить – тоже сделал. Голова у меня уже соображала очень плохо.

Опять в холл, встреча с новым БобомN. Но тут меня ждал сюрприз, я услышал “Привет, Денис”. Вот и можете оценить процентное соотношение русских в Microsoft.

Пятое интервью

Я был безумно рад, что с новым БобомN мы говорили по-русски. Голова была уже тугая. В предыдущем собеседовании я уже даже говорил “Ok… And… then will be… пять”, и слышал “What? What?”, а я и не понимал, а чего не понятно, сказал же пять.

БобN спросил опять меня про то, как мы работаем удаленно, как осуществляется координация проекта и т.п. Потом он акцентировал внимание, что на месте первой работы у меня еще написано Project Lead. Я объяснил ситуацию, что тогда на меня возложили ответственность по Code Review, по архитектурным идеям и т.п. БобN спросил меня, давал ли я советы менеджерам, в каком направлении должен идти продукт. Я честно признался, что нет, и что сейчас я считаю, что тогда я был слишком юн для той позиции.

БобN мне поставил следующую задачу: Выбрать из коллекции Person (их количество N) количество T объектов, у которых Age > x, причем N >> T (кто мало помнит математику – это намного больше). Чисто для уточнения, я просто сказал, что это как оператор SQL select top T * from Person where Age > x(upd: еще конечно же тут order by Age, а то как заметил vorrtex задача становится очень простой, с задачей был пример, потому я оттуда это понял).

Начал думать, как можно решить. Опять предлагал сначала самые тупые решения, и сразу же говорил их минусы. Например, можно сначала отсортировать всех person, потом выбрать просто top. Либо пройтись по коллекции T раз, выбирая максимальный Age последовательно. Минусы решений очевидны. Потом я нахожу решение, что просто создаем коллекцию SortedList, специального назначения, которая может хранить не более T объектов, если добавляем T+1 объект, то выкидываем наименьший и добавляем элемент. В общем, просто проходим один раз по всей коллекции persons и добавляем каждый элемент в мной созданный SortedList. Отрефакторили его немного, БобN спросил, что я могу предложить в качестве оптимизации решения (не шибкой оптимизации, так чуть-чуть в коде), нашел так же, правда, искал долго. 

Опять холл… Следующий БобN был женщиной.

Шестое интервью

Было уже около 18 часов. БобN мне сказал, что не будет спрашивать никаких задач и технических вопросов, так как картина более или менее ясна. Все довольны. Пока решение не окончательное, всем нужно обговорить все точно, собрать информацию и потом примут решение. Главный вопрос был, а ты готов к realocation? И знаете, в этот момент я понял, что меня заинтересовала эта возможность. Действительно, это большой шаг вперед, большая возможность. Только тут я понял, куда я попал, и что я прошел. Сказал, что в принципе не вижу проблем, нужно подумать, обговорить с семьей. В общем, дайте мне время. На том и расстались.

Этап 6. После интервью.

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

На следующий день я полетел домой в Россию. Когда ехал из аэропорта домой мне позвонили и сказали, что готовы предоставить мне предложение. А его я уже ждал с недельку.

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

P.S. 0. Если я соглашусь на эту работу, то переезд все равно будет не скоро, где-то ближе к концу года, так что пока со мной не прощайтесь ;)

P.S. 1. Ну и конечно хочется выразить благодарность всем Бобам, я провел время просто здорово, они устроили мне интересный challenge.

Comments