Idempotency Key Handler

Start from brute force

The obvious first version answers each request by looking back: for request i, scan requests[0..i] from the start and return the value of the first request with the same key. It works because the first occurrence is, by definition, the result for that key, and an empty-string first value is handled correctly because nothing is tested for truthiness. It costs O(n²) time and O(1) extra space beyond the output. With all-distinct keys every scan runs all the way to i, so 100,000 requests take about 5 billion comparisons, and a real server would be rescanning its whole request history on every call.

The approach

The insight is that “first write wins” needs only one fact per key: the value its first request carried. Remember that fact in a hash map and every later request becomes a constant-time lookup instead of a scan. The invariant: after request i, store maps every key seen so far to the value from its first occurrence, and nothing else.

The reference keeps store = {} and out = []. For each key, value it tests membership with if key not in store and only then writes store[key] = value, so a retry can never overwrite the original. It then appends store[key], not value, to out: for a new key the two are the same, and for a replay it is the first result. Testing membership rather than truthiness matters, because a first value of "" must still win. One pass, one dict.

Walk through an example

The first example, one row per request: only a new key writes to store, and every row appends the stored value.

Complexity

Hash map: O(n) time for n requests, since each does one average O(1) membership test and at most one insert (hashing a key costs its length), and O(u) space for u distinct keys plus O(n) for out. Brute force: O(n²) time, because each request rescans everything before it, and O(1) extra space.

Edge cases to test

• An empty request list returns [].
• A falsy first value, [["k", ""], ["k", "x"]], returns ["", ""]. A truthiness check such as if not store.get(key) treats "" as missing, overwrites it, and returns ["", "x"].
• Interleaved keys, [["a", "1"], ["b", "2"], ["a", "9"], ["b", "8"]], return ["1", "2", "1", "2"]: each key keeps its own first result.
• Keys are compared exactly, so [["k1", "a"], ["K1", "b"]] returns ["a", "b"]: two keys that differ only in case are two different operations.
• An immediate replay with the same value, [["k", "v"], ["k", "v"]], returns ["v", "v"], and the second request must still be treated as a replay, not a new operation.

Common mistakes

• Writing store[key] = value on every request. Last write wins, and the first example returns ["a", "b", "c", "d"].
• Checking truthiness instead of membership (if not store.get(key)): an empty-string first value counts as missing and gets overwritten.
• Storing the response only after executing, with no atomicity — a concurrent retry then double-executes.
• No expiry on stored keys, so the store grows without bound.
• Keying on the wrong thing (the whole payload, or a value that changes between retries).

Follow-ups an interviewer asks next

Two copies of the same request arrive at the same moment on two servers.

The check and the write must be one atomic step, or both copies see “not stored” and both execute. Use an insert-if-absent on a shared store, such as a unique constraint on the key column or Redis SET key value NX, and record the key as “in progress” before doing the work. The loser of the race then waits for the stored result or gets a conflict error instead of executing.

The same key arrives with a different payload.

This handler silently returns the old result, which hides a client bug: the key was reused for a different operation. Store a hash of the request body next to the key and compare it on every replay. A match returns the stored response; a mismatch returns an error instead of a response that belongs to another request.

The store grows without bound. How do you expire keys?

Give each entry a time-to-live longer than the longest window in which a client might retry, and delete entries older than that, with a TTL in Redis or a periodic cleanup job in a database. Do not evict by memory pressure alone, as an LRU cache would: a key evicted early lets a late retry execute a second time.

The server crashes after charging the card but before storing the result.

Then the retry finds no key and charges again. When the side effect is local, write the key, the effect and the stored response in one database transaction. When it is a call to another service, record the key as started before the call and pass the same idempotency key downstream, so that service deduplicates the retry too.

Where this shows up

Idempotency keys are what make payment and order APIs safe to retry: the network will make a client resend after a timeout, and this handler guarantees “charge once” even when the request arrives twice. Stripe-style idempotency keys are the reference implementation of this pattern.

Reference solution

def process(requests):
    store = {}
    out = []
    for key, value in requests:
        if key not in store:
            store[key] = value        # first write wins
        out.append(store[key])        # replays return the first result
    return out


print(process([["k1","a"],["k1","b"],["k2","c"],["k1","d"]]))  # -> ['a', 'a', 'c', 'a']

function process(requests: string[][]): string[] {
  const store = new Map<string, string>();
  const out: string[] = [];
  for (const [key, value] of requests) {
    if (!store.has(key)) store.set(key, value);   // first write wins
    out.push(store.get(key)!);                     // replays return the first result
  }
  return out;
}

console.log(process([["k1","a"],["k1","b"],["k2","c"],["k1","d"]])); // -> ["a","a","c","a"]