Contents

Rate Limiter: The 90-Minute Build Session

This is a different animal from the other write-ups: a practical session, 90 minutes total — a short design conversation, an implementation you drive on a shared screen, and a production discussion at the end. The duration is itself information: nobody hand-types three algorithms, a CSV tool, tests, and a web server in an hour, so the session almost certainly expects AI-assisted coding. That moves the evaluation to what the tool can't do for you: asking the questions that change the design, decomposing so the time degrades gracefully, proving the generated code correct, and defending every line.

The code below is the target artifact: real, in Go, and tested — every output shown is from an actual run, and the working module lives in code/ next to this document. Treat it as what a good 90 minutes should end with, and rehearse producing it once with your AI tool before the real session; the rehearsal is where you find out which prompts work.

Go is a good fit here and worth saying why in one breath: a single static binary, an HTTP server in the standard library, table-driven tests, and go test -race — a built-in answer to "how do you know the concurrent path is safe."

Time budget (90 minutes, said out loud at the start)

The scope ladder, cut from the bottom and never the top:

  1. sliding log + CSV replay + blocked count — the literal ask;
  2. boundary tests + the oracle — the proof;
  3. token bucket behind the same interface — the second contract;
  4. the HTTP server;
  5. the fixed-window comparison.

If it turns out AI is not allowed, drop rungs 4–5 on the spot and hand-write 1–3; they're ~120 lines total and the session still lands. Either way, if everything runs long you have a working CSV-answering program by minute 50, and everything after it is additive.

Driving the AI — the actual skill on display

Design discussion (~10 minutes, compressed)

Questions that change the design

Ask these before drawing anything, because each one forks the implementation:

  1. What is the limit keyed on? Per IP? Per host? Per (IP, host) pair? A CSV with both columns is a hint that the interviewer wants you to notice this is a choice. Make it a parameter, not an assumption.
  2. What are "the parameters"? "N requests per W seconds" implies a windowed limiter; "R per second with burst B" implies a token bucket. Support the one they want; keep the seam to add the other.
  3. Is the CSV sorted by timestamp? Real logs aren't, quite. Limiters assume time moves forward. Decide out loud: sort first (batch replay can afford it), and note what you'd do online (tolerate small skew, never refill negative time).
  4. What does the output need to be? A single count satisfies the prompt; a per-key breakdown of top offenders is twenty extra lines and is what an operator would actually want. Offer it.
  5. Do rejected requests consume quota? In most real limiters, no: rejections aren't recorded, so a client hammering at 2x the limit gets roughly the limit through, not zero. Pick "rejected requests don't count" and say why.

The algorithm tour

Do this on the whiteboard in about two minutes — the point is to show you know the space, then commit.

Algorithm Guarantee Memory/key The flaw
Fixed window ≤ limit per aligned window O(1) up to 2x limit across a boundary
Sliding window log exactly ≤ limit in any trailing window O(limit) memory grows with the limit
Sliding window counter approximate trailing window O(1) approximation error at window edges
Token bucket sustained rate R, burst B O(1) "window" isn't directly expressible

The fixed-window flaw is worth thirty seconds of the discussion because it's the classic probe: 100/minute allows 100 requests at 0:59 and 100 more at 1:01 — 200 in two seconds. The test suite demonstrates it deliberately.

Pick: sliding window log for the CSV replay, token bucket as the second algorithm. The log is exact, which makes the printed "blocked" count defensible and testable against a brute-force oracle; O(limit) memory is irrelevant in a replay. The token bucket is what production edges actually run (rate plus burst is how operators think), so implementing both behind one interface shows the interface was right. Both fit in the time because they're each ~30 lines of Go.

The structure

One decision carries the whole session: the limiter core knows nothing about files, HTTP, or wall clocks. Allow(key string, ts float64) bool, timestamp passed in. Then the CSV replay and the web server are two thin drivers over the same package, and the core is testable with fabricated time — no sleeps in tests.

flowchart LR
    subgraph cmds [cmd/ — thin drivers]
        CLI[cmd/replay<br/>CSV replay, batch]
        SRV[cmd/server<br/>HTTP /check, wall clock + mutex]
        GEN[cmd/gensample<br/>deterministic test traffic]
    end
    subgraph core [package limiter — pure, injectable time]
        IF["Limiter interface<br/>Allow(key, ts) bool"]
        TB[TokenBucket]
        SL[SlidingWindowLog]
        FW[FixedWindow]
        KF[KeyFuncs:<br/>ip / host / ip-host]
    end
    CSV[(requests.csv)] --> CLI
    CLI --> core
    SRV --> core
    T["limiter_test.go<br/>fabricated timestamps +<br/>brute-force oracle<br/>(go test -race)"] --> core

