Choosing the Right Data Structure: The Decision Framework

A vegetable vendor doesn't buy a truck. A construction contractor can't work with a scooter. Nobody picks the vehicle first and then asks what they'll carry — the cargo decides the vehicle. Obviously.

Yet in code, we do exactly that backwards thing all the time: "I'll use a list" — typed before asking what the program actually needs to DO with the data. Eleven lessons gave you nine vehicles. This final lesson is the discipline that makes them useful: list the operations first; the structure picks itself.

The framework: four questions, in order

Ask these four questions about YOUR problem, in this order:

• 1. How do I need to FIND things? By exact key → hash. By position → array. By order or range → BST. By prefix → trie. By "most extreme first" → heap.
• 2. What must come OUT next? Most recent → stack. Earliest → queue. Highest priority → heap. Doesn't matter → anything cheap.
• 3. How does the data CHANGE? Append-mostly → array. Constant splicing at held nodes → linked list. Groups merging → union-find.
• 4. What are the CONSTRAINTS? Memory-tight → in-place and arrays. Latency-critical → beware resize/rehash pauses. Small n → simplicity beats everything.

Answer honestly and the structure usually names itself before you finish question 2.

The master table

Eleven lessons compressed into one grid — the course, revisable in a minute:

Signal phrases → structures

Problems announce their structure in their vocabulary. Train these reflexes — they fire before conscious thought in a timed round:

"have I seen / does it exist / duplicate"      -> hash set
"count / frequency / most common"              -> hash map (+ heap for top-K)
"undo / most recent / matching brackets"       -> stack
"first come / level by level / minimum steps"  -> queue (BFS)
"top K / k-th largest / most urgent next"      -> heap
"starts with / autocomplete / spell check"     -> trie
"range / between / sorted order / rank"        -> balanced BST
"groups merging / same circle / connected?"    -> union-find
"index i / random access / iterate fast"       -> array

The Algorithms course closes the loop with the technique-side twin of this table in its final lesson.

Let's derive one together: the LRU cache

The canonical design question, asked at every product company: build a cache holding N entries; get(key) and put(key, value) in O(1); when full, evict the least-recently-used entry.

Step 1 — list the operations, refusing to name any structure yet:

a) find any entry by key           - instantly
b) mark an entry as just-used      - move it to the 'recent' end
c) evict the least-recent entry    - remove from the other end

Step 2 — shop for each operation. (a) is exact-key lookup → hash map, O(1). (b) and (c) need an ordering by recency with removal from the middle (a just-used entry could be anywhere) and eviction at the back → a doubly linked list, whose entire reason for the second pointer (lesson 3) is O(1) removal of a held node.

Step 3 — notice neither structure alone survives. The map finds anything but has no order. The list keeps order but can't find a key without an O(n) walk. So wire them together: the map's values ARE the list nodes.

# map:  key -> node               (find anything: O(1))
# DLL:  most-recent ... least-recent    (order: O(1) at both ends)

# get(key):    node = map[key]         O(1) via the map
#              unlink node             O(1) - it's doubly linked
#              relink at the front     O(1)
# put(key, v): if full: evict the tail node AND its map entry
#              insert at front; map[key] = node
# every arrow is O(1) - requirement met

No memorisation happened here — three operations, two specialists, one wiring. That derivation IS the answer interviewers score.

The composite principle

The LRU move generalises: when no single structure satisfies all the operations, give each operation to the structure that does it in O(1), and keep them in sync. The same shape appears everywhere:

• Leaderboard (top scores + "what's Kohli's rank?") → ordered structure (BST/skip list) + player→node map.
• Rate limiter ("max 5 requests per user per minute") → hash map OF deques (per-user sliding windows) — in your Practice Zone.
• Median of a stream → two heaps facing each other (a Microsoft favourite — on the company pages).
• insert/delete/getRandom in O(1) → array + map (a Google favourite — also on the company pages).

The price of composites, worth saying aloud: every update must touch BOTH structures, consistently. Two sources of truth is a bug factory unless the sync is disciplined.

When the boring answer wins

