The 90-Second Pattern Diagnosis Drill (Episode 7 of 10)
Six episodes taught you the patterns. This one tests whether you can recognize them: ten unlabeled problems, ninety seconds each. The goal is not to solve them, but to name the pattern.
The Coding Interview Pattern Series covers the ten patterns that handle the large majority of coding interview problems. Episodes 1 through 6 covered hash maps, sliding windows, binary search and two pointers, graphs, dynamic programming, and fast and slow pointers with linked lists. This is Episode 7: the drill episode. No new patterns today. Pure recognition practice.
Here is something true about how you actually use patterns in an interview: you do not solve a problem and then identify what pattern you used. You identify the pattern first, in the first ninety seconds, before you write anything.
The identification is what tells you where to start.
The code follows from the identification.
If the identification is wrong, the code is wrong regardless of how well you implement it.
This means pattern recognition is not a consequence of knowing the patterns. It is a separate skill that requires separate practice.
Reading about sliding windows builds your ability to implement sliding windows. Diagnosing an unlabeled problem as a sliding window in ninety seconds, under interview conditions, builds your recognition reflex. These are different activities, and most preparation does only the first one.
This episode is about the second one.
The format is ten problems, presented without labels, without hints, and without the solution visible.
For each one, read the problem, set a mental timer for ninety seconds, and answer two questions: what pattern does this problem want, and what is the specific signal in the problem statement that told you?
Then check your diagnosis against the answer key.
The goal is not to solve the problems.
Many of them you have seen before and could implement right now.
The goal is to practice the diagnosis before the implementation, which is the order the interview rewards.
Before the drill, two things about the right way to use it.
How to Run the Drill
Actively diagnose, do not passively read. The drill only works if you actually stop after each problem statement, think for ninety seconds, and form a diagnosis before reading the answer. If you read the problem and the answer in the same motion, you are practicing recognition of answers, not generation of diagnoses. The generation is the skill.
Name both the pattern and the signal. A diagnosis is not complete with just the pattern name. “This is a sliding window” is half a diagnosis. “This is a sliding window because the problem asks for the longest contiguous substring, and ‘contiguous’ is the sliding window tell” is a complete one. The signal is what you would state out loud in an interview before writing code, and it is what this drill is training you to produce automatically.
Track your misses. After each answer, note whether you diagnosed correctly, diagnosed the wrong pattern, or had no diagnosis at all. Correct diagnoses tell you what you have internalized. Wrong diagnoses tell you where your pattern boundaries are blurry. Missing diagnoses tell you which patterns need more exposure. All three are useful information. A correct diagnosis with the wrong signal is also worth noting: you got lucky on the pattern but did not find the right evidence for it.
The Drill: Ten Problems (Ninety Seconds Each)
Read each problem. Stop. Form your diagnosis (pattern and signal). Then read the answer.
Problem 1
Given an array of integers and a target integer, return the indices of the two numbers that add up to the target. You may assume that each input has exactly one solution, and you may not use the same element twice. The array is not sorted.
Your diagnosis: pattern and signal.
Problem 2
Given an array of integers and a positive integer k, find the maximum sum of any contiguous subarray of size exactly k.
Your diagnosis: pattern and signal.
Problem 3
You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad. You have n versions [1, 2, ..., n] and you want to find out the first bad one. You are given an API isBadVersion(version) that returns true if version is bad. Minimize the number of API calls.
Your diagnosis: pattern and signal.
Problem 4
Given a two-dimensional grid of ‘1’s (land) and ‘0’s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.
Your diagnosis: pattern and signal.
Problem 5
Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string.
Your diagnosis: pattern and signal.
Problem 6
You are given an integer array representing coin denominations and a total amount. Return the fewest number of coins needed to make up that amount. If that amount cannot be made up by any combination of the coins, return -1. You may use each coin denomination an unlimited number of times.
Your diagnosis: pattern and signal.
Problem 7
Given an integer array and an integer k, return the k most frequent elements. You may return the answer in any order.
Your diagnosis: pattern and signal.
Problem 8
Given a string s, return the longest palindromic substring in s. A palindrome is a string that reads the same forward and backward.
Your diagnosis: pattern and signal.
Problem 9
Given the head of a linked list, return true if the linked list has a cycle in it. There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer.
Your diagnosis: pattern and signal.
Problem 10
Given an array of intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.
Your diagnosis: pattern and signal.
The Answer Key
Read each answer only after you have formed your own diagnosis.
For each problem, the answer gives the pattern, the signal that identifies it, the solution approach, and the disambiguation notes that explain why other patterns do not fit.
Problem 1 answer: Hash Map
Signal: “two numbers that add up to the target” on an unsorted array.
Pattern: hash map, specifically the complement trick from Episode 1.
For each number, check whether its complement (target minus the current number) has already been seen. Store values with their indices in a hash map as you go. One pass, O(n) time, O(n) space.
Disambiguation: the input is unsorted, which rules out two pointers.
Two pointers require sorted input to work: the pointer movement logic (left increases sum, right decreases) breaks on unsorted data.
If the array were sorted, two pointers would apply. Unsorted means hash map.
python
def two_sum(nums, target):
seen = {}
for i, x in enumerate(nums):
if target - x in seen:
return [seen[target - x], i]
seen[x] = i
return NoneWhat to watch for. If you diagnosed “two pointers” here, the miss is the unsorted condition. The unsorted-versus-sorted check is the most important disambiguation for pair problems, and it belongs in your first ninety seconds every time you see “find a pair.” Check sortedness before reaching for either tool.
Problem 2 answer: Sliding Window (fixed-size)
Signal: “contiguous subarray of size exactly k” with a maximum.
Pattern: fixed-size sliding window from Episode 2. Compute the first window once, then slide by adding the entering element and subtracting the leaving one. O(n) time, O(1) space.
python
def max_sum_k(nums, k):
window = sum(nums[:k])
best = window
for i in range(k, len(nums)):
window += nums[i] - nums[i-k]
best = max(best, window)
return bestDisambiguation: “contiguous” is the loudest signal in the problem. “Exactly k” (fixed size) distinguishes this from the variable-size variant.
If the problem said “longest subarray with sum at most k” or “minimum subarray with sum at least k,” the size would not be fixed and the variable-size form would apply.
What to watch for. If you diagnosed “dynamic programming” here, the miss is the contiguous constraint. DP handles subsequences (non-contiguous), whereas “contiguous” and “subarray” point to the sliding window.
The sliding window’s linear pass is only possible because of contiguity: you can update the window by adding one element and removing one, which only works when the window is a continuous range.
Problem 3 answer: Binary Search (boundary variant)
Signal: “first bad version” in a sequence where all subsequent versions after the first bad one are also bad, with a yes/no test function.
Pattern: binary search on the answer space, specifically the “find first” boundary variant from Episode 3. The versions are implicitly sorted (1 through n), and the condition “is this version bad?” flips from false to true exactly once. Find that boundary with binary search.
The API call count matters because binary search reduces it from O(n) to O(log n).
python
def first_bad_version(n, isBadVersion):
lo, hi = 1, n
while lo < hi:
mid = lo + (hi - lo) // 2
if isBadVersion(mid):
hi = mid # could be the first bad; keep looking left
else:
lo = mid + 1
return loDisambiguation: the word “minimize the number of API calls” is the tell that linear scan is not expected.
A linear scan from version 1 is correct but O(n) calls. Binary search is O(log n). This problem in a slightly different dress (find the smallest true in a sequence of false-then-true) appears in many interview problems and always resolves to binary search on the answer space.
What to watch for. If you diagnosed no pattern, the miss is not recognizing that a binary yes/no function over a sorted or monotonic space is always a binary search opportunity.
The product manager framing hides the structure. Strip away the story: you have a range [1,n], a monotonic yes/no function, and you want the boundary. That is binary search.
Problem 4 answer: DFS flood fill (graph traversal on a grid)
Signal: two-dimensional grid where you need to count connected components.
Pattern: DFS (or BFS) flood fill from Episode 4. The grid is a graph: each ‘1’ cell is a node, adjacent ‘1’ cells are connected by edges. Counting islands is counting connected components. Scan every cell; when you find an unvisited ‘1’, flood-fill its entire island (DFS or BFS) marking everything visited, and increment the count.
python
def num_islands(grid):
rows, cols = len(grid), len(grid[0])
grid = [row[:] for row in grid]
count = 0
def dfs(r, c):
if r<0 or r>=rows or c<0 or c>=cols or grid[r][c]!='1': return
grid[r][c] = '0'
dfs(r+1,c); dfs(r-1,c); dfs(r,c+1); dfs(r,c-1)
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1': dfs(r,c); count += 1
return countDisambiguation: this is not a sliding window (the window is contiguous and one-dimensional). It is not dynamic programming (we are not computing an optimal value, we are counting components).
The two-dimensional grid structure plus “connected” plus “count” is the DFS/BFS connected-components signal.
What to watch for. If you diagnosed “DP” here, the miss is the distinction between counting components (traversal) and counting paths or ways (DP).
Number of islands is counting how many separate connected groups exist, not how many ways you can traverse the grid. Traversal problems are BFS/DFS. Counting-ways problems are DP.
Problem 5 answer: Sliding Window (variable-size)
Signal: “minimum window substring” containing all characters of t.
Pattern: variable-size sliding window from Episode 2, specifically the shortest-valid form (shrink while valid, not when invalid).
Expand the right edge until the window contains all required characters, then shrink the left edge as much as possible while still containing all required characters.
Use a frequency map (from Episode 1’s hash map pattern) to track what the window still needs.
This is the canonical two-pattern combination from Episode 2: sliding window plus frequency counting.
python
from collections import Counter
def min_window(s, t):
need = Counter(t)
missing = len(t)
best = ""
lo = 0
for hi, ch in enumerate(s):
if need[ch] > 0: missing -= 1
need[ch] -= 1
if missing == 0:
while need[s[lo]] < 0: need[s[lo]] += 1; lo += 1
if not best or hi-lo+1 < len(best): best = s[lo:hi+1]
need[s[lo]] += 1; missing += 1; lo += 1
return bestDisambiguation: this is a minimum-window problem (shortest-valid shrink form), not longest-window (shrink-when-invalid form).
“Minimum window” is the tell for shortest-valid. “Longest substring without repeating” is the tell for shrink-when-invalid.
What to watch for. If you diagnosed “DP” or “brute force,” the miss is not recognizing the window structure. The string s is being scanned linearly and a contiguous window is being maintained.
Any time you need the shortest or longest contiguous substring satisfying a condition, sliding window applies.
The frequency map for “contains all characters of t” is the Episode 1 hash map inside the Episode 2 window.
Problem 6 answer: Dynamic Programming (optimization shape)
Signal: “fewest number of coins” to make an amount, using coins with unlimited reuse.
Pattern: dynamic programming, optimization shape from Episode 5. The subproblem is dp[a] = the minimum coins to make amount a.
The recurrence is: for each amount, try every coin denomination and take the minimum. dp[a] = min over all coins c of (dp[a-c] + 1). Base case: dp[0] = 0.
python
def coin_change(coins, amount):
dp = [0] + [float('inf')] * amount
for a in range(1, amount+1):
for c in coins:
if c <= a and dp[a-c]+1 < dp[a]:
dp[a] = dp[a-c]+1
return dp[amount] if dp[amount] != float('inf') else -1Disambiguation: the key DP signals are all present: an optimization goal (”fewest”), a sequence of choices (which coin at each step), and reused subproblems (making amount 8 reuses the answer for making amount 6 regardless of what larger amounts it feeds into).
The “unlimited reuse” of coins is the unbounded knapsack variant (versus 0/1 knapsack where each item is used at most once).
What to watch for. If you diagnosed “greedy,” note that greedy does not work for arbitrary coin denominations.
For [1,5,6] with target 10, greedy picks 6+1+1+1+1 (5 coins), but optimal is 5+5 (2 coins). DP is required when greedy’s locally optimal choice does not lead to the globally optimal solution.
The coin change problem is the standard example of when greedy fails.
Problem 7 answer: Hash Map then Heap
Signal: “k most frequent elements.”
Pattern: two-step from Episodes 1 and (Episode 8’s preview): frequency count with a hash map, then extract the top K using a heap.
Count each element’s occurrences in one pass. Use a min-heap of size K or heapq.nlargest to extract the K items with the highest counts.
python
from collections import Counter
import heapq
def top_k_frequent(nums, k):
counts = Counter(nums)
return [x for x, _ in heapq.nlargest(k, counts.items(), key=lambda p: p[1])]Disambiguation: “top K” or “K most frequent” is the heap signal (covered fully in Episode 8). The reason a heap beats sorting: sorting all elements is O(n log n). A size-K heap extraction is O(n log K), better when K is small.
The hash map is the prerequisite (you need the counts before you can rank them).
What to watch for. If you diagnosed “sort and slice,” that is correct but suboptimal. Sorting the full frequency map is O(n log n). The heap approach is O(n log K). Both are accepted in interviews, but naming the heap approach and explaining the improvement is the signal of deeper knowledge.
Problem 8 answer: Expand Around Center
Signal: “longest palindromic substring.”
Pattern: expand around center, which is not one of the six primary patterns in this series but is the standard O(n squared) approach for this specific problem.
For each index, treat it as the center of a palindrome and expand outward while the characters match. Try both odd-length centers (single character) and even-length centers (gap between two characters).
python
def longest_palindrome(s):
def expand(l, r):
while l >= 0 and r < len(s) and s[l] == s[r]:
l -= 1; r += 1
return s[l+1:r]
best = ""
for i in range(len(s)):
for p in [expand(i, i), expand(i, i+1)]:
if len(p) > len(best): best = p
return bestThis problem is worth including in the drill precisely because it does not map to one of the primary six patterns.
Pattern recognition includes recognizing when a problem falls outside your primary toolkit and reaching for a problem-specific technique.
Disambiguation: this is not a sliding window.
A sliding window maintains a window that expands from one end and shrinks from the other, scanning left to right.
Palindrome checking requires bidirectional expansion from a center. It is not DP (DP for palindromes exists but is O(n squared) time and O(n squared) space, strictly worse than O(n squared) time O(1) space expand-around-center). It is not two pointers (the two-pointer approach works for palindrome detection on a full string, not finding the longest palindromic substring).
What to watch for. If you diagnosed “DP,” you are not wrong (DP can solve this), but you are reaching for a tool with worse space complexity when a simpler O(1) space approach exists. Recognizing when a simpler approach beats DP is itself a useful skill.
Problem 9 answer: Fast and Slow Pointers
Signal: “cycle in a linked list,” detect with O(1) extra space.
Pattern: fast and slow pointers (Floyd’s algorithm) from Episode 6.
One pointer moves one step per iteration, the other moves two steps. If a cycle exists, the fast pointer eventually laps the slow pointer inside the cycle and they meet. If no cycle exists, the fast pointer reaches the end.
python
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True
return FalseDisambiguation: a hash set of visited nodes also works and is simpler to reason about, but uses O(n) space.
The fast and slow approach uses O(1) space, which is why it is the preferred interview answer when the interviewer implies O(1) space is desired (or when they ask “can you do it without extra space?”).
What to watch for. If you diagnosed “hash set,” you have a correct approach but missed the O(1) space opportunity. In an interview, state the hash set approach first as the obvious solution, then improve it to fast and slow. This demonstrates both knowledge of the direct approach and the more elegant optimization.
Problem 10 answer: Sort then Sweep (Merge Intervals)
Signal: “merge all overlapping intervals.”
Pattern: sort by start time, then sweep.
After sorting, each interval either overlaps the last merged interval (extend it to the larger end) or does not overlap (start a new merged interval). You only ever compare the current interval to the last merged one.
python
def merge_intervals(intervals):
intervals.sort(key=lambda x: x[0])
merged = [intervals[0][:]]
for start, end in intervals[1:]:
if start <= merged[-1][1]:
merged[-1][1] = max(merged[-1][1], end)
else:
merged.append([start, end])
return mergedDisambiguation: this is not a sliding window (intervals can have arbitrary gaps, and you are not maintaining a continuous window of data). It is not DP (you are not building an optimal value from subproblems; you are greedily merging).
The sort-and-sweep approach works because sorting creates the invariant that makes greedy correct: once you have processed interval i, no interval before i can overlap anything after i.
What to watch for. The merge condition is start <= merged[-1][1] (less than or equal), not strict less than. Two intervals that share only an endpoint (like [1,4] and [4,5]) should merge to [1,5]. Using strict less than would incorrectly treat them as non-overlapping.
Scoring Your Diagnoses
Count how many you diagnosed correctly with the right signal. Here is a rough calibration:
Nine or ten correct: your pattern recognition is interview-ready for these six patterns. Focus your remaining preparation on the patterns in Episodes 8 through 10 (heaps, backtracking, and the final integration drill) and on practicing under time pressure in mock interviews.
Six to eight correct: solid foundation with a few gaps. Review the episodes for the patterns you missed and do two or three more problems in those specific categories. Pay attention to which signals you are misreading.
Three to five correct: your pattern knowledge is there but your recognition is not yet automatic.
Go back to the practice loop from each episode: for every practice problem, force a ninety-second diagnosis before touching any code. The recognition reflex is built by repeating the diagnosis step deliberately, not by solving more problems.
Fewer than three correct: you have the right instinct by being here (practice is the right move) but your pattern vocabulary needs more depth before diagnosis can work.
Return to Episodes 1 through 6, pick two problems from each episode’s practice section, and solve them while naming the pattern and signal before coding. Come back to this drill in a week.
What the Drill Reveals about Your Preparation
The diagnoses you missed reveal something specific about your preparation, and it is almost never “I don’t know this pattern.”
More commonly, it is one of three things.
Pattern boundary confusion: You know sliding window and DP, but you are not sure which applies when. The disambiguation notes in each answer key address this directly. For every incorrect diagnosis, read the disambiguation for that problem and the one you diagnosed instead. The confusion is almost always at the boundary between two patterns, and naming the specific boundary (contiguous means sliding window, non-contiguous means DP) makes it crisp.
Signal blindness: You know the patterns but cannot find the signal in the problem statement. For each miss, reread the problem and find the specific phrase that should have triggered the pattern before you read the answer. Train yourself to underline that phrase mentally in every problem. Over time, the signals become visible by reflex.
Surface-form fixation: You recognize patterns in the forms you practiced but not in their disguises. Number of islands looks like a grid problem, not a graph problem, until you recognize that a grid is a graph. First bad version looks like a story problem, not a binary search, until you see the monotonic yes/no function over a sorted range. The cure for surface-form fixation is practicing on problems where the graph or the binary search is hidden, not announced.
The Two-question Discipline
Before closing this episode, lock in the two questions that generate a complete diagnosis. These are the exact two things to say out loud in an interview before touching the keyboard.
Question 1: What pattern does this problem want?
Name it by its pattern name (hash map, sliding window, binary search, BFS, DFS, dynamic programming, fast and slow pointers, merge intervals, heap, backtracking). A named pattern is a starting point. An unnamed vague sense is not.
Question 2: What is the specific signal that told me?
Name the phrase or condition in the problem that pointed to the pattern (”contiguous subarray” for sliding window, “unsorted, find a pair” for hash map, “minimum steps” for BFS, “fewest or optimal” for DP). A stated signal is evidence. The interviewer wants evidence, not conclusions.
Together these two questions produce: “I think this is a sliding window because the problem asks for the longest contiguous substring, and ‘contiguous’ is the tell for sliding windows.”
That sentence, stated before writing code, is what pattern recognition looks like from the outside.
The drill in this episode is building the reflex that produces that sentence automatically.
What Comes Next
Episode 8 covers heaps and priority queues, the pattern behind every “top K” problem and any problem that repeatedly needs the current minimum or maximum. You saw the heap preview in Problem 7 of this drill (top K frequent elements), and you saw how merge K sorted lists from Episode 6 connects to heaps.
Episode 8 makes both concrete with the full heap pattern, the size-K min-heap trick, and the problems that look like they need sorting but actually need a heap.
Between Episodes 7 and 8, run this drill again, but with a timer this time.
Set ninety seconds per problem and stop at the buzzer, whether or not you have a diagnosis.
The time constraint is part of the training: in an interview, you do not have the luxury of thinking for as long as you need.
The reflex has to work fast, and fast reflexes are only built under speed.
How many did you diagnose correctly on the first pass?