Double-Tap Pay Button
A food delivery app has a "Pay" button. People double-tap it, and on a weak connection the app retries a request whose reply was lost, even though the charge went through. To stop double charges, the app sends a random idempotency key with each payment attempt and reuses the same key for every retry of that attempt. The payment service remembers each key: the first request runs, a repeat gets the saved reply, and a repeat that arrives while the first is still running is told to wait.
This is the idempotency-key store from Idempotency and Retries, used in front of any write that must not happen twice (see Design a Payment System).
Your task
Write a class IdempotencyStore. Each key has at most one live record; a record made at time s is live while t < s + ttlMs and is treated as gone from s + ttlMs on.
constructor(ttlMs).begin(key, fingerprint, t): a request arrives at timet.fingerprintsummarizes the request body. Return:"run"if the key has no live record. Create one (in progress, made att); the caller now performs the payment."conflict"if the live record has a different fingerprint: the same key was reused for a different request."wait"if the live record has the same fingerprint and is still in progress.- the saved response if the live record has the same fingerprint and is finished.
finish(key, response, t): the payment finished. If the key has a live record that is in progress, saveresponseon it and mark it finished. Otherwise do nothing.release(key, t): the payment failed in a way that is safe to retry. If the key has a live record that is in progress, delete it. Otherwise do nothing.
Expiry counts from when the record was created by begin, whether or not it has finished.
class IdempotencyStore
Examples
new IdempotencyStore(60000)
.begin("k1", "pay 45 card 4242", 0)
.begin("k1", "pay 45 card 4242", 100)
.finish("k1", "201 paid #7", 250)
.begin("k1", "pay 45 card 4242", 300)
.begin("k1", "pay 99 card 4242", 400)[null, "run", "wait", null, "201 paid #7", "conflict"]
The first tap creates the record and runs the payment. The second tap, 100 ms later, finds it still in progress: "wait", so the card is not charged twice. At 250 the payment finishes and the reply is saved. A retry at 300 gets that exact reply back without charging again. At 400 the same key arrives with a different amount, which is a bug in the client, so it is refused.
new IdempotencyStore(1000)
.begin("a", "x", 0)
.finish("a", "201 ok", 10)
.begin("a", "x", 999)
.begin("a", "x", 1000)
.begin("b", "y", 1000)
.release("b", 1005)
.begin("b", "y", 1006)[null, "run", null, "201 ok", "run", "run", null, "run"]
Key "a" was made at 0 with a TTL of 1,000, so at 999 it still replays "201 ok", and at 1,000 it is gone and the request runs again. That is why the TTL must be longer than any client keeps retrying. Key "b" fails safely and is released, so the retry at 1,006 runs.
Constraints
- 1 ≤ ttlMs ≤ 1,000,000,000
- 0 ≤ t ≤ 1,000,000,000,000, and t never decreases from one call to the next
- Keys and fingerprints are non-empty strings of up to 40 characters.
- Every response starts with a three-digit status code, like "201 paid #7", so it never equals "run", "wait" or "conflict".
- At most 2,000 calls per test
Start with brute force
Without a store, the server could look for an existing payment with the same amount and card in the last minute. That blocks legitimate repeat orders and still double-charges when the two requests arrive at the same moment, because neither finds the other's payment yet.
The key says exactly which requests are the same attempt, and the in-progress record closes the gap between "started" and "finished". In a real system, begin must be one atomic insert-if-absent in the shared store, or two servers can both see "no record" for the same double-tap.
Hints
0 of 4 shown- Hint 1
For one key, list the states a record can be in, and what each kind of repeat request should get back in each state.
- Hint 2
A live record is either in progress or finished, and it carries a fingerprint, a creation time and, once finished, a response. A missing or expired record behaves the same way: as if the key were new.
- Hint 3
Keep a map from key to record. Write one helper,
live(key, t), that returns the record only ift < created + ttlMs, and deletes it otherwise. Use it at the start of all three methods. - Hint 4
In
begin, check in this order: no live record → create it and return "run"; different fingerprint → "conflict"; in progress → "wait"; otherwise return the saved response.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
Each key maps to one record: fingerprint, creation time, and the response once there is one. An empty response means "in progress". Every method first drops the record if it has expired, so an expired key behaves exactly like a new one.
Trace the first example, TTL 60,000:
begin(k1, …, 0): no record. Store{fp, 0, null}and return "run".begin(k1, same, 100): live (100 < 60,000), same fingerprint, response still empty: "wait".finish(k1, "201 paid #7", 250): live and in progress, so save the reply.begin(k1, same, 300): live, same fingerprint, finished: return "201 paid #7".begin(k1, "pay 99 …", 400): live, fingerprint differs: "conflict".
Be precise about what this buys. It does not make the network deliver a request exactly once; it makes repeats harmless, so the charge takes effect once. One gap remains: if the server charges the card and crashes before finish, the record expires and a later retry runs again. Real systems close it by saving the result in the same transaction as the side effect, or by passing the key on to a payment provider that is itself idempotent. Real stores also give in-progress records a shorter lease than finished ones; this problem uses one TTL for both.
class IdempotencyStore {
constructor(ttlMs) {
this.ttlMs = ttlMs;
this.records = new Map(); // key -> { fingerprint, created, response (null while running) }
}
live(key, t) {
const r = this.records.get(key);
if (r && t >= r.created + this.ttlMs) { this.records.delete(key); return undefined; } // expired
return r;
}
begin(key, fingerprint, t) {
const r = this.live(key, t);
if (!r) {
this.records.set(key, { fingerprint, created: t, response: null });
return 'run';
}
if (r.fingerprint !== fingerprint) return 'conflict'; // key reused for another request
if (r.response === null) return 'wait'; // first request still running
return r.response; // replay the saved reply
}
finish(key, response, t) {
const r = this.live(key, t);
if (r && r.response === null) r.response = response;
}
release(key, t) {
const r = this.live(key, t);
if (r && r.response === null) this.records.delete(key);
}
}class IdempotencyStore:
def __init__(self, ttl_ms):
self.ttl_ms = ttl_ms
self.records = {} # key -> [fingerprint, created, response or None while running]
def _live(self, key, t):
r = self.records.get(key)
if r is not None and t >= r[1] + self.ttl_ms: # expired
del self.records[key]
return None
return r
def begin(self, key, fingerprint, t):
r = self._live(key, t)
if r is None:
self.records[key] = [fingerprint, t, None]
return "run"
if r[0] != fingerprint: # key reused for another request
return "conflict"
if r[2] is None: # first request still running
return "wait"
return r[2] # replay the saved reply
def finish(self, key, response, t):
r = self._live(key, t)
if r is not None and r[2] is None:
r[2] = response
def release(self, key, t):
r = self._live(key, t)
if r is not None and r[2] is None:
del self.records[key]Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.