Design an LRU Cache, Idempotent Payments and Other Classic Mini-Problems

Each design is short enough to write on a whiteboard. Each one also matches a pattern used in real production systems. The code samples below are JavaScript that you can run.

1. An LRU cache

Requirement: a cache with a fixed size. A cache is a small, fast store that keeps copies of recent results, so you do not have to compute or fetch them again. get(key) and put(key, value) must both take O(1) time. O(1) ("constant time") means the work does not grow, however big the cache is. When the cache is full, evict (remove) the least recently used entry. "LRU" stands for least recently used.

The data structure

• A hash map (in JavaScript, a Map) is a structure that finds a value from its key in O(1) time.
• A doubly linked list is a chain of nodes where each node points to both the next and the previous node. Here it keeps the entries in order of use. The most recent entry is at the head. The least recent entry is at the tail. Moving a node to the head, or removing the tail, takes O(1) time because you already hold the node and its neighbours.

map: key → nodelist: head ⇄ (most recent) ⇄ … ⇄ (least recent) ⇄ tailget(k):  find node via map → move to head → return valueput(k):  if exists: update, move to head         else: create node at head; if size > capacity: remove tail, delete its key from the map

A singly linked list (one link per node) cannot remove a node from the middle in O(1) time, because you need the previous node. This is why the list is doubly linked.

