Design an LRU Cache and a Rate Limiter

Two small components that interviewers love

This lesson covers two of the most frequently asked machine-coding problems. Both are small enough to finish in 45 minutes, which is exactly why they appear so often: the interviewer can watch you write complete, correct, thread-safe code rather than boxes on a whiteboard.

• An LRU cache (least recently used) keeps a fixed number of entries and, when full, throws out the entry that has gone unused the longest. The challenge is to make both get and put run in O(1) time, meaning constant time regardless of how many entries the cache holds.
• A rate limiter decides whether a request from a user should be allowed or rejected, so that no user can send more than, say, 100 requests per minute. The challenge is choosing an algorithm with the right accuracy, memory use and burst behaviour, and making it correct when many threads call it at once.

What interviewers probe:

• For LRU: can you explain why you need both a hash map and a doubly linked list, write the pointer updates without bugs, make it generic, and make it thread-safe? Do you know the LinkedHashMap shortcut, and can you still write the real thing when they disallow it?
• For rate limiting: can you name and compare fixed window, sliding log, sliding window counter, token bucket and leaky bucket; explain the boundary burst problem; and implement per-user limits without one global lock?

Everything below is implemented in one Java file whose real output is included, and every number in the worked examples is computed by hand and matched against that output. The high-level view of caches is in Caching.

Part 1: the LRU cache

Problem statement and requirements

Design a cache with a fixed capacity that supports:

• get(key): return the value if present and mark the key as most recently used; otherwise return nothing.
• put(key, value): insert or update; mark the key as most recently used; if inserting into a full cache, first evict the least recently used key.

Clarifying questions and the answers we assume:

Why one data structure is not enough

Think about what each operation needs:

1. Find a key quickly: a hash map gives O(1) average lookup.
2. Know which key is least recently used: you need the keys in recency order.
3. Move any key to the front when it is used, and remove the oldest key: you need O(1) removal from the middle of the order and O(1) insertion at the front.

An array keeps order but removing from the middle costs O(n). A singly linked list can remove a node in O(1) only if you know the node before it, which you do not. A doubly linked list, where each node points to both its previous and next node, can unlink any node in O(1) given just that node. So the design is:

• A hash map from key to list node.
• A doubly linked list of nodes ordered from most recent (front) to least recent (back).

The map finds the node; the list moves or removes it.

 HashMap                      Doubly linked list (most recent -> least)
 +-----+------+
 | "A" |  *---+------+
 | "C" |  *---+--+   |
 | "B" |  *---+  |   |
 +-----+------+  |   |
                 v   v
 [head] <-> [A:1] <-> [C:3] <-> [B:2] <-> [tail]
 sentinel                                sentinel

Sentinel nodes

head and tail are sentinels: dummy nodes that are always present and hold no data. With them, the first real node is always head.next and the last is always tail.prev, and inserting or unlinking never has to check for null at the ends. This removes the most common source of bugs in this problem.

The two pointer operations are four lines each:

void unlink(Node n)   { n.prev.next = n.next; n.next.prev = n.prev; }
void addFront(Node n) { n.next = head.next; n.prev = head;
                        head.next.prev = n; head.next = n; }

Order matters in addFront: read head.next into n.next before overwriting head.next.

Worked trace

Capacity 3. The list is shown most recent first.

put A=1         [A]
put B=2         [B, A]
put C=3         [C, B, A]
get A -> 1      [A, C, B]        A moves to the front
put D=4         full: evict tail.prev = B
                [D, A, C]
get B -> null   B was evicted
put C=30        C exists: update value, move to front
                [C, D, A]
put E=5         full: evict A
                [E, C, D]
get C -> 30     get A -> null

The program's first section prints exactly these states.

"Average" is there because hash map operations are O(1) on average; with many colliding keys they degrade (Java's HashMap turns long collision chains into balanced trees, bounding the worst case at O(log n)).

Making it generic

The Java implementation is LRUCache<K, V>. Keys must have correct equals and hashCode, as for any HashMap key. Records and String satisfy this. A mutable key whose hash changes while it is in the cache will be lost; say so if asked.

The LinkedHashMap shortcut

Java's LinkedHashMap already is a hash map plus a doubly linked list. Constructed with accessOrder = true, every get moves the entry to the end, and overriding removeEldestEntry evicts automatically:

class LinkedHashMapLRU<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;
    LinkedHashMapLRU(int capacity) { super(16, 0.75f, true); this.capacity = capacity; }
    @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }
}

