Scratch-Building Problems

This chapter is for live coding or architecture rounds where the interviewer asks you to build something from scratch.

The goal is not to master every possible problem. The goal is to get good at the few problem shapes that show up again and again in backend and systems interviews.

Strategy

These problems are usually not testing whether you can invent a production system from nothing. They are testing whether you can:

identify the underlying pattern
clarify the constraints
choose the simplest correct model
write clean Rust
discuss trade-offs

Highest-Yield 40%

If you only have time to get good at 40% of this list, start with these four:

Rate limiter
Worker pool / job queue
In-memory cache
Event bus / pub-sub

These cover a large fraction of the design patterns underneath the other problems:

HashMap state
queues
timing and expiration
channels
synchronization
trait boundaries
backpressure

Build an in-memory rate limiting component that decides whether a request for a given key should be allowed right now. The core shape is per-key state plus time-based admission control. Clarify whether the algorithm is fixed window, sliding window, or token bucket, whether the limiter is single-process or distributed, and whether limits are global, per user, per IP, or per API key.

Equivalent prompt shapes:

implement a rate limiter for requests identified by a key
design a component that allows or rejects traffic based on recent request volume
build a per-customer throttling system for an API
implement request admission control with time-based limits
build an in-memory quota checker with per-key counters and reset logic
design a bounded request policy that smooths traffic and prevents overload

Common business disguises:

API throttling
login attempt limiting
SMS or email send limits
per-tenant usage quotas
webhook delivery throttling

Simplest correct version

Fixed window counter per key.

What it tests

HashMap
time handling
synchronization
per-key state
API design
trade-offs between simplicity and correctness

First sentences to say

I'd model this first as per-key state plus time-based admission control. Before I code, I want to clarify whether we want fixed window, sliding window, or token bucket, whether this is single-process or distributed, and what key we are limiting on. I'll start with the simplest correct in-memory fixed-window version, then explain how I'd evolve it for smoother behavior or distributed enforcement.

Minimal shape

#![allow(unused)]
fn main() {
use std::collections::HashMap;
use std::time::{Duration, Instant};

struct Entry {
    window_start: Instant,
    count: u32,
}

struct RateLimiter {
    limit: u32,
    window: Duration,
    entries: HashMap<String, Entry>,
}

impl RateLimiter {
    fn allow(&mut self, key: &str, now: Instant) -> bool {
        let entry = self.entries.entry(key.to_string()).or_insert(Entry {
            window_start: now,
            count: 0,
        });

        if now.duration_since(entry.window_start) >= self.window {
            entry.window_start = now;
            entry.count = 0;
        }

        if entry.count < self.limit {
            entry.count += 1;
            true
        } else {
            false
        }
    }
}
}

Full runnable example

use std::collections::HashMap;
use std::time::{Duration, Instant};

struct Entry {
    window_start: Instant,
    count: u32,
}

struct RateLimiter {
    limit: u32,
    window: Duration,
    entries: HashMap<String, Entry>,
}

impl RateLimiter {
    fn new(limit: u32, window: Duration) -> Self {
        Self {
            limit,
            window,
            entries: HashMap::new(),
        }
    }

    fn allow(&mut self, key: &str, now: Instant) -> bool {
        let entry = self.entries.entry(key.to_string()).or_insert(Entry {
            window_start: now,
            count: 0,
        });

        if now.duration_since(entry.window_start) >= self.window {
            entry.window_start = now;
            entry.count = 0;
        }

        if entry.count < self.limit {
            entry.count += 1;
            true
        } else {
            false
        }
    }
}

fn main() {
    let mut limiter = RateLimiter::new(3, Duration::from_secs(10));
    let start = Instant::now();

    println!("{}", limiter.allow("alice", start));
    println!("{}", limiter.allow("alice", start));
    println!("{}", limiter.allow("alice", start));
    println!("{}", limiter.allow("alice", start));

    let later = start + Duration::from_secs(11);
    println!("{}", limiter.allow("alice", later));
}