This is the same shape as any good production limiter library: the algorithm is a pure function of (state, key, now), and "now" is an argument precisely so that replay, simulation, and testing are trivial. Say that sentence in the interview. The module layout is the idiomatic small-Go-project shape: one library package, three cmd/ binaries, go.mod, zero dependencies.

Implementation

The core (limiter/limiter.go)

// Package limiter implements rate-limiting algorithms with injectable time.
//
// Every limiter answers one question: Allow(key, ts) -> bool.
// State is per-key; ts is a float64 (epoch seconds). Nothing here knows
// about CSV files, HTTP, or wall clocks — that's what makes it testable.
// The types are NOT goroutine-safe; callers that share a limiter across
// goroutines (the HTTP server) guard it with a mutex.
package limiter

import "fmt"

// Limiter is the one interface every algorithm satisfies.
type Limiter interface {
	Allow(key string, ts float64) bool
}

// TokenBucket refills rate tokens/second up to burst capacity. The
// production default: short bursts up to burst, sustained throughput
// capped at rate.
type TokenBucket struct {
	rate, burst float64
	state       map[string]bucketState
}

type bucketState struct {
	tokens, last float64
}

func NewTokenBucket(rate, burst float64) (*TokenBucket, error) {
	if rate <= 0 || burst <= 0 {
		return nil, fmt.Errorf("rate and burst must be positive")
	}
	return &TokenBucket{rate: rate, burst: burst, state: make(map[string]bucketState)}, nil
}

func (tb *TokenBucket) Allow(key string, ts float64) bool {
	s, ok := tb.state[key]
	if !ok {
		s = bucketState{tokens: tb.burst, last: ts}
	}
	// Refill for elapsed time; clamp to capacity. max() guards against
	// out-of-order timestamps minting tokens from negative elapsed time.
	s.tokens = min(tb.burst, s.tokens+max(0, ts-s.last)*tb.rate)
	s.last = ts
	if s.tokens >= 1 {
		s.tokens--
		tb.state[key] = s
		return true
	}
	tb.state[key] = s
	return false
}

// SlidingWindowLog is exact: at most limit requests in any trailing
// window seconds. Keeps one timestamp per allowed request — memory is
// O(limit) per key.
type SlidingWindowLog struct {
	limit  int
	window float64
	state  map[string][]float64
}

func NewSlidingWindowLog(limit int, window float64) (*SlidingWindowLog, error) {
	if limit <= 0 || window <= 0 {
		return nil, fmt.Errorf("limit and window must be positive")
	}
	return &SlidingWindowLog{limit: limit, window: window, state: make(map[string][]float64)}, nil
}

func (sl *SlidingWindowLog) Allow(key string, ts float64) bool {
	log := sl.state[key]
	cutoff := ts - sl.window
	// Evict entries at or before the cutoff (<= makes the boundary exact:
	// a request exactly window seconds old has aged out).
	i := 0
	for i < len(log) && log[i] <= cutoff {
		i++
	}
	log = log[i:]
	if len(log) < sl.limit {
		sl.state[key] = append(log, ts)
		return true
	}
	sl.state[key] = log
	return false
}

// FixedWindow allows limit per aligned window (e.g. per clock minute).
// O(1) memory per key, but permits up to 2x limit across a boundary.
type FixedWindow struct {
	limit  int
	window float64
	state  map[string]windowState
}

type windowState struct {
	win   int64
	count int
}

func NewFixedWindow(limit int, window float64) (*FixedWindow, error) {
	if limit <= 0 || window <= 0 {
		return nil, fmt.Errorf("limit and window must be positive")
	}
	return &FixedWindow{limit: limit, window: window, state: make(map[string]windowState)}, nil
}

func (fw *FixedWindow) Allow(key string, ts float64) bool {
	w := int64(ts / fw.window)
	s, ok := fw.state[key]
	if !ok || s.win != w {
		s = windowState{win: w}
	}
	if s.count < fw.limit {
		s.count++
		fw.state[key] = s
		return true
	}
	fw.state[key] = s
	return false
}