Note the opposite convention: LinkedHashMap iterates from least recent to most recent, so after the same operations the demo prints [D, C, E], the reverse of our [E, C, D].

When to use it in an interview: mention it first. Some interviewers accept it and move on to harder questions. Most say "good, now implement it without LinkedHashMap", because the point of the question is the pointer manipulation. Never silently use it, and never claim it is thread-safe: it is not. Wrapping it in Collections.synchronizedMap works but locks on every get.

Thread safety

A subtle point: in an LRU cache, get is a write. It moves the node to the front, changing four pointers. Two threads calling get at once on a plain LRUCache can corrupt the list, for example both unlinking neighbouring nodes and leaving a node pointing to a removed one.

That means a ReadWriteLock does not help: there are no pure reads to share. Options:

The demo runs 8 threads doing 400,000 random gets and puts on a shared cache of capacity 100 and then checks the invariants: the map has 100 entries, the list has 100 nodes, and no key appears twice in the list. Under a broken, unsynchronised cache these checks fail or the program throws.

LFU in brief

An LFU cache (least frequently used) evicts the key with the fewest accesses, breaking ties by least recent. It keeps popular items even if they were not touched recently, which suits workloads with a stable set of hot keys. The O(1) design uses:

• A map from key to node, where each node knows its frequency.
• A map from frequency to a doubly linked list of nodes with that frequency (most recent first).
• A variable minFreq holding the smallest frequency currently present.

On access, move the node from list f to list f + 1; if list f became empty and f == minFreq, increment minFreq. On insert, the new key has frequency 1 and minFreq becomes 1. To evict, remove the tail of list minFreq.

A trace with capacity 2:

put A        freq: A=1               minFreq=1
get A        freq: A=2               list 1 empty -> minFreq=2
get A        freq: A=3               minFreq=3
put B        freq: A=3, B=1          minFreq=1
put C        full: evict tail of list 1 -> B
             freq: A=3, C=1          minFreq=1

Run the same sequence through LRU: after put B the recency order is B then A, so put C evicts A, the key that was used three times. LFU kept A because it is popular. The flip side: if A was popular yesterday and is never used again, LFU keeps it for a long time unless frequencies are periodically halved (aged).

Part 2: the rate limiter

Problem statement and requirements

Design a component that decides, for each request, whether to allow it based on how many requests the same user has made recently.

Functional requirements: tryAcquire(userId) returns allow or reject; limits are per user; configuration is per limiter instance. Non-functional: O(1) time per check, small memory per user, thread-safe, testable with a fake clock.

Rejected HTTP requests usually get status 429 Too Many Requests, often with a Retry-After header saying when to try again. See API design.

The five algorithms

1. Fixed window counter. Divide time into fixed windows (for example, each minute starting at :00). Count requests per user per window; reject when the count reaches the limit. One counter per user: tiny memory. The flaw is the boundary burst: a user can send the full limit at the end of one window and again at the start of the next.

limit 5 per 10 s
window 1 [0s, 10s)     window 2 [10s, 20s)
            | 5 at 9.0s | 5 at 10.0s |
            +-----------+------------+
 10 requests in one second, all allowed

2. Sliding log. Store the timestamp of every accepted request. On each request, drop timestamps older than one window, and allow only if fewer than the limit remain. Exact, but memory grows with the limit: a limit of 10,000 per hour stores up to 10,000 timestamps per user.

3. Sliding window counter. Keep only two counters: the current fixed window's count and the previous window's count. Estimate the number of requests in the last full window by assuming the previous window's requests were spread evenly:

estimate = previous * (fraction of previous window still inside
                       the sliding window) + current
fraction = (window - time elapsed in current window) / window

Two counters per user, close to sliding-log accuracy, no boundary burst. It is an approximation: if the previous window's requests were all bunched at its end, the estimate is too low; at its start, too high.

4. Token bucket. Each user has a bucket holding up to capacity tokens. Tokens are added at a steady refill rate, never beyond capacity. Each request takes one token; if none is available, reject. This allows bursts up to the capacity while enforcing the long-run average rate. Implementation detail: you do not need a timer to add tokens; on each request, compute how many tokens accrued since the last request (elapsed × rate), add them, cap at capacity.

5. Leaky bucket. Requests enter a queue (the bucket) of fixed size and leave at a constant rate, like water leaking from a hole. If the queue is full, new requests are dropped. Output is perfectly smooth, which protects a downstream system that cannot handle bursts, but requests wait in the queue, adding latency. A "leaky bucket as a meter" variant does not queue and behaves like a token bucket.

Worked example: token bucket

