Педиатр-программист: Как я попал в Майкрософт | "Интервью", часть 5 из 7 (пост 1)⁠⁠

Предыдущие части смотрите в моей ленте
=====
На согласование дня интервью, получение американской визы и подготовку к полёту ушло еще порядка двух с половиной недель. Майкрософт отплачивал мне перелет и проживание, а также прокатную машину в Сиэтле. Мне даже удалось выторговать один дополнительный день, так как мой рейс прилетал слишком поздно, и я не хотел после короткой ночи в гостинице сразу идти на такое важное собеседование.

Поездка не прошла без приключений. Так как у меня не было навигации для США, я скачал на телефон бесплатную навигацию на основе Open Street Maps, но неожиданно выяснилось, что у них нет номеров домов, и я так и не смог найти свою гостиницу: сделав два круга я запарковался на какой-то стройке и там позвонил друзьям, что ждали меня в фойе, чтобы они помогли мне найти въезд в подземный гараж гостиницы, который я каждый раз пропускал, принимая его за служебный въезд.

На следующий день, в воскресенье, я целый день готовился к интервью, повторял наиболее сложные задачи и алгоритмы, а также места, где я часто делал ошибки. Выйдя из номера только для того, чтобы покушать, я опять прокололся: заказав в небольшой вьетнамской забегаловке что-то дешевое за 10 долларов я получил счет на 14, и заплатил ровно 14, ни оставив никаких чаевых, что очень разозлило и огорчило официантку. Ну откуда ж я знал, что в меню была указана kitchen price, без налогов и чего-то еще, и туда еще нужно добавить 15% чаевых? Для меня это и сейчас довольно много, а тогда вообще казалось дикостью.

Вечером в воскресенье у нас была небольшая вечеринка вместе с остальными кандидатами, которых пригласили на собеседование в понедельник. Всего, как оказалось, было около 30 кандидатов, которые собеседовались в два различных департамента: Windows Phone и OSD.

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

Тем не менее, в той папке, что мне дали после вечеринки, с ознакомительными материалами перед собеседованием, стояло OSD. Во время боулинга, что мы играли на вечеринке, я даже и не поинтересовался, что же это за второй такой департамент – о чем сейчас жалел. Поиск в интернете ничего не прояснил, вариант On-Screen Display (экранное меню) меня тоже не очень устраивал.

Сбор был утром в 8:15, я быстро позавтракал и в 7:45 уже был в фойе, ожидая автобус, который должен был повезти нас на интервью. Одновременно я нашел еще пару других ребят, которые должны были проходить собеседование в OSD, которые и просветили меня, что за этой аббревиатурой, означающей Online Services Division, скрывается Бинг и относящаяся к нему инфраструктура. Очевидно, кандидатов распределяли по департаментам совершенно случайно, без учета их резюме. Иначе как объяснить тот факт, что я попал на собеседование в OSD, к которому не имел никакого отношения…

Автобус приехал ровно в 8:25, но ехать оказалось всего около 10 минут (пешком идти, в общем, столько же) – мы поехали не в Редмонд, а в большое здание Бинга в Bellevue, где и должны были проходить собеседования кандидатов из Бинга. Во время поездки нам рассказали о том, как запланирован этот день: у каждого из нас сначала должно было быть 4 интервью по 50 минут, после которых был небольшой обед и лекция про облачные технологии. Затем нам объявляли результаты собеседования и у нас было свободное время для поездки в Сиэтл, чтобы осмотреть его достопримечательности.

Лифт привез нас на 18-й этаж в большой зал, где можно было оставить свою одежку и комфортно сидеть за столами в ожидании интервью. В этот зал с нескольких уровней спускались лестницы, а параллельно им шли горки – видно для сотрудников, которые не признавали лестницы для спуска. Рядом была кухня с чаем и кофе-автоматом, а с окна открывался чудесный вид. Но наслаждаться им мне было суждено не так долго, потому что уже через 5 минут, одним из первых, за мной пришел первый интервьюер и повел меня в свой офис.

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

Задача 1: «Для данного телефонного номера США необходимо выдать все возможные комбинации букв, которыми он может быть записан».

В США, оказывается, на каждом телефонном аппарате есть буквы рядом с цифрами, и многие фирмы даже свои телефоны записывают как 1-800-YOUR-FURNITURE или что-то подобное – очень удобно в рекламных целях и не нужно учить последовательность цифр.

Так как последовательность полученных «слов» была не важна, то для решения можно было использовать любой алгоритм для обхода дерева, поэтому любой алгоритм такого обхода подходил для решения этой задачи. Единственное, что меня смутило в задаче – какой структурой данной воспользоваться для хранения и передачи этого списка слов. В целях простоты синтаксиса я выбрал List, при этом соответствие цифра – буквы у меня хранились в readonly структуре List.

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

Вообще, использование char вместе со string оказалось не очень хорошим решением. С одной стороны, всегда можно было легко получить нужную цифру номера из строки, но это добавляла дополнительные сложности в алгоритм усечения. Но в целом алгоритм работал. В оставшиеся 10 минут интервью мы обсудили возможности его улучшения, и я даже сумел аргументировать наличие метода размером в одну строку тем, что компилятор, скорее всего, при оптимизации кода сделает method inlining.

По итогам первого интервью я был очень доволен собой и уже значительно более спокойно стал ждать второго интервьера.
Второй собеседующий оказался из Канады, и мы сначала несколько минут поговорили по-французски (в моем резюме было указано, что я владею им). Он сразу признался, что он работает в back-end и не знает С# -- моего основного языка – а использует только С++. Он спросил меня, могу ли я для решения задачи использовать С++. Мне хватила ума и осторожности сказать, что я могу попробовать использовать синтаксис этого языка, если нужно. Он согласился и сразу дал следующую задачу:

Задача 2: «Дана матрица n x m, заполненная целыми числами (положительными и отрицательными и нулями). Необходимо обнулить все строки и столбцы матрицы где встречается элемент с нулевым значением.»

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

Это задание показалось мне проще, нежели остальные. Ключевым было слово «вектор бит» (bit vector), которое я произнес достаточно рано и остаток времени ушел на реализацию этого вектора (я не знал, есть ли он в стандартной библиотеке C++, поэтому решил реализовать сам). Также отдельное внимание пришлось уделить работе с памятью, так как для упрощения решения я передавал в метод расчета одномерный массив и размерности матрицы.

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

Третье интервью стало же полным провалом.

(продолжение во втором посте )