The Core Interview Patterns
9 min read- The Core Interview Patterns
- TL;DR
- How it works
- Pattern 1 — hash counting: "I keep rescanning for something I already saw"
- Pattern 2 — two pointers: "the input is sorted, so I can move both ends inwards"
- Pattern 3 — sliding window: "contiguous run, and I keep recomputing its aggregate"
- Pattern 4 — prefix sums: "I keep re-adding the same range"
- Pattern 5 — fast and slow pointers: cycle detection in O(1) space
- Pattern 6 — top-k with a heap: "I sorted everything but only needed k"
- Pattern 7 — sort by start, then sweep: intervals
- Key takeaways
The Core Interview Patterns
TL;DR
A small number of linear-scan patterns cover most of the "make this O(n²) solution faster" questions: hash counting, two pointers, sliding window, prefix sums, fast/slow pointers, top-k with a heap, and interval sorting. Each one removes a specific redundancy from a nested loop. Learning to name the redundancy — "I am rescanning what I already saw", "I am recomputing a sum I could have carried" — is what lets you pick the right pattern instead of pattern-matching on the problem's surface wording.
How it works
Pattern 1 — hash counting: "I keep rescanning for something I already saw"
// Two-sum. Brute force is O(n^2): for each element, rescan for the complement.
// The rescan is redundant because we already walked those elements once.
public static (int, int)? TwoSum(int[] nums, int target)
{
var seen = new Dictionary<int, int>(); // value -> index
for (int i = 0; i < nums.Length; i++)
{
if (seen.TryGetValue(target - nums[i], out int j)) return (j, i);
seen[nums[i]] = i;
}
return null;
}O(n) time, O(n) space. This is the single most common improvement in interviews: trade memory for the rescan. The same shape solves anagram grouping, duplicate detection, first-unique-character, and subarray-sum-equals-k (with prefix sums as the key).
Pattern 2 — two pointers: "the input is sorted, so I can move both ends inwards"
// Sorted two-sum in O(1) space -- no hash needed because order carries information.
public static (int, int)? TwoSumSorted(int[] sorted, int target)
{
int lo = 0, hi = sorted.Length - 1;
while (lo < hi)
{
int sum = sorted[lo] + sorted[hi];
if (sum == target) return (lo, hi);
if (sum < target) lo++; // only increasing the small end can help
else hi--; // only decreasing the big end can help
}
return null;
}The correctness argument is the interesting part: at each step, one of the two candidates is provably in no valid pair, so discarding it loses nothing. Being able to state that is worth more than the code.
Pattern 3 — sliding window: "contiguous run, and I keep recomputing its aggregate"
// Longest substring without repeating characters.
public static int LongestUnique(string s)
{
var lastSeen = new Dictionary<char, int>();
int best = 0, start = 0;
for (int end = 0; end < s.Length; end++)
{
// Only ever move `start` forward -- never backwards -- which is what
// keeps the total work O(n) rather than O(n^2).
if (lastSeen.TryGetValue(s[end], out int prev) && prev >= start)
start = prev + 1;
lastSeen[s[end]] = end;
best = Math.Max(best, end - start + 1);
}
return best;
}The window is valid when the problem says contiguous and the validity condition is monotonic — growing the window can only ever make it "more invalid", so shrinking from the left is guaranteed to restore validity. If that monotonicity does not hold, a sliding window is silently wrong.
Pattern 4 — prefix sums: "I keep re-adding the same range"
Precompute prefix[i] = sum of the first i elements, then any range sum is prefix[hi] - prefix[lo] in O(1). Combined with a hash of previously-seen prefix values, this turns "count subarrays summing to k" from O(n²) into O(n). The generalisation is any invertible aggregate — sums, XOR, counts — but not min or max, which have no inverse and need a sparse table or monotonic deque instead.
Pattern 5 — fast and slow pointers: cycle detection in O(1) space
Floyd's tortoise and hare: advance one pointer by one step and another by two. If there is a cycle they must eventually meet, because the gap between them changes by exactly one each step and therefore hits zero modulo the cycle length. Used for linked-list cycle detection, finding the cycle entry point, and finding the middle of a list in one pass.
Pattern 6 — top-k with a heap: "I sorted everything but only needed k"
// k largest elements. O(n log k) time and O(k) space -- not O(n log n).
public static IEnumerable<int> TopK(IEnumerable<int> source, int k)
{
var minHeap = new PriorityQueue<int, int>(); // .NET 6+
foreach (int x in source)
{
minHeap.Enqueue(x, x);
if (minHeap.Count > k) minHeap.Dequeue(); // evict the smallest
}
return minHeap.UnorderedItems.Select(t => t.Element);
}Note the counter-intuitive bit: for the k largest you keep a min-heap, so the cheapest element to evict is always at the top. This also works on a stream of unknown length, which a sort does not.
Pattern 7 — sort by start, then sweep: intervals
Merging overlapping intervals, meeting-room counts, and calendar conflicts are all "sort by start time, then sweep while carrying the current end". The O(n log n) is the sort; the sweep is O(n). If you need the maximum concurrent count, sweep the start and end events separately as a timeline.
A: Replace an inner rescan with a hash lookup. The quadratic term almost always comes from "for each element, look through the others for something", and if that something is an exact-match query — a complement, a duplicate, a previously-seen prefix sum — a dictionary or set answers it in O(1) average. You pay O(n) memory for the map, which is the classic time-for-space trade. The tell in the code is a nested loop whose inner loop walks elements you have already visited in the outer loop.
A: It applies when the answer is a contiguous subarray or substring and the validity condition is monotonic — extending the window can only preserve or break validity, and shrinking from the left can only restore it. That monotonicity is what justifies never moving the left pointer backwards, which is exactly what keeps the total work O(n). It is silently wrong when validity is not monotonic, for example when negative numbers mean a longer window can have a smaller sum, so shrinking the window does not reliably help; there you need prefix sums with a hash map instead.
A: Because the decision to move a pointer must be provably safe, and it is the ordering that provides the proof. In sorted two-sum, if the current pair sums to less than the target then no pair using the current low element can reach the target, since the high element is already the largest available — so discarding the low element loses nothing. Without ordering, moving either pointer might skip the answer, and you have no basis for choosing which to move. Unsorted input needs a hash instead, which trades the O(1) space for O(n).
A: Keep a min-heap of size k: push each element, and whenever the heap exceeds k, pop the smallest. At the end the heap holds exactly the k largest, at O(n log k) time and O(k) space instead of O(n log n) and O(n). The counter-intuitive part is using a min-heap for the largest elements — the root is the weakest survivor, which is precisely the one to evict when a stronger candidate arrives. It also works on a stream of unknown or unbounded length, where sorting is not an option at all.
A: They eliminate repeated re-summation of overlapping ranges: precompute cumulative totals once in O(n) and any range sum becomes a single subtraction in O(1), which turns range-query loops from O(n·q) into O(n + q). Combined with a hash of previously-seen prefix values they answer "how many subarrays sum to k" in one pass. The limitation is that the technique needs an invertible aggregate — sum, XOR, and count work because you can subtract the prefix off; minimum and maximum do not, since there is no inverse, so range-min queries need a sparse table, segment tree, or monotonic deque instead.
A: You advance a slow pointer one step and a fast pointer two steps per iteration. If the sequence is acyclic the fast pointer runs off the end; if there is a cycle both pointers eventually enter it, and since the fast one closes the gap by exactly one position each iteration, the gap must reach zero and they meet. It is O(1) space because it stores two pointers rather than a visited set, which is the whole point compared with the hash-set approach — it is the technique to reach for when the input is huge or the "nodes" are generated rather than stored, as in detecting cycles in a functional iteration.
A: Sort the intervals by start time, then sweep once carrying the current merged interval: if the next interval starts at or before the current end, extend the end to the maximum of the two ends; otherwise emit the current one and start a new one. Total cost is O(n log n), dominated entirely by the sort, with the sweep O(n) and O(1) extra space beyond the output. Sorting by start is the load-bearing step because it guarantees that any interval overlapping the current one must be the next one you encounter, so a single pass suffices.
A: Write the brute force and name the specific redundancy in it. If the inner loop re-searches elements already visited, that is hash counting. If it recomputes an aggregate over a contiguous range that mostly overlaps the previous range, that is sliding window or prefix sums. If it compares every pair in sorted data, that is two pointers. If it sorts everything to look at only a few, that is a heap. If it re-solves identical subproblems, that is memoisation. The pattern follows from the redundancy, which is why naming the redundancy out loud beats trying to recall which named technique the question resembles.
Key takeaways
- Pick the pattern by naming the redundancy in the brute force, not by matching the problem's wording.
- Hash counting is the workhorse: it removes rescans and trades O(n) memory for an O(n) runtime.
- Sliding window is only valid when the validity condition is monotonic — otherwise it is silently wrong.
- Two pointers needs sorted input, because ordering is what proves a pointer move discards nothing.
- For k largest keep a min-heap of size k: O(n log k), O(k) space, and it works on streams.
- Prefix sums need an invertible aggregate — sums and XOR yes, min and max no.