Chapter 18 — Design & Caches
Source:
src/main/kotlin/cache/,src/main/kotlin/design/, and thestack/+probability/design filesMaster idea: design questions test data-structure composition: which structures combine to meet the stated complexity? The classic answers: hash map + linked list (LRU), three maps + a min-counter (LFU), hash map + array swap-remove (O(1) random access), and stateful iterators (buffers and stacks that make traversal lazy).
Prerequisites: hash maps (Chapter 10), linked lists (Chapter 4), heaps/queues (Chapter 7), and stacks (Chapter 8) — every design here composes those.
Problems at a glance (this chapter’s core set)
| # | Problem | Pattern | Complexity | Page |
|---|---|---|---|---|
| 18.1 | LRU Cache | LinkedHashMap, access-order | O(1) per op | → |
| 18.2 | LFU Cache | 3 maps + min-frequency | O(1) per op | → |
| 18.3 | Thread-Safe Sharded LRU | sharding + locks | O(1) amortized | → |
| 18.4 | Peeking Iterator | one-element buffer | O(1) per op | → |
| 18.5 | Flatten Nested List Iterator | stack of nested lists | O(1) amortized | → |
| 18.6 | Design A Stack With Increment Operations | lazy increment array | O(1) per op | → |
| 18.7 | Insert Delete GetRandom O(1) | map + list swap-remove | O(1) per op | → |
| 18.8 | Weighted Reservoir Sampling | A-Res randomized keys | $O(N log k)$ | → | | 18.9 | LRU Cache — The Repo’s Seven Implementations | variant consolidation | $O(1)$ | → | | 18.11 | My Calendar | TreeMap floor/ceiling | $O(log n)$ | → | | 18.12 | BST Iterator | left-spine stack | $O(1)$ amortized | → | | 18.13 | Moving Average | windowed queue + sum | $O(1)$ | → | | 18.14 | Number Of Recent Calls | expiry queue | $O(1)$ amortized | → | | 18.15 | Product Of Last K Numbers | prefix products + zero-reset | $O(1)$ | → | | 18.16 | Design Circular Queue | ring buffer | $O(1)$ | → | | 18.17 | Maximum Frequency Stack | frequency stacks | $O(1)$ | → | | 18.18 | Range Sum Query 2D Immutable | 2-D prefix sums | $O(1)$ query | → | | 18.19 | Convert BST To DLL | inorder threading | $O(n)$ | → | | 18.20 | Design TicTacToe | signed line counters | $O(1)$ | → | | 18.21 | My Calendar II | lazy segment tree | $O(log U)$ | → | | 18.22 | Linked List Random Node | reservoir sampling | $O(n)$ | → | | 18.23 | Random Pick Index | index buckets | $O(1)$ | → | | 18.24 | Random Pick With Weight | prefix sums + bisect | $O(log n)$ | → |
The rest of the design-related directories
cache/ holds many LRU/LFU flavors (LRUCacheLinkedList.kt, LRUCacheBetter.kt, the LruCacheNobodyDoesItBetter.kt family, LFUCacheGigaCHAD.kt, …) — this chapter documents the canonical structures. design/ adds SelfDoubtSimulation.kt; stack/ holds the nested-list iterator and increment-stack; probability/ holds the O(1) random-access set.
New pages are appended to the table above as they’re written.