Проектирование 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
}

// заметим, что ID пользователя берется из сессии или auth-токена и
// не передается в теле или параметрах пути запроса

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

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 задач
• до 100k участников
• результат - число решенных задач за 90 минут; при равенстве - время решения всех задач (от начала соревнования)

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

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

SELECT userId, COUNT(*) as numSuccessfulSubmissions
FROM submissions
WHERE competitionId = :competitionId AND passed = true
GROUP BY userId
ORDER BY numSuccessfulSubmissions 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 участников?

Основная проблема - всплеск трафика во время соревнования, который может перегрузить контейнеры, в которых выполняется пользовательский код. 100k пользователей - это все еще немного, и наш основной сервер за счет горизонтального масштабирования должен справиться с этой нагрузкой без каких-либо проблем. Однако, поскольку выполнение кода требует большого количества ресурсов 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
    }
  ]
}

Здесь мы решили сериализовать сущность Дерево в массив, используя обход по порядку (inorder). Каждый язык будет иметь свою собственную версию 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+ кандидатам. Тем не менее, от таких кандидатов ожидается, что они смогут вести весь разговор, заранее выявляя потенциальные проблемы с дизайном и предлагая решения для их устранения. Они должны быть в состоянии обсуждать компромиссы между различными подходами и обосновывать свои решения. В идеале они должны спроектировать очень простую систему, без overengineering-а, но с ясным планом масштабирования в случае необходимости.