Mutable Data Structure API Design

What's being tested

Candidates must demonstrate designing mutable data-structure APIs that preserve clear invariants while meeting time/space guarantees (often amortized O(1)). Interviewers probe choices for backing representations, how mutation affects indices/state, correctness under concurrent-seeming operations (random sampling, buffered reads), and clear, testable API contracts.

Patterns & templates

• Array + hash map for constant-time membership and removal: store items in an array, map value→index, remove by swapping with last — O(1) amortized.

• Prefix-sum array or alias method for weighted sampling: prefix-sum + binary search O(log n) or alias O(1) for repeated samples; updates cost O(n) vs O(1) with Fenwick tree.

• Circular buffer (ring buffer) for deque semantics with pop_front/push_back in O(1), extend with doubling for amortized O(1) growth.

• Block-deque / unrolled linked list to get O(1) indexable access with segmented arrays, avoiding full-copy shifts.

• Fenwick (BIT) / segment tree to support dynamic weight updates + prefix queries in O(log n) for weighted sampling with updates.

• Internal buffer + cursor for stream-wrapping: persist leftover bytes between calls, return exact requested lengths until EOF; handle mid-call state cleanly.

• Explicit invariants docstring: state what indices mean after each op, exception behavior, and complexity guarantees.

• Test harness templates: randomized ops + oracle (naïve model) to validate correctness under many interleavings.

Common pitfalls

Pitfall: Assuming swapping removal preserves order — it breaks positional semantics; document whether your API preserves order or not.

Pitfall: Using prefix-sum array for weighted sampling without supporting efficient updates — forgets that updates can be O(n) and will timeout at scale.

Pitfall: For stream wrappers, not persisting leftover buffer across calls leads to lost bytes at EOF or incorrect lengths.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.