Capacity 5, refill 1 token per second. Asha's bucket starts full.

t = 0.0 s   tokens 5. 7 requests:
            5 allowed (tokens 5 -> 0), 2 rejected        YYYYYnn
t = 2.5 s   refill 2.5 s x 1/s = 2.5 tokens -> 2.5
            3 requests: allow (1.5), allow (0.5), reject YYn
            tokens left 0.5
Bharat at 2.5 s: his own full bucket                     YY
t = 60 s    refill 57.5 tokens, capped at 5
            7 requests: 5 allowed, 2 rejected            YYYYYnn

Even after a long idle period, the burst is limited to the capacity.

Worked example: sliding window counter

Limit 10 per 60 seconds. Dev's requests:

t = 30 s    window [0, 60): previous 0, current 0
            8 requests, estimates 1..8 all <= 10           YYYYYYYY
t = 65 s    new window [60, 120): previous = 8, current = 0
            elapsed 5 s, fraction = 55/60 = 0.9167
            base = 8 x 0.9167 = 7.33
            req 1: 7.33 + 0 + 1 = 8.33  <= 10 allow (current 1)
            req 2: 7.33 + 1 + 1 = 9.33  <= 10 allow (current 2)
            req 3: 7.33 + 2 + 1 = 10.33 >  10 reject
            req 4, 5: rejected                             YYnnn
t = 75 s    fraction 45/60 = 0.75: 8 x 0.75 + 2 = 6 + 2 = 8.00
            1 request: 9 <= 10 allow (current 3)           Y
t = 105 s   fraction 15/60 = 0.25: 8 x 0.25 + 3 = 2 + 3 = 5.00
            3 requests: 6, 7, 8 <= 10                      YYY

As time passes inside the new window, the old window's weight fades, freeing capacity gradually rather than all at once.

The boundary test

The demo sends 5 requests at 9.0 s and 5 at 10.0 s, with a limit of 5 per 10 s (the token bucket uses capacity 5 and refill 0.5 per second, the same long-run rate). The fixed window allows all 10, twice the intended rate, while the sliding log, sliding window counter and token bucket each allow only 5.

Design decisions and patterns

One interface, many algorithms

interface RateLimiter { boolean tryAcquire(String userId); }

Every algorithm implements it, so callers (an HTTP filter, an API gateway) do not change when you switch algorithms. This is the Strategy pattern again. You can also decorate a limiter (log rejections, emit metrics) with the Decorator pattern, or compose several (100 per minute and 1,000 per day) by checking each in turn.

Inject the clock

Every limiter takes a LongSupplier that returns the current time in milliseconds. Production passes System::currentTimeMillis (or a monotonic source such as System.nanoTime converted to milliseconds, which never jumps backwards when the system clock is adjusted). The demo passes a manual clock so every result is deterministic. Without this, testing "2.5 seconds later" requires sleeping and produces flaky tests.

Per-user state in a concurrent map

Each limiter keeps a ConcurrentHashMap<String, State>. computeIfAbsent atomically creates a user's state on first use, so two first requests from the same user cannot create two buckets.

Concurrency considerations

The race inside a limiter

The token bucket's check is a read-modify-write: read tokens, refill, check, subtract. Two threads doing this at once on the same bucket can both see 1 token and both subtract, allowing two requests for one token. This is the same check-then-act race as in the parking lot.

Locking granularity: one user at a time

The code uses synchronized (bucket) on the user's own state object. The demo's last section freezes the clock and fires 16,000 requests from 16 threads for one user at limits of 100: both limiters allow exactly 100. Without the per-bucket lock, the count would occasionally exceed 100.

Memory growth

Every user who ever sends a request gets an entry. A service with millions of users needs to remove idle entries: store a last-seen time and periodically remove entries idle for longer than the window (a full bucket or empty counter is equivalent to no entry), or keep the state in a cache with expiry.

Distributed rate limiting

With many application servers behind a load balancer, each server's in-memory limiter sees only part of a user's traffic. Options:

• Central store: keep counters in Redis. A fixed window is INCR key plus EXPIRE key window on first use. A token bucket or sliding window counter runs as a Lua script so the read-modify-write executes atomically on the Redis server.
• Local limits with a share of the global budget: each of N servers allows limit / N. No network calls, but uneven load balancing makes it inaccurate.
• Sticky routing: send each user to the same server so a local limiter sees all their traffic.

Discuss these as extensions; the in-process design is the same RateLimiter interface with a different implementation. See Scalability for the broader context.

Complete Java implementation

