The Google "Flavor"
Google interviews are famous for "Constraint Satisfaction" and "Optimization under Infinity." They rarely give standard LeetCode problems; they give you a scenario and expect you to derive the graph or DP state yourself.
The Top 15 Must-Know Problems
| Category | Problem | Key Pattern |
|---|---|---|
| Hard Graph | Alien Dictionary | TopoSort |
| State Search | Race Car | BFS / DP |
| Grid Logic | Making A Large Island | DFS + Map |
| Trie Design | Search Autocomplete | Trie + Top K |
| Intervals | Employee Free Time | Heap / Sweep |
| Advanced DP | Burst Balloons | Interval DP |
| Denary Tree | K-th Lexicographical | Trie Traversal |
| Optimization | Swim in Rising Water | Dijkstra |
| Strings | Word Ladder II | BFS + DFS |
| Trees | Max Path Sum | Post-order DFS |
| Design | Serialize Binary Tree | Pre-order DFS |
| Math | Maximize Score (GCD) | Bitmask DP |
| Matrix | Longest Increasing Path | Memoized DFS |
| Concurrency | Design LFU Cache | Frequency DLL |
| Puzzles | Sliding Puzzle | State BFS |
Google Interview Tips:
- Clarify the Range: Always ask about the input size. Google loves to push you from $O(N^2)$ to $O(N \log N)$ or $O(N)$.
- Think in Graphs: If something has dependencies, it's a DAG. If it has states, it's a State Machine.
- No Fluff: Get to the optimized solution quickly. They value engineers who see through the noise.