Q3 - Stripe Idempotency Keys & Safe Retries Problem

As a Backend Engineer at Stripe, you work on the API layer behind write endpoints like POST /v1/charges and POST /v1/payment_intents. The internet is unreliable: a client fires a request, the connection drops before the response comes back, and the client retries. Without a safety net, that retry creates a second charge and double-bills the cardholder.

Stripe's answer is the Idempotency-Key header. The client attaches a unique key to each logical operation, and the server promises that any replay of that key returns the original result instead of running the operation again. Your task is to build that idempotency layer from the ground up.

This problem comes in three progressive parts. You will start with basic replay, then make keys expire on a time window, and finally detect the conflict case where a client reuses a live key with different parameters. Each part builds directly on the previous one.

Part 1: Idempotent Replay (~10 minutes)

You need to implement a function that processes a sequence of incoming write requests and returns the response each caller receives. Each request is a pair (idempotency_key, amount), processed in order.

The function should:

• Execute a request with a brand new key: record the response (here, the amount) under that key and return it.
• Replay a request whose key was already seen: return the stored response from the first time, without executing again.
• Treat an empty key ("") as "no idempotency key": always execute, and never store it.
• Return the list of responses in the same order as the requests.

Input:
requests = [
  ("key_a", 1000),
  ("key_b", 500),
  ("key_a", 1000),   # a retry of key_a
]

Output: [1000, 500, 1000]
Explanation: key_a is stored on its first use (1000). key_b is new (500). The third
request replays key_a, so it returns the stored 1000 instead of charging the customer again.

Input:
requests = [
  ("", 700),
  ("", 700),
]

Output: [700, 700]
Explanation: An empty idempotency key means "no key", so every request executes. Two
un-keyed charges of 700 create two separate charges.

Input:
requests = [
  ("key_a", 1000),
  ("key_a", 9999),   # same key, different amount
]

Output: [1000, 1000]
Explanation: In Part 1, a repeated key always returns the original stored response
(1000), even when the caller sends a different amount. We revisit this exact case in Part 3.

Solution - Part 1

The whole problem is a hash map keyed by the idempotency key. On a new key you execute and remember the response; on a known key you return what you remembered. The only twist is the empty key, which bypasses the store entirely.

def process_requests(requests: list) -> list:
    store = {}            # idempotency_key -> stored response
    responses = []

    for key, amount in requests:
        if key and key in store:
            # Replay: return the response we stored the first time.
            responses.append(store[key])
        else:
            # New key (or no key): execute and remember it.
            if key:
                store[key] = amount
            responses.append(amount)

    return responses

Complexity Analysis

• Time Complexity: O(n), where n is the number of requests. Each request is a single hash-map lookup and insert.
• Space Complexity: O(k), where k is the number of distinct idempotency keys we store.

Part 2: Key Expiration with TTL (~15 minutes)

Real idempotency keys do not live forever. Stripe expires them after a fixed time-to-live (about 24 hours in production). After that, the same key is free to be reused for a genuinely new operation.

Each request now carries a timestamp, so a request is a triple (idempotency_key, amount, ts), and you are given a ttl. The rule: a key is live if the current request arrives within ttl seconds of when the key was first stored. If a known key arrives after it has expired (more than ttl seconds since it was stored), execute the request again and overwrite the stored entry. Crucially, the window is fixed from the moment the key is first stored: a replay does not extend it.

Input: ttl = 3600
requests = [
  ("key_a", 1000, 1000),
  ("key_a", 2000, 2000),
  ("key_a", 3000, 5000),
  ("key_a", 4000, 6000),
]

Output: [1000, 1000, 3000, 3000]
Explanation:
- t=1000: new key, execute and store 1000.
- t=2000: 1000 seconds later, still within the 3600 window, replay 1000.
- t=5000: 4000 seconds after creation, past the window, so the key expired: re-execute and store 3000.
- t=6000: 1000 seconds after the new entry, live again, replay 3000.

Input: ttl = 100
requests = [
  ("key_x", 50, 0),
  ("key_x", 77, 100),
]

Output: [50, 50]
Explanation: 100 seconds is exactly the ttl, which still counts as live (we only expire
when the gap is strictly greater than ttl), so the second request replays the original 50.

Solution - Part 2

Store the creation timestamp alongside the response. On a known key, compare ts - created_ts against ttl. If it is strictly greater, the key has expired, so you re-execute and overwrite (resetting the creation time). Otherwise you replay. The boundary detail, "strictly greater than ttl expires," is the kind of off-by-one Stripe loves to test.

def process_requests(requests: list, ttl: int) -> list:
    store = {}            # key -> (stored_amount, created_ts)
    responses = []

    for key, amount, ts in requests:
        if key and key in store:
            stored_amount, created_ts = store[key]
            if ts - created_ts > ttl:
                # Expired: treat as a brand new request.
                store[key] = (amount, ts)
                responses.append(amount)
            else:
                # Still live: replay the original response.
                responses.append(stored_amount)
        else:
            if key:
                store[key] = (amount, ts)
            responses.append(amount)

    return responses