Trade-offs to mention

fixed window is simple but bursty at boundaries
sliding window or token bucket is smoother
distributed rate limiting changes everything

2. Worker Pool / Job Queue

Prompt shape

Build a small concurrent job execution system. Work is submitted by producers into a shared queue, and a fixed number of worker threads or tasks pull from that queue and process jobs in parallel.

Equivalent prompt shapes:

implement a worker pool that accepts submitted jobs and processes them concurrently with fixed parallelism
build an in-memory job queue where producers enqueue work and background workers consume it
design a task dispatcher that decouples job submission from job execution and limits concurrency to N workers
implement a producer-consumer system in Rust with a shared queue, multiple workers, and explicit shutdown semantics
write a small thread pool that executes closures or work items submitted by callers
design a bounded work queue that introduces backpressure when producers submit work faster than workers can process it

Common business disguises:

email sender
webhook dispatcher
image processing backend
report generator
background file processor

Simplest correct version

Bounded or unbounded queue plus worker threads or tasks.

What it tests

channels
ownership across threads
shutdown semantics
backpressure
error handling

First sentences to say

I'd model this first as a producer-consumer system with explicit queue semantics and fixed worker concurrency. Before I code, I want to clarify whether this is thread-based or async, whether the queue is bounded or unbounded, whether ordering or results matter, and whether shutdown means stop immediately or drain accepted work. I'll start with a simple bounded queue and fixed workers, because that gives us the cleanest correct concurrency model first.

Minimal shape

use std::sync::mpsc;
use std::thread;

type Job = Box<dyn FnOnce() + Send + 'static>;

fn main() {
    let (tx, rx) = mpsc::channel::<Job>();
    let rx = std::sync::Arc::new(std::sync::Mutex::new(rx));

    for _ in 0..4 {
        let rx = std::sync::Arc::clone(&rx);
        thread::spawn(move || loop {
            let job = {
                let guard = rx.lock().unwrap();
                guard.recv()
            };

            match job {
                Ok(job) => job(),
                Err(_) => break,
            }
        });
    }

    tx.send(Box::new(|| println!("job 1"))).unwrap();
}

Full runnable example

use std::sync::{mpsc, Arc, Mutex};
use std::thread;
use std::time::Duration;

type Job = Box<dyn FnOnce() + Send + 'static>;

fn main() {
    let (tx, rx) = mpsc::channel::<Job>();
    let rx = Arc::new(Mutex::new(rx));
    let mut handles = Vec::new();

    for worker_id in 0..2 {
        let rx = Arc::clone(&rx);
        handles.push(thread::spawn(move || loop {
            let job = {
                let guard = rx.lock().unwrap();
                guard.recv()
            };

            match job {
                Ok(job) => {
                    println!("worker {worker_id} got a job");
                    job();
                }
                Err(_) => break,
            }
        }));
    }

    for i in 0..4 {
        tx.send(Box::new(move || {
            println!("running job {i}");
            thread::sleep(Duration::from_millis(50));
        }))
        .unwrap();
    }

    drop(tx);

    for handle in handles {
        handle.join().unwrap();
    }
}

Verbal walkthrough

A clean interview-safe walkthrough for this solution is:

I'd model this first as a producer-consumer system. Producers submit work into a queue, and a fixed set of worker threads pull jobs from that queue and execute them. I'll start with the simplest correct thread-based version using a channel plus a fixed worker set.

Then walk through the structure in this order:

