Разбор задач с on-site интервью в Microsoft

9 min readFeb 10, 2019

Этот пост рассказывает о технических деталях моего интервью в Microsoft Ireland, которые, скорее всего, будут интересны только близким к программированию людям.

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

Всего, как я и писал в первой части рассказа, у меня было 4 интервью с 4 разными интервьюерами, по 1 часу каждое.

Два интервью — на реализацию и тестирование

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

Типовая задача:
Дано два отсортированных массива строк A и B. Необходимо “слить” два массива вместе и вернуть один отсортированный массив C

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

Пишем сигнатуру метода и на раннем этапе спрашиваем “я верно понимаю, что от меня ожидается реализация этого интерфейса?”.

string[] Merge(string[] left, string[] right)

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

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

“В начале метода необходимо проверить аргументы, это стандартная практика безопасного (защитного) программирования”

if (left == null)
    throw new ArgumentNullException(nameof(left));if (right == null)
    throw new ArgumentNullException(nameof(right));

“Пишем стандартную реализацию операции слияния с “указателями” за O(n). Создаём массив, в котором будем хранить результат. Мы знаем, что длина результата будет равна сумме длин двух массивов.”

string[] result = new string[left.Length + right.Length];

“Создаём указатели на левый, правый и результирующий массив”

int l = 0, r = 0, i = 0;

“Теперь выполняем процесс слияния, сравниваем и берём значения из левого и правого массива, заполняя результирующий массив”

while (l < left.Length && r < right.Length)
{
    if (left[l].CompareTo(right[r]) <= 0)
    {
        result[i++] = left[l++];
    } else {
        result[i++] = right[r++];
    }
}

“Используем CompareTo вместо оператора сравнения, чтобы была возможность использовать спефицичную культуру, ведь строки сравниваются по-разному в разных языках”

Стоит помнить, что такие компании, как Microsoft, пишут софт, который используется по всему миру, и локализация — очень важный аспект их разработки.

“Когда один из массивов закончился, основной цикл прекращается, и у нас может остаться “хвост” в одном из массивов. Этот “хвост” нужно просто дописать в конец массива. Из двух циклов ниже выполнится только один, потому что один из массивов был пройден в основном цикле, поэтому можно обойтись без дополнительных проверок”

while (l < left.Length)
{
    result[i++] = left[l++];
}while (r < right.Length)
{
    result[i++] = right[r++];
}

“И возвращаем результат”

return result;

Иногда может показаться, что то, что вы озвучиваете — очевидно и понятно из кода, поэтому про это нет смысла говорить. Для наблюдателя это не так, поэтому попрактикуйтесь озвучивать всё, вслух, чётко и громко.

Если вы не знаете это решение за O(n), то ничего страшного — можете просто слить два массива, например с помощью LINQ, отсортировать и вернуть результат:

return left.Concat(right).OrderBy(x => x).ToArray();

Это будет немного хуже по асимптотической сложности — O(N * log(N)), но это тоже правильное решение поставленной задачи.

Еще лучше, если вы в самом начале озвучите наличие нескольких рабочих решений — одно лаконичное с помощью LINQ, а другое производительное с циклом; и дождётесь просьбы интервьюера реализовать одно из них.

После каждой задачи идёт обсуждение тестирования задачи:

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

В большинстве команд Microsoft нет тестировщиков, здесь используется модель combined engineering, то есть в обязанности разработчика входит тестирование собственных решений, а также написание автоматизированных тестов. Здесь считают, что такой подход положительно сказывается на скорости и качестве работы. Именно поэтому умение тестировать свой код и ПО в целом — обязательное и важное условие для разработчиков в Microsoft.

Также в конце интервью могут задаваться вопросы вроде:

Какие типы тестирования вы знаете?
Как можно протестировать работу приложения или сайта?
Как можно протестировать веб-сервис под нагрузкой?

Еще несколько типовых задач:

Найти в массиве подмассив с максимальной суммой элементов
Был ряд натуральных чисел от 1 до N. Какое-то из чисел удалили. Дан неотсортированный массив длины N-1, найти отсутствующее число
Дано дерево. Проверить, является ли оно бинарным деревом поиска

Задачи на реализацию посложнее зачастую дают больший простор для размышлений и вариантов реализации:

Least Recently Used cache — то есть, кэш с ограниченным объемом хранимых значений, где при добавлении записи в заполненный кэш удаляется самый давно используемый или добавленный элемент.
Очевидный подход — это создать класс для элемента кэша с датой добавления, создать Dictionary элементов по ключу, и при необходимости бегать по нему и искать самый старый элемент для удаления.
Хороший способ — это Dictionary элементов по ключу + очередь на двусвязном списке, чтобы искать самый старый элемент и перемещать его в начало (реактивировать) можно было за O(1).
Fuzzy string search — то есть, приблизительный поиск строки. Можно начать с рассказа про расстояние Левенштейна, перейти к более сложным алгоритмам, а можно рассказать о существовании готовых решений, например Elasticsearch.

Третье интервью — на алгоритмы и структуры данных

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

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

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

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

В случае с этой задачей для любого дерева у нас есть три возможных случая:

Этот длиннейший путь лежит полностью в левом поддереве
То есть, ответ на Diameter(node) равен Diameter(node.Left)
Этот длиннейший путь лежит полностью в правом поддереве
То есть, ответ на Diameter(node) равен Diameter(node.Right)
Этот длиннейший путь проходит через корень поддерева
То есть, ответ на Diameter(node) равен Height(node.Left) + Height(node.Right) + 1

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

