Design LeetCode

What the interviewer is asking

"Design LeetCode" means design an online judge: a site that shows coding problems, takes people's code, runs it on hidden tests and says whether it passed. The interesting part isn't the problem pages: it's that the site runs strangers' code all day on its own machines, slow, expensive and dangerous work that can't happen inside the web servers. The walkthrough follows the 8 steps of the interview framework: scope, data, API, the busy path, numbers, services, scale and deep dives.

1. Scope: what version 1 must do

• See a problem: its statement, examples and limits.
• Submit code in a few languages, such as Python, Java and C++.
• Get a verdict on hidden tests: Accepted, Wrong Answer, Time Limit Exceeded, Runtime Error or Compile Error.

Name the rest and park it: discussions, editorials, ratings, plagiarism checks and contests. Contests come back as a deep dive: they change the traffic.

2. Data: problems, tests and submissions

record       fields
problem      id, title, statement, examples, time limit, memory limit, test keys
submission   id, user, problem, language, code, status, verdict, failed test, time, memory
test files   tests/two-sum/17.in, tests/two-sum/17.out   (in object storage)

Problems and submissions are small rows the site shows, searches and counts, so they live in a database; the code is a few KB of text and fits in the row. The limits (say 2 seconds and 256 MB of memory per test) belong to the problem. The hidden tests are files: a test of a million 9-digit numbers is about 10 MB, a problem's 50 tests can add up to about 100 MB, and only the judge reads them, whole. They go in object storage under their own keys, which the problem row keeps.

3. The API: three calls

GET  /problems/two-sum
  → 200 OK          statement, examples, limits

POST /submissions   {"problem": "two-sum", "language": "cpp", "code": "…"}
  → 202 Accepted    {"id": "s42"}

GET  /submissions/s42
  → 200 OK          {"status": "done", "verdict": "Wrong Answer", "test": 4}

Running the code takes seconds, sometimes a minute or more, so POST /submissions doesn't wait for the verdict: it saves the submission and answers 202 Accepted with its id. The page then asks for the result every second or so (polling), or the server pushes it over WebSockets or server-sent events (the Real-Time Updates lesson compares them). A request held open for the whole run would tie up servers during a rush and lose the verdict on a reload.

4. The busy path: running code

Problem pages are opened about 10 times for every submission, but they're cheap: the same few KB for everyone, from a cache or a CDN in about a millisecond. A submission is compiled and run on about 50 hidden tests. Running code is the busy path. Here's Ana's C++ submission s42:

1. A runner compiles it: about 1 s of CPU.
2. It runs test 1 with a 2-second limit and compares the output with the expected one. Tests 1 to 3 pass, in about 0.02 s each.
3. Test 4's output differs, so it stops and saves Wrong Answer on test 4. Tests 5 to 50 never run.

A compile failure, a crash or running past the limit ends the loop the same way, with Compile Error, Runtime Error or Time Limit Exceeded. A run that passes all 50 tests costs about 1 s to compile plus 50 × 0.02 s = 1 s of tests: about 2 CPU-seconds. The limit is a ceiling, not the usual cost: if every test went right up to it, a run would take 50 × 2 = 100 s.

5. The numbers

From the interviewer: 1 million submissions a day, busy hours at about 5× the average. A day has 86,400 seconds; round it to 100,000.

• Submissions: 1 million ÷ 100,000 = about 10 a second (about 12 with the exact 86,400), so about 50 a second at busy hours.
• Cores: 50 a second × 2 s each = 100 cores running code at any moment.
• Runner machines: at 8 cores each, 100 ÷ 8 is about 13 machines, plus a few spare.
• Problem pages: 500 a second at busy hours, at about 1 ms each: half a core.
• Storage: say 2 KB per submission, mostly code: about 2 GB a day, 730 GB a year.

6. Services: the API never runs code

One judge app that also runs the code puts 100 cores of untrusted code next to the pages: one run that eats the memory or loops forever slows or crashes the site, and you can't add cores for code without adding web servers. Split it:

• API service: serves problems, saves each submission as queued, puts its id on a queue and answers 202. It never runs code.
• Queue: holds submissions until a runner is free, so a rush waits instead of failing (Message Queues).
• Runners: take a submission, fetch its tests from object storage, run the code in a sandbox and save the verdict.

Calling runners directly, without a queue, breaks as soon as every runner is busy: the API must hold or refuse submissions.

7. Scale: runners pull

Runs take from about 1 s (a compile error) to 100 s (50 tests close to the limit). Round robin from a load balancer can't see that: a runner stuck with long runs keeps getting its turn while another sits idle. Instead, runners pull: each takes the next submission from the queue whenever it has a free core, so the queue does the balancing and a new runner starts working as soon as it's up. The load balancer stays in front of the API servers, whose requests are short and alike. Prefer many small runners to one huge machine: when one fails, judging slows down instead of stopping.