Define the job type as Box<dyn FnOnce() + Send + 'static> so each job is an owned closure that can move to another thread and run once.
Create the channel with mpsc::channel::<Job>(), which gives a sending endpoint for producers and a receiving endpoint for workers.
Wrap the receiver in Arc<Mutex<_>> because std::sync::mpsc is multi-producer, single-consumer, and multiple workers must coordinate access to one receiver.
Spawn a fixed number of worker threads, each looping forever, waiting on recv(), and executing the next job it receives.
Submit jobs by sending boxed closures into the channel from the producer side.
Call drop(tx) when no more jobs will be submitted so recv() eventually returns Err(_) and each worker exits its loop.
Join all worker threads so shutdown is explicit and the main thread waits for all accepted work to finish.

Trade-offs to mention

bounded queues create backpressure
unbounded queues are simpler but risk memory growth
shutdown and cancellation matter

Common follow-up questions

Why does `let (tx, rx) = mpsc::channel::<Job>();` use `(tx, rx)`?

Because mpsc::channel::<Job>() returns two values: a Sender<Job> and a Receiver<Job>. The pattern let (tx, rx) is tuple destructuring, which binds both returned endpoints at once.

What does `::<Job>` mean here?

::<Job> is turbofish syntax. It tells Rust that this channel carries Job values. The trailing () is the ordinary function call.

Why are the names `tx` and `rx` used?

They are conventional abbreviations:

tx means transmit
rx means receive

In larger examples, names like job_tx and job_rx are often clearer.

Why is `rx` shadowed?

#![allow(unused)]
fn main() {
let (tx, rx) = mpsc::channel::<Job>();
let rx = Arc::new(Mutex::new(rx));
}

The first rx is a Receiver<Job>. The second line creates a new binding with the same name that wraps the receiver in Arc<Mutex<_>>. This is shadowing, not mutation.

Why bind `rx` first if it is going to be shadowed anyway?

Because mpsc::channel::<Job>() returns a plain Receiver<Job>, and you need that value before you can wrap it. The code first binds the raw receiver, then transforms it into Arc<Mutex<Receiver<Job>>>, which is the form needed to share it across worker threads. Shadowing just reuses the same name for the next stage of the value.

A more explicit version would be:

#![allow(unused)]
fn main() {
let (tx, raw_rx) = mpsc::channel::<Job>();
let shared_rx = Arc::new(Mutex::new(raw_rx));
}

This is the same logic with different names.

What are the types of `tx` and `rx`?

They are:

std::sync::mpsc::Sender<Job>
std::sync::mpsc::Receiver<Job>

You can think of them as the typed sending and receiving endpoints of the channel.

Why is the receiver wrapped in `Arc<Mutex<_>>`?

Because std::sync::mpsc is multi-producer, single-consumer.

That means:

the sender can be cloned for multiple producers
the receiver is a single receiving endpoint

If multiple worker threads need to pull jobs from the same receiver, they must share that one receiver behind:

Arc for shared ownership
Mutex for synchronized access to recv()

Why is the sender not wrapped too?

The sender side is already designed to support multiple producers. If several threads need to submit jobs, you usually clone the sender instead of putting it behind Arc<Mutex<_>>.

What does `join()` actually do?

join() blocks the calling thread until the target thread finishes. Interview-safe, the right model is: the child thread runs to completion, while the calling thread sleeps in an OS-level wait instead of busy-polling. When the child exits, the OS wakes the waiting thread, and join() returns the result or panic information. In this example, storing JoinHandles lets the main thread join each worker so shutdown is explicit and worker panics are not ignored.

Why is `unwrap()` acceptable in the example but usually not ideal in production?

In examples like this, unwrap() keeps the code small and lets the concurrency shape stay visible. In production, it is usually better to avoid unwrap() on recoverable failures because it turns an error case into a panic. Interview-safe, the right framing is: unwrap() is fine for compact examples and strong invariants, but production code usually propagates or handles failures explicitly instead of crashing.

Production handling

If I were hardening this for production, I would replace the unwrap() calls with explicit policy at each failure boundary:

