Design an Online Judge

You read a problem, write a solution and press Submit. A few seconds later the site says "Accepted, 48 ms", or "Wrong Answer on test 12". During a weekly contest, tens of thousands of people do this at once while a live leaderboard reorders itself. LeetCode is the kind of product this question means.

Interviewers like it because the core action is alarming: strangers send you programs and you run them on your machines. A good answer treats every submission as hostile, keeps the slow judging work off the request path, and plans for a spike whose start time is known to the second. The steps follow A Framework for Any Design.

#Clarify the problem

• Functional: list and view problems; submit code in several languages; run against sample tests; get a verdict (accepted, wrong answer, time or memory limit exceeded, runtime or compile error); contests with a start, an end and a live leaderboard.
• Non-functional: untrusted code is fully isolated (no network, no access to other data); verdicts are deterministic; verdict in 10 s at p95 normally, 30 s during contests; no accepted submission is lost; leaderboard at most a few seconds stale; problem pages load instantly at contest start.
• Out of scope: discussions, plagiarism detection, problem authoring tools, payments.

#Estimate the scale

A day has 86,400 seconds. Assume a submission needs about 2 seconds of CPU in total: compiling plus running about 50 hidden tests.

• Normal day: 1 million ÷ 86,400 ≈ 12 submissions a second, so 12 × 2 = 24 cores busy judging.
• Contest: 50,000 people × 8 submissions or runs each = 400,000 in 90 minutes (5,400 s): about 74 a second on average. Bursts after each easy problem are about 3x that: 220 a second.
• Problem pages at the start: if 50,000 people load them within 10 seconds of the start, that is 5,000 page loads a second for content that is identical for everyone.
• Storage: 1 million × 2 KB of code = 2 GB a day, about 730 GB a year. Test data: 3,000 problems × 10 MB = 30 GB, small enough to cache on every judge machine.

#Define the API

GET  /v1/problems/{slug}                    static page, served by the CDN
  403 Forbidden      contest problem before the contest starts
 
POST /v1/submissions   Idempotency-Key: (client-generated)
  body: { "problem": "two-ferries", "language": "cpp", "code": "...", "contest": "w214"? }
  202 { "submission_id": "s88123", "status": "queued" }
  413 Payload Too Large     code over 64 KB
  429 Too Many Requests     more than 1 submission per 5 s per user
 
GET  /v1/submissions/{id}                   poll; the server suggests Retry-After: 1
  200 { "status": "judging", "tests_done": 31, "tests_total": 50 }
  200 { "status": "done", "verdict": "accepted", "time_ms": 48, "memory_kb": 9216 }
 
GET  /v1/contests/{id}/standings?page=1     top 50 per page, cached for 5 s
GET  /v1/contests/{id}/standings/me         { "rank": 812, "solved": 2, "penalty": 3120 }

The decision worth arguing is polling against pushing the verdict. Polling is a plain read that works through any proxy, retries trivially, and the estimate shows only 2,200 polls a second at the peak. Pushing over a WebSocket or server-sent events (see Realtime Communication) saves those reads but needs 50,000 open connections and a way to route each verdict to the right one. Start with polling, one request a second with Retry-After so the server can slow clients down under load.

#Model the data

problems      (problem_id PK, slug, statement_html, time_limit_ms, memory_mb,
               tests_version INT)          -- tests live in object storage, by version
 
submissions   (submission_id PK, user_id, problem_id, contest_id NULL,
               language, code_key,         -- code in object storage, about 2 KB
               status,                     -- queued | judging | done
               verdict NULL, time_ms, memory_kb, tests_version,
               created_at, judged_at)
  INDEX (user_id, problem_id, created_at)
 
contest_results (contest_id, user_id, problem_id,      PK (contest_id, user_id, problem_id)
                 wrong_before_accept INT, accepted_at TIMESTAMP NULL)

The volumes are modest (12 rows a second normally, a few hundred in a contest), and contest scoring needs a small transaction: "record this accept only if it is the first one". A relational database fits, partitioned by user if it ever outgrows one primary. Code and test files go in object storage, referenced by key. Recording tests_version on each submission makes a verdict repeatable: a rejudge after tests change uses the new version on purpose, not by accident.

#High-level design

#Deep dives

Interviewers push on running hostile code safely, on the queue and how results get back, on the leaderboard, and on the minute the contest starts.

#Running untrusted code

Assume every submission is an attack. It may loop forever, allocate all memory, fork until the process table is full, write gigabytes of output, read the expected outputs, open a connection to send them out, or try a kernel exploit to escape. Each needs its own defence:

• Time: a CPU-time limit per test, counted by the kernel, plus a wall-clock limit (say twice the CPU limit) for programs that sleep or block.
• Memory, processes, output: a memory cap (256 MB), a process cap (64), an output cap (a few MB), all enforced by the kernel's resource controls, such as cgroups on Linux.
• Files: a read-only system image, a small writable temp directory, and the test input on standard input. Expected outputs never enter the sandbox; the judge compares outside it.
• Network: none. The sandbox gets an empty network namespace.
• System calls: a filter that allows only what normal programs need, and a non-root user.

