Concurrency & System Coding

Rubrik's "System Coding" round is runnable, low-level, and overwhelmingly about concurrency. You are handed a systems-flavored prompt on CoderPad, you write code against it, and you compile and run it, so the bar is working thread-safe machinery, not whiteboard pseudocode. The recurring twist is a ban on the convenient tools: the interviewer forbids ExecutorService, BlockingQueue, and the concurrent collections, then asks you to build the equivalent from a lock and a condition variable. This lesson works the three families that recur, a dependency job scheduler, a producer-consumer buffer, and a resource limiter, each stripped to the core logic first and then wrapped in the real concurrency.

The Rubrik angle

The problems are largely Rubrik-original, so what transfers is command of the primitives. A memorized solution set will not. Candidates report over and over that the questions are not findable on LeetCode because an internal team frames them. They also say the round becomes a discussion you can reason through when your fundamentals are solid. What carries across an unfamiliar prompt is the machinery. Know how a blocking queue blocks and when a semaphore beats a condition variable. Know what InterruptedException means and where you catch it, and how a clean shutdown() drains in-flight work. Build that base cold and the novel scheduler or allocator becomes a variation on machinery you already own.

The dependency scheduler

Scheduling dominates the concurrency family. The recurring shape is a job scheduler that runs tasks respecting a dependency graph. Task B cannot start until task A finishes, several independent tasks may run at once, and on any failure the whole run stops. Before you touch a thread, the question underneath is pure graph work. Which jobs are runnable now, which unlock once those finish, and is the graph even schedulable or does a cycle make it impossible. That resolution into ordered waves is deterministic, so it is the piece the widget can test. The parallel execution that consumes the waves is the layer you add in code.

1

Job Scheduler: Resolve the Dependency Graph into Parallel Waves

MediumFrequently asked

Problem

You are given n jobs labeled 0 to n - 1 and a list deps where deps[i] = [job, prereq] means job cannot start until prereq has finished. Resolve the graph into ordered execution waves: wave 0 is every job with no unfinished prerequisites, wave 1 is every job whose prerequisites all complete in wave 0, and so on. Every job in a wave can run in parallel because none depends on another in the same wave.

Return the list of waves, each wave a list of job ids sorted ascending. If the dependencies contain a cycle so that some job can never run, return an empty list.

Input: n = 3, deps = [[1,0],[2,0]]

Output: [[0],[1,2]]

Job 0 has no prerequisite, so it runs first. Jobs 1 and 2 both wait only on 0, so they run together in the next wave.

Input: n = 2, deps = [[0,1],[1,0]]

Output: []

Job 0 waits on 1 and job 1 waits on 0, a cycle, so neither can ever start.

How this uses the pattern

This is a level-by-level topological sort (Kahn's algorithm). Count each job's unfinished prerequisites as an in-degree. The current wave is every job at in-degree zero; process it, decrement the in-degree of everything it unlocks, and the newly-zero jobs form the next wave. If you never process all n jobs, a cycle remains.

Job Scheduler: Resolve the Dependency Graph into Parallel Waves

Python

Focus Mode

Loading...

OutputSubmissions

Run

Submit

Click "Run" to execute your code

Test Cases

Input: [3,[[1,0],[2,0]]]Expected: [[0],[1,2]]

Input: [1,[]]Expected: [[0]]

Input: [2,[[0,1],[1,0]]]Expected: []

Input: [4,[[1,0],[2,0],[3,1],[3,2]]]Expected: [[0],[1,2],[3]]

Input: [3,[]]Expected: [[0,1,2]]

Input: [5,[[1,0],[2,0],[3,1],[3,2]]]Expected: [[0,4],[1,2],[3]]

Need a hint? (3 available)

The Rubrik angle

The DAG scheduler is Rubrik's most-named scheduling prompt, and resolving the graph into waves first is how you keep the concurrent version honest. Interviewers want the runnable executor to launch a wave across a hand-rolled thread pool, wait for it to drain, then launch the next, and to stop everything the instant any job throws. All of that is far easier to reason about once the wave structure is a plain data structure you computed up front. Name the cycle case out loud too. A scheduler that hangs forever on an unschedulable graph has a correctness bug, and calling it slow misses that.

Take it further

Now run the waves concurrently and stop on the first failure. Feed each wave's jobs into a hand-rolled thread pool, block until the wave finishes, then release the next. Track completion with a counter guarded by a lock and a condition variable that the main thread waits on. On any job throwing, set a shared failed flag, stop dispatching new work, and wake the waiter so the whole run unwinds promptly instead of draining every remaining job.

Show solution & walkthrough

With the waves in hand, the concurrent executor is a loop over them. It dispatches a wave's jobs to a pool of worker threads, blocks until that wave drains, and then releases the next. The blocking, the completion counting, and the stop-on-failure are the parts the interviewer watches, and the ban on built-ins means you build the pool and the wait yourself.

// waves comes from the deterministic resolver above.
// pool is a hand-rolled fixed thread pool (see the bounded-queue section).
void runWaves(List<List<Integer>> waves, ThreadPool pool, Map<Integer, Runnable> jobs) {
    for (List<Integer> wave : waves) {
        final int size = wave.size();
        final int[] done = {0};                 // completed jobs in this wave
        final ReentrantLock lock = new ReentrantLock();
        final Condition waveDrained = lock.newCondition();
        for (int id : wave) {
            pool.submit(() -> {
                try {
                    if (!failed) jobs.get(id).run();
                } catch (RuntimeException e) {
                    failed = true;              // one throw stops the run
                } finally {
                    lock.lock();
                    try {
                        done[0]++;
                        if (done[0] == size) waveDrained.signal();
                    } finally {
                        lock.unlock();          // release even if run() threw
                    }
                }
            });
        }
        lock.lock();
        try {
            while (done[0] < size) waveDrained.await();   // while, not if
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();           // restore the flag, do not swallow
            return;
        } finally {
            lock.unlock();
        }
        if (failed) break;                      // do not launch the next wave
    }
}

The bounded blocking queue

The thread pool that ran those waves needs a queue between the submitter and the workers, and Rubrik's ban on BlockingQueue means you write it. A bounded queue is the canonical producer-consumer primitive: producers add work, consumers take it, the buffer has a fixed capacity, and the interesting moments are the boundaries. A producer that finds the buffer full must wait, and a consumer that finds it empty must wait. Those waits are the concurrency. Strip them away and what remains is a fixed-capacity FIFO whose enqueue and dequeue semantics are entirely deterministic, so that core is what the widget tests.

2

Bounded Buffer: Model the Producer-Consumer Semantics

MediumSometimes asked

Problem

Model a fixed-capacity FIFO buffer without real threads. Build a class BoundedBuffer(capacity) with three operations:

- offer(x): add x if there is room, returning true. If the buffer is already full, change nothing and return false, which is the point where a real producer thread would block on the not-full condition.
- poll(): remove and return the oldest item in first-in-first-out order. Return null when the buffer is empty, the point where a real consumer would block on not-empty.
- size(): return the current number of items.

Modeling each blocking boundary as a returned value lets you prove the buffer's invariant before wrapping it in a lock and two condition variables.

Input: ops = [offer(1), offer(2), offer(3), size(), poll(), offer(3), poll(), poll(), poll()], capacity = 2

Output: [null, true, true, false, 2, 1, true, 2, 3, null]

The third offer fails because capacity is 2 and the buffer is full. Items leave oldest-first, and the final poll on an empty buffer returns null. The leading null is the constructor.

Input: ops = [offer(1), size(), poll(), size()], capacity = 0

Output: [null, false, 0, null, 0]

A zero-capacity buffer refuses every offer and always polls null.

How this uses the pattern

Hold the capacity and a list acting as the queue. offer compares the length against capacity. Room means append and return true; full means change nothing and return false. poll removes and returns the front element, or null when empty. size is the length. Everything reduces to those two boundary checks.

Bounded Buffer: Model the Producer-Consumer Semantics

Python

Focus Mode

Loading...

OutputSubmissions

Run

Submit

Click "Run" to execute your code

Test Cases

Input: [["BoundedBuffer",[2]],["offer",[1]],["offer",[2]],["offer",[3]],["size",[]],["poll",[]],["offer",[3]],["poll",[]],["poll",[]],["poll",[]]]Expected: [null,true,true,false,2,1,true,2,3,null]

Input: [["BoundedBuffer",[1]],["poll",[]],["offer",[9]],["offer",[8]],["poll",[]],["size",[]]]Expected: [null,null,true,false,9,0]

Input: [["BoundedBuffer",[3]],["offer",[10]],["offer",[20]],["offer",[30]],["poll",[]],["poll",[]],["poll",[]]]Expected: [null,true,true,true,10,20,30]

Input: [["BoundedBuffer",[0]],["offer",[1]],["size",[]],["poll",[]]]Expected: [null,false,0,null]

Input: [["BoundedBuffer",[2]],["offer",[1]],["poll",[]],["offer",[2]],["offer",[3]],["offer",[4]],["poll",[]],["poll",[]]]Expected: [null,true,1,true,true,false,2,3]

Need a hint? (3 available)

The Rubrik angle

A hand-rolled bounded queue is the most common Rubrik concurrency ask because it sits under every thread pool and every producer-consumer pipeline in a backup system. Modeling it single-threaded is how the reasoning happens: separate the buffer's invariant, full refuses and empty yields nothing in FIFO order, from the threading that enforces waiting. Once the invariant is provably right, the concurrent version is one lock plus not-full and not-empty condition variables around these exact checks. Grading then moves to whether you wait in a loop and release the lock cleanly.

Take it further

Turn the returned booleans into real waits. Replace return false with a producer waiting on a not-full condition, and return null with a consumer waiting on not-empty. Guard both with a single lock, wait inside a while loop that rechecks the predicate after each wakeup, and signal the opposite condition after every state change. Decide deliberately how put and take propagate InterruptedException rather than swallowing it.

Show solution & walkthrough

The concurrent buffer keeps those same two checks and turns each boundary into a wait. One lock guards the buffer so the size check and the mutation cannot interleave. A not-full condition parks a producer while the buffer is full; a not-empty condition parks a consumer while it is empty. Each side signals the other after it changes the buffer. Both waits sit inside a while loop, because a signal wakes a thread without promising the predicate still holds when it runs.

class BlockingBuffer<T> {
    private final Deque<T> buf = new ArrayDeque<>();
    private final int capacity;
    private final ReentrantLock lock = new ReentrantLock();
    private final Condition notFull = lock.newCondition();
    private final Condition notEmpty = lock.newCondition();
    BlockingBuffer(int capacity) { this.capacity = capacity; }
    void put(T x) throws InterruptedException {
        lock.lock();
        try {
            while (buf.size() == capacity) notFull.await();   // while, so a spurious wake rechecks
            buf.addLast(x);
            notEmpty.signal();                                // a taker may now proceed
        } finally {
            lock.unlock();                                    // released even if await threw
        }
    }
    T take() throws InterruptedException {
        lock.lock();
        try {
            while (buf.isEmpty()) notEmpty.await();
            T x = buf.removeFirst();
            notFull.signal();                                 // a putter may now proceed
            return x;
        } finally {
            lock.unlock();
        }
    }
}

Resource allocation and rate limiting

The other pole of the concurrency family is resource allocation: bound how many threads may hold a resource, or how fast they may consume it. The named puzzles here are the "Political Bathroom" (one room, at most three people, never a mix of the two parties, fair queueing with no starvation) and a shared playground capped at ten players. There is also a searcher-inserter-deleter that allows concurrent reads but exclusive writes. Each is really a question about which synchronization construct fits. The runnable core in this section is a rate limiter, whose admit-or-deny decision on a stream of timestamps is fully deterministic, and the construct discussion follows it.

3

Token-Bucket Limiter: The Deterministic Admit-or-Deny Decision

MediumSometimes asked

Problem

A token-bucket limiter guards a shared resource. The bucket holds up to capacity tokens and starts full. It gains refillRate tokens per unit of time, never exceeding capacity. Each request costs one token: if at least one token is available the request is admitted and a token is spent, otherwise it is denied and nothing changes.

You are given capacity, refillRate, and a chronological list times of request arrival times (non-decreasing integers). Return a list of booleans, one per request, where true means admitted and false means denied.

Input: capacity = 2, refillRate = 1, times = [0,0,0,2,2]

Output: [true, true, false, true, true]

The bucket starts with 2 tokens, so the first two same-instant requests pass and the third is denied. By time 2 it has refilled to 2 tokens (capped), so both requests at time 2 pass.

Input: capacity = 3, refillRate = 0, times = [0,0,0,0]

Output: [true, true, true, false]

With no refill, only the three starting tokens are ever available.

How this uses the pattern

Carry a token count and the time of the last request. On each request, add refillRate tokens for the elapsed time and cap at capacity; then admit and spend a token if at least one is available, else deny. Because refillRate and the times are integers, the token count stays an integer and the decisions are exact.

Token-Bucket Limiter: The Deterministic Admit-or-Deny Decision

Python

Focus Mode

Loading...

OutputSubmissions

Run

Submit

Click "Run" to execute your code

Test Cases

Input: [2,1,[0,0,0,2,2]]Expected: [true,true,false,true,true]

Input: [3,0,[0,0,0,0]]Expected: [true,true,true,false]

Input: [1,1,[0,1,2]]Expected: [true,true,true]

Input: [1,1,[0,0,0]]Expected: [true,false,false]

Input: [2,2,[0,0,0,1]]Expected: [true,true,false,true]

Input: [5,1,[]]Expected: []

Need a hint? (3 available)

The Rubrik angle

A rate limiter appears in Rubrik's loop as both a System Coding problem and a distributed-systems design prompt, and the deterministic bucket is the core both build on. Proving the admit-or-deny arithmetic first keeps the concurrent version clean, because the only shared state is a token count and a timestamp, and the whole critical section is the refill-then-spend step. The instinct interviewers reward is capping the refill at capacity so idle time cannot bank unlimited tokens, and spending a token only on an admitted request.

Take it further

Make it thread-safe, then distributed. For one process, guard the refill-then-spend step with a single lock so two threads cannot both see the last token and both spend it. Across processes, the token count moves to a shared store such as Redis. The refill-and-decrement must be atomic there, through a Lua script or an atomic compare-and-set, or the same double-spend race reappears over the network.

Show solution & walkthrough

Made concurrent, the limiter's whole critical section is the refill-then-spend step: two threads must not both observe the last token and both spend it. One lock around that step is enough for a single process. The resource-allocation puzzles differ only in which construct enforces the bound, and naming the right one is itself part of the score.

The Rubrik angle

Choosing the synchronization construct is graded, so name the tradeoff before you commit. A semaphore caps a count of permits and fits the playground's ten-player limit and the token bucket's available tokens cleanly. A condition variable fits the "wait until this predicate holds" shape of the blocking queue. A read-write lock fits the searcher-inserter-deleter split, concurrent reads but exclusive writes. The "Political Bathroom" layers a fairness rule on top of a capacity cap, so it wants a semaphore for the three-person limit plus explicit queueing to keep either party from starving the other. Interviewers notice the candidate who says why a semaphore beats a barrier for a given constraint. Grabbing the first tool in reach reads worse. Rehearse the mapping until you can justify the pick in a sentence.

// Single-process limiter: refill and spend cannot interleave.
boolean tryAcquire(long now) {
    lock.lock();
    try {
        tokens = Math.min(capacity, tokens + (now - last) * refillRate);
        last = now;
        if (tokens >= 1) { tokens -= 1; return true; }   // admit
        return false;                                    // deny
    } finally {
        lock.unlock();
    }
}
// Playground capped at ten: a semaphore is the natural fit for a counted resource.
Semaphore slots = new Semaphore(10, true);   // fair, so no player starves
void enter() throws InterruptedException {
    slots.acquire();                          // blocks past the tenth player
}
void leave() {
    slots.release();                          // frees a slot for a waiter
}

The details that decide it

The System Coding round is medium-to-hard in raw algorithmic terms but hard in execution. The algorithm under a scheduler or a blocking queue is not exotic. The hard part is producing it as correct, runnable, thread-safe code with the right primitives and clean exception handling, on the first real attempt and under time. Because CoderPad runs the code, the interviewer sees whether it compiles, whether it deadlocks, and whether it races, so a plain implementation that survives execution outscores an ambitious design that does not quite work.

Common questions