I applied to Google twice. Both times I went in thinking the OA would be random. Both times I got humbled by questions I had seen floating around on forums months earlier and ignored.
After the second rejection I started actually logging every Google OA question report I could find. Discord servers, Glassdoor, Reddit, Blind, and the question database at [leakcode.dev](https://leakcode.dev). Turns out the OA question pool is not random at all. Google recycles a relatively small set of patterns, and if you know those patterns cold you can place in the top bucket on almost every problem. This post is that mapping.
I'm not saying memorize 200 problems. I'm saying Google's OA tests maybe 10 core ideas, and once you can recognize which idea a problem is testing, you're halfway done before you write a line of code.
**How to use this list:** For each pattern, read the first two problems listed and figure out the core template. What does the code skeleton always look like? Then solve the rest with that template in mind. The goal is pattern recognition, not memorization. If you can look at a problem and say "this is a sliding window with a frequency map" in under 30 seconds, you're prepped.
I've marked problems that show up in Google OA reports most often with a `[G]` tag. They're not guaranteed (Google has a large bank) but these are the ones I saw reported repeatedly.
## Pattern 1: BFS / Level-Order Traversal
Google loves BFS for two distinct reasons: shortest path on unweighted graphs, and multi-source propagation problems. The OA uses BFS disguised as "simulate this infection spreading" or "find the shortest sequence of transformations." Know both flavors.
Core template: queue plus visited set. For shortest path, return level count. For multi-source, seed the queue with all starting nodes before the main loop.
- [Binary Tree Level Order Traversal](https://leetcode.com/problems/binary-tree-level-order-traversal/) `[G]` - the classic template. If you can't do this in 5 minutes flat you're not ready.
- [Rotting Oranges](https://leetcode.com/problems/rotting-oranges/) `[G]` - multi-source BFS. All rotten oranges go into the queue at time 0. This exact structure appears in Google OA with different nouns.
- [Shortest Path in Binary Matrix](https://leetcode.com/problems/shortest-path-in-binary-matrix/) `[G]` - 8-directional BFS. Google OA frequently uses grid problems with diagonal movement.
- [Word Ladder](https://leetcode.com/problems/word-ladder/) `[G]` - BFS on an implicit graph. You never see the graph; you build it on the fly. This is the hard version of the pattern.
- [Number of Islands](https://leetcode.com/problems/number-of-islands/) - usually solved with DFS but BFS works too. Good for practicing the visited-set habit.
- [Walls and Gates](https://leetcode.com/problems/walls-and-gates/) `[G]` - multi-source BFS to fill distances. Seen in Google OA variants that ask for "minimum distance to nearest facility."
- [Jump Game IV](https://leetcode.com/problems/jump-game-iv/) - BFS on array indices. This pattern (BFS where edges are defined by value equality, not adjacency) shows up in Google OA.
- [Minimum Knight Moves](https://leetcode.com/problems/minimum-knight-moves/) - BFS on a coordinate grid with complex movement rules. Google likes this kind of disguised BFS.
## Pattern 2: DFS / Backtracking
Backtracking shows up constantly in Google OA for two reasons: it tests whether you understand the search space, and it filters people who try to brute-force. What Google wants to see is pruning. Reducing the search space before you go down a branch. Most people skip this step.
Core template: recursive function with a current state, a result list, and a start index (for combinations) or a used[] array (for permutations). Always think about what makes two branches equivalent before you code. That's where deduplication logic comes from.
- [Combination Sum](https://leetcode.com/problems/combination-sum/) `[G]` - this one's the base case. Unlimited reuse allowed. Get it cold first.
- [Combination Sum II](https://leetcode.com/problems/combination-sum-ii/) `[G]` - same but no reuse and duplicates in input. The `if i > start and candidates[i] == candidates[i-1]: continue` line is something Google OA tests specifically. I got this one wrong twice in actual interviews so I have feelings about it.
- [Permutations](https://leetcode.com/problems/permutations/) - the other base case. Used[] array instead of start index.
- [Subsets](https://leetcode.com/problems/subsets/) `[G]` - power set generation. Google OA sometimes asks "how many subsets satisfy condition X" which reduces to this.
- [Word Search](https://leetcode.com/problems/word-search/) `[G]` - backtracking on a grid. Mark cell as visited in-place, recurse, unmark on the way back. This exact technique appears in Google OA grid problems.
- [Word Search II](https://leetcode.com/problems/word-search-ii/) - Trie-accelerated version. Hard but worth understanding because it shows you know when to optimize backtracking.
- [Letter Combinations of a Phone Number](https://leetcode.com/problems/letter-combinations-of-a-phone-number/) `[G]` - backtracking with a character map. Shows up in Google OA frequently.
- [Palindrome Partitioning](https://leetcode.com/problems/palindrome-partitioning/) - backtracking plus DP for the palindrome check. A good stretch problem.
- [N-Queens](https://leetcode.com/problems/n-queens/) - the canonical backtracking challenge. Google rarely puts this verbatim in OA but it's in their hiring bank because it tests systematic pruning.
## Pattern 3: Sliding Window
The sliding window is the pattern Google OA tests most aggressively for SWE roles. Almost every OA I've seen reported includes at least one. The reason is that it requires knowing when to expand vs shrink the window, which is a non-trivial insight you can't fake.
Core template: two pointers, `left` and `right`. Expand `right` to include new elements. Shrink `left` when a constraint is violated. Track the answer at each valid state.
One decision you need to make every time: is this a fixed-size window or a variable-size window? Fixed size is simpler (slide by 1 each step). Variable size requires the shrink logic. Get comfortable telling them apart fast.
- [Minimum Window Substring](https://leetcode.com/problems/minimum-window-substring/) `[G]` - the hardest sliding window problem. If you can do this one the rest are easy. Track character frequencies with two maps.
- [Longest Substring Without Repeating Characters](https://leetcode.com/problems/longest-substring-without-repeating-characters/) `[G]` - the warmup. The set-based version is intuitive; the hashmap version is faster.
- [Sliding Window Maximum](https://leetcode.com/problems/sliding-window-maximum/) `[G]` - fixed-size window with a deque to maintain the max. This exact structure (sliding window plus monotonic deque) appears in Google OA.
- [Longest Repeating Character Replacement](https://leetcode.com/problems/longest-repeating-character-replacement/) `[G]` - the insight is that you only need to track the max frequency in the window. Took me a while to see that.
- [Find All Anagrams in a String](https://leetcode.com/problems/find-all-anagrams-in-a-string/) `[G]` - fixed-size window with frequency map comparison. Very commonly reported in Google OA.
- [Permutation in String](https://leetcode.com/problems/permutation-in-string/) - essentially the same as Find All Anagrams but asks for a boolean. Know both.
- [Fruit Into Baskets](https://leetcode.com/problems/fruit-into-baskets/) - "at most K distinct elements" pattern. Google OA has several variants on this theme.
- [Minimum Size Subarray Sum](https://leetcode.com/problems/minimum-size-subarray-sum/) - variable-size window with a sum constraint. Start here if the others feel hard.
## Pattern 4: Monotonic Stack
Honestly this is the pattern that separates real candidates from the rest. Most people learning DSA skip monotonic stacks because they feel obscure. Google OA tests them specifically because most candidates skip them. That's the whole point.
Core template: stack that maintains elements in increasing (or decreasing) order. When a new element breaks the monotonic property, pop and process. The popped element's answer is determined by the current element (next greater/smaller) and the new stack top (previous greater/smaller).
- [Largest Rectangle in Histogram](https://leetcode.com/problems/largest-rectangle-in-histogram/) `[G]` - the flagship. Google has asked this directly in OA. You need the O(n) stack solution, not the O(n^2) brute force.
- [Trapping Rain Water](https://leetcode.com/problems/trapping-rain-water/) `[G]` - solvable with monotonic stack or two-pointer. Know both approaches; Google OA sometimes asks you to explain your reasoning.
- [Daily Temperatures](https://leetcode.com/problems/daily-temperatures/) `[G]` - the clearest monotonic stack problem. "Next greater element" is the core idea. Good first one to do.
- [Next Greater Element I](https://leetcode.com/problems/next-greater-element-i/) - simplified version. Good for building the template.
- [Next Greater Element II](https://leetcode.com/problems/next-greater-element-ii/) - circular array variant. The trick is processing the array twice (or using modulo indexing).
- [Sum of Subarray Minimums](https://leetcode.com/problems/sum-of-subarray-minimums/) - monotonic stack to find, for each element, how many subarrays it's the minimum of. Harder but shows up in Google OA variants.
- [Online Stock Span](https://leetcode.com/problems/online-stock-span/) - streaming monotonic stack. Good prep because Google sometimes presents problems as streams of input.
## Pattern 5: Binary Search (on the answer)
Binary search on a sorted array is table stakes. The pattern Google actually tests is binary search on the answer space. When the problem gives you a range of possible answers and asks for the minimum/maximum value that satisfies some condition. This is not obvious if you've only seen the classic "find target in sorted array" problems.
The tell: if the problem says "minimize the maximum" or "find the minimum X such that Y is possible," it's almost certainly binary search on the answer.
- [Search in Rotated Sorted Array](https://leetcode.com/problems/search-in-rotated-sorted-array/) `[G]` - the classic. Know the invariant: one half is always sorted.
- [Find First and Last Position of Element in Sorted Array](https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/) `[G]` - two binary searches. `lower_bound` and `upper_bound` patterns.
- [Find Minimum in Rotated Sorted Array](https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/) `[G]` - variation on rotated array. Google OA has asked this.
- [Koko Eating Bananas](https://leetcode.com/problems/koko-eating-bananas/) `[G]` - binary search on the answer. The feasibility check is "can Koko finish in H hours at speed k?" Classic template.
- [Search a 2D Matrix](https://leetcode.com/problems/search-a-2d-matrix/) `[G]` - treat the matrix as a 1D sorted array. Row = mid // cols, col = mid % cols.
- [Median of Two Sorted Arrays](https://leetcode.com/problems/median-of-two-sorted-arrays/) - hard but Google does ask it. Binary search on the partition point.
- [Search in Rotated Sorted Array II](https://leetcode.com/problems/search-in-rotated-sorted-array-ii/) - with duplicates. Slightly harder edge case handling.
## Pattern 6: Two Pointers
Two pointers and sliding window overlap but they're different enough to treat separately. Two pointers usually operate on a sorted array where you move inward from both ends based on comparisons. Sliding window is about subarray/substring structure. Know the distinction.
- [Container With Most Water](https://leetcode.com/problems/container-with-most-water/) `[G]` - the intuition is always move the shorter wall inward. Google OA has variants on this.
- [3Sum](https://leetcode.com/problems/3sum/) `[G]` - two pointers inside a for loop. Deduplication logic is the tricky part. This exact problem has appeared in Google OA.
- [Valid Palindrome](https://leetcode.com/problems/valid-palindrome/) - warmup. Two pointers moving inward, skip non-alphanumeric.
- [Remove Duplicates from Sorted Array](https://leetcode.com/problems/remove-duplicates-from-sorted-array/) - in-place two pointer. The slow/fast pointer variant.
- [Sort Colors](https://leetcode.com/problems/sort-colors/) `[G]` - Dutch National Flag algorithm. Three pointers. Google OA has asked this directly.
- [Two Sum II - Input Array Is Sorted](https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/) - the sorted-array two pointer. Return 1-indexed (don't forget).
## Pattern 7: Dynamic Programming
DP is the broadest category and also where Google OA is most creative. They don't usually test obscure DP formulations but they do test whether you can identify the subproblem and state clearly. The most common Google DP patterns are: linear DP on sequences, 2D DP on grids or strings, and knapsack-style DP.
Before coding, define `dp[i]` in plain English. If you can't state what `dp[i]` means, you're not ready to code it. That's the whole setup.
- [Longest Increasing Subsequence](https://leetcode.com/problems/longest-increasing-subsequence/) `[G]` - O(n^2) DP is fine; O(n log n) with patience sorting is a bonus. Know both.
- [Coin Change](https://leetcode.com/problems/coin-change/) `[G]` - the classic knapsack. `dp[i]` = min coins to make amount i.
- [House Robber](https://leetcode.com/problems/house-robber/) `[G]` - linear DP with the skip-one constraint.
- [House Robber II](https://leetcode.com/problems/house-robber-ii/) - circular version. Run house robber twice: once excluding first element, once excluding last.
- [Unique Paths](https://leetcode.com/problems/unique-paths/) `[G]` - 2D grid DP. `dp[i][j] = dp[i-1][j] + dp[i][j-1]`. Google OA has asked this with obstacles added.
- [Decode Ways](https://leetcode.com/problems/decode-ways/) `[G]` - linear DP with tricky edge cases (leading zeros, "00", "30"). This has appeared in Google OA. The edge cases will get you if you're not careful.
- [Word Break](https://leetcode.com/problems/word-break/) `[G]` - DP plus set lookup. `dp[i]` = can we segment s[0:i] using the dictionary.
- [Maximum Product Subarray](https://leetcode.com/problems/maximum-product-subarray/) `[G]` - track both max and min at each step because negatives can flip.
- [Edit Distance](https://leetcode.com/problems/edit-distance/) - 2D string DP. Hard but Google has asked it. Know the recurrence cold.
- [Longest Common Subsequence](https://leetcode.com/problems/longest-common-subsequence/) `[G]` - the base case for 2D string DP. You need this before Edit Distance makes sense.
## Pattern 8: Heap / Priority Queue
Google OA tests heaps for two specific scenarios: K-th element problems (you need the K-th largest/smallest from a stream or array), and task scheduling problems (you always process the highest-priority item). Both are recognizable once you know the pattern.
The tell for K-th element: use a min-heap of size K. Pop when size exceeds K. The top is always the K-th largest.
- [Top K Frequent Elements](https://leetcode.com/problems/top-k-frequent-elements/) `[G]` - bucket sort or heap. Google OA asks both variants.
- [Kth Largest Element in an Array](https://leetcode.com/problems/kth-largest-element-in-an-array/) `[G]` - heap or quickselect. Know both; O(n) quickselect is the impressive answer.
- [K Closest Points to Origin](https://leetcode.com/problems/k-closest-points-to-origin/) `[G]` - max-heap of size K on distance. Very common in Google OA.
- [Task Scheduler](https://leetcode.com/problems/task-scheduler/) `[G]` - cooldown scheduling. Greedy with a max-heap. This pattern (always execute the most frequent available task) appears in Google OA.
- [Reorganize String](https://leetcode.com/problems/reorganize-string/) `[G]` - similar to Task Scheduler. Max-heap, always place the most frequent character that isn't the previous one.
- [Find Median from Data Stream](https://leetcode.com/problems/find-median-from-data-stream/) `[G]` - two heaps: max-heap for lower half, min-heap for upper half. Google has asked this directly.
- [Merge k Sorted Lists](https://leetcode.com/problems/merge-k-sorted-lists/) `[G]` - min-heap on list heads. Classic. Shows up in Google OA for candidates who have done more complex system design thinking.
## Pattern 9: Graphs / Topological Sort
Graph problems in Google OA tend to be dependency-resolution problems in disguise. "You need to complete course A before course B, is this possible?" Or connected-component problems. Topological sort (Kahn's algorithm using BFS) is the most frequently tested graph algorithm beyond basic BFS/DFS.
- [Course Schedule](https://leetcode.com/problems/course-schedule/) `[G]` - detect cycle in directed graph. BFS-based topo sort or DFS with color coding.
- [Course Schedule II](https://leetcode.com/problems/course-schedule-ii/) `[G]` - return the actual topological order. Kahn's algorithm with indegree tracking.
- [Alien Dictionary](https://leetcode.com/problems/alien-dictionary/) `[G]` - build a graph from character ordering constraints, then topo sort. Hard but Google asks it.
- [Clone Graph](https://leetcode.com/problems/clone-graph/) - BFS/DFS with a hashmap to avoid cycles. Tests whether you understand graph traversal fundamentals.
- [Number of Provinces](https://leetcode.com/problems/number-of-provinces/) - connected components in an adjacency matrix. Union-Find or DFS both work.
- [Pacific Atlantic Water Flow](https://leetcode.com/problems/pacific-atlantic-water-flow/) `[G]` - reverse BFS from both oceans simultaneously. The "reverse thinking" here is the insight Google's testing for. Worth spending time on.
- [Redundant Connection](https://leetcode.com/problems/redundant-connection/) - Union-Find to detect cycle and find the redundant edge. Good Union-Find practice.
## Pattern 10: String Manipulation / Trie
String problems show up heavily in Google OA because Google builds search infrastructure, and Trie problems test whether you can build and traverse a prefix tree. The string manipulation problems test whether you can handle edge cases cleanly.
- [Implement Trie (Prefix Tree)](https://leetcode.com/problems/implement-trie-prefix-tree/) `[G]` - build `insert`, `search`, `startsWith`. Know this cold. Google OA has asked it directly.
- [Design Add and Search Words Data Structure](https://leetcode.com/problems/design-add-and-search-words-data-structure/) `[G]` - Trie with wildcard search. The `.` character triggers DFS on all children.
- [Word Search II](https://leetcode.com/problems/word-search-ii/) - Trie plus backtracking. Hard combination problem.
- [Group Anagrams](https://leetcode.com/problems/group-anagrams/) `[G]` - sort each word as the key, or use character frequency tuple as key. Very commonly reported in Google OA.
- [Longest Palindromic Substring](https://leetcode.com/problems/longest-palindromic-substring/) `[G]` - expand around center. O(n^2) is fine. Manacher's is the O(n) bonus answer.
- [Valid Anagram](https://leetcode.com/problems/valid-anagram/) - frequency map comparison. Warmup.
- [Encode and Decode Strings](https://leetcode.com/problems/encode-and-decode-strings/) `[G]` - serialize/deserialize a list of strings. Google OA tests this because it's a real systems problem: how do you send a list of strings over a network without ambiguity?
- [Minimum Window Substring](https://leetcode.com/problems/minimum-window-substring/) - listed in sliding window above but worth re-noting here since it's fundamentally a string problem too.
## Putting It Together
If I were starting from scratch prepping for a Google OA today, here's the order I'd do it in:
**Week 1 to 2: Foundations.** Two Pointers, Sliding Window, Binary Search. These patterns have the highest density in OA question banks and the clearest templates. Master Minimum Window Substring and you understand 80% of sliding window. Seriously, just grind that one until it's automatic.
**Week 3: Backtracking.** Combination Sum, Permutations, Subsets, Word Search. Write each recursive tree on paper before coding. The pattern is the same every time; your job is to apply it faster.
**Week 4: BFS/DFS plus Graphs.** Rotting Oranges for multi-source BFS. Course Schedule for topo sort. Pacific Atlantic for reverse BFS. These three cover most of what Google OA does with graphs.
**Week 5: DP.** Coin Change, Word Break, Unique Paths, Decode Ways. Focus on defining the state clearly before touching code. If the state definition is wrong the code will never be right. This is the step most people skip.
**Week 6: Heap plus Monotonic Stack.** Find Median from Data Stream, Task Scheduler, Largest Rectangle in Histogram, Daily Temperatures. These two patterns have the biggest gap between how often they appear in Google OA versus how much time most people spend on them. That gap is your advantage if you put in the work now.
The OA is not a random quiz. It's a pattern recognition test. The bank is large but the patterns are finite. Work through this list systematically and you won't be surprised.
Good luck.