Pattern & Structure Selection

## Three asks that look identical Consider a submissions service. Three requirements arrive in the same sprint: 1. Reject a submission whose idempotency token has been used before. 2. Show each user how many submissions they have made this hour. 3. When a duplicate is rejected, tell the caller which earlier submission won. All three are "look something up fast", all three are satisfied by a hash-backed container with expected O(1) operations, and a candidate who has only learned "hash lookup is fast" will reach for the same thing three times. The selection question is not *how fast* but *what do I have to be able to read back*. ## The three structures, by what they retain **A set** retains membership and nothing else. `add(token)` and `contains(token)` are the whole surface. Requirement 1 is exactly this shape: the answer the guard needs is one bit. Because there is no payload, there is nothing that can be stale — a set cannot disagree with itself. **A counter map** retains a number per key. `count[user] = count[user] + 1` on write, `count[user]` on read. Requirement 2 needs this, and a set cannot be retrofitted into it: once you have stored only membership, the second occurrence of a key is indistinguishable from the fortieth. The counter is strictly more state than the set — one machine word per key — and it must be incremented on every path that accepts a submission, including the ones added next quarter. **A key-to-value map** (here, key to the index or identifier of the first occurrence) retains a pointer back into the original data. Requirement 3 needs this. Note the direction: you are indexing *from* the value you will be asked about *to* the position you will have to produce. Building the map the other way around — position to token — is the natural way the data already sits and answers nothing, because you would have to scan it. ## The failure modes this question aims at The first is *storing too little*. A set is chosen for the guard, and two weeks later the requirement becomes "tell me which submission won". Now the only way to produce the position is to rescan the source input — an O(n) pass per rejection, or a second full build. A set does not record insertion positions; "the order I added things" is not part of what a set promises, and even a container that happens to preserve insertion order tells you the order of *first insertion*, not the index in the original data unless you put it there. The second is *storing too much*. A counter map used where a set would do costs memory per key and, worse, adds a field that every write path must maintain. Unused state rots: someone adds a code path that inserts without incrementing, and the count is quietly wrong for months because nothing reads it hard enough to notice. The third is *choosing the container before naming the read*. The disciplined move in an interview is to say the read out loud first — "the only thing I ever ask this structure is whether the token is present" — and let the structure fall out of that sentence. It also makes the answer defensible when the interviewer changes the requirement mid-question, which is usually why they asked. ## Costs, honestly stated All three give O(1) *expected* time for insert and lookup, amortized over resizes; the worst case is O(n) when many keys land in the same bucket, and an adversary who can choose your keys can force that. Space is O(n) keys for the set, plus one counter or one value per key for the maps. None of the three supports ordered iteration, range queries, or "the nearest key below this one" — if the requirement contains a comparison rather than an equality, none of these three is the answer, and that is a different selection question. ## The multiset case One more variant is worth naming: a *multiset* is a counter map wearing different clothes. When you need "how many of this key are currently present" together with removal — a running count that goes down as well as up — a counter map with an explicit rule for deleting the entry at zero is the honest implementation, and forgetting that rule is a classic slow leak: keys accumulate at count zero and the structure grows without bound.