A confession that makes engineers trustworthy: for n = 200, a plain list with a linear scan beats everything in this course. Setup cost, code complexity, bug surface — all lower; and 200 comparisons are invisible. The complexity ladder from lesson 1 separates contenders only when n is large enough for the curves to diverge.

So the framework has a step zero: how big is n, really? A trie for 50 config entries is résumé-driven engineering. The sentence that has genuinely won offers: "at this scale a list is fine; here's what I'd switch to when it grows, and the switch point."

What if...?

What if two structures both seem to fit? Tie-break on the secondary operations and constraints: hash vs BST for lookups → does anything need order? Heap vs sorted list → how write-heavy? Still tied → pick the simpler one and say why. Reasoned simplicity outranks clever complexity.

What if the workload changes later? It will. Name the assumption your choice rests on ("this assumes reads dominate writes") — then the future engineer (usually you) knows exactly when to revisit. Structures aren't forever; assumptions are documented.

What if I genuinely can't tell what the operations are? Then the problem is under-specified, and asking — "will lookups be by ID or by name? how often do writes happen?" — is not weakness, it's the job. Interviewers plant ambiguity to see who asks.

Common mistakes

• Choosing the structure before listing the operations — the root cause of most wrong choices.
• Defaulting to a list for membership tests — the O(n)-per-check habit that quietly turns pipelines quadratic.
• A heap where arbitrary lookup is needed, or a hash where order is needed — right store, wrong question.
• Over-engineering small n.
• Forgetting the sync burden in composite designs.
• Ignoring worst-case pauses (resize, rehash) in latency-critical paths — pre-size or choose predictable structures.

How this is actually tested in interviews

Design-flavoured DS questions ("how would you build X?") are scored on the derivation, not the answer: operations listed → costs assigned → structure(s) chosen → trade-offs named. A memorised "LRU = hashmap + DLL" without the derivation scores poorly even though it's correct — because the interviewer's real question is whether you can derive the NEXT design, the one that isn't on any list. The framework in this lesson is that derivation, practised until it's reflex.

Quick revision

One thing to remember

Operations first, structure second — the cargo decides the vehicle, never the other way around.

Practice Zone — PYQs from real selection rounds

Six MCQs, then two design drills: route five scenarios to their structures, and derive a rate limiter from its operations — the full framework, twice.

Q1Choosing structureseasy

You need: insert items, and always serve the CHEAPEST available one next. Best structure?

Asked in

aSorted arraybMin-heap — O(log n) insert, O(log n) extract-min, O(1) peekcHash tabledStack

Q2Choosing structureseasy

Checking "has this order ID been processed before?" across crores of IDs, thousands of times per second, wants:

Asked in

aA list, scanned each timebA hash set — O(1) average membership checkscA sorted array with binary searchdA trie of the digits

Q3Choosing structuresmedium

An LRU cache needs O(1) get and O(1) eviction of the least-recently-used entry. The standard combination is:

Asked in

aA heap alonebA hash map (key → node) PLUS a doubly linked list ordered by recencycTwo stacksdA BST keyed by timestamp

Q4Choosing structuresmedium

A gaming leaderboard must show the top 100 by score AND answer "what is player X's rank?". Ranks change constantly. The weakest choice is:

Asked in

aA balanced BST (or skip list) keyed by scorebA hash map from player to score, re-sorted on every querycA heap of size 100 for the top-100 displaydA sorted structure plus a player→node map

Q5Choosing structuresmedium

Undo/redo in an editor is naturally:

Asked in

aTwo stacks — undo pops the most recent action; redo holds what was undonebTwo queuescA hash map of actionsdA trie of document states

Q6Choosing structureshard

You must support: add(number), and median() of everything added so far — both fast, called alternately. Best design?

Asked in

aKeep a sorted list; insert with bisectbTWO heaps — a max-heap of the smaller half and a min-heap of the larger half, kept balanced; median reads the topscA hash map of countsdRe-sort on every median() call

Hands-on tasks:

FAQ

Course complete — nine structures and the judgement to choose among them. Prove it against real rounds: Company-wise Data Structures PYQs → — or begin the sibling course: Learn Algorithms →