Когда мы говорим о кодинг-интервью, у многих начинаются флешбеки от разворачивания дерева до домашних заданий на 14 часов.

Я развлекаюсь интервьюингом больше десяти лет, лет пять вёл SRE Interview Club для собратьев по пейджеру и набрал небольшую базу любимых вопросов — которые задаю по сиюминутному желанию, в зависимости от фазы луны: они все работают для любых ситуаций.

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

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

Давайте рассмотрим один из моих любимых вопросов: доставайте свои вайтборды или блокнотики, начинаем кодить на доске!

Задача

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

Грубо говоря, это выглядит вот так:

class Robot:
    def Move(self) -> bool:
        """Moves robot 1 step ahead. Returns True on success, False if hits obstacle."""
        
    def TurnLeft(self):
        """Turns robot in place counter-clockwise 90 degrees."""
    
    def TurnRight(self):
        """Turns robot in place clockwise 90 degrees."""

def DoClean(robot: Robot):
    ...

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

Фаза 0: адаптация задачи

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

Фаза 1: обсуждение проблемы

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

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

• Где именно в комнате расположен робот?
   — Где угодно, мы не управляем пользователем.

• А что такое «комната» — это прямоугольник? Или выпуклый многоугольник? Есть ли препятствия?
   — В общем‑то «что угодно», мы не знаем, где пользователь поставит робота. Препятствия могут быть, мы не контролируем их.

• А препятствия двигаются?
   — Отличный вопрос... для первой версии, решим, что нет, но надо будет подумать обязательно.

• А многоугольник замкнутый? Что, если пользователь оставит дверь квартиры открытой?
   — Если пользователь оставит дверь открытой, то у него будет очень чистый микрорайон.

• То есть ограничения на размер комнаты нет?
   — Мы не хотели бы его ограничивать.

• А что на тему прямоугольности углов?
   — Первая модель прошивки умеет только ходить по прямой и поворачиваться на 90 градусов, чистим как можем исходя из этого.

• А если препятствие на половине шага?
   — Робот отойдёт назад, если наедет на препятствие, и мы получим False.

• Может ли робот застрять и не смочь повернуться на месте?
   — Хороший вопрос... надо будет учесть для следующей версии прошивки.

В принципе, ответов должно хватить для того, чтобы стало понятно, что же надо.

Фаза 2: попытка в MVP

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

Пишется что-то типа:

def Clean(robot: Robot):
    while True:  # потом поправлю
        if not robot.Move():
            robot.TurnRight()

Ой, нет, так не пойдёт же. Наверное, надо сперва дойти до угла, а там уже делать:

def Clean(robot: Robot):
    while robot.Move(): # Идём до стены
        pass
    robot.TurnRight()
    while robot.Move(): # Идём до другой стены
        pass
    robot.TurnRight()
    # Теперь мы в углу, и смотрим вдоль стены

    while True:  # потом поправлю
        while robot.Move():
            pass # Идём до стены напротив
        robot.TurnRight()
        if not robot.Move():
            break # Мы в углу!
        robot.TurnRight()
        while robot.Move():
            pass # Идём до верхней стены
        robot.TurnLeft()
        if not robot.Move():
            break # Мы в углу!
        robot.TurnLeft()
        # Готово, мы опять у верхней стены смотрим вниз

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

Так что где‑то через 10 минут подталкиваем к следующей фазе, если контрпримеров не хватило.

Фаза 3: рекурсия — см.рекурсия

Окей, раз мы не можем stateless — решим проблему иначе. Комната — это прямоугольник N на M. Пусть N и M будут по тысяче. Или по 10 тысяч. Машины мощные, памяти много, что нам, жалко что ли? Нет, конечно. Начинаем с координаты [0,0]. (Пауза 2–3 секунды.) А, нет, начнём с [N/2, M/2]. Будем считать, что «вперёд» для начала — это «смотрим вверх». И просто рекурсивно зальём всё поле: для каждой клетки пробуем сходить вверх, влево, вправо, вниз. Если встретили стену — стоп. Если встретили место, где уже были — стоп. Иначе запоминаем, что уже были, и рекурсивно повторяем. Прекрасное решение, идеально для MVP, гарантирует решение «всё, что доступно, — обработано».

Итак, стремимся к вот такому:

state = set()