class LRUCache {  constructor(capacity) {    this.capacity = capacity;    this.map = new Map();    this.head = { prev: null, next: null };   // sentinels (empty marker nodes) simplify edge cases    this.tail = { prev: null, next: null };    this.head.next = this.tail;    this.tail.prev = this.head;  }  _remove(node) { node.prev.next = node.next; node.next.prev = node.prev; }  _addToFront(node) {    node.next = this.head.next; node.prev = this.head;    this.head.next.prev = node; this.head.next = node;  }  get(key) {    const node = this.map.get(key);    if (!node) return undefined;    this._remove(node); this._addToFront(node);    return node.value;  }  put(key, value) {    let node = this.map.get(key);    if (node) { node.value = value; this._remove(node); this._addToFront(node); return; }    node = { key, value, prev: null, next: null };    this.map.set(key, node);    this._addToFront(node);    if (this.map.size > this.capacity) {      const lru = this.tail.prev;             // least recently used      this._remove(lru);      this.map.delete(lru.key);    }  }}const c = new LRUCache(2);c.put("a", 1); c.put("b", 2);console.log(c.get("a"));        // 1   (a is now most recent)c.put("c", 3);                  // evicts b, the least recently usedconsole.log(c.get("b"));        // undefinedconsole.log(c.get("c"));        // 3c.put("a", 10);                 // update moves a to the frontc.put("d", 4);                  // evicts cconsole.log(c.get("c"), c.get("a"), c.get("d")); // undefined 10 4

The JavaScript shortcut

A JavaScript Map remembers the order in which keys were added. So if you delete a key and add it again, it moves to the "most recent" place:

class TinyLRU {  constructor(cap) { this.cap = cap; this.m = new Map(); }  get(k) {    if (!this.m.has(k)) return undefined;    const v = this.m.get(k);    this.m.delete(k); this.m.set(k, v);                  // refresh recency    return v;  }  put(k, v) {    this.m.delete(k); this.m.set(k, v);    if (this.m.size > this.cap) this.m.delete(this.m.keys().next().value);   // oldest key  }}const t = new TinyLRU(2);t.put("a", 1); t.put("b", 2); t.get("a"); t.put("c", 3);console.log([...t.m.keys()].join(","));                  // a,c

Mention both versions in an interview. The linked list version shows that you know why it is O(1). The Map version is what you would use in a small helper in real code.

Production considerations

• Thread safety: a thread is one line of execution inside a program. JavaScript runs your code on one thread, so two get calls never run at the same instant. In languages with many threads you need locks (a lock lets only one thread use the data at a time), or you split the cache into parts (sharding, so each part has its own lock).
• TTL (time to live, a time after which an entry expires) on top of LRU. Measure size in bytes, not in number of entries, when values have different sizes.
• Variants: LFU (least frequently used: evict the entry with the fewest uses), 2Q and ARC (which keep separate lists for "seen once" and "seen often"), and TinyLFU (used by modern caches such as Caffeine). They resist scans: one pass over many rarely used keys that would fill an LRU cache with useless data.
• Redis (a fast in-memory data store) has an approximate LRU/LFU. You set it with the maxmemory-policy setting (allkeys-lru, allkeys-lfu). It checks a few sample keys instead of tracking the exact order.

2. Idempotent payments

Problem: a network timeout leaves the client unsure if the payment went through. A retry must not charge the customer twice. Idempotent means that doing an operation many times has the same effect as doing it once. (PUT /user/1 {name: "A"} is idempotent. "Add 10 to the balance" is not.) (This is covered more in Backend, Lesson 02 and Debugging, Lesson 05.)

Design

1. The client creates an idempotency key (a unique value, usually a UUID, which is a random 128-bit id) once for each payment the user intends to make (not for each HTTP retry). It sends the key as the Idempotency-Key header. Retries use the same key.
2. The server has a table with a unique constraint (a database rule that refuses a second row with the same values) on (account_id, key).
3. For each request, the server tries to insert the key with the status IN_PROGRESS and a fingerprint of the request (a hash of the body: a short value that is always the same for the same input and almost surely different for different input). Then there are five cases:
   • The insert works. This request owns the work. Call the payment provider with the same key, save the result and mark it COMPLETED.
   • The key exists, it is COMPLETED and the fingerprint is the same. Return the saved response. There is no new charge.
   • The key exists and it is IN_PROGRESS. Return 409 (or wait a short time). Another request is already doing the work.
   • The key exists and it is FAILED (the provider clearly refused). Return the saved error. A new try needs a new key.
   • The key exists but the fingerprint is different. Return 422. The key was reused for a different request.
4. Pass the key to the payment provider too (Stripe and others support idempotency keys). (The payment provider is the outside company, such as Stripe, that really moves the money.) Then, even if your server crashes after it calls the provider but before it saves the result, a retry cannot make a second charge. If a server crashes while the row is IN_PROGRESS, the row would block that key forever. Store a locked_at time. After a timeout, a retry may take over the row and call the provider again with the same key.
5. Let keys expire after some time (for example 24 hours) and clean them up.

CREATE TABLE idempotency_keys (  account_id   uuid NOT NULL,  key          text NOT NULL,  request_hash text NOT NULL,  status       text NOT NULL,              -- IN_PROGRESS | COMPLETED | FAILED  response     jsonb,  locked_at    timestamptz,                -- when the current owner started the work  created_at   timestamptz NOT NULL DEFAULT now(),  PRIMARY KEY (account_id, key));

The payment as a state machine

A state machine is a model where a thing is always in exactly one state, and only some moves between states are allowed. In the diagram, authorize means "check the card and reserve the money", capture means "take the reserved money", void means "cancel a reservation" and refund means "give captured money back".

CREATED ──authorize──▶ AUTHORIZED ──capture──▶ CAPTURED ──refund──▶ REFUNDED   │                        │   └───fail───▶ FAILED      └──void──▶ VOIDED

Allow only the legal moves. Enforce this with a conditional update (UPDATE payments SET status = 'CAPTURED' WHERE id = $1 AND status = 'AUTHORIZED', then check how many rows changed). Then repeated or parallel attempts cannot corrupt the state. Write every change into an append-only ledger (a log where you only add lines and never edit them). Use double-entry bookkeeping (every money move is written twice, as a debit from one account and a credit to another, so the books always add up). Store amounts as integers in the smallest unit (for example cents), because decimal fractions such as 0.1 cannot be stored exactly in floating-point numbers.

Reliability extras

• Reconciliation job: a scheduled job that compares your records with the provider's daily report, and fixes any differences.
• Webhooks (HTTP calls that the provider sends to your server when something happens) can also arrive more than once. Remove duplicates by event ID.
• Timeouts: treat a timeout as unknown, never as a failure. Find out the real result by asking the provider with the key.

3. Retries with exponential backoff and jitter

A retry means trying a failed operation again. Rule: retry only temporary failures (timeouts, connection resets, 429 Too Many Requests, 502/503/504 gateway or service errors). Retry only idempotent operations, or ones that an idempotency key protects. Never retry 400, 401, 403 or 422 (the request itself is wrong, so it will fail again).

Why not retry immediately?

Imagine a service is overloaded and 1,000 clients all retry at once. This makes things worse. It is called a retry storm. Exponential backoff doubles the wait after each failed try (1 s, 2 s, 4 s, 8 s…), so the retries are spaced out more and more. Jitter (a random amount added to the wait) stops clients from retrying all at the same moment. That problem is called the thundering herd (many clients acting together). In the formula, base is the first wait, cap is the longest allowed wait, and attempt counts the tries so far.

Full jitter is a widely used method:

delay = random(0, min(cap, base × 2^attempt))

function backoffDelay(attempt, { base = 100, cap = 5000 } = {}) {  const ceiling = Math.min(cap, base * 2 ** attempt);  return Math.random() * ceiling;              // full jitter: anywhere between 0 and the ceiling}async function retry(fn, { retries = 4, base = 100, cap = 5000, isRetryable = () => true } = {}) {  let lastError;  for (let attempt = 0; attempt <= retries; attempt++) {    try {      return await fn(attempt);    } catch (e) {      lastError = e;      if (attempt === retries || !isRetryable(e)) break;      await new Promise((r) => setTimeout(r, backoffDelay(attempt, { base, cap })));    }  }  throw lastError;}// Demo: fails twice, then succeeds (top-level await works in an ES module, such as a .mjs file)let calls = 0;const result = await retry(async () => {  calls++;  if (calls < 3) throw Object.assign(new Error("503"), { transient: true });  return "ok after " + calls + " calls";}, { base: 5, cap: 20, isRetryable: (e) => e.transient });console.log(result);                                          // ok after 3 calls// The delay ceiling doubles but never exceeds the capconst ceilings = [0, 1, 2, 3, 4, 5, 6].map((a) => Math.min(5000, 100 * 2 ** a));console.log(ceilings.join(","));                              // 100,200,400,800,1600,3200,5000

Good habits for production:

• Obey Retry-After (a response header in which the server says how many seconds to wait) when the server sends it.
• Set a limit on total time (a deadline), not only on the number of attempts. Pass the deadline on to the services you call.
• Retry budgets: allow retries for only a small part of the traffic (for example 10%). Then retries cannot multiply the load.
• Circuit breaker: a wrapper that watches a dependency. After many failures it "opens the circuit" and fails fast (it returns an error at once, without calling the dependency) for a cool-down time. Then it lets a few requests through ("half-open") to test the dependency. This stops you from wasting resources on a dead service (Backend, Lesson 04).
• Do not retry at every layer. With 3 layers and 3 attempts each, you make 27 calls. Retry in one layer only. Usually this is the outermost caller, because it understands idempotency.
• Log and measure the attempts, the final results and the retry rate.

Job queues with retries

A job queue is a waiting line of background tasks, and a worker is a program that takes tasks from it. It is used for background jobs (emails, webhooks, image processing):

queue ─▶ worker takes job (it becomes invisible for a "visibility timeout")          ├─ success → delete the job          └─ failure → job reappears after the timeout (or is re-enqueued with a delay = backoff)                       after N attempts → move to the dead-letter queue (DLQ) + alert

• At-least-once delivery means a job is never lost but can arrive more than once. (At-most-once means it may be lost but never repeats. Exactly-once is very hard to get, so we use at-least-once plus idempotency.) So consumers must be idempotent. Use the job ID as an idempotency key, or check the state first.
• Visibility timeout: the time a taken job stays hidden from other workers. Make it longer than a normal run of the job. For long jobs, send heartbeats (small "I am still working" signals).
• Poison messages (messages that always fail) must not block the queue. The dead-letter queue (DLQ) keeps them apart so that you can look at them and replay them.
• Delayed retries: use a delay queue or scheduled messages. Store attempts and nextRunAt.
• Order and concurrency: limit the parallel work for each tenant (one customer of a system that serves many customers), so that one busy tenant does not hurt the others (the "noisy neighbour" problem).

4. Feature flags

Requirement: turn features on or off, or roll them out to a percentage of users, without a new deploy. A deploy is putting new code on the servers. Support targeting (choosing who gets the feature by rules, such as staff first, then 5%, then 50%) and an instant kill switch (a flag that turns a feature off at once).

Flag types

• Release flags: hide unfinished or risky code. They live for a short time.
• Experiment flags: A/B tests (showing version A to one group and version B to another, to see which works better). Each user is always put in the same group.
• Ops flags / kill switches: turn a feature off during high load or an incident.
• Permission flags: features that depend on a plan or a customer.

Evaluation

isEnabled(flagKey, user):  1. flag disabled globally?            → false  2. user in an explicit deny/allow list? → that answer  3. rule matches (country = IN, plan = pro, internal staff…)? → rule's answer  4. percentage rollout: bucket = hash(flagKey + userId) mod 100; enabled if bucket < percent  5. otherwise default

The key idea is stable hashing. A hash function turns text into a number, and the same text always gives the same number. A bucket is one of 100 slots (0 to 99) that a user falls into. A rollout is turning a feature on for more and more users step by step. This gives two benefits:

• The same user gets the same answer every time. The feature does not flicker between on and off.
• When you raise the percentage from 10 to 20, the first 10% stay enabled. You only add users.

Hash flagKey + userId to get both. Adding the flag key also puts each flag's rollout in a different random slice of users. Otherwise "the same unlucky 5%" would see every new feature.

// A small, fast, deterministic 32-bit hash (FNV-1a). Deterministic = same input, same outputfunction hash32(str) {  let h = 0x811c9dc5;  for (let i = 0; i < str.length; i++) {    h ^= str.charCodeAt(i);    h = Math.imul(h, 0x01000193) >>> 0;  }  return h >>> 0;}const bucket = (flag, userId) => hash32(`${flag}:${userId}`) % 100;function isEnabled(flag, user) {  if (!flag.enabled) return false;  if (flag.denyUsers?.includes(user.id)) return false;  if (flag.allowUsers?.includes(user.id)) return true;  if (flag.rules?.some((r) => user[r.attr] === r.equals)) return true;  return bucket(flag.key, user.id) < (flag.percent ?? 0);}const flag = { key: "new-checkout", enabled: true, percent: 10, allowUsers: ["staff-1"], rules: [{ attr: "plan", equals: "enterprise" }] };// Stable: same user, same answer, every timeconsole.log(isEnabled(flag, { id: "u42" }) === isEnabled(flag, { id: "u42" }));   // true// Monotonic (only goes one way): raising 10% → 25% never turns anyone OFFconst users = Array.from({ length: 5000 }, (_, i) => ({ id: "u" + i }));const at10 = users.filter((u) => isEnabled({ ...flag, percent: 10 }, u));const at25 = users.filter((u) => isEnabled({ ...flag, percent: 25 }, u));console.log(at10.every((u) => at25.includes(u)));                                   // true// Roughly the right sizeconsole.log(Math.abs(at10.length / 5000 - 0.10) < 0.02);                            // trueconsole.log(isEnabled(flag, { id: "staff-1" }), isEnabled(flag, { id: "x", plan: "enterprise" })); // true true

Architecture

Admin UI ─▶ Flag service (DB + audit log) ─▶ publishes changes                                                  │        SDK (a code library you add to your app) in each app: loads all flag rules, caches in memory, subscribes to updates (server-sent events or polling),        evaluates LOCALLY (no network call per check)

• Check flags locally with cached rules (a cache here is a copy of the rules kept in the app's memory). A flag check on every request must not add a network call.
• Safe defaults: if the flag service cannot be reached, use the last rules you know, or a default written in code for each flag. Usually the default is "off" for new features and "on" for kill switches that protect the old behaviour.
• Same answers in frontend and backend: decide on the server and send the final values to the client. Then the client does not need the rules, and users cannot change them. Or use an SDK on both sides with the same hash.
• Audit log: record who changed what and when. Use permissions to control who can change production flags.
• Flag hygiene (keeping flags clean): every release flag has an owner and an end date. After the rollout, remove the flag and the dead code. Old flags are tech debt (shortcuts that leave extra work for later) and cause bugs. Test both branches.
• Rollout steps: staff, then 1%, 10%, 50% and 100%. Watch error rates and latency all the time, and keep the kill switch ready.
• Do not use flags for authorization (deciding what a user is allowed to do). Permissions and security belong in your access control code.

Common mistakes

1. An LRU cache with a singly linked list (removals take O(n)), or one that does not move the entry on get.
2. Idempotency keys made for each click or each retry, instead of each intended payment.
3. Treating a payment timeout as a failure and retrying with a new key.
4. Retrying at once with no backoff or jitter, and retrying calls that are not idempotent.
5. Retries at every layer, which multiply the load.
6. No DLQ, so one poison message blocks the queue forever.
7. Random (not hashed) percentage rollouts, which flicker on each request.
8. Flag checks over the network on every request, and flags that are never cleaned up.

Interview questions

Key takeaways

• LRU: a hash map plus a doubly linked list gives O(1) get and put. In JS, a Map can do it by deleting and adding the key again.
• Idempotent payments: one key per intended payment (reused on retries), a unique constraint, a fingerprint, a saved response, the key passed to the provider, a state machine, and timeouts treated as "unknown".
• Retries: only for temporary failures and idempotent calls. Use exponential backoff with full jitter, deadlines, budgets, circuit breakers, DLQs and idempotent consumers.
• Feature flags: local checks, stable hashing of flag key plus user for percentage rollouts, targeting, a kill switch, safe defaults, an audit log and cleanup.

What's next

That completes Practical Design Problems. Continue with Senior Frontend Depth for React internals, TypeScript and testing. Or review the big picture in the System Design series.