Save as CacheAndLimiterDemo.java, compile with javac CacheAndLimiterDemo.java and run java CacheAndLimiterDemo. Java 17 or later (it uses a switch expression).

import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.*;
import java.util.concurrent.locks.ReentrantLock;
import java.util.function.LongSupplier;

// ======================= LRU cache =======================

interface Cache<K, V> {
    V get(K key);                 // null if absent
    void put(K key, V value);
    int size();
}

/** HashMap for O(1) lookup + doubly linked list for O(1) recency updates. Not thread-safe. */
final class LRUCache<K, V> implements Cache<K, V> {
    private static final class Node<K, V> {
        final K key; V value; Node<K, V> prev, next;
        Node(K key, V value) { this.key = key; this.value = value; }
    }

    private final int capacity;
    private final Map<K, Node<K, V>> index = new HashMap<>();
    // Sentinels: head.next is the most recently used, tail.prev the least. No null checks needed.
    private final Node<K, V> head = new Node<>(null, null), tail = new Node<>(null, null);

    LRUCache(int capacity) {
        if (capacity <= 0) throw new IllegalArgumentException("capacity must be positive");
        this.capacity = capacity;
        head.next = tail; tail.prev = head;
    }

    public V get(K key) {
        Node<K, V> n = index.get(key);
        if (n == null) return null;
        unlink(n); addFront(n);                       // touched: now most recent
        return n.value;
    }

    public void put(K key, V value) {
        Node<K, V> n = index.get(key);
        if (n != null) { n.value = value; unlink(n); addFront(n); return; }
        if (index.size() == capacity) {
            Node<K, V> lru = tail.prev;                // evict least recently used
            unlink(lru);
            index.remove(lru.key);
        }
        n = new Node<>(key, value);
        index.put(key, n);
        addFront(n);
    }

    public int size() { return index.size(); }

    private void unlink(Node<K, V> n) { n.prev.next = n.next; n.next.prev = n.prev; }
    private void addFront(Node<K, V> n) { n.next = head.next; n.prev = head; head.next.prev = n; head.next = n; }

    /** Most recent first; for printing and for checking that list and map agree. */
    List<K> keysByRecency() {
        List<K> out = new ArrayList<>();
        for (Node<K, V> n = head.next; n != tail; n = n.next) out.add(n.key);
        return out;
    }
}

/** Thread-safe wrapper. get() reorders the list, so even reads need the exclusive lock. */
final class SynchronizedLRUCache<K, V> implements Cache<K, V> {
    private final LRUCache<K, V> inner;
    private final ReentrantLock lock = new ReentrantLock();
    SynchronizedLRUCache(int capacity) { inner = new LRUCache<>(capacity); }
    public V get(K k) { lock.lock(); try { return inner.get(k); } finally { lock.unlock(); } }
    public void put(K k, V v) { lock.lock(); try { inner.put(k, v); } finally { lock.unlock(); } }
    public int size() { lock.lock(); try { return inner.size(); } finally { lock.unlock(); } }
    List<K> keysByRecency() { lock.lock(); try { return inner.keysByRecency(); } finally { lock.unlock(); } }
}

/** The interview shortcut: LinkedHashMap in access order with an eviction hook. */
final class LinkedHashMapLRU<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;
    LinkedHashMapLRU(int capacity) { super(16, 0.75f, true); this.capacity = capacity; }  // true = access order
    @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { return size() > capacity; }
}

// ======================= Rate limiters =======================

interface RateLimiter {
    boolean tryAcquire(String userId);
}

/** Fixed window: count per user per window. Shown to expose the boundary burst. */
final class FixedWindowLimiter implements RateLimiter {
    private final int limit; private final long windowMs; private final LongSupplier clock;
    private final ConcurrentHashMap<String, long[]> state = new ConcurrentHashMap<>();   // {windowStart, count}
    FixedWindowLimiter(int limit, long windowMs, LongSupplier clock) { this.limit = limit; this.windowMs = windowMs; this.clock = clock; }

    public boolean tryAcquire(String user) {
        long now = clock.getAsLong(), start = now - now % windowMs;
        long[] s = state.computeIfAbsent(user, k -> new long[] { start, 0 });
        synchronized (s) {
            if (s[0] != start) { s[0] = start; s[1] = 0; }
            if (s[1] >= limit) return false;
            s[1]++;
            return true;
        }
    }
}

/**
 * Token bucket: each user has a bucket of up to `capacity` tokens, refilled continuously at
 * `refillPerSecond`. A request spends one token. Allows short bursts up to capacity.
 */