// KeyFunc turns a request's (ip, host) into the identity a limit applies to.
type KeyFunc func(ip, host string) string

var KeyFuncs = map[string]KeyFunc{
	"ip":      func(ip, host string) string { return ip },
	"host":    func(ip, host string) string { return host },
	"ip-host": func(ip, host string) string { return ip + "|" + host },
}

Details worth narrating while typing: the max(0, ts-s.last) in the token bucket is an out-of-order-timestamp guard (a request from the past must not mint tokens); the sliding log evicts with <= so the boundary is exact ("100 in any 60s" means a request exactly 60s old has aged out); SlidingWindowLog only appends on allow, which is the "rejected requests don't consume quota" decision from the design discussion, now visible as one line. And the doc comment says out loud that the package is not goroutine-safe — that's a design choice (the replay is single-threaded; the server owns the mutex), not an oversight, and stating it preempts the concurrency question.

The CSV replay (cmd/replay/main.go)

The full file is in code/cmd/replay/; the shape is: parse flags → load rows (tolerating a header, blank lines, bad rows with a warning to stderr, and both epoch and RFC 3339 timestamps — csv.Reader with FieldsPerRecord = -1 so one malformed row doesn't abort the file) → sort by timestamp → feed the limiter → print the report.

// Real traffic logs are rarely perfectly ordered; the limiters assume
// monotonic time per key, so sort. Stable sort preserves same-ts order.
sort.SliceStable(rows, func(i, j int) bool { return rows[i].ts < rows[j].ts })

blocked := map[string]int{}
allowed := 0
for _, r := range rows {
	k := keyFn(r.ip, r.host)
	if lim.Allow(k, r.ts) {
		allowed++
	} else {
		blocked[k]++
	}
}

fmt.Printf("%d requests: %d allowed, %d blocked (%.1f%%)\n", total, allowed, nBlocked, pct)

Tests (limiter/limiter_test.go) — where the session is won

Seven tests, plain go test, each pinned to a specific claim from the design discussion. The two that matter most:

The boundary tests prove the sliding log is exact and the fixed window is not:

func TestSlidingLogExactBoundary(t *testing.T) {
	sl, _ := NewSlidingWindowLog(3, 10.0)
	for _, ts := range []float64{0, 1, 2} {
		if !sl.Allow("k", ts) {
			t.Fatalf("t=%v should be allowed", ts)
		}
	}
	if sl.Allow("k", 9.9) {
		t.Fatal("t=9.9 should be blocked: 3 already inside trailing 10s")
	}
	if !sl.Allow("k", 10.1) {
		t.Fatal("t=10.1 should be allowed: t=0 aged out (0 <= 10.1-10)")
	}
}

func TestFixedWindowBoundaryBurst(t *testing.T) {
	fw, _ := NewFixedWindow(3, 10.0)
	// 3 at the end of window 0 and 3 at the start of window 1 all pass:
	// 6 requests in 0.2s — the documented fixed-window weakness.
	...
}

And the brute-force oracle: 5,000 random exponentially-spaced events across three keys, each decision checked against a naive count-the-trailing-window implementation. This is the test that converts "I think it's right" into "it agrees with the obvious slow version on 5,000 cases," and it's ~20 lines:

func bruteForceAllow(history []float64, ts float64, limit int, window float64) bool {
	n := 0
	for _, h := range history {
		if h > ts-window {
			n++
		}
	}
	return n < limit
}

func TestSlidingLogMatchesBruteForceOnRandomTraffic(t *testing.T) {
	rng := rand.New(rand.NewSource(42))
	sl, _ := NewSlidingWindowLog(5, 30.0)
	history := map[string][]float64{}
	ts := 0.0
	for i := 0; i < 5000; i++ {
		ts += rng.ExpFloat64()
		key := []string{"a", "b", "c"}[rng.Intn(3)]
		expected := bruteForceAllow(history[key], ts, 5, 30.0)
		if got := sl.Allow(key, ts); got != expected {
			t.Fatalf("event %d key=%s ts=%f: got %v, oracle says %v", i, key, ts, got, expected)
		}
		if expected {
			history[key] = append(history[key], ts)
		}
	}
}

Actual run, including the race detector:

$ go vet ./... && go test ./... -v
--- PASS: TestTokenBucketBurstThenStarve (0.00s)
--- PASS: TestTokenBucketSustainedRate (0.00s)
--- PASS: TestTokenBucketOutOfOrderTimestampNoNegativeRefill (0.00s)
--- PASS: TestSlidingLogExactBoundary (0.00s)
--- PASS: TestFixedWindowBoundaryBurst (0.00s)
--- PASS: TestKeysAreIndependent (0.00s)
--- PASS: TestSlidingLogMatchesBruteForceOnRandomTraffic (0.00s)
PASS
ok  	ratelimiter/limiter	0.244s

$ go test -race ./...
ok  	ratelimiter/limiter	1.160s

Running it on data

cmd/gensample produces a deterministic 10-minute trace: 40 polite clients, one scraper doing a sustained 10 req/s, one client sending 50-request bursts every two minutes. 9,635 rows. Real output:

$ go run ./cmd/replay -algo sliding-log -limit 100 -window 60 -key ip sample.csv
9635 requests: 5134 allowed, 4501 blocked (46.7%)
top blocked ip keys:
  203.0.113.99: 4501

$ go run ./cmd/replay -algo token-bucket -rate 2 -burst 20 -key ip sample.csv
9635 requests: 5188 allowed, 4447 blocked (46.2%)
top blocked ip keys:
  203.0.113.99: 4302
  198.51.100.7: 145

The two outputs disagree, and explaining why is a strong moment: the sliding log at 100/60s never blocks the bursty client (50 per burst < 100 per minute), while the token bucket at burst 20 clips every burst's tail — 30 blocked per burst, 145 total. Same traffic, different contract. That's the "which parameters do you want?" question from minute five, now visible in numbers.

The web server (cmd/server/main.go)

Thin: net/http, GET /check?ip=&host= → 200 or 429 with Retry-After, the same limiter behind a sync.Mutex (net/http runs each request on its own goroutine, and the core isn't goroutine-safe by design — the mutex is the whole concurrency story at this scale, and go test -race is the receipt). Time comes from time.Since(start), which rides Go's monotonic clock — NTP can't step it backward. Real smoke test, -rate 1 -burst 3:

req1: 200   req2: 200   req3: 200   req4: 429   req5: 429
other-ip: 200

HTTP/1.1 429 Too Many Requests
Retry-After: 1
{"allowed":false}

Burst honored, different key unaffected, and the 429 carries Retry-After — the header that separates "I've built one" from "I've read about one."

Edge cases to name even if you don't code them

The production discussion (final ~10 minutes)

Ten minutes won't cover all of this — lead with distributed state and fail-open versus fail-closed, and keep the rest in your pocket for follow-ups.

The single-process limiter has two properties production breaks: state lives in one process, and correctness under concurrency currently costs a global mutex.

Distributed state. The moment there are two instances behind a load balancer, each enforces its own limit — a 100/min limit becomes 200/min. The standard fix is a shared in-memory store (Redis), with the check-and-decrement done atomically server-side (a Lua script or Redis functions), because GET-then-SET from the client is a read-modify-write race: two gateways read 99, both allow, count hits 101. Token bucket in Lua is ~10 lines, and this exact race is the follow-up question to expect — it's the distributed version of the mutex the server already needed locally.

The latency/accuracy trade. A Redis round trip per request adds ~1ms and a hard dependency. Production systems split the limiter in two tiers: a generous local in-process limiter (cheap, protects the box — the mutex version we just wrote, maybe sharded 16 ways to kill lock contention) and the precise shared limiter (the actual product limit). Under Redis failure, fail open and alarm — for a platform, briefly over-admitting traffic is cheaper than blocking every customer because the limiter's dependency blinked. Say the exception too: fail closed where the limiter is a security control (login attempts, password resets).

Hot keys. One viral customer routes every check to one Redis shard. Mitigations: key-sharded Redis with local caching of "definitely blocked" verdicts (a blocked verdict can be cached for Retry-After seconds — it's self-expiring), or approximate global limiting where each node gets limit / n with periodic rebalancing.

Product surface. Limits become configuration: per-plan defaults, per-customer overrides, per-endpoint costs (a search costs 10 tokens, a read costs 1). Responses should carry the draft-standard RateLimit-* headers plus Retry-After. And the operator needs observability: blocked-rate per key and per limit before enabling enforcement — every serious rollout ships in shadow mode first, logging what would have been blocked. Which is exactly what the CSV replay tool is: the shadow-mode analyzer, pointed at history. The interview exercise and the production rollout tool are the same program — closing on that observation ties the whole session together.