Searching, Hashing & DP
When the naive solution is "too slow," the speed-up almost never comes for free — you pay for it with memory or precomputation. A hash map removes the nested loop by replacing the repeated scan with keyed access in average O(1), but takes O(n) memory for the keys. Dynamic programming collapses an exponential tree of recomputations into a linear pass, but stores a cache of subproblems. An LRU cache keeps three operations constant only by combining a map and a doubly linked list at once. And brute force is an admission that there is nothing to prune: it honestly pays an exponential and therefore must be bounded.
A strong candidate does not just name the technique — they name the cost. Go adds its own details: a set is a map[T]struct{} with a zero-size value, a map key must be a comparable type, and the hash map's "O(1)" is an average complexity, not a guarantee. This topic dissects search and optimization techniques layer by layer — each with its own time-versus-memory trade.
Topic Map
- Hash-map lookup — a
mapgives keyed access in average O(1) and collapses an O(n²) nested loop into a single O(n) pass at the cost of O(n) memory. - Set and deduplication —
map[T]struct{}as a set for membership tests and removing duplicates in O(1); the key must be comparable. - LRU cache — a
mapplus a doubly linked list give O(1)get,put, and eviction of the least-recently-used element. - Dynamic programming — overlapping subproblems and optimal substructure; memoization and a table remove recomputation, a sliding window cuts memory to O(1).
- Brute-force search — exhaustive enumeration of the candidate space when there is no structure to prune; the cost is exponential and must be bounded.
Common Mistakes and Traps
| Mistake | Consequence |
|---|---|
| Solving with a nested loop what a hash map solves | O(n²) instead of O(n) — a frequent cause of TLE in interviews |
Treating map's "O(1)" as guaranteed | It is an average complexity; collisions and table growth give a worst case worse than O(1) |
Confusing map[T]bool and map[T]struct{} as a set | struct{}{} uses no memory for the value — idiomatic for a set |
Using a slice, map, or func as a set key | Non-comparable types — the code will not compile; the key must be comparable |
| Treating naive recursive Fibonacci as acceptable | Without memoization it is O(2ⁿ) — one subproblem is recomputed in both branches |
Storing only a map in an LRU, no list | No O(1) eviction of the oldest element |
| Building an LRU on a singly linked list | A node cannot be unlinked in O(1) — you need prev, or finding the neighbor is O(n) |
| Reaching for brute force where structure exists | Exponential cost instead of polynomial |
| Running brute force with no bound | It formally "works" but will not finish in a lifetime on a large space |
Interview Relevance
The search-and-optimization section tests not algorithm memorization but the understanding of the trade: what you spend to win time, and how reliable that win is.
What interviewers usually check:
- When a hash map or set collapses a quadratic into a linear pass, and what it costs in memory.
- Why
map's "O(1)" is an average complexity, not a guarantee. - Which type qualifies as a
mapkey and why aslicedoes not. - How an LRU cache's
get/putachieve O(1) and why it needs a doubly linked list specifically. - What overlapping subproblems are and how memoization or a table removes recomputation.
- When brute force is justified and why it is always bounded.
A typical wrong answer: "A map access is O(1), so the solution is always O(1)." That opens a discussion of how the hash map's O(1) is an amortized average complexity: with collisions and table growth a single operation can cost more, and the win over the double loop itself is paid for with O(n) extra memory.