Common Pattern and Data Structure Questions
35 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)Most interview questions are one of a dozen patterns in new clothes. Learn the clue that points to each pattern and the one sentence of cost you say after coding it. The patterns themselves are taught in the Problem Solving Patterns and Data Structures sections; here you practise naming and explaining them. Find more questions in the Python DSA 150 sheet at /learn/python/dsa-sheet.
Match the clue to the tool
A pattern clue is a phrase in the problem that points to a known technique, such as 'sorted array and a pair' for two pointers or 'top k' for a heap. Naming the clue shows you recognise the problem type.
Most interview problems repeat a few patterns. Read the problem for a clue, name the pattern aloud, then code it. Revise: Two pointers from both ends (opens in a new tab)
- Sorted data and a pair or triple: two pointers. Longest or shortest part with a condition: sliding window.
- Count, group or 'seen before': dict, Counter or set. Many range sums: prefix sums.
- Top k or running smallest: heap. Next greater item: monotonic stack.
- Search in sorted data: binary search or
bisect. Matching brackets or undo: stack.
Hash map questions: count, group and find
A frequency map is a dict that stores how many times each value appears. In Python, collections.Counter builds one in a single line and runs in O(n) time.
A dict turns a search into a lookup. Say what the key is and what the value stores.
from collections import defaultdict
def group_anagrams(words): groups = defaultdict(list) for word in words: groups["".join(sorted(word))].append(word) return list(groups.values())
print(group_anagrams(["listen", "silent", "enlist", "google", "gogole"]))The key is the sorted letters, so anagrams share a key. With n words of length k, the cost is O(n k log k) time and O(n k) space.
Sliding window and prefix sums
A sliding window is a range of a list with a left and a right end that move forward together. It turns repeated work over overlapping parts into one pass, O(n) time.
A window avoids recomputing the sum of an overlapping part. Add the item that enters, remove the item that leaves. Revise: Variable-size windows (opens in a new tab)
def best_window(marks, k): window = sum(marks[:k]) best = window for i in range(k, len(marks)): window += marks[i] - marks[i - k] best = max(best, window) return best
print(best_window([4, 2, 9, 1, 7, 3], 3))Example 1 · Subarray sum equals k: brute force, then prefix sums with a dict
def count_brute(nums, k): # O(n^2): try every start and extend. count = 0 for start in range(len(nums)): total = 0 for end in range(start, len(nums)): total += nums[end] if total == k: count += 1 return count
def count_prefix(nums, k): # O(n): a part sums to k when prefix - earlier prefix == k. seen = {0: 1} prefix = count = 0 for value in nums: prefix += value count += seen.get(prefix - k, 0) seen[prefix] = seen.get(prefix, 0) + 1 return count
nums = [1, 2, 3, -3, 1, 1, 1]print(count_brute(nums, 3), count_prefix(nums, 3))6 6
What this code does
- The brute force restarts the sum at every start. The prefix version remembers how often each running total has appeared.
- Seeding the dict with {0: 1} counts parts that begin at index 0. Negative numbers are why a sliding window would not work here.
Example 2 · Longest substring without repeating characters
def longest_brute(text): best = 0 for start in range(len(text)): seen = set() for ch in text[start:]: if ch in seen: break seen.add(ch) best = max(best, len(seen)) return best
def longest_window(text): last = {} # character -> latest index start = best = 0 for i, ch in enumerate(text): if ch in last and last[ch] >= start: start = last[ch] + 1 last[ch] = i best = max(best, i - start + 1) return best
for word in ["abcabcbb", "bbbbb", ""]: print(longest_brute(word), longest_window(word))3 3 1 1 0 0
What this code does
- The brute force is O(n squared). The window keeps the last index of each character and jumps the start past a repeat.
- Each character is visited once, so it is O(n) time and O(k) space for k different characters. Test the empty string.
Say: "I add the new mark and drop the oldest, so each step is O(1) and the whole pass is O(n)."
Heaps, stacks and bisect
A monotonic stack is a stack whose items always stay in increasing or decreasing order. Each item is pushed and popped once, so a pass costs O(n) time. It answers 'next greater item' questions.
Three small tools answer many questions. heapq gives the smallest item fast. A stack remembers items waiting for an answer. bisect finds a position in sorted data by halving.
Revise: Top k with a heap (opens in a new tab)
Example 3 · Top k frequent words with Counter and a heap
import heapqfrom collections import Counter
words = "ticket order ticket refund order ticket invoice refund ticket".split()counts = Counter(words)print(counts.most_common(2))top = heapq.nlargest(2, counts, key=counts.get)print(top)[('ticket', 4), ('order', 2)]
['ticket', 'order']What this code does
most_common(k)andheapq.nlargest(k, ...)both run in about O(n log k) time. They are short and fine to use in Python.- If asked to write it by hand, keep a min-heap of size k and drop the smallest when it grows past k.
Example 4 · Daily temperatures with a monotonic stack
def days_until_warmer(temps): answer = [0] * len(temps) stack = [] # indices still waiting for a warmer day for i, temp in enumerate(temps): while stack and temps[stack[-1]] < temp: j = stack.pop() answer[j] = i - j stack.append(i) return answer
print(days_until_warmer([73, 74, 75, 71, 69, 72, 76, 73]))[1, 1, 4, 2, 1, 1, 0, 0]
What this code does
- The stack holds days with no warmer day yet. A warmer day resolves every colder day on top of the stack.
- Each index is pushed once and popped once, so the cost is O(n) time and O(n) space, although there is a loop inside a loop.
Example 5 · Valid brackets with a stack, and bisect on sorted data
from bisect import bisect_left
def is_valid(text): pairs = {")": "(", "]": "[", "}": "{"} stack = [] for ch in text: if ch in pairs: if not stack or stack.pop() != pairs[ch]: return False else: stack.append(ch) return not stack
print(is_valid("([]{})"), is_valid("([)]"), is_valid("(("))prices = [10, 20, 20, 40]print(bisect_left(prices, 20), bisect_left(prices, 25))True False False 1 3
What this code does
- The stack matches each closing bracket with the latest opening one. The final
not stackcatches leftover openings. bisect_leftreturns the first position where the value could be inserted: O(log n) on sorted data.
Next step
Check your understanding
12 quick questions