Two details matter at this size. Fetching 100 MB of tests for each of 50 runs a second would pull 5 GB a second from storage, so runners keep each problem's tests on local disk until the tests change. And the queue's timeout for unacknowledged messages must be longer than the longest run, about 100 s, or a slow run is handed to a second runner while the first is still working.

8. Deep dive: sandboxing

Every run happens in a sandbox: a fresh machine of its own, thrown away after the run. Containers, built from Linux namespaces (their own view of files, processes and network) and cgroups (caps on CPU, memory and processes), start fast but share the host's kernel; micro-VMs such as Firecracker add a stronger wall for a little more start-up time. Each attack meets its own wall:

attack                                       what stops it
a loop that never ends                       a CPU time limit
a fork bomb                                  a limit on the number of processes
printing 10 GB of output                     an output size limit
making a 50 GB array                         the memory limit (256 MB)
reading other users' code on the disk        a fresh, read-only file system per run
sending the hidden tests to its own server   no network at all

Scanning the code for dangerous calls doesn't work: there are endless ways to write the same call, and an endless loop contains no dangerous word. Only the code is cut off: the runner around the sandbox still reads the queue, fetches tests and writes verdicts.

9. Deep dive: time limits

A 2-second limit can count CPU time, the work the code did, or time on the clock. Cy's code calls sleep(10) and does no work. Dee's needs 1.5 s of CPU, but her runner runs more programs than it has cores, so it ends 2.4 s after it starts. On the clock alone, Dee fails because her machine was busy. On CPU time alone, Cy never hits the limit: sleeping uses no CPU, so her program holds a sandbox as long as it likes.

A common design uses both: the verdict compares CPU time with the limit, and a looser clock limit, say 3× (6 s), stops programs that just wait. Cy gets Time Limit Exceeded at 6 s; Dee passes. Even CPU time shifts a little with noisy neighbors sharing caches and memory bandwidth, so a run within a few percent of the limit can pass once and fail the next time. Run one program per core and set limits well above the official solution's time.

10. Deep dive: contests

In a contest everyone starts at once. Say 10,000 contestants submit the easy first problem within 2 minutes, about 5,000 a minute, and the runners have room for about 3,000 a minute:

minute   arrived   runs done   waiting
1        5,000     3,000       2,000
2        5,000     3,000       4,000
3        1,000     3,000       2,000
4        1,000     3,000       0

The queue loses nothing, but at the peak a new submission waits about 80 s (4,000 ÷ 50 a second) before a runner starts it. Adding runners when the queue grows is too late: it passes 1,000 within the first minute, and a new machine takes a few minutes to start and copy the tests. Contests run on a schedule, so scale ahead: start extra runners shortly before, with the contest's tests on their disks, and stop them after. With twice the runners, about 6,000 runs a minute, nothing piles up.

If turnout still beats the plan, give contest submissions their own contest queue that runners serve first, and keep a few runners for practice so a long contest can't starve it.

The leaderboard ranks by problems solved; ties go to less time, the minutes taken plus a penalty per wrong try (say 10). Ben, with 4 solved, is first; Ana (3 in 45 minutes) beats Cy (3 in 30 minutes plus 2 wrong tries: 50). Thousands refresh it, so keep an in-memory sorted set (Redis has one) scored by solved × 1,000,000 − minutes and updated on each Accepted: the top 50, or one contestant's rank, is a quick read (Top K / Leaderboard).

What breaks first

• A runner dying mid-run: the queue hands the submission out again after its timeout, so it's judged twice. Save verdicts by submission id, so the second save changes nothing.
• One user submitting in a loop: it takes cores from everyone; limit submissions per user (Rate Limiting).
• A sandbox escape: a kernel bug can let code out of a container. Keep runners on a network that reaches only the queue, the storage and the database, and use micro-VMs for the strongest wall.
• The database growing: about 730 GB of submissions a year. Move old ones to cheaper storage.

Summary: the order to follow

1. Scope: see a problem, submit code, get a verdict.
2. Data: problem and submission rows; hidden tests in object storage.
3. API: POST /submissions answers 202 and an id; GET /submissions/{id} returns the verdict.
4. Busy path: running code, test by test until the first failure.
5. Numbers: about 50 submissions a second at busy hours, 100 cores, 13 runner machines.
6. Services: the API never runs code; a queue feeds the runners.
7. Scale: runners pull work when they have a free core.
8. Deep dives: a sandbox per run; CPU time plus a clock limit; contests with runners started ahead, a contest queue and a sorted-set leaderboard.

The same shape fits any system that runs code it didn't write, such as CI pipelines: queue the work and run it in isolated workers.