def Clean(robot: Robot, x=0, y=0):
    state.add((x,y))
    if (x,y-1) not in state and robot.Up():
        Clean(robot, x, y-1)
    if (x,y+1) not in state and robot.Down():
        Clean(robot, x, y+1)
    if (x-1,y) not in state and robot.Left():
        Clean(robot, x-1, y)
    if (x+1,y) not in state and robot.Right():
        Clean(robot, x+1, y)

Когда кандидат пишет такое, я внутренне радуюсь! Потому что зачастую пишут другое:

def Clean(robot: Robot):
    state = dict()
    while True:
        for range(4):
            if robot.Move():
                ...
            robot.TurnLeft()

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

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

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

Фаза 4: делаем лучше

Редко когда на этом месте хватает времени на большее, чем обсудить, но спросить, какая сложность у алгоритма, обязательно. А потом сделаем намёк: а по памяти? А почему тогда попытка почистить комнату 50×50 роботом вызывает исключение? (Для питона, для других языков подводим немного другим маршрутом к тому же вопросу). В общем да, рекурсия -- это обход в глубину, а глубина прямо пропорциональна числу клеток, а у питона глубина рекурсии по умолчанию всего 1000, так что уже от 32×32 и выше идёт переполнение.

А ещё, можно вспомнить, что препятствия не обязательно занимают всю клетку: возможна просто тонкая стена, когда из [0,0] в [0,1] пройти нельзя, но из [1,1] в [0,1] — можно. Что примечательно: эта проблема проявляется не во всех реализациях, которые обычно порождаются к этому моменту собеседования. Например, решение выше — иммунно к нему.

Можно ещё спросить: а как бы так избавиться от многократного прохода по одному и тому же месту? Батарея не резиновая. Конечно, мы говорили, что оптимизацией займёмся потом, но вдруг что-то можно сделать уже сейчас?

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

Разумеется, первый шаг: переписываем рекурсию в цикл:

def Clean(robot: Robot):
    state = [(0,0)]
    while state:
        x,y = state.pop(0)
        robot.MoveTo(x,y)
        ...

В этот момент соображаем, что нам надо MoveTo, а раз MoveTo, то надо поиск по карте (как ещё добраться?), значит, надо отслеживать не просто карту, но и состояние связей (см. выше про тонкие стенки), добавить поиск ближайшей клетки, в которой ещё не были, и так далее.

Всё это -- очень весело и позволяет занять произвольное оставшееся от интервью время, даже если собеседование не в геймдев (а если в геймдев, то А* должен от зубов отлетать, ни в коем случае не пользоваться библиотеками!).

Фаза 5: закругляемся

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

Поэтому строго по таймауту: прерываем интервью. Таймаут подобран так, чтобы всегда было минут 5 у кандидата на вопросы в отместку.

В случае проведения двойного интервью (кодинг + системный дизайн) — самое время рассказать анекдот про сисадмина.

После чего переходим к system design:

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

Фаза 6: отчет и аналитика

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

Отчёт откладывается на 1–2 дня, после чего перечитывается и анализируется максимально новыми глазами.

Оцениваются:

• Аналитика: о чём спрашивал кандидат вначале, как разрешал противоречия, какие допущения заявлял explicit, что оставлял implicit;

• Архитектура: как структурировался код, в каком порядке конструировалось решение (снизу вверх или сверху вниз);

• Надежность: были ли попытки сделать код тестируемым, пытался ли кандидат вообще тестировать код, строил ли инварианты;

• Читаемость: была ли попытка сделать код читаемым, были ли комментарии, разбивка на функции, именование функций;

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

НЕ оцениваются:

• Отступы, ijkl внутренние переменные, CamelCase vs snake_case vs THIS_IS_THE_BEST_JAVA_VARIABLE_BY_SOME_ONE_WHO_ONLY_HEAR_ABOUT_JAVA_ONE_IN_THEIR_LIFE_BUT_THEY_CANT_STOP_GIGGLE_ABOUT_IT.

• Компилируемость кода.

• Порядок аргументов системных функций.

• Существование системных функций.

• Сортировка импортов.

• Сами импорты.

Другие вопросы

Что ещё можно спросить (вместо обхода матрицы)?

По сути, я спрашиваю что-нибудь из:

• как просуммировать листья произвольного дерева за O(1) по памяти;

• как найти узел в дереве по произвольному условию;

• как сделать LRU-кеш;

• как сделать связный список.

И ни один из этих вопросов не задаётся так, как он есть на самом деле. Всегда в форме не настоящей задачи, но которая могла бы быть и настоящей. Потому что понимание задачи — 80% задачи. Кодинг же — всего лишь вторые 80%...