final class TokenBucketLimiter implements RateLimiter {
    private static final class Bucket {
        double tokens; long lastRefillMs;
        Bucket(double tokens, long now) { this.tokens = tokens; this.lastRefillMs = now; }
    }

    private final int capacity; private final double refillPerMs; private final LongSupplier clock;
    private final ConcurrentHashMap<String, Bucket> buckets = new ConcurrentHashMap<>();

    TokenBucketLimiter(int capacity, double refillPerSecond, LongSupplier clock) {
        if (capacity <= 0 || refillPerSecond <= 0) throw new IllegalArgumentException("positive values required");
        this.capacity = capacity; this.refillPerMs = refillPerSecond / 1000.0; this.clock = clock;
    }

    public boolean tryAcquire(String user) {
        long now = clock.getAsLong();
        Bucket b = buckets.computeIfAbsent(user, k -> new Bucket(capacity, now));   // new users start full
        synchronized (b) {                                                          // lock one user's bucket only
            long elapsed = Math.max(0, now - b.lastRefillMs);
            b.tokens = Math.min(capacity, b.tokens + elapsed * refillPerMs);
            b.lastRefillMs = Math.max(b.lastRefillMs, now);
            if (b.tokens < 1) return false;
            b.tokens -= 1;
            return true;
        }
    }

    double tokens(String user) { Bucket b = buckets.get(user); synchronized (b) { return b.tokens; } }
}

/**
 * Sliding window counter: keep this window's and the previous window's counts and weight the
 * previous one by how much of it still overlaps the last `window` milliseconds.
 */
final class SlidingWindowCounterLimiter implements RateLimiter {
    private static final class Counter { long windowStart; long current; long previous; }

    private final int limit; private final long windowMs; private final LongSupplier clock;
    private final ConcurrentHashMap<String, Counter> counters = new ConcurrentHashMap<>();

    SlidingWindowCounterLimiter(int limit, long windowMs, LongSupplier clock) {
        this.limit = limit; this.windowMs = windowMs; this.clock = clock;
    }

    public boolean tryAcquire(String user) {
        long now = clock.getAsLong(), start = now - now % windowMs;
        Counter c = counters.computeIfAbsent(user, k -> { Counter n = new Counter(); n.windowStart = start; return n; });
        synchronized (c) {
            if (start != c.windowStart) {                        // roll the windows forward
                c.previous = (start - c.windowStart == windowMs) ? c.current : 0;
                c.current = 0;
                c.windowStart = start;
            }
            double overlap = (windowMs - (now - start)) / (double) windowMs;   // share of previous window still inside
            double estimate = c.previous * overlap + c.current;
            if (estimate + 1 > limit) return false;
            c.current++;
            return true;
        }
    }

    double estimate(String user) {
        long now = clock.getAsLong(), start = now - now % windowMs;
        Counter c = counters.get(user);
        synchronized (c) { return c.previous * ((windowMs - (now - start)) / (double) windowMs) + c.current; }
    }
}

/** Sliding log: exact, but stores one timestamp per accepted request. */
final class SlidingLogLimiter implements RateLimiter {
    private final int limit; private final long windowMs; private final LongSupplier clock;
    private final ConcurrentHashMap<String, ArrayDeque<Long>> logs = new ConcurrentHashMap<>();
    SlidingLogLimiter(int limit, long windowMs, LongSupplier clock) { this.limit = limit; this.windowMs = windowMs; this.clock = clock; }

    public boolean tryAcquire(String user) {
        long now = clock.getAsLong();
        ArrayDeque<Long> log = logs.computeIfAbsent(user, k -> new ArrayDeque<>());
        synchronized (log) {
            while (!log.isEmpty() && log.peekFirst() <= now - windowMs) log.pollFirst();
            if (log.size() >= limit) return false;
            log.addLast(now);
            return true;
        }
    }
}

