leetcode

Test cases are language-agnostic — stored as raw input/output text files. The execution worker reads test_case_1.in, runs the user's code with this input, captures stdout, and compares it character-by-character against test_case_1_expected_output.out. This means the same test cases work for Python, Java, C++, or any other supported language.

Submissions have a 1-month retention policy. A background job runs daily to delete submissions older than 30 days. Contest submissions may be retained longer for dispute resolution.

Requirement: Users browse a catalogue of problems with descriptions, examples, constraints, and starter code.

This follows a standard three-tier architecture. The Problems Service exposes two endpoints:

• GET /problems?start={start}&end={end} — paginated problem list
• GET /problems/:problem_id — full problem details including test case samples

The problem data (3,000 problems × ~50 KB each = ~150 MB) easily fits in memory. A Redis cache in front of the database serves problem data with sub-millisecond latency. Cache invalidation is simple because problems are updated rarely (new problems added ~weekly by admins).

Requirement: Users submit code and receive feedback on correctness within seconds.

This is where the architecture gets interesting. We can't execute user code on the API server — a single malicious submission could crash the entire service. We need separation of concerns:

• Code Evaluation Service — Receives submissions, validates input, and enqueues work
• Message Queue — Buffers submissions to handle burst traffic
• Code Execution Workers — Run untrusted code in sandboxed Docker containers

Why three components? Each has a different traffic pattern and scaling profile:

Why Polling Over WebSockets?

The user submits code. Execution takes 1-10 seconds. How does the user get results?

Short polling wins for this use case. With a typical 3-second execution time, the client polls 2-3 times before getting results. The "wasted" polls are trivially cheap — simple database reads that hit a cached submission status. Meanwhile, the server holds zero persistent connections.

This is how LeetCode works in production — you can verify by watching Chrome DevTools during a submission. You'll see repeated GET /submission/{id}/status requests every 1-2 seconds.

Requirement: Real-time leaderboard showing top 50 contestants, updated within seconds of each graded submission.

The submission infrastructure already works. The new challenge is the leaderboard — a sorted ranking that updates on every score change.

Why Not SQL for the Leaderboard?

SELECT user_id, score FROM contest_participants
ORDER BY score DESC, finish_time ASC
LIMIT 50;

This query scans and sorts the entire table. With 10,000 participants and hundreds of score changes per second, the ORDER BY constantly invalidates indexes. PostgreSQL would need to re-sort on every query — O(n log n) per request at 2,000 leaderboard polls/sec.

Redis Sorted Sets (ZSET)

Redis ZSET maintains elements sorted by score using a skip list internally. Operations:

• ZADD (insert/update score) → O(log n)
• ZREVRANGE (top N by score) → O(log n + N)

With 10,000 participants, log₂(10,000) ≈ 13 — both updates and queries touch ~13 skip list nodes. This is orders of magnitude faster than SQL sorting.

Score Composition

The leaderboard must rank by points first (primary) and time second (tie-breaker). But Redis ZSET only supports a single numeric score per member. We pack both values into one number:

compositeScore = (points × 1,000,000,000) + (1,000,000,000 - finishTimeInSeconds)

Why this works: Points occupy the billions place. Time (inverted so faster = higher) occupies everything below. They never overlap because finishTimeInSeconds for a 2-hour contest is at most 7,200 — far below 1 billion.

Example:

Redis ranks: Alice > Bob > Carol. Alice beats Bob despite equal points because she finished faster (higher inverted time component).

Service Ownership and Scaling

Key architecture property: The submission pipeline is fully asynchronous. The Code Evaluation Service responds in < 100 ms (just enqueues). The Worker processes seconds later. The Client polls for results. No component blocks on another.

How does the Code Evaluation Service decide if a submission is correct?

This question tests whether you can move beyond box-drawing into concrete implementation. The key insight: test cases must be language-agnostic so we don't maintain separate test suites for Python, Java, C++, etc.

The Verification Flow

Consider a simple problem: "Add two numbers."

Step 1 — Input file: test_case_1.in

2 3

Step 2 — Expected output file: test_case_1_expected.out

5

**Step 3 — User submits code (Python):

Step 4 — Execution:
The worker runs the user's code with test_case_1.in piped to stdin. The program writes to stdout, which the worker captures as test_case_1_actual.out.

Step 5 — Comparison:
The worker compares test_case_1_actual.out with test_case_1_expected.out character-by-character. If they match, the test case passes.

Step 6 — Verdict determination:

The submission gets one overall verdict based on the first failing test case: if test case 5 gives Wrong Answer, the overall verdict is Wrong Answer — even if test cases 6-20 would pass. This matches LeetCode's behavior and provides useful debugging information (the user knows which test case failed first).

What about the comparison? Exact string matching with strip() handles trailing whitespace/newlines. Some judges implement more lenient comparison (ignore trailing spaces per line, allow floating-point tolerance) but exact match is the standard approach.

How do we ensure security and isolation when executing untrusted code?

Running untrusted code is the highest security risk in this system. A user could submit code that:

• Infinite loops — consumes CPU indefinitely
• Fork bombs — spawns processes until the system crashes
• Memory bombs — allocates memory until OOM
• Filesystem access — reads test case answers or other users' code
• Network access — exfiltrates data or launches attacks from your servers
• System calls — escapes the sandbox

Defense in Depth: Six Isolation Layers

Layer 1: Container isolation. Each submission runs in a fresh Docker container. Containers use Linux namespaces (PID, network, mount, user) to isolate processes. The container's filesystem snapshot is discarded after execution.

