Company Problems — Master Recap & Interview Cheatsheet
Sanjeev SharmaAdvertisement
Company Problems — Master Recap
Problem Index by Company
Google (6 problems):
- 01 — Staircase Search → top-right corner elimination O(m+n)
- 02 — Alien Dictionary → topological sort on char graph
- 03 — Sliding Window Max → monotonic deque O(n)
- 04 — Min Window Substring → two-pointer have/need O(n)
- 11 — Longest Substring K Distinct → sliding window
- 14 — Count Inversions → merge sort O(n log n)
- 19 — Word Break II → DP + backtrack with memo
- 21 — Trapping Rain Water II → min-heap BFS 3D
Meta/Facebook (7 problems):
- 05 — Flatten Nested Iterator → stack lazy flatten
- 06 — Serialize/Deserialize Tree → BFS/preorder
- 07 — Read N Characters → buffer + read4
- 12 — Generate Parentheses → backtracking
- 15 — Subarray Sum = K → prefix sum + hashmap
- 17 — Right Side View → BFS level order last node
- 20 — Accounts Merge → union-find on emails
- 23 — Clone Graph → DFS + hashmap
Amazon (6 problems):
- 08 — Number of Islands II → incremental union-find
- 09 — Kth Largest Stream → min-heap size k
- 10 — Task Scheduler → greedy frequency
- 13 — Merge K Sorted Lists → min-heap O(n log k)
- 16 — Top K Frequent → bucket sort O(n)
- 18 — Two Sum variants → hashmap + two-pointer
- 22 — Median Two Sorted → binary search partition
Pattern Quick Reference
Sliding Window → min window, max window, k-distinct
Monotonic Deque → sliding max/min (O(n))
Two Pointers → 2sum sorted, 3sum, 4sum
Prefix Sum → subarray sum = k, range queries
Union-Find → islands II, accounts merge
BFS/DFS+HashMap → clone graph, serialize tree
Backtracking → generate parens, word break II
Merge Sort → count inversions (O(n log n))
Min-Heap Merge → merge k lists, k-way sort
Binary Search → median two arrays, search matrix
Topological → alien dictionary, course schedule
Interview Patterns by Difficulty
| Level | Pattern | Problem |
|---|---|---|
| Easy | HashMap | Two Sum |
| Easy | BFS Level | Right Side View |
| Med | Sliding Window | Min Window Substring |
| Med | Union-Find | Accounts Merge |
| Med | Heap | Task Scheduler |
| Hard | 3D BFS | Trapping Rain Water II |
| Hard | Binary Search | Median Two Sorted |
| Hard | DP + Memo | Word Break II |
Time Complexity Cheatsheet
O(1) Kth Largest after add (heap top)
O(log k) Kth Largest add, Merge K Lists per node
O(n) Two Sum, Sliding Window, Prefix Sum, Bucket Sort
O(n log n) Merge Sort, 3Sum (sort + two-ptr)
O(m+n) Search Matrix, Median Two Sorted
O(V+E) Clone Graph, Topological Sort
O(n log mn) Trapping Rain Water II
Behavioral Integration (Amazon LP)
Amazon expects you to connect solutions to leadership principles:
- Invent and Simplify: "I started with O(n²) brute force and simplified to O(n) using the prefix sum insight..."
- Dive Deep: "Let me trace through the heap invariant step by step..."
- Bias for Action: "I'd implement the O(n log k) heap solution first, then optimize if needed..."
Advertisement