public class CacheAndLimiterDemo {
    static String burst(RateLimiter l, String user, int n) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) sb.append(l.tryAcquire(user) ? 'Y' : 'n');
        return sb.toString();
    }

    public static void main(String[] args) throws Exception {
        System.out.println("== 1. LRU cache, capacity 3 ==");
        LRUCache<String, Integer> lru = new LRUCache<>(3);
        lru.put("A", 1); lru.put("B", 2); lru.put("C", 3);
        System.out.println("after put A,B,C     " + lru.keysByRecency());
        System.out.println("get A = " + lru.get("A") + "           " + lru.keysByRecency());
        lru.put("D", 4);
        System.out.println("put D (evicts B)    " + lru.keysByRecency());
        System.out.println("get B = " + lru.get("B"));
        lru.put("C", 30);
        System.out.println("put C=30 (update)   " + lru.keysByRecency());
        lru.put("E", 5);
        System.out.println("put E (evicts A)    " + lru.keysByRecency());
        System.out.println("get C = " + lru.get("C") + ", get A = " + lru.get("A"));

        System.out.println("== 2. Same operations with LinkedHashMap ==");
        LinkedHashMapLRU<String, Integer> lhm = new LinkedHashMapLRU<>(3);
        lhm.put("A", 1); lhm.put("B", 2); lhm.put("C", 3); lhm.get("A"); lhm.put("D", 4);
        lhm.put("C", 30); lhm.put("E", 5);
        System.out.println("least to most recent " + lhm.keySet());

        System.out.println("== 3. Thread-safe LRU under 8 threads ==");
        SynchronizedLRUCache<Integer, Integer> shared = new SynchronizedLRUCache<>(100);
        ExecutorService pool = Executors.newFixedThreadPool(8);
        List<Future<?>> fs = new ArrayList<>();
        for (int t = 0; t < 8; t++) {
            final int seed = t;
            fs.add(pool.submit(() -> {
                Random r = new Random(seed);
                for (int i = 0; i < 50_000; i++) {
                    int k = r.nextInt(500);
                    if (r.nextBoolean()) shared.put(k, k * 10);
                    else { Integer v = shared.get(k); if (v != null && v != k * 10) throw new IllegalStateException("bad value"); }
                }
            }));
        }
        for (Future<?> f : fs) f.get();
        List<Integer> keys = shared.keysByRecency();
        System.out.println("size=" + shared.size() + ", list length=" + keys.size()
                + ", distinct keys in list=" + new HashSet<>(keys).size());

        AtomicLong now = new AtomicLong(0);                         // manual clock in milliseconds
        LongSupplier clock = now::get;

        System.out.println("== 4. Token bucket: capacity 5, refill 1 token/s ==");
        TokenBucketLimiter tb = new TokenBucketLimiter(5, 1.0, clock);
        System.out.println("t=0.0s  7 requests: " + burst(tb, "asha", 7));
        now.set(2_500);
        System.out.println("t=2.5s  3 requests: " + burst(tb, "asha", 3) + "  tokens left " + tb.tokens("asha"));
        System.out.println("t=2.5s  bharat 2 requests: " + burst(tb, "bharat", 2) + "  (separate bucket)");
        now.set(60_000);
        System.out.println("t=60s   7 requests: " + burst(tb, "asha", 7) + "  (refill is capped at 5)");

        System.out.println("== 5. Sliding window counter: 10 per 60 s ==");
        now.set(0);
        SlidingWindowCounterLimiter sw = new SlidingWindowCounterLimiter(10, 60_000, clock);
        now.set(30_000); System.out.println("t=30s  8 requests: " + burst(sw, "dev", 8));
        now.set(65_000); System.out.println("t=65s  5 requests: " + burst(sw, "dev", 5));
        now.set(75_000); System.out.printf("t=75s  estimate %.2f -> 1 request: %s%n", sw.estimate("dev"), burst(sw, "dev", 1));
        now.set(105_000); System.out.printf("t=105s estimate %.2f -> 3 requests: %s%n", sw.estimate("dev"), burst(sw, "dev", 3));

        System.out.println("== 6. Boundary burst: limit 5 per 10 s, 5 requests at 9.0 s and 5 at 10.0 s ==");
        for (String name : List.of("fixed window", "sliding log", "sliding counter", "token bucket")) {
            now.set(0);
            RateLimiter l = switch (name) {
                case "fixed window" -> new FixedWindowLimiter(5, 10_000, clock);
                case "sliding log" -> new SlidingLogLimiter(5, 10_000, clock);
                case "sliding counter" -> new SlidingWindowCounterLimiter(5, 10_000, clock);
                default -> new TokenBucketLimiter(5, 0.5, clock);
            };
            now.set(9_000); String a = burst(l, "u", 5);
            now.set(10_000); String b = burst(l, "u", 5);
            long allowed = (a + b).chars().filter(ch -> ch == 'Y').count();
            System.out.printf("%-16s 9.0s %s  10.0s %s  allowed in 1 s: %d%n", name, a, b, allowed);
        }

        System.out.println("== 7. 16 threads x 1,000 requests, one user, frozen clock ==");
        now.set(0);
        for (RateLimiter l : List.of(new TokenBucketLimiter(100, 10, clock), new SlidingWindowCounterLimiter(100, 60_000, clock))) {
            AtomicInteger ok = new AtomicInteger();
            List<Future<?>> jobs = new ArrayList<>();
            CountDownLatch go = new CountDownLatch(1);
            for (int t = 0; t < 16; t++) jobs.add(pool.submit(() -> {
                go.await();
                for (int i = 0; i < 1000; i++) if (l.tryAcquire("hot-user")) ok.incrementAndGet();
                return null;
            }));
            go.countDown();
            for (Future<?> f : jobs) f.get();
            System.out.println(l.getClass().getSimpleName() + ": allowed " + ok.get() + " of 16000");
        }
        pool.shutdown();
    }
}

