LeetCode

Understanding the Problem

Functional Requirements

1. Users should be able to view a list of coding problems.
2. Users should be able to view a given problem, code a solution in multiple languages.
3. Users should be able to submit their solution and get instant feedback.
4. Users should be able to view a live leaderboard for competitions.

• User authentication
• User profiles
• Payment processing
• User analytics
• Social features

Non-Functional Requirements

1. The system should prioritize availability over consistency.
2. The system should support isolation and security when running user code.
3. The system should return submission results within 5 seconds.
4. The system should scale to support competitions with 100,000 users.

• The system should be fault-tolerant.
• The system should provide secure transactions for purchases.
• The system should be well-tested and easy to deploy (CI/CD pipelines).
• The system should have regular backups.

The Set Up

Planning the Approach

Defining the Core Entities

1. Problem: This entity will store the problem statement, test cases, and the expected output.
2. Submission: This entity will store the user's code submission and the result of running the code against the test cases.
3. Leaderboard: This entity will store the leaderboard for competitions.

API or System Interface

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

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

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

- userId not passed into the API, we can assume the user is authenticated and the userId is stored in the session

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

High-Level Design

1) Users should be able to view a list of coding problems

1. API Server: This server will handle incoming requests from the client and return the appropriate data. So far it only has a single endpoint, but we'll add the others as we go.
2. Database: This is where we'll store all of our problems. We'll need to make sure that the database is indexed properly to support pagination. While either a SQL or NoSQL database could work here, I'm going to choose a NoSQL DB like DynamoDB because we don't need complex queries and I plan to nest the test cases as a subdocument in the problem entity.

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

2) Users should be able to view a given problem and code a solution

3) Users should be able to submit their solution and get instant feedback

1. The API Server will receive the user's code submission and problem ID and send it to the appropriate container for the language specified.
2. The isolated container runs the user's code in a sandboxed environment. The container itself doesn't make outbound calls. Instead, the worker that manages the container invokes it synchronously (e.g. via Docker's exec API), waits for completion, and reads the output directly from stdout or a mounted volume.
3. The API Server will then store the submission results in the database and return the results to the client.

4) Users should be able to view a live leaderboard for competitions

• 90 minutes long
• 10 problems
• Up to 100k users
• Scoring is the number of problems solved in the 90 minutes. In case of tie, we'll rank by the time it took to complete all 10 problems (starting from competition start time).

SELECT userId, COUNT(DISTINCT problemId) as numSolvedProblems, MIN(submittedAt) as lastSolveTime
FROM submissions
WHERE competitionId = :competitionId AND passed = true
GROUP BY userId
ORDER BY numSolvedProblems DESC, lastSolveTime ASC

1. User requests the leaderboard via /leaderboard/:competitionId
2. The API server initiates a query to the submission table in our database to get all successful submissions for the competition.
3. Whether via the query itself, or in memory, we'll create the leaderboard by ranking users by the number of distinct problems solved, with ties broken by earliest solve time.
4. Return the leaderboard to the client.
5. The client will request the leaderboard again after 5 seconds so ensure it is up to date.

Potential Deep Dives

1) How will the system support isolation and security when running user code?

1. Read Only Filesystem: To prevent users from writing to the filesystem, we can mount the code directory as read-only and write any output to a temporary directory that is deleted a short time after completion.
2. CPU and Memory Bounds: To prevent users from consuming excessive resources, we can set CPU and memory limits on the container. If these limits are exceeded, the container will be killed, preventing resource exhaustion.
3. Explicit Timeout: To prevent users from running infinite loops, we can wrap the user's code in a timeout that kills the process if it runs for longer than a predefined time limit, say 5 seconds. This will also help us meet our requirement of returning submission results within 5 seconds.
4. Limit Network Access: To prevent users from making network requests, we can disable network access in the container, ensuring that users can't make any external calls. If working within the AWS ecosystem, we can use Virtual Private Cloud (VPC) Security Groups and NACLs to restrict all outbound and inbound traffic except for predefined, essential connections.
5. No System Calls (Seccomp): We don't want users to be able to make system calls that could compromise the host system. We can use seccomp to restrict the system calls that the container can make.

