What it is
Design questions hand you an interface — a list of method names and the time complexity each must meet — and ask you to implement it from scratch. There is no single algorithm; the skill is picking the right combination of built-in structures (hash maps, heaps, linked lists, arrays, tries) so that every required operation, not just the common one, hits its target. Many of these are really "which structure gives O(1)/O(log n) for this specific operation" puzzles stacked two or three deep.
When it applies
- The prompt is phrased as "design a class that supports get/put/insert/delete..." with named methods and per-method complexity targets.
- You need a structure that no single built-in type provides on its own — e.g. O(1) insert, delete, and random access, which no plain list, set, or dict gives you alone.
- If the ask is really just "process a stream and answer one kind of query fast" with no eviction, ordering, or multi-operation contract, a simpler pattern (heap, prefix sum, sliding window) may be a better fit than building a bespoke class.
- Reach for this pattern when a naive choice (say, a plain list for O(1) removal) would force an O(n) operation somewhere in the interface.
Tells in the problem
- A method list with
__init__followed by named operations, each given its own big-O requirement. - "In O(1) time" attached to more than one operation that would normally conflict (fast lookup and fast removal and fast random pick).
- Keywords like "least recently used", "least frequently used", "prefix", or "iterator" that map directly to a known structure (linked list + hash map, frequency buckets, trie, lazy pointer).
- A request to serialize/deserialize or encode/decode a structure so it survives a round trip through a flat string or byte stream.
- Follow-up variations on the same class (e.g. add a new method to an already-designed cache) that test whether your first design leaves room to extend.
The classic mistake
Under-designing the eviction or ordering logic is the usual failure mode: reaching for a single hash map and believing a sorted() call or a linear scan over its values will keep things fast enough, only to have every operation degrade to O(n) once the interface is checked against its stated complexity. This usually happens because the map correctly answers the "everyday" query and the candidate stops there, without checking every method against its own complexity requirement. Before writing code, write down each method and the structure that satisfies it in isolation — if one structure can't cover a method, you need a second structure kept in sync with the first (e.g. a hash map for lookup plus a linked list for order), not a cleverer way to search the first one.
Questions to start with
- Min Stack — the simplest two-structures-in-sync design: track the minimum alongside a normal stack.
- Insert Delete GetRandom O(1) — forces a hash map plus an array, because no single structure gives O(1) insert, delete, and random access.
- LRU Cache — the canonical hash map plus doubly linked list combination, the base every eviction-based design builds on.
- Implement Trie (Prefix Tree) — a different axis: designing around prefixes rather than key/value pairs.
- LFU Cache — layers frequency buckets on top of the LRU idea, testing whether your first design generalizes.