Module 40
Designing Data Structures
"Design X" problems: combine hash maps, linked lists, heaps and sorted maps to hit O(1) or O(log n) per operation. LRU, LFU, time-based stores, snapshots and feeds.
Design problems give you a list of operations and a speed requirement, and ask for a class. No single structure fits, so the answer is a combination: a hash map for O(1) lookup glued to a linked list for O(1) ordering, a map of sorted lists for history, or a heap for merging feeds.
This module teaches a repeatable method (list operations → required complexity → pick a structure per need → keep them consistent) and applies it to the classic designs asked in interviews and used in real caches and services.
Best after: Hashing, Linked Lists, Heaps and Priority Queues
Unlocks next: 41. Concurrency-Aware Data Structures
Where this shows up in real systems
- System Design · Topic 10.6 — Eviction Policies: LRU, LFU, TTL — LRU eviction is a hash map for lookup plus a doubly linked list for recency, both O(1).
- System Design · Problem 4.16 — LRU Cache — The same class, built and tested step by step with a dry run.
- System Design · System 12.2 — Rate Limiter (HLD) — Counting requests in the last N seconds is a sliding window over time.
- System Design · System 12.8 — News Feed — A feed merges followed users' timelines with a heap: K-way merge.
Part 1
Learn the ideas
- 40.1The Design Method and LRU CacheWrite each operation with its target cost, choose a structure that gives each cost, then make every operation update all structures together. LRU = hash map + doubly linked list.18 min
- 40.2Frequencies, History and RandomnessLFU groups keys by use count with a pointer to the minimum. Time-based and snapshot stores keep sorted histories per key and binary search them. O(1) random choice uses an array plus an index map, deleting by swapping with the last element.14 min
Part 2
Solve the problems
Work through them in order. Each one shows the pattern it teaches.
HashMap + doubly linked list with sentinels.
Frequency buckets with a minimum-frequency pointer; ties broken by recency.
Append-only versions per key plus binary search for the latest version at a time.
Store only changes per index, tagged with the snapshot id; answer with a floor lookup.
Array + index map, deleting by swapping with the last element.
A sliding time window with a queue, or a fixed ring of 300 buckets for O(1) memory.
A news feed is a K-way merge of followed users' tweet lists, newest first.
What's inside a hash set: an array of buckets, a hash function to pick the bucket, and a small list per bucket for collisions.
A hash map is a hash set whose bucket entries carry a value: update in place when the key is already there.
Two views of the same items: a doubly linked list for stack order and a TreeMap for "largest", kept in sync.
Paths as keys: a parent must exist before its child, which is a prefix check (map of full paths, or a trie of path parts).
Autocomplete: keep the typed prefix, find matching past sentences, rank by popularity then alphabet, return the top 3; '#' saves the sentence.
Two maps: who is currently travelling (id → start), and running totals per route ("from→to" → sum and count).