Проектирование LeetCode

Постановка задачи

Функциональные требования

Основные требования

1. Пользователи могут видеть список задач.
2. Пользователи могут просматривать задачу и писать решение на нескольких языках.
3. Пользователи могут отправлять свое решение и получать результат прогона по тест-кейсам.
4. Пользователи могут просматривать таблицу лидеров соревнований в реальном времени.

За рамками задачи:

• Аутентификация и профили пользователей
• Платежи
• Аналитика пользователей

В рамках этой задачи, как и в большинстве задач по System Design, мы считаем, что пользователь уже аутентифицирован, а его ID хранится в сессии или auth-токене.

Нефункциональные требования

Основные требования

1. Система должна быть ориентирована на доступность (availability >> consistency).
2. Система должна обеспечивать изоляцию и безопасность при запуске кода пользователей.
3. Результаты решений пользователей должны возвращаться в течение 5 секунд.
4. Система должна масштабироваться, чтобы выдерживать нагрузку от соревнований со 100 000 участников.

За рамками задачи:

• Система должна быть отказоустойчивой
• Система должна обеспечивать безопасные транзакции покупок

Важно отметить, что у LeetCode всего несколько миллионов пользователей и около 4000 задач. По меркам большинства System Design интервью это небольшой масштаб, что сильно влияет на дизайн.

Вот как это могло бы выглядеть на доске:

Подготовка

Планирование подхода

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

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

Проектирование API

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

Чтобы покрыть основные функциональные требования, нам понадобятся следующие сущности:

1. Problem: хранит условие задачи, тест-кейсы и ожидаемый результат.
2. Submission: хранит отправленное пользователем решение и результат прогона по тест-кейсам.
3. Leaderboard: хранит таблицу лидеров соревнований.

API - основной интерфейс, через который пользователи взаимодействуют с системой. Его полезно определить с самого начала, поскольку он направляет high-level дизайн. Обычно нам нужен один эндпоинт на каждое функциональное требование.

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

GET /problems?page=1&limit=100 -> Partial<Problem>[]

Далее нам понадобится еще один GET-эндпоинт для просмотра конкретной задачи. Он принимает ID задачи (который мы получили, когда пользователь выбрал задачу из списка) и возвращает полное описание задачи и заглушку кода на выбранном языке (параметр language).

GET /problems/:id?language={language} -> Problem

Затем нам понадобится POST-эндпоинт для отправки пользовательского решения задачи. Он принимает ID задачи и отправленный пользователем код и возвращает результат выполнения кода по тест-кейсам.

POST /problems/:id/submissions -> Submission
{
  code: string,
  language: string
}

Наконец, нам понадобится GET-эндпоинт для просмотра таблицы лидеров соревнований в режиме реального времени. Он возвращает ранжированный список пользователей на основе их результатов в соревновании.

GET /leaderboard/:competitionId?page=1&limit=100 -> Leaderboard

Высокоуровневый дизайн

Определив наши основные сущности и API, мы можем перейти к high-level дизайну. Здесь мы описываем компоненты системы и их взаимодействие. Мы снова можем просмотреть наши функциональные требования одно за другим и убедиться, что у нас есть набор компонентов или сервисов для их удовлетворения. Во время интервью важно явно проговаривать, как данные перемещаются в системе и где хранится состояние.

1. Пользователи могут просматривать список задач

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

Основные компоненты:

• Основной сервер: принимает запросы и возвращает данные. Сейчас у него один эндпоинт, но мы добавим остальные далее.
• База данных: хранит все задачи. Нам нужно убедиться, что база данных правильно проиндексирована для поддержки разбиения на страницы. Подойдет и SQL, и NoSQL. Мы выбрали NoSQL (например, DynamoDB), потому что сложные запросы не нужны, а тест-кейсы можно вложить в Problem. Для простоты не будем создавать отдельную сущность.

Схема Problem может выглядеть следующим образом:

{
  id: string,
  title: string,
  description: string,
  level: string,
  tags: string[],
  codeStubs: {
    python: string,
    javascript: string,
    typescript: string,
    ...
  },
  testCases: { type: string, input: string, output: string }[]
}

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

2. Пользователи могут просматривать задачу и писать решение на нескольких языках

Чтобы просмотреть задачу, клиент отправляет запрос GET /problems/:id, а сервер извлекает из базы и возвращает ее полное описание и заглушку кода. Мы будем использовать редактор Monaco, чтобы пользователи могли писать код своего решения в браузере.

3. Пользователи могут отправлять свое решение и получать результат прогона по тест‑кейсам

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

Давайте разберем некоторые варианты выполнения кода:

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

Когда пользователь отправляет решение, система делает следующее:

1. Сервер принимает код и ID задачи и передает их в соответствующий контейнер для нужного языка.
2. Изолированный контейнер запускает код и возвращает результат серверу.
3. Сервер сохраняет результат в базу данных и возвращает его клиенту.

4. Пользователи могут просматривать таблицу лидеров соревнований в реальном времени

Сначала определим, что такое соревнование:

• длительность 90 минут
• 10 задач
• до 100 000 участников
• результат - число решенных задач за 90 минут; при равенстве - время решения всех задач (от начала соревнования)

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

В SQL это будет выглядеть так:

SELECT
  user_id,
  COUNT(DISTINCT problem_id) as num_solved_problems
FROM submissions
WHERE
  competition_id = :competition_id AND passed = true
GROUP BY user_id
ORDER BY
  num_solved_problems DESC, ...

В NoSQL (например, DynamoDB) competitionId должен быть ключом партиционирования, по которому мы извлекаем все элементы, а затем группируем и сортируем.