public int Diameter(Node node)
{
    if (node == null)
        throw new ArgumentNullException(nameof(node));

Нам понадобится рекурсивно вычислять два значения для каждого поддерева (высоту и диаметр), так что создадим вспомогательный рекурсивный метод, а для возврата двух значений используем ValueTuple:

    return DiameterAndHeight(node).diameter;
}public (int diameter, int height) DiameterAndHeight(Node node)
{
    if (node == null)
        return (0, 0);

Естественно, у пустого поддерева и высота, и диаметр — ноль.

Далее, делаем постфиксный обход дерева, считаем высоту и диаметр для левого и правого поддерева. Высота поддерева по логике — это максимум из высоты левого и высоты правого потомка + 1. А диаметр, как уже было описано выше, это максимум из трёх значений: Diameter(node.Left), Diameter(node.Right) и Height(node.Left) + Height(node.Right) + 1.

В итоге получается вот такой вот код:

public int Diameter(Node node)
{
    if (node == null)
        throw new ArgumentNullException(nameof(node));    return DiameterAndHeight(node).diameter;
}private (int diameter, int height) DiameterAndHeight(Node node)
{
    if (node == null)
        return (0, 0);    var left = DiameterAndHeight(node.Left);
    var right = DiameterAndHeight(node.Right);    int diameter = Math.Max(left.height + right.height + 1, Math.Max(left.diameter, right.diameter));
    int height = Math.Max(left.height, right.height) + 1;    return (diameter, height);
}

Решение также необходимо будет защитить: корректность, эффективность, пограничные случаи, тестирование и так далее.

Четвёртое интервью — на архитектуру

На этом интервью писать код, скорее всего, не придётся.
Я весь час просто говорил с интервьюером.

System design — очень важная часть разработки программного обеспечения. Умение создать правильную архитектуру целого проекта ожидается намного больше от кандидатов на позиции Senior и выше. Если же вы собеседуетесь на позицию Junior или Middle, то главным объектом исследования станет ваше умение рассуждать и подстраиваться под меняющиеся требования.

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

Вторую часть интервью я рассуждал на тему “как бы ты спроектировал вот такую систему?”. Интервьюер ставит вопрос и по большей части молчит, слушая ваш монолог и рассуждения, иногда говоря что-то вроде “ну, предположим, что мы выбрали вот такой способ”.

Задача:
Вам необходимо реализовать систему для электронной оплаты проезда в автобусах (наподобие “Онай”, “Тройка”, “LeapCard” и подобные, в зависимости от того где вы живёте) на базе терминалов и NFC-карт.
Задачу придумал я, когда проводил интервью в прошлом, но, вполне вероятно, вы услышите что-то подобное на интервью.

Архитектурное решение 1: что и как будем хранить на карте?
Есть два варианта, к которым кандидат должен прийти сам и озвучить:

оффлайн — терминал не подключен к Интернету, на карте хранится баланс и обновляется терминалом
онлайн — терминал подключен к мобильному интернету, на карте хранится уникальный идентификатор, баланс проверяется и обновляется терминалом на сервере

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

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

Как будем отслеживать транспорт на карте в оффлайн режиме?
Как будем обновлять информацию на терминалах?
Как будем синхронизировать информацию о маршрутах \ водителях?
и так далее…

Если же вы выбираете онлайн, то после недолгого диалога приходите к…

Архитектурное решение 2: как будем обмениваться данными?

Кандидат: например, терминал может постоянно опрашивать сервер, но что делать, если есть районы со слабым покрытием. Стоит ли учитывать этот вариант или таких проблем нет?
Интервьюер: конечно, стоит учитывать. У людей должна быть возможность воспользоваться транспортом в условиях отсутствия Интернет-соединения у терминала
Кандидат: давайте в таком случае записывать все поездки в локальное хранилище, а при появлении Интернета — отправлять на сервер
Интервьюер: то есть, в таком случае я смогу проехать на автобусе при отрицательном балансе, если связи нет?

Какой протокол, формат данных будем использовать для безопасного обмена?
Как реализуем API?
Как будем аутентифицировать терминал?
Как часто будем обмениваться данными?
Стоит ли использовать очереди?
и так далее…

Определившись с общей идеей, вас могут попросить перейти к дизайну системы. В некоторых компаниях system design делает упор на техническую часть и сразу начинается с технических вопросов:
Проектирование схемы: базы данных, сервисы, очереди
Облачный хостинг или on premise?
Микросервисы или монолит?
Service-to-service вызовы или event bus?
Шардирование данных, отказоустойчивость, балансировщики
Мониторинг: логирование, alerts, watchdogs
Развёртывание: CI/CD, кластеры
и так далее…

На этом интервью нет правильных и неправильных ответов, есть только вы, ваше умение размышлять и корректно выражать свои мысли. Чем больше тем вы затронете и проанализируете — тем выше шансы получить положительный ответ.

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

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

Закончилось интервью несколькими открытыми проблемами, которые не очень укладываются и в мою новую архитектуру. Я так понял, что это было моё домашнее задание, чтобы дома я мог поразмышлять на эту тему. Мне повезло, что это интервью было у меня последним, поэтому я уже достаточно бегло и без волнения говорил по-английски.

Эта статья отлично раскрывает все типовые задачи на system design, а также вопросы, которые нужно продумать по каждой задаче:

Ссылки

Добро пожаловать
Оглавление по всем статьям в этом блоге

Разбор задач с on-site интервью в Microsoft

Два интервью — на реализацию и тестирование

Третье интервью — на алгоритмы и структуры данных

Четвёртое интервью — на архитектуру

Top 10 System Design Interview Questions for Software Engineers

Designing Large Scale Distributed Systems has become the standard part of the software engineering interviews…

Ссылки

Written by Yeldar Kurmangaliyev

No responses yet