Real output

This is the actual output from Temurin JDK 21:

== 1. LRU cache, capacity 3 ==
after put A,B,C     [C, B, A]
get A = 1           [A, C, B]
put D (evicts B)    [D, A, C]
get B = null
put C=30 (update)   [C, D, A]
put E (evicts A)    [E, C, D]
get C = 30, get A = null
== 2. Same operations with LinkedHashMap ==
least to most recent [D, C, E]
== 3. Thread-safe LRU under 8 threads ==
size=100, list length=100, distinct keys in list=100
== 4. Token bucket: capacity 5, refill 1 token/s ==
t=0.0s  7 requests: YYYYYnn
t=2.5s  3 requests: YYn  tokens left 0.5
t=2.5s  bharat 2 requests: YY  (separate bucket)
t=60s   7 requests: YYYYYnn  (refill is capped at 5)
== 5. Sliding window counter: 10 per 60 s ==
t=30s  8 requests: YYYYYYYY
t=65s  5 requests: YYnnn
t=75s  estimate 8.00 -> 1 request: Y
t=105s estimate 5.00 -> 3 requests: YYY
== 6. Boundary burst: limit 5 per 10 s, 5 requests at 9.0 s and 5 at 10.0 s ==
fixed window     9.0s YYYYY  10.0s YYYYY  allowed in 1 s: 10
sliding log      9.0s YYYYY  10.0s nnnnn  allowed in 1 s: 5
sliding counter  9.0s YYYYY  10.0s nnnnn  allowed in 1 s: 5
token bucket     9.0s YYYYY  10.0s nnnnn  allowed in 1 s: 5
== 7. 16 threads x 1,000 requests, one user, frozen clock ==
TokenBucketLimiter: allowed 100 of 16000
SlidingWindowCounterLimiter: allowed 100 of 16000

What to check:

1. The LRU states match the worked trace line by line.
2. LinkedHashMap gives the same contents in the opposite order.
3. After 400,000 concurrent operations, map size, list length and distinct list keys all equal 100.
4. The token bucket lines match the worked example, including 0.5 tokens left.
5. The sliding window counter estimates 8.00 and 5.00 match the hand calculation.
6. Only the fixed window lets 10 requests through around the boundary.
7. Under 16 threads, each limiter allows exactly its limit of 100.

Extensions interviewers ask

LRU with expiry (TTL). Store an expiry time in each node. get treats expired nodes as missing and removes them (lazy expiry). Optionally a background task or a second structure ordered by expiry removes them proactively.

LRU with size in bytes rather than count. Track total weight; evict from the tail until the new entry fits. Reject entries larger than the whole capacity.

Write-back or loading cache. On a miss, call a loader function and cache the result. Prevent a cache stampede (many threads loading the same missing key at once) by storing a future per key so only one thread loads and others wait for it.

Eviction listener. Notify an observer with the evicted key and value, for example to write dirty entries back to a database.

Rate limiter with tiers. Free users get 60 per minute, paid users 600: the limiter looks up the user's plan and uses per-plan parameters, or holds one limiter per tier.

Multiple limits at once. Per second and per day: a composite limiter that must pass all. Careful: if the second limit rejects, the first has already consumed a token. Either check all first and then consume, or accept that small over-counting.

Return retry time. Token bucket: time until one token accrues is (1 - tokens) / rate. Return it so the HTTP layer can set Retry-After.

Rate limiting by IP behind proxies. Use the client address from a trusted proxy header, not a header the client can forge.

Common mistakes