Как только мы получили таблицу лидеров, мы возвращаем ее клиенту для отображения. Чтобы поддерживать актуальность информации, клиент запрашивает таблицу лидеров каждые 5 секунд.

Связываем все вместе:

1. Пользователь запрашивает таблицу лидеров через /leaderboard/:competitionId.
2. Сервер делает запрос к базе данных по успешным решениям для соревнования.
3. Через запрос или в памяти мы строим таблицу лидеров, ранжируя пользователей по числу решенных задач и времени.
4. Возвращаем таблицу лидеров клиенту.
5. Клиент повторяет запрос через 5 секунд, чтобы обновить данные.

Потенциальные погружения в детали

Когда основные функциональные требования выполнены, пришло время углубиться в нефункциональные.

1. Как обеспечить изоляцию и безопасность при запуске кода?

Запуск кода в контейнере - большой шаг к обеспечению безопасности и изоляции. Но есть несколько вещей, которые стоит включить в настройку контейнера для повышения безопасности:

• Файловая система только для чтения: чтобы пользователи не могли выполнять запись в файловую систему, мы можем смонтировать каталог с пользовательским кодом только для чтения и записывать любые выходные данные во временный каталог, который удаляется после завершения.
• Ограничение CPU и памяти: чтобы пользователи не потребляли чрезмерное количество ресурсов, мы можем установить ограничения на CPU и память для контейнера. Если эти ограничения будут превышены, контейнер будет остановлен.
• Таймаут: чтобы пользовательский код не исполнялся бесконечно долго, мы можем использовать таймаут, который принудительно завершает контейнер, если он выполняется дольше заданного времени, например, 5 секунд. Это также поможет нам выполнить требование о возврате результатов отправки в течение 5 секунд.
• Ограничение сети: чтобы пользователи не могли выполнять сетевые запросы, мы можем отключить доступ к сети в контейнере. Работая в экосистеме AWS, мы можем использовать виртуальное частное облако (VPC), Security Groups и NACLs для ограничения всего исходящего и входящего трафика, за исключением предопределенных соединений.
• Ограничение системных вызовов (seccomp): мы не хотим, чтобы пользователи могли совершать системные вызовы, которые могут поставить под угрозу хост-систему. Мы можем использовать seccomp, чтобы ограничить вызовы, которые может выполнять контейнер.

2. Как сделать получение таблицы лидеров эффективнее?

Как мы отмечали в high-level дизайне, текущий подход неэффективен. Рассмотрим несколько вариантов:

3. Как масштабировать систему для соревнований со 100 000 участников?

Основная проблема - всплеск трафика во время соревнования, который может перегрузить контейнеры, выполняющие пользовательский код. 100 000 пользователей - это все еще немного, и наш основной сервер за счет горизонтального масштабирования справится с этой нагрузкой без проблем. Однако, поскольку выполнение кода требует большого количества ресурсов CPU, нам нужно быть осторожными с тем, как мы управляем контейнерами.

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

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

4. Как система будет запускать тест-кейсы?

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

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

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

Например, возьмем задачу Максимальная глубина бинарного дерева. В Go функция принимает указатель на TreeNode:

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func maxDepth(root *TreeNode) int {
 
}

Чтобы запустить этот код, нам понадобится файл с определением TreeNode, который находится в том же каталоге, что и пользовательский код в контейнере. Мы берем стандартизированные сериализованные входные данные для тест-кейса, десериализуем их в объект TreeNode и передаем в пользовательский код. Тест-кейс может выглядеть примерно так:

{
  "id": 1,
  "title": "Максимальная глубина бинарного дерева",
  ...
  "testCases": [
    {
      "type": "tree",
      "input": [3,9,20,null,null,15,7],
      "output": 3
    },
    {
      "type": "tree",
      "input": [1,null,2],
      "output": 2
    }
  ]
}

Здесь мы сериализуем дерево в массив, используя обход в ширину (level-order / BFS). Каждый язык содержит свою версию TreeNode, которая десериализует массив из input в TreeNode для передачи в пользовательский код.

Финальный дизайн

Соберем все вместе. Итоговый дизайн может выглядеть так:

Что ожидается на каждом уровне?

Возникает резонный вопрос: сколько из этого реально ожидается от меня на интервью? Разберем по уровням.

Middle

Ширина vs глубина: от Middle-кандидата чаще ожидается ширина кругозора и знаний (примерно 80% vs 20%). Вы должны собрать понятный высокоуровневый дизайн, закрывающий все функциональные требования, но многие компоненты могут оставаться абстракциями, проработанными на поверхностном уровне.

Проверка базовых знаний: интервьюер будет прощупывать базу, чтобы удостовериться, что вы понимаете, что делает каждый компонент. Например, добавив API Gateway, ожидайте вопросы "что он делает" и "как работает".

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

Задача LeetCode: от Middle-кандидата ожидается четко определенный API и модель данных, а также высокоуровневый дизайн, удовлетворяющий всем функциональным требованиям. Также важно понимать необходимость безопасного изолированного запуска кода.

Senior

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

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

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

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

Задача LeetCode: от Senior-кандидата ожидается, что вы быстро пройдете высокоуровневый дизайн и потратите время на детальное обсуждение того, как запускать код безопасно и изолированно, какие существуют компромиссы между контейнерами/VM/serverless и аргументируете свой выбор. Будет хорошо, если вы сможете также рассказать, как планируете запускать тест-кейсы с пользовательским кодом.

Staff+

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

Интервьюер понимает, что вы знаете основы (REST, нормализация данных и т. п.), так что вы можете быстро пройти их на high-level дизайне и перейти к самому интересному.

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

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

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

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