Layer 2: Resource limits. Docker's --cpus, --memory, and --pids-limit flags enforce hard ceilings:

Layer 3: System call filtering (seccomp). Even inside a container, some system calls are dangerous (mount, ptrace, reboot). A seccomp profile whitelists only the ~40 syscalls needed for code execution (read, write, mmap, etc.) and blocks everything else.

Layer 4: User namespace. Run the code as a non-root user inside the container. Even if an attacker exploits a container escape vulnerability, they land in an unprivileged user space on the host.

Layer 5: Ephemeral containers. Each submission gets a fresh container from a pre-built image. After execution, the container is destroyed. There is no persistent state between submissions — nothing to exfiltrate from a previous user's run.

Layer 6: Worker isolation. Execution workers run on dedicated hosts separated from the API servers, databases, and internal services. Even a catastrophic container escape only compromises the worker host, not the production database or user data.

How do we implement a real-time leaderboard with O(log n) operations?

The leaderboard must handle two operations at high frequency during contests:

• Update score — happens on every graded submission (~28/sec average, 83/sec peak)
• Query top 50 — happens on every leaderboard poll (~2,000/sec)

Data Structure Options

Redis Sorted Set wins because:

1. Both updates AND queries are O(log n) — no other option matches this
2. Contest data is temporary (2 hours) — in-memory storage is ideal
3. Redis is single-threaded, so concurrent ZADD/ZREVRANGE operations are serialized without application-level locking

Redis ZSET Commands

Skip List Internals

Under the hood, Redis ZSET uses a skip list — a probabilistic data structure that maintains sorted order with O(log n) operations. Unlike balanced BSTs which require complex rotations, skip lists achieve balance through randomization.

A skip list is a hierarchy of linked lists. The bottom list (Level 0) contains all elements. Each higher level contains a random subset (~50%) of the level below. To search, you start at the top level, walk forward until you overshoot, then drop down a level. This is analogous to binary search but on linked lists.

To get the top 50 for the leaderboard, Redis:

1. Navigates to the end of the skip list (highest score) — O(log n)
2. Walks backward through Level 0 for 50 elements — O(50)
3. Total: O(log 10,000 + 50) ≈ O(63) — trivially fast

This is why Redis ZSET is the industry standard for real-time leaderboards.

How are contest scores calculated and stored as a single Redis score?

A fair ranking system answers three questions: Who solved harder problems? (points), Who solved them faster? (time), and Who made fewer mistakes? (penalties). These three factors must collapse into a single Redis ZSET score that preserves correct ranking order.

Scoring Model

Example:

• User solves Problem A (500 pts) at minute 15 after 1 wrong attempt
• User solves Problem B (1000 pts) at minute 45 with no mistakes
• Total points: 1500
• Finish time: 45 minutes (last accepted submission)
• Penalty: 1 × 5 = 5 minutes
• Effective time: 50 minutes

Packing Two Values Into One Redis Score

Redis ZSET only accepts one numeric score per member. We need to encode points (primary) and effective time (secondary, lower is better) into a single number where higher is always better.

The Big Multiplier formula:

redis_score = (points × 1,000,000,000) + (1,000,000,000 - effectiveTimeInSeconds)

Points occupy the billions place. Inverted time occupies everything below. They never overlap because effective time for a 2-hour contest is at most ~10,000 seconds (7,200 + penalties) — far below 1 billion.

redis_score = points + 1 / (1 + effectiveTimeInSeconds)

MAX_TIME = 0xFFFFFFFF  # 32-bit max
redis_score = (points << 32) | (MAX_TIME - effective_time_seconds)

The on_submission_graded function is called by the Contest Service whenever a submission finishes execution. It handles deduplication (don't score a problem twice), penalty tracking, and composite score calculation — all using Redis data structures for atomic operations.

How do we handle 10,000 contestants submitting simultaneously?

At contest start, 10,000 developers click "Submit" within the first few minutes. That's 5,000+ submissions in the first minute — far beyond steady-state capacity. By the time auto-scaling detects the spike and provisions new workers, users are already waiting minutes for results. We need a comprehensive strategy.

Strategy 1: Pre-Scaling

We know exactly when contests start. Five minutes before start time, a scheduler provisions the full fleet of execution workers:

Strategy 2: Message Queue as Buffer

The message queue absorbs the submission spike. Workers pull at their own pace:

The first-minute spike creates a ~60 second worst-case wait. This is acceptable for most coding contests — users are still reading problems in the first minute.

Strategy 3: Two-Phase Processing

For extremely large contests (50K+ participants), even 250 workers may not be enough. Two-phase processing reduces computation by 90% during the contest:

Phase 1 (During Contest): Run submissions against only 10% of test cases (2 out of 20). Provide instant preliminary feedback: "Passed 2/2 sample cases." Users know immediately if their approach is correct.

Phase 2 (After Contest Deadline): Run all submissions against the full test case suite (20 cases). Determine official results with complete validation.

Why does this work? Users care most about instant feedback during the contest — they need to know if their approach is correct so they can debug and resubmit. Running 10% of test cases gives them that signal in seconds. Full validation after the deadline is fine because users can't change their code anyway.

This is a battle-tested approach. Codeforces uses two-phase processing (they call it "pretests" during the contest and "system tests" after) for contests with 10,000+ participants.

The following topics contain open-ended architectural questions without prescriptive solutions. They are designed for staff+ conversations where you demonstrate systems thinking, trade-off analysis, and strategic decision-making.