Coding interviews
Reveal answer and reasoning
An idempotency key is bound to a specific request meaning, not merely remembered as seen. This bounded in-memory ledger accepts a new key and amount, replays an equal request, rejects a changed amount and rejects new keys once capacity is full. Previously accepted requests remain replayable at capacity. The task is a single-owner decision model with no external side effect or persistence.
Lookup precedes capacity admission because an already known key owns an existing decision. Repeating it needs no new slot. Payload equality is part of identity: the same key with another amount is a conflict even if there is otherwise room. The example uses an integer amount as its entire bounded request meaning.
Expected lookup and insertion cost are O(1) dictionary operations plus key hashing. Retained entry count is bounded by capacity, but key lengths and payload representation still affect memory. There is no eviction policy; dropping old keys would change the period over which retries can be recognized. An entry-count cap can coexist with arbitrarily long key strings unless key length is bounded separately.
The amount is fixed-size here, but storing a complete result or request fingerprint can alter memory. Retention and eviction also determine how long a retry can be recognized, making them correctness policies as well as resource choices.
What a strong answer covers
- An idempotency key is bound to a specific request meaning, not merely remembered as seen.
- The third x request does not overwrite ten with eleven, so later replay still refers to the original accepted amount.
- Expected lookup and insertion cost are O(1) dictionary operations plus key hashing.
Common pitfall
This local dictionary is not thread-safe and cannot provide distributed exactly-once effects. Accepting a record before or after an external payment leaves a failure window unless storage and effect ownership are designed together. A key reused with changed payload must not silently replay an unrelated result.
Follow-up questions
- Replay x after the ledger is full and verify replay rather than full. Hint: capacity limits new ownership, not lookup of already owned decisions. Add invalid empty-key and negative-amount cases.
- What does idempotency-key expiry mean for a retry arriving after the retention horizon?
Self-review
Choose what to revisit. These marks are your own assessment and are separate from lesson completion.