Q4 - Idempotent Charges (Safe Retries at Checkout)

Scenario: Amazon's checkout runs over an unreliable network, so clients retry requests that may have already gone through. To stay safe, every charge carries an idempotency key: a token the client generates once per intended charge and reuses on every retry. You are building the service that applies these charges without ever double-charging.

Each request is [key, orderId, amount]. Process the stream in order, following three rules:

• New key: apply the charge (add amount to that orderId's running total) and remember the key with its (orderId, amount).
• Key seen before, same (orderId, amount): this is a retry. Ignore it (do not charge again), and count it as a safely deduplicated request.
• Key seen before, different (orderId, amount): the same key is being reused for a different request (a client bug or a replay). Reject it as a conflict, record the key, and change nothing.

Part 1: After the whole stream, return the total charged per orderId, the count of deduplicated retries, and the list of conflicting keys (in the order they were rejected).

Input:  requests = [
          ["k1", "o1", 30],
          ["k2", "o1", 20],
          ["k1", "o1", 30],
          ["k3", "o2", 15],
          ["k2", "o1", 25],
        ]
Output: totals = {"o1": 50, "o2": 15},  deduped = 1,  conflicts = ["k2"]
Why: k1 and k2 charge o1 (total 50). The second k1 is an exact retry, so it is ignored
        (deduped = 1). k3 charges o2 15. The last k2 reuses key k2 but with 25 instead of 20, so
        it is a conflict and is rejected.

Part 1: Modeling the State

The whole solution is one map plus two tallies:

• seen: a map from key to the (orderId, amount) it first charged. This is the memory that makes the service idempotent. Without storing what a key charged, you cannot tell a safe retry from a conflicting reuse.
• totals: a map from orderId to the amount charged so far, and a deduped counter and conflicts list for the two edge cases.

Each request is a single lookup in seen: not there means charge it, there and matching means retry, there and different means conflict. One O(n) pass.

In code the three rules are one three-way branch, the whole idempotency check:

if key not in seen:                      # new key: apply the charge
    seen[key] = (order_id, amount)
    totals[order_id] += amount
elif seen[key] == (order_id, amount):    # identical retry: ignore it
    deduped += 1
else:                                    # same key, different charge: conflict
    conflicts.append(key)

Here is the state after each request of Example 1. Watch a retry get absorbed and a conflict get rejected, both without moving a total:

request               seen (key -> orderId,amount)      totals          deduped  conflicts
-------------------------------------------------------------------------------------------
k1 o1 30  (new)       {k1:(o1,30)}                      o1:30           0        []
k2 o1 20  (new)       {k1:(o1,30), k2:(o1,20)}          o1:50           0        []
k1 o1 30  (retry)     unchanged                         o1:50           1        []
k3 o2 15  (new)       {..., k3:(o2,15)}                 o1:50  o2:15    1        []
k2 o1 25  (conflict)  unchanged                         o1:50  o2:15    1        [k2]
-------------------------------------------------------------------------------------------
final: totals {o1:50, o2:15},  deduped 1,  conflicts [k2]

# O(n) over the request stream | O(keys + orders) space
class ChargeProcessor:
    def __init__(self):
        self.seen = {}          # key -> (orderId, amount) it first charged
        self.totals = {}        # orderId -> total charged
        self.deduped = 0        # retries safely ignored
        self.conflicts = []     # keys reused for a different request

    def charge(self, key, order_id, amount):
        if key not in self.seen:                        # first time: apply it
            self.seen[key] = (order_id, amount)
            self.totals[order_id] = self.totals.get(order_id, 0) + amount
        elif self.seen[key] == (order_id, amount):      # identical retry: ignore
            self.deduped += 1
        else:                                           # same key, different request: conflict
            self.conflicts.append(key)

Part 2: When Keys Expire

Got Part 1? Here is the follow-up. In the real world you cannot remember every key forever, so an idempotency key has a lifetime. Model it the simplest useful way: the service remembers only the W most recently added keys. When a new key arrives and the memory already holds W keys, the oldest remembered key is forgotten.

A forgotten key loses its protection: if that same key shows up again, it looks brand-new and charges again. (Retries and conflicts are still detected, but only against keys that are still remembered.)

Input:  requests = [
          ["k1", "o1", 30],
          ["k2", "o1", 20],
          ["k3", "o1", 10],
          ["k1", "o1", 30],
        ],  W = 2
Output: totals = {"o1": 90},  deduped = 0,  conflicts = []
Why: After k1, k2, k3 the memory can hold only 2 keys, so k1 (the oldest) is forgotten.
        The final k1 is therefore treated as new and charges o1 again, giving 90. Under Part 1's
        unlimited memory that last k1 would have been a retry, leaving o1 at 60.

The clean way to age keys out is a FIFO queue of keys alongside seen. A new key is pushed on the back; when the memory is full, evict from the front and drop it from seen. Retries and conflicts never touch the queue, so keys expire in first-seen order, exactly W new keys after they arrived.

Only the new-key branch changes; a FIFO queue of keys rides alongside seen so the oldest can be evicted:

if key not in seen:
    if len(seen) == window:                # memory full: forget the oldest key
        del seen[order.popleft()]          # FIFO: evict the first-seen key
    seen[key] = (order_id, amount)
    order.append(key)                      # remember it as the newest
    totals[order_id] += amount
# the retry and conflict branches are exactly as in Part 1

Trace Example 2 with W = 2, watching the oldest key fall out of memory and let a repeat charge slip through:

W = 2                 remembered keys (oldest -> newest)   totals    note
------------------------------------------------------------------------------
k1 o1 30  (new)       [k1]                                 o1:30
k2 o1 20  (new)       [k1, k2]                             o1:50
k3 o1 10  (new)       [k2, k3]                             o1:60     memory full: k1 forgotten
k1 o1 30  (new again) [k3, k1]                             o1:90     k1 was forgotten -> charged again
------------------------------------------------------------------------------
final: totals {o1:90}   (with Part 1's unlimited memory this would be o1:60)

# O(n) over the request stream | O(W + orders) space
from collections import deque

class ChargeProcessor:
    def __init__(self, window):
        self.window = window
        self.seen = {}           # key -> (orderId, amount), at most `window` entries
        self.order = deque()     # keys in first-seen order, for eviction
        self.totals = {}
        self.deduped = 0
        self.conflicts = []

    def charge(self, key, order_id, amount):
        if key not in self.seen:
            if len(self.seen) == self.window:            # memory full: forget the oldest key
                del self.seen[self.order.popleft()]
            self.seen[key] = (order_id, amount)
            self.order.append(key)
            self.totals[order_id] = self.totals.get(order_id, 0) + amount
        elif self.seen[key] == (order_id, amount):
            self.deduped += 1
        else:
            self.conflicts.append(key)

Complexity Analysis

Time: O(n) for a stream of n requests. Each request is a constant number of hash-map operations (and, in Part 2, one queue push and at most one eviction).

Space: O(keys + orders) in Part 1. Part 2 caps the key memory at W, so it is O(W + orders): the whole reason to expire keys is to keep that memory bounded no matter how long the stream runs.

Final Notes

1. Idempotency means remembering the result, not just the key. Storing only "have I seen this key" lets you skip retries but blinds you to conflicts. Storing (orderId, amount) per key is what lets you catch a key reused for a different charge, and that is usually the point of the question.
2. A retry and a conflict look the same until you compare. Both are a repeated key. The whole safety of the system is in that comparison: same request means ignore, different request means reject. Say that distinction out loud.
3. Never mutate state on the unhappy paths. A retry and a conflict must both leave every total exactly as it was. The most common bug is letting a conflicting request still bump a counter or a total.
4. Bounded memory needs an eviction order. Part 2 is a small lesson in why a plain map is not enough: to forget the oldest key you need to track insertion order, so a FIFO queue rides alongside the map. That "map plus queue" shape shows up any time a cache has to forget things.

Do not let the short code fool you: the whole interview lives in the edge cases. A retry must not charge twice, a conflict has to be caught, a key eventually expires. Handle those and you have written payment code you would actually trust with real money. 🚀