• LRU with an ArrayList or Queue for order, making removal O(n).
• Singly linked list, which cannot unlink a node in O(1) without its predecessor.
• Not storing the key in the node, so eviction cannot remove the map entry.
• Forgetting that put on an existing key must move it to the front.
• Using a read-write lock for LRU, not realising get mutates.
• Fixed window without mentioning the boundary burst.
• Running a timer thread per user to add tokens, instead of computing the refill lazily on each request.
• One global lock in the limiter, making the limiter itself the bottleneck.
• Calling System.currentTimeMillis() directly, making tests depend on real time; inject the clock.
• Unbounded per-user maps that grow forever.

Interview questions

Q1. Why does an LRU cache need both a hash map and a doubly linked list?

The map gives O(1) lookup by key. The doubly linked list keeps recency order and lets you unlink any node and insert at the front in O(1) when you already have the node. Neither alone gives O(1) for both get and put with eviction.

Q2. Why doubly linked and not singly linked?

To remove a node from the middle you must update its predecessor's next pointer. A singly linked list only lets you reach the predecessor by walking from the head, which is O(n). With a prev pointer it is O(1).

Q3. What are sentinel nodes and why use them?

They are permanent dummy head and tail nodes. Every real node always has non-null neighbours, so insert and unlink need no special cases for an empty list or the ends. This removes the most common pointer bugs.

Q4. How do you make the LRU cache thread-safe?

Guard every operation, including get, with one lock, because get reorders the list. For more throughput, split the cache into segments by key hash, each with its own lock, accepting that eviction is then per segment. A read-write lock does not help since there are no pure reads.

Q5. When would an interviewer disallow LinkedHashMap, and what do you say?

When the goal is to see you implement the structure. Mention it first, explain access order and removeEldestEntry, then implement the map plus list yourself. Note it is not thread-safe either.

Q6. How is LFU different from LRU, and how do you make it O(1)?

LFU evicts the least frequently used key rather than the least recent. O(1) LFU keeps a map from key to node, a map from frequency to a recency-ordered list, and the minimum frequency; access moves a node to the next frequency's list, and eviction removes the tail of the minimum-frequency list.

Q7. What is the boundary problem in fixed window rate limiting?

Counts reset at window boundaries, so a user can send the full limit just before a boundary and again just after it, getting twice the limit in a short span. Sliding windows and token buckets avoid it.

Q8. Explain the token bucket and how you refill without a timer.

A bucket holds up to capacity tokens and gains tokens at a fixed rate; each request spends one. On each request, compute the tokens earned since the last refill as elapsed time multiplied by rate, add them, cap at capacity, then try to spend one. No background thread is needed.

Q9. Token bucket versus leaky bucket?

Token bucket allows bursts up to capacity while limiting the average rate, and rejects excess immediately. Leaky bucket queues requests and releases them at a constant rate, smoothing output but adding latency. Use token bucket for user-facing APIs and leaky bucket to protect a backend that cannot handle bursts.

Q10. How does the sliding window counter approximate the sliding log?

It keeps only the current and previous fixed-window counts and weights the previous count by the fraction of that window that still lies within the last full window. It assumes requests in the previous window were evenly spread, so it is approximate, but it uses two counters instead of one timestamp per request.

Q11. How do you make a rate limiter thread-safe without a global lock?

Keep per-user state in a ConcurrentHashMap, create it with computeIfAbsent, and lock only that user's state object during the read-modify-write. Requests from different users never contend.

Q12. How would you rate limit across 20 servers?

Store counters centrally, typically in Redis, and run the algorithm atomically there with a Lua script or atomic increments with expiry. Alternatives are giving each server a share of the limit or routing each user to one server, both less accurate.

Q13. How do you stop the per-user map from growing forever?

Record each entry's last activity and periodically remove entries idle for longer than a window, since an idle user's state equals the default. Or store states in a cache with time-based expiry.

Q14. What should the client see when rate limited?

HTTP 429 Too Many Requests, ideally with a Retry-After header computed from the algorithm, such as the time until the next token. Clients should back off rather than retry immediately.

Key takeaways

• LRU = hash map for lookup + doubly linked list for order; sentinels remove edge cases; store the key in the node.
• In LRU, get writes; protect it with an exclusive lock or stripe the cache.
• Mention LinkedHashMap(…, true) with removeEldestEntry, then be ready to implement without it.
• LFU adds frequency buckets and a minimum-frequency pointer to stay O(1).
• Know all five rate limiting algorithms and the boundary burst that only fixed windows suffer.
• Token bucket refills lazily from elapsed time; sliding window counter weights the previous window.
• Lock per user, not per limiter; inject the clock; bound the per-user map.
• Distributed limits need a shared atomic store such as Redis with scripts.

Next lesson

Continue with Design a vending machine and an ATM.