2) How would you make fetching the leaderboard more efficient?

3) How would the system scale to support competitions with 100,000 users?

Bad Solution: Vertical Scaling

Approach

The easiest option is to just run our containers on a larger instance type with more CPU and memory. This is known as vertical scaling and is the simplest way to increase the capacity of our system.

This is a good time to do a bit of math. If we estimate a peak of 10k submission at a time (imagine its a competition) and each submission runs against ~100 test case. We are likely to become CPU bound very quickly. Let's make a conservative assumption that each test case takes 100ms to run (in practice, most test cases finish in 10-50ms). This means that each submission could take up to 10s to run in the worst case, though typical submissions would land within our 5-second target. If we have 10k submissions, that's 1 million test cases, which will take 100,000 seconds to run. That's over 27 hours and we would need approximately 1,667 CPU cores to handle this load within one minute. This clearly indicates that vertical scaling alone, especially considering that even the largest AWS instance types top out at a few hundred vCPUs, is not a viable solution.

Even if we could, it's not easy to vertically scale dynamically so we'd have a big expensive machine sitting around most of the time not doing much. Big waste of money!

Great Solution: Dynamic Horizontal Scaling

Approach

We can horizontally scale each of the language specific containers to handle more submissions. This means that we can spin up multiple containers for each language and distribute submissions across them. This can be dynamically managed through auto-scaling groups that automatically adjust the number of active instances in response to current traffic demands, CPU utilization, or other memory metrics. In the case of AWS, we can use ECS to manage our containers and ECS Auto Scaling to automatically adjust the number of containers based on demand.

Challenges

The only considerable downside here is the risk of over-provisioning. If we spin up too many containers, we could end up wasting resources and incurring unnecessary costs. That said, modern cloud providers make it easy to scale up and down based on demand, so this is a manageable risk.

Great Solution: Horizontal Scaling w/ Queue

Approach

We can take the same exact approach as above but add a queue between the API server and the containers. This will allow us to buffer submissions during peak times and ensure that we don't overwhelm the containers. We can use a managed queue service like SQS to handle this for us.

When a user submits their code, the API server will add the submission to the queue and the containers will pull submissions off the queue as they become available. This will help us manage the load on the containers and ensure that we don't lose any submissions during peak times.

Once our worker gets the results, it will notify the App Server so it can update both the database and the cache simultaneously.

One important thing to note is that the introduction of the queue has made the system asynchronous. This means that the API server will no longer be able to return the results of the submission immediately. Instead, the user will need to poll the server for the results. We introduce a new endpoint, say GET /check/:id, that is polled every second by the client to check if the submission has been processed. It simply looks up the submission in the database and returns the results if they are available or returns a "processing" message if not.

Some candidates try to introduce a persistent connection like WebSockets to avoid polling. This could certainly work, but it adds complexity to the system and is likely not necessary given the polling interval is only a second.

Fun fact, this is exactly what LeetCode does when you submit a solution to a problem. Click submit with your network tab open and you'll see the polling in action!

Challenges

There could be a really strong case made that this is overengineering and adding unnecessary complexity. Given the scale of the system, it's likely that we could handle the load without the need for a queue and if we require users to register for competitions, we would have a good sense of when to expect peak traffic and could scale up the containers in advance.

4) How would the system handle running test cases?

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """

{
  "id": 1,
  "title": "Max Depth of Binary Tree",
  ...
  "testCases": [
    {
      "type": "tree",
      "input": [3,9,20,null,null,15,7],
      "output": 3
    },
    {
      "type": "tree",
      "input": [1,null,2],
      "output": 2
    }
  ]
}

Final Design

What is Expected at Each Level?

Mid-level

Senior

Staff+