Complexity Analysis

• Time Complexity: O(n), where n is the number of requests. Each one is still constant work.
• Space Complexity: O(k), for the live keys we track. (In production you would also evict expired entries to bound memory.)

Part 3: Parameter Conflict Detection (~25 minutes)

Here is the behavior that actually ships at Stripe. If a client reuses a live idempotency key but sends different parameters, that is almost certainly a bug on their side (two different operations sharing one key). Stripe refuses to guess: it rejects the request with an HTTP 409 conflict rather than silently returning the old result.

Extend Part 2 so that, for a live key, you compare the incoming amount to the stored one:

• Same parameters: it is a genuine retry, so replay the stored response.
• Different parameters: return -1 to represent the 409 conflict (and do not overwrite the stored entry).
• Expired key: this is a clean new request, so re-execute regardless of parameters.
• Empty key: always execute, as before.

Input: ttl = 3600
requests = [
  ("key_a", 1000, 1000),
  ("key_a", 1000, 2000),
  ("key_a", 2000, 2500),
  ("key_a", 9999, 9000),
  ("key_a", 1234, 9500),
  ("",      5000, 9600),
]

Output: [1000, 1000, -1, 9999, -1, 5000]
Explanation:
- t=1000: new key, execute and store 1000.
- t=2000: live key, same amount, safe replay of 1000.
- t=2500: live key, different amount (2000 vs the stored 1000), conflict, return -1.
- t=9000: 8000 seconds after creation, the key expired, so re-execute and store 9999.
- t=9500: live key, different amount (1234 vs 9999), conflict, return -1.
- t=9600: empty key, always execute, return 5000.

Input: ttl = 3600
requests = [
  ("key_b", 250, 0),
  ("key_b", 250, 10),
  ("key_b", 251, 20),
]

Output: [250, 250, -1]
Explanation: The first stores 250. The second is an identical live retry (replay 250).
The third reuses the live key with 251, one cent off, which is a conflict (-1). A single
mismatched field is enough to reject.

Solution - Part 3

The structure is identical to Part 2, with one extra branch inside the "live key" case: compare parameters and reject on mismatch. The ordering of the checks matters. Test expiry first (an expired key is always a clean slate), and only compare parameters when the key is still live.

def process_requests(requests: list, ttl: int) -> list:
    store = {}            # key -> (stored_amount, created_ts)
    responses = []

    for key, amount, ts in requests:
        if key and key in store:
            stored_amount, created_ts = store[key]
            if ts - created_ts > ttl:
                # Expired: a fresh request reuses the key cleanly.
                store[key] = (amount, ts)
                responses.append(amount)
            elif amount == stored_amount:
                # Live and identical: safe replay.
                responses.append(stored_amount)
            else:
                # Live but different parameters: reject (HTTP 409).
                responses.append(-1)
        else:
            if key:
                store[key] = (amount, ts)
            responses.append(amount)

    return responses

Complexity Analysis

• Time Complexity: O(n), where n is the number of requests. The added parameter comparison is constant work.
• Space Complexity: O(k), for the keys currently tracked. In production the stored "fingerprint" would be a hash of the full request body, not a single amount.

Final Notes

Here is what separates a clean pass from a near miss on this one:

1. The state creeps up on you: Part 1 is a five-line hash map and most candidates fly through it. The difficulty is not any single part, it is keeping the same data structure correct as you bolt on a timestamp in Part 2 and a comparison in Part 3. Build Part 1 so it is easy to extend, and the later parts become small edits instead of rewrites.

2. Fixed window, not sliding: The TTL is measured from when the key was first stored, not from the last time it was touched. It is very common to accidentally refresh the timestamp on every replay, which turns a 24-hour key into one that never expires under steady traffic. Decide this out loud and get it right.

3. Expiry is checked before conflict: In Part 3 the order of branches is the one thing you have to get right. An expired key is a clean slate, so it can never be a conflict, even if the parameters differ. Check expiry first, then compare parameters only for live keys. Swap that order and you will return a spurious 409 on a perfectly valid reuse of an old key.

4. The empty key is a real test case, not a footnote: A missing or empty idempotency key means "do not deduplicate", so it must execute every time and never be written to the store. Candidates who special-case it cleanly look far more senior than those who let "" collide in the map.

5. Talk in payments, not just code: Stripe interviewers light up when you connect the logic to the stakes: "if I get this wrong, a customer gets charged twice." Mention that production keys store a fingerprint of the whole request body, that you would persist the store (not keep it in memory), and that real systems also handle the in-flight case where the first request has not finished yet. You do not have to implement those, but naming them shows you have built real APIs.

The bottom line: this question is less about algorithms and more about whether you can model mutable state precisely and reason about time and edge cases the way a payments engineer has to every day. Get the boundaries and the branch order right, narrate the customer impact, and you will hit the bull's eye.