I would run each submission in a fresh container inside a micro-VM (Firecracker is one example), taken from a pool of pre-started ones and destroyed afterwards, so nothing one program leaves behind can affect the next. The cost is memory and a pool to manage. Pin each sandbox to its own CPU core: if two submissions share a core, one slows the other, and the same program could pass on Monday and time out on Tuesday.

#The queue and getting results back

Judging takes seconds and may need retries, so it must not happen inside the HTTP request. The API writes the submission, then enqueues its id. Writing the row first matters: if the enqueue fails, a sweeper finds rows still queued after a minute and enqueues them again, so an accepted submission is never lost.

The queue (see Message Queues and Streams) delivers at least once. A worker holds a 15-second lease, renews it every 5 seconds, and acknowledges only after writing the verdict and the score. If it dies, another worker judges again within 15 seconds; a 60-second lease alone would break the 30-second target. Judging twice is harmless as long as the effects are idempotent: the verdict write is conditional on the row not being done, and the leaderboard counts only the first accept per user and problem. That gives the effect of exactly-once without needing it from the queue, the same pattern as in Design a Job Scheduler.

Use separate queues: contest submissions, practice submissions, and "Run" on sample tests. Workers prefer the contest queue, so a flood of practice traffic can never delay a contest verdict. Rate limit each user to one submission every 5 seconds; at 50,000 users that caps the theoretical worst case at 10,000 a second, and in practice it stops scripts from flooding the queue.

#The live leaderboard

Rank by problems solved (more is better), then by penalty (less is better). Penalty is the sum, over solved problems, of the seconds from the start to the accept, plus 300 seconds for each wrong submission before it. Zoe solved A at 460 seconds after one wrong try: 460 + 300 = 760.

Turn that into one number that sorts the right way: score = solved × 10,000,000 − penalty. A penalty can never reach 10 million seconds (about 115 days), so more solved always wins. Keep scores in an in-memory sorted set such as a Redis sorted set: an update and "what is my rank" are both O(log n), and a page of the top 50 is a range read. 50,000 entries of about 100 bytes is 5 MB, so one node holds it.

Submissions finish out of order: a wrong answer sent at 400 s can be judged after the accept sent at 460 s. So the verdict transaction recomputes the user's row in contest_results from their submissions in submit order, not judge order. The worker then sets the score on the sorted set (a set, not an increment), so a redelivered job writes the same value again.

The load is in reads, not writes. If each person solves 3 of the 4 problems on average, that is 150,000 accepts ÷ 5,400 s ≈ 28 a second. But if every participant refreshes standings every 30 seconds, that is 50,000 ÷ 30 ≈ 1,700 reads a second, more with spectators. Render each standings page once every 5 seconds and serve it from a cache or CDN; only "my rank" goes to the sorted set, at O(log n) each. The sorted set is derived data: if it is lost, rebuild it from contest_results, about 50,000 rows, in seconds. The leaderboard case study covers rankings at much larger scale.

#The spike at contest start

Unlike most spikes, this one is on the calendar. Use that.

• Pages: render problem pages ahead of time and publish them to the CDN at the start time, so 5,000 loads a second never reach the API. The API returns 403 for the problem before the start, using the server's clock, not the browser's.
• Judges: scale the worker fleet from 24 busy cores to about 600 fifteen minutes before the start, warm the sandbox pool, and copy the contest's test data to every worker.
• Queue: the queue absorbs bursts above capacity. If the contest queue holds 3,000 jobs and workers finish 300 a second, the newest job waits about 10 seconds: inside the 30-second target. Watch queue age, not just length.
• Sign-in: warm session caches so 50,000 logins at 10:00 do not all hit the user database.

#Bottlenecks and failures

At 10x (a 500,000-person contest), judging needs about 4,400 busy cores at the peak, which is a capacity and cost question: reserve it for contest hours and release it after. The CDN takes 50,000 page loads a second without change. The leaderboard sorted set holds 500,000 entries, about 50 MB, still one node; the cached standings pages do the rest. The submissions database sees about 2,200 new rows a second at the peak plus as many verdict updates, so partition it by user.

#What a strong answer sounds like

#Follow-up questions

#A test case was wrong. How do you rejudge a contest?

Publish a new tests_version, enqueue every affected submission on a low-priority queue, and recompute contest_results and the leaderboard from the new verdicts. The leaderboard is derived, so rebuilding it is routine.

#How do you support "interactive" problems?

Run a trusted interactor program next to the submission, connected only by pipes. It sits outside the sandbox and decides the verdict.

#How do you make time limits fair across languages?

Measure each problem's reference solutions per language on the judge hardware and set limits per language, or multiply a base limit by a factor per language.

#How would you freeze the leaderboard for the last 15 minutes?

Keep updating the sorted set but serve a snapshot taken at the freeze; each user still sees their own verdicts. Unfreeze by publishing the live set.

#How would you push verdicts instead of polling?

Each API server holds the WebSockets of its users; a worker publishes verdicts to a channel keyed by user, and the server holding that user's socket forwards it. Keep polling as the fallback.