treat recv() returning Err(_) as normal shutdown when all senders are dropped
treat send() failure as a submission error such as pool closed, not a panic
decide how to handle a poisoned mutex: fail closed, recover with logging, or mark the pool unhealthy
inspect join() results so worker panics are logged or surfaced instead of blindly unwrapped
return structured errors from job submission rather than crashing the caller

Interview-safe framing:

In production, I would replace unwrap() with explicit failure policy. A closed channel during shutdown is a normal lifecycle event, while a poisoned mutex or worker panic is a health signal that should be logged, surfaced, and handled deliberately.

3. In-Memory Cache

Prompt shape

Build a small in-memory cache that stores values by key and serves repeated reads efficiently. The core shape is key-value storage with optional policies around eviction, expiration, size limits, and concurrent access. Clarify whether this is just a map, whether entries expire, whether we need LRU or LFU behavior, and whether the cache is single-threaded or shared across threads.

Equivalent prompt shapes:

implement a cache with get and set semantics
build a key-value store optimized for repeated reads
design an in-memory lookup layer in front of a slower data source
implement a cache with optional TTL expiration
build a small LRU-style cache for hot items
design a concurrent cache for shared application state

Common business disguises:

user profile cache
configuration cache
feature flag cache
database result cache
session or token lookup cache

Simplest correct version

HashMap<K, V> without eviction.

What it tests

API design
ownership of keys and values
optional expiration
synchronization for concurrent access

First sentences to say

I'd model this first as key-value storage with explicit policy decisions around eviction, expiration, and concurrency. Before I code, I want to clarify whether this is just a map, whether entries expire, whether we need bounded memory, and whether the cache is shared across threads. I'll start with the simplest correct in-memory HashMap, then layer on TTL, LRU, or synchronization if the requirements call for it.

Minimal shape

#![allow(unused)]
fn main() {
use std::collections::HashMap;

struct Cache<K, V> {
    items: HashMap<K, V>,
}

impl<K: std::cmp::Eq + std::hash::Hash, V> Cache<K, V> {
    fn new() -> Self {
        Self {
            items: HashMap::new(),
        }
    }

    fn set(&mut self, key: K, value: V) {
        self.items.insert(key, value);
    }

    fn get(&self, key: &K) -> Option<&V> {
        self.items.get(key)
    }
}
}

Full runnable example

use std::collections::HashMap;

struct Cache<K, V> {
    items: HashMap<K, V>,
}

impl<K: std::cmp::Eq + std::hash::Hash, V> Cache<K, V> {
    fn new() -> Self {
        Self {
            items: HashMap::new(),
        }
    }

    fn set(&mut self, key: K, value: V) {
        self.items.insert(key, value);
    }

    fn get(&self, key: &K) -> Option<&V> {
        self.items.get(key)
    }
}

fn main() {
    let mut cache = Cache::new();
    cache.set("language", "rust");
    cache.set("runtime", "tokio");

    println!("{:?}", cache.get(&"language"));
    println!("{:?}", cache.get(&"runtime"));
    println!("{:?}", cache.get(&"missing"));
}

Trade-offs to mention

no eviction is simplest
TTL expiration needs timestamps
LRU needs usage tracking
concurrent access changes the synchronization story

4. Event Bus / Pub-Sub

Prompt shape

Build a simple in-memory event distribution component where producers publish events and multiple consumers subscribe to receive them. The core shape is fan-out from one publisher side to many subscriber endpoints. Clarify whether delivery is broadcast or point-to-point, whether ordering matters, whether messages must be durable or can be lossy, and how subscriber lifecycle should be handled.

Equivalent prompt shapes:

implement an event bus where producers publish and consumers subscribe
build a pub-sub system with multiple subscribers per event stream
design a broadcast mechanism for in-process notifications
implement a message fan-out component for multiple listeners
build an in-memory notification hub for events
design a subscriber registry plus event delivery path

Common business disguises:

webhook event fan-out
internal notification hub
metrics or audit event stream
plugin callback system
application-level message broadcast

Simplest correct version

One broadcast path to multiple subscribers.

What it tests

channels
fan-out
message cloning
trait boundaries
subscription lifecycle

First sentences to say

I'd model this first as an in-memory fan-out system with explicit subscriber lifecycle. Before I code, I want to clarify whether delivery is broadcast or point-to-point, whether ordering matters, whether events must be durable or can be lossy, and how we handle dead subscribers. I'll start with the simplest correct broadcast model and make subscription and cleanup behavior explicit.

Minimal shape

#![allow(unused)]
fn main() {
use std::sync::mpsc::{self, Sender};

struct EventBus<T> {
    subscribers: Vec<Sender<T>>,
}

impl<T: Clone> EventBus<T> {
    fn new() -> Self {
        Self { subscribers: Vec::new() }
    }

    fn subscribe(&mut self) -> std::sync::mpsc::Receiver<T> {
        let (tx, rx) = mpsc::channel();
        self.subscribers.push(tx);
        rx
    }

    fn publish(&mut self, event: T) {
        self.subscribers.retain(|tx| tx.send(event.clone()).is_ok());
    }
}
}

Full runnable example

use std::sync::mpsc::{self, Receiver, Sender};
use std::thread;

struct EventBus<T> {
    subscribers: Vec<Sender<T>>,
}

impl<T: Clone> EventBus<T> {
    fn new() -> Self {
        Self {
            subscribers: Vec::new(),
        }
    }

    fn subscribe(&mut self) -> Receiver<T> {
        let (tx, rx) = mpsc::channel();
        self.subscribers.push(tx);
        rx
    }

    fn publish(&mut self, event: T) {
        self.subscribers.retain(|tx| tx.send(event.clone()).is_ok());
    }
}

fn main() {
    let mut bus = EventBus::new();
    let rx1 = bus.subscribe();
    let rx2 = bus.subscribe();

    let h1 = thread::spawn(move || {
        println!("subscriber 1 got {}", rx1.recv().unwrap());
    });

    let h2 = thread::spawn(move || {
        println!("subscriber 2 got {}", rx2.recv().unwrap());
    });

    bus.publish("event-1");

    h1.join().unwrap();
    h2.join().unwrap();
}

Trade-offs to mention

cloning cost
ordering guarantees
dead subscriber cleanup
bounded vs unbounded channels

time
queues
backoff
state transitions

Core trade-offs

fixed retry vs exponential backoff
max retries
dead-letter behavior

aggregation
time buckets
memory growth control

Core trade-offs

exact vs approximate windows
bucket granularity
cleanup cost

resource lifetime
synchronization
blocking vs timeout behavior

Core trade-offs

fairness
max size
timeout policy

data structure choice
update-on-access semantics
eviction policy

Core trade-offs

correctness vs implementation complexity
map + linked structure vs a simpler approximation

time-based state updates
arithmetic correctness
API semantics under concurrency

Core trade-offs

precision vs simplicity
monotonic time
per-key cleanup

batching
flush triggers
durability/failure behavior

Core trade-offs

throughput vs latency
memory growth
partial flush and retry behavior

How To Start Any Scratch-Building Problem

Use this sequence every time:

Clarify the model.
Clarify the scope.
Pick the simplest correct version.
State the core data structures.
Implement the minimal API.
Only then discuss optimization and production evolution.

Universal Opening Script

Before I code, I want to make the constraints explicit so I solve the right problem. I'll start with the simplest correct in-memory version, choose the cleanest data structures for that, and then I can talk through how I would evolve it for concurrency, scale, or stricter guarantees.

What To Master First

To get good at 40% quickly, master these patterns:

HashMap state keyed by ID
queue + worker model
time windows and expiration
channels and fan-out
Arc<Mutex<T>> or async mutex around shared state

If those are fluent, most of the listed problems stop being "new problems" and start becoming variations of familiar structures.

Keyboard shortcuts

Bobby Interview Notes