The whole track at a glance — costs, the right tool for a job, and the Go that already ships it. Each row links to the full page; skim to find the tool, then dive in.
🎯 How to read this
Complexities are average case unless noted. Big-O drops constants and lower-order terms — it describes how cost grows, which is what decides whether your code survives 10× the data.
Complexity at a glance
| Class | Name | Example in Go |
|---|---|---|
| O(1) | constant | m[key], s[i], len(s) |
| O(log n) | logarithmic | binary search, balanced-tree lookup |
| O(n) | linear | one loop over a slice |
| O(n log n) | linearithmic | slices.Sort, merge sort |
| O(n²) | quadratic | nested loops over the same input |
| O(2ⁿ) | exponential | naive recursive subsets / Fibonacci |
Data structures — cost & when
| Structure | Access | Search | Insert | Delete | Reach for it when |
|---|---|---|---|---|---|
| Array / slice | O(1) | O(n) | O(1)* | O(n) | dense indexed data; the default |
| Linked list | O(n) | O(n) | O(1)† | O(1)† | O(1) splice at a held node (LRU) |
| Stack / queue | — | — | O(1) | O(1) | LIFO / FIFO discipline |
| Hash table | — | O(1) | O(1) | O(1) | fast lookup by key, unordered |
| BST (balanced) | — | O(log n) | O(log n) | O(log n) | ordered iteration, range queries |
| Heap | O(1) peek | — | O(log n) | O(log n) | always pop the min/max next |
| Trie | — | O(L) | O(L) | O(L) | prefix search, autocomplete |
| Union-find | — | O(α(n)) | O(α(n)) | — | dynamic connectivity, merge groups |
* amortized for append; † given a pointer to the node; α = inverse Ackermann (≈ constant).
Algorithm patterns
| Pattern | Use it when | Cost |
|---|---|---|
| Binary search | input is sorted, or a monotonic predicate | O(log n) |
| Sorting | order matters; unlocks search & two-pointer | O(n log n) |
| Two pointers | sorted array, pair/triplet, in-place | O(n) |
| Sliding window | contiguous subarray / substring | O(n) |
| BFS | shortest path in hops (unweighted) | O(V + E) |
| DFS | reachability, cycles, topological order | O(V + E) |
| Backtracking | enumerate candidates, undo on dead ends | exponential, pruned |
| Dynamic programming | overlapping subproblems + optimal substructure | states × transition |
| Greedy | a local choice is provably global | often O(n log n) |
The Go standard library already has it
| Need | Reach for |
|---|---|
| Sort a slice | slices.Sort, slices.SortFunc, sort.Slice |
| Binary search | slices.BinarySearch, sort.Search |
| Map / set | built-in map; a set is map[T]struct{} |
| Priority queue | container/heap |
| Doubly linked list | container/list |
| Min / max of two | min, max builtins (Go 1.21) |
| Clone a slice / map | slices.Clone, maps.Clone |
Decision shortcuts — “I need to…”
✅ Pick a structure or pattern by what you're doing
- …look up by key, fast → hash table
- …keep data sorted / range queries → balanced BST (or sorted slice + binary search)
- …always take the smallest/largest next → heap
- …prefix match / autocomplete → trie
- …LIFO or FIFO ordering → stack / queue
- …shortest path in an unweighted graph → BFS
- …visit everything / detect a cycle → DFS
- …all combinations or permutations → backtracking
- …optimize over overlapping subproblems → dynamic programming
- …a provably-optimal local choice → greedy
- …track connectivity / merge groups as edges arrive → union-find
🐹 Interview reflex: brute force first, then trade space for time
State the costs and edge cases out loud, write a correct brute force, then name the bottleneck and the pattern that removes it — a hash set turns an O(n²) duplicate scan into O(n); sorting unlocks two pointers; memoization collapses exponential recursion to polynomial. And in real Go, prefer the standard library over a hand-rolled structure unless asked to build it.
Related topics
Measure cost before you optimize — Big-O for time and space, the common growth classes, and how to read the complexity of real Go code.
linearHash TablesAverage O(1) lookup via hashing — how Go's built-in map works, collisions and load factor, the comma-ok idiom, and the ordering and nil-map gotchas.
algorithmsDynamic ProgrammingSolve problems with overlapping subproblems and optimal substructure — from exponential recursion to top-down memoization and bottom-up tabulation in Go.
Check your understanding
Score: 0 / 51. You need average O(1) lookup, insert and delete by key, and order doesn't matter. Which structure?
Hashing gives average O(1) for all three; a BST is O(log n) and keeps order you don't need here. Reach for a map (a set is map[T]struct{}).
2. What's the right tool for the shortest path in hops on an unweighted graph?
BFS visits in ring order, so it reaches every node by a fewest-edges path first. DFS may find a longer path first; Dijkstra is for weighted graphs.
3. Greedy makes change for 6 from coins {1,3,4} as 4+1+1 = 3 coins. Why prefer DP here?
Greedy only works when the coin system has the greedy-choice property. For {1,3,4} making 6, greedy gives 3 coins but DP gives the optimal 2 (3+3).
4. Edges arrive over time and you repeatedly ask 'are these two nodes connected yet?' Which structure fits?
Dynamic connectivity is union-find's specialty: Union to join, Find to compare roots, both effectively O(1). A one-shot BFS/DFS can't cheaply answer the query as edges keep arriving.
5. You need the k largest items from a huge stream without sorting it all. Which structure?
Keep only k elements in a min-heap; its root is the smallest kept, so any larger newcomer replaces it. You never hold more than k or sort the whole input — O(n log k), the canonical top-k pattern.
Comments
Sign in with GitHub to join the discussion.