Python for Coding Interviews: Data Structures Companion Guide
Our Data Structures for Coding Interviews guide covers the concepts and patterns. This companion covers the other half: how to implement them in Python quickly and correctly during a live interview. If you’re building your full preparation plan, start with the How to Prepare for a Coding Interview guide first.
Most Python interview solutions rely on a small set of built-in tools and a handful of templates. If you know the right tool for each data structure, the right idiom for each pattern, and the common pitfalls that cost time under pressure, you can write clean solutions fast. That’s what this guide teaches.
Want to test your Python fluency under real interview pressure? Try a mock coding interview on Intervu →
1. Python Data Structure Cheat Sheet
Every conceptual data structure maps to a specific Python built-in. Reaching for the right one without hesitation is the first signal interviewers notice.
Basic Containers
| Structure | Python Tool | When to Use | Example Problem |
|---|---|---|---|
| Array / String | list, str | Indexed access, in-place manipulation, sequential iteration | Two Sum, sliding window |
| Hash Map | dict | O(1) lookup, frequency counting, memoization | LRU Cache, Group Anagrams |
| Hash Set | set | O(1) membership check, deduplication, visited tracking | Longest Consecutive Sequence |
| Stack | list | LIFO — matching brackets, undo, monotonic patterns | Valid Parentheses |
| Queue | collections.deque | FIFO — BFS, level-order traversal, sliding window max | Binary Tree Level Order |
Priority and Ordering
| Structure | Python Tool | When to Use |
|---|---|---|
| Min-Heap | heapq | Top-K problems, streaming min/max, merge K sorted |
| Max-Heap | heapq (negated values) | Kth largest, greedy scheduling |
| Sorted Output | sorted() | One-time sort; not for dynamic ordering |
Custom Structures (implement from scratch)
| Structure | Python Tool | When to Use |
|---|---|---|
| Tree Node | class TreeNode | Binary trees, BSTs, recursion problems |
| Graph | defaultdict(list) | Adjacency list for BFS/DFS |
| Trie | class TrieNode | Prefix search, autocomplete, word matching |
| Union Find | parent[] + rank[] | Dynamic connectivity, grouping, component counting |
[!TIP] Quick rule: O(1) lookup →
dict/set. Ordered min/max →heapq. FIFO →deque. LIFO →list.
2. Python Syntax You Must Know Cold
These idioms should be muscle memory. Hesitating on syntax during an interview burns time and breaks your flow.
enumerate — index + value in one pass
for i, val in enumerate(nums):
print(i, val)
zip — iterate two sequences together
for a, b in zip(list1, list2):
print(a, b)
reversed — iterate backwards without copying
for val in reversed(nums):
print(val)
sorted with key — custom sort order
# Sort intervals by start time
intervals.sort(key=lambda x: x[0])
# Sort by multiple keys
words.sort(key=lambda w: (-len(w), w)) # longest first, then alphabetical
defaultdict — auto-initialize missing keys
from collections import defaultdict
graph = defaultdict(list)
graph[u].append(v) # no KeyError if u is new
Counter — frequency counting in one line
from collections import Counter
freq = Counter("aabbc") # {'a': 2, 'b': 2, 'c': 1}
freq.most_common(2) # [('a', 2), ('b', 2)]
Set membership — O(1) lookup
seen = set()
if val not in seen:
seen.add(val)
Tuple ordering — free comparison
# Python compares tuples element-by-element
# Useful for heap entries and sorting
heap_entry = (distance, node_id)
heapq — min-heap operations
import heapq
heap = []
heapq.heappush(heap, 5)
smallest = heapq.heappop(heap)
heapq.heapify(existing_list) # O(n) in-place
List comprehensions — concise transforms
squares = [x * x for x in range(10)]
evens = [x for x in nums if x % 2 == 0]
flat = [val for row in grid for val in row]
3. Core Python Templates by Data Structure
Each template below is interview-ready. Understand it, memorize the shape, and adapt it to the problem.
Arrays and Strings
Arrays are the foundation of coding interviews. Most multi-pointer and window problems use two patterns — see the sliding window template and two pointers template below.
Two Pointers — sorted arrays, pair-finding, partitioning.
def two_sum_sorted(nums, target):
left, right = 0, len(nums) - 1
while left < right:
total = nums[left] + nums[right]
if total == target:
return [left, right]
elif total < target:
left += 1
else:
right -= 1
return []
[!NOTE] Complexity: O(n) time, O(1) space.
Sliding Window — contiguous subarrays or substrings.
def max_sum_subarray(nums, k):
window_sum = sum(nums[:k])
best = window_sum
for i in range(k, len(nums)):
window_sum += nums[i] - nums[i - k]
best = max(best, window_sum)
return best
[!NOTE] Complexity: O(n) time, O(1) space.
Variable-length sliding window:
def longest_unique_substring(s):
seen = {}
left = 0
best = 0
for right, ch in enumerate(s):
if ch in seen and seen[ch] >= left:
left = seen[ch] + 1
seen[ch] = right
best = max(best, right - left + 1)
return best
Prefix Sums — O(1) range-sum queries after O(n) setup.
def subarray_sum_equals_k(nums, k):
prefix = {0: 1}
total = 0
count = 0
for num in nums:
total += num
if total - k in prefix:
count += prefix[total - k]
prefix[total] = prefix.get(total, 0) + 1
return count
[!NOTE] Complexity: O(n) time, O(n) space.
Hash Maps and Sets
Hash maps are the Swiss Army knife of interview optimization — whenever you’re searching repeatedly, counting, or need to remember something you’ve seen, reach for dict. The canonical example is Two Sum: instead of a nested O(n²) loop, one pass with a dict gives O(n).
Counting occurrences:
from collections import Counter
def majority_element(nums):
counts = Counter(nums)
return counts.most_common(1)[0][0]
First occurrence / two-pass lookup:
def two_sum(nums, target):
seen = {}
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
Grouping by key:
from collections import defaultdict
def group_anagrams(strs):
groups = defaultdict(list)
for s in strs:
key = tuple(sorted(s))
groups[key].append(s)
return list(groups.values())
Stacks
Basic stack pattern:
def is_valid_parentheses(s):
stack = []
pairs = {')': '(', ']': '[', '}': '{'}
for ch in s:
if ch in pairs:
if not stack or stack[-1] != pairs[ch]:
return False
stack.pop()
else:
stack.append(ch)
return len(stack) == 0
Monotonic stack — next greater element:
def daily_temperatures(temps):
n = len(temps)
result = [0] * n
stack = [] # indices of temps we haven't resolved
for i, temp in enumerate(temps):
while stack and temps[stack[-1]] < temp:
prev = stack.pop()
result[prev] = i - prev
stack.append(i)
return result
[!NOTE] Complexity: O(n) time. Each index is pushed and popped at most once.
Queues
BFS with deque:
from collections import deque
def bfs(graph, start):
visited = {start}
queue = deque([start])
while queue:
node = queue.popleft()
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
[!WARNING] Why
list.pop(0)is a trap: Removing from the front of a Python list is O(n) because every element shifts left.deque.popleft()is O(1). In a BFS with thousands of nodes, this difference turns a linear algorithm into a quadratic one causingTime Limit Exceeded.
Heaps
Top K elements:
import heapq
def top_k_frequent(nums, k):
counts = Counter(nums)
return heapq.nlargest(k, counts.keys(), key=counts.get)
Manual heap push/pop:
heap = []
heapq.heappush(heap, (cost, node))
cost, node = heapq.heappop(heap) # smallest cost first
Max heap using negation:
Python’s heapq is a min-heap only. To simulate a max-heap, negate values:
max_heap = []
heapq.heappush(max_heap, -value)
largest = -heapq.heappop(max_heap)
Trees
Recursive DFS — most tree problems:
def max_depth(root):
if not root:
return 0
return 1 + max(max_depth(root.left), max_depth(root.right))
Iterative DFS — when recursion depth is a concern:
def inorder_iterative(root):
result = []
stack = []
current = root
while current or stack:
while current:
stack.append(current)
current = current.left
current = stack.pop()
result.append(current.val)
current = current.right
return result
BFS level-order traversal:
from collections import deque
def level_order(root):
if not root:
return []
result = []
queue = deque([root])
while queue:
level = []
for _ in range(len(queue)):
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level)
return result
Graphs
Adjacency list construction:
from collections import defaultdict
def build_graph(edges):
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u) # omit for directed graphs
return graph
DFS on a graph:
def dfs(graph, node, visited):
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
dfs(graph, neighbor, visited)
BFS shortest path:
from collections import deque
def shortest_path(graph, start, end):
queue = deque([(start, 0)])
visited = {start}
while queue:
node, dist = queue.popleft()
if node == end:
return dist
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, dist + 1))
return -1
Trie
A minimal Python trie that handles insert, search, and startsWith:
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for ch in word:
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
node.is_end = True
def search(self, word):
node = self._find(word)
return node is not None and node.is_end
def startsWith(self, prefix):
return self._find(prefix) is not None
def _find(self, prefix):
node = self.root
for ch in prefix:
if ch not in node.children:
return None
node = node.children[ch]
return node
Union Find
Path compression + union by rank in a clean class:
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
self.components = n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # path compression
return self.parent[x]
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py:
return False
if self.rank[px] < self.rank[py]:
px, py = py, px
self.parent[py] = px
if self.rank[px] == self.rank[py]:
self.rank[px] += 1
self.components -= 1
return True
[!NOTE] Complexity: Both
findandunionrun in O(α(n)) amortized, which is effectively O(1).
4. Pattern → Python Template Mapping
Interview problems follow patterns. Recognizing the pattern tells you which template to reach for.
Array / String Patterns
| Pattern | You’ll see… | Template shape | Typical Problems |
|---|---|---|---|
| Two Pointers | Sorted array, pair-finding, partitioning | left and right move toward each other | Two Sum II, Container With Most Water |
| Sliding Window | ”Longest / shortest contiguous subarray” | right expands, left shrinks on violation | Longest Substring Without Repeating, Minimum Window Substring |
| Prefix Sum + Hash Map | ”Subarray sum equals k”, count valid subarrays | Running total + hash map for complement lookup | Subarray Sum Equals K, Product of Array Except Self |
Graph / Tree Patterns
| Pattern | You’ll see… | Template shape | Typical Problems |
|---|---|---|---|
| BFS | Shortest path, level-order, “spreading” | deque + visited set + popleft() loop | Number of Islands, Binary Tree Level Order |
| DFS | Connectivity, tree traversal, exhaustive search | Recursion or explicit stack + visited set | Max Depth of Binary Tree, Clone Graph |
| Topological Sort | Dependencies, course scheduling, ordering | BFS with in-degrees (Kahn’s) or DFS post-order | Course Schedule |
Specialized Patterns
| Pattern | You’ll see… | Template shape | Typical Problems |
|---|---|---|---|
| Top K / Heap | ”k-th largest”, streaming data, merge sorted | Size-k heap — push new, pop smallest if over k | Merge K Sorted Lists, Kth Largest Element |
| Monotonic Stack | ”Next greater/smaller”, histogram problems | Pop while top violates order, push current index | Daily Temperatures, Largest Rectangle in Histogram |
| Backtracking | All combinations, permutations, subsets | Append → recurse → pop (choose/explore/unchoose) | Combination Sum, Permutations |
| Union Find | Connected components, dynamic grouping | find() with path compression + union() by rank | Accounts Merge, Number of Provinces |
Two Pointers Template
def two_pointer(nums, target):
left, right = 0, len(nums) - 1
while left < right:
current = nums[left] + nums[right]
if current == target:
return [left, right]
elif current < target:
left += 1
else:
right -= 1
[!TIP] When to use: sorted input, finding pairs, removing duplicates, partitioning.
Sliding Window Template
def sliding_window(s):
window = {} # or Counter, set, etc.
left = 0
best = 0
for right in range(len(s)):
# expand: add s[right] to window
window[s[right]] = window.get(s[right], 0) + 1
# shrink: move left until window is valid
while not valid(window):
window[s[left]] -= 1
if window[s[left]] == 0:
del window[s[left]]
left += 1
best = max(best, right - left + 1)
return best
[!TIP] When to use: contiguous substring/subarray optimization with a constraint.
BFS Template
from collections import deque
def bfs(start):
queue = deque([(start, 0)])
visited = {start}
while queue:
node, depth = queue.popleft()
for neighbor in get_neighbors(node):
if neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, depth + 1))
[!TIP] When to use: shortest path in unweighted graph, level-order traversal, spreading problems.
Backtracking Template
def backtrack(candidates, target, start, path, result):
if target == 0:
result.append(path[:])
return
for i in range(start, len(candidates)):
if candidates[i] > target:
break
path.append(candidates[i])
backtrack(candidates, target - candidates[i], i, path, result)
path.pop() # undo choice
[!TIP] When to use: generating all combinations, permutations, subsets, or solving constraint satisfaction problems.
Top K Heap Template
import heapq
def top_k(nums, k):
heap = []
for num in nums:
heapq.heappush(heap, num)
if len(heap) > k:
heapq.heappop(heap) # remove smallest
return heap # contains k largest elements
[!TIP] When to use: “k-th largest,” “top k frequent,” or streaming data where you can’t sort everything.
5. Python Pitfalls in Coding Interviews
These mistakes cost candidates time and correctness under pressure. Know them before you walk into the room.
Using list.pop(0) Instead of deque.popleft()
# BAD — O(n) per pop
queue = [1, 2, 3]
queue.pop(0)
# GOOD — O(1) per pop
from collections import deque
queue = deque([1, 2, 3])
queue.popleft()
Forgetting heapq Is a Min-Heap
# This gives you the SMALLEST element, not the largest
import heapq
heapq.heappop(heap)
# For max-heap behavior, negate values
heapq.heappush(heap, -value)
largest = -heapq.heappop(heap)
Mutating a List During Iteration
# BAD — skips elements
nums = [1, 2, 3, 4, 5]
for num in nums:
if num % 2 == 0:
nums.remove(num) # modifies list while iterating
# GOOD — build a new list
nums = [num for num in nums if num % 2 != 0]
2D List Aliasing Bug
# BAD — all rows share the same list object
grid = [[0] * n] * m
grid[0][0] = 1 # changes ALL rows
# GOOD — each row is independent
grid = [[0] * n for _ in range(m)]
grid[0][0] = 1 # changes only row 0
[!CAUTION] This is one of the most common Python bugs in interviews. If an interviewer sees
[[0]*n]*m, they know you’ll hit a subtle correctness issue because every row points to the same underlying list object in memory.
Mutable Default Arguments
# BAD — the default list is shared across all calls
def append_to(val, lst=[]):
lst.append(val)
return lst
# GOOD
def append_to(val, lst=None):
if lst is None:
lst = []
lst.append(val)
return lst
Recursion Depth Issues
[!WARNING] Python’s default recursion limit is 1000. Deep trees or large graphs can easily hit this limit and crash your program.
import sys
sys.setrecursionlimit(10000) # increase if needed
Better yet, convert deep recursion to an iterative approach with an explicit stack.
Forgetting the Visited Set in Graph Problems
# BAD — infinite loop on cyclic graphs
def dfs(graph, node):
for neighbor in graph[node]:
dfs(graph, neighbor)
# GOOD
def dfs(graph, node, visited):
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
dfs(graph, neighbor, visited)
Overusing Clever One-Liners
# This might impress you, but it confuses interviewers
return [x for x in (lambda f: f(f))(lambda f: lambda n: [n] if n <= 1 else f(f)(n-1) + [n])(10)]
# Write clear code instead
result = list(range(1, 11))
[!IMPORTANT] Interviewers evaluate readability and communication, not code golf. Write clear, explicit code your interviewer can follow easily while you explain it.
6. How to Explain Your Python Solution in Interviews
Writing correct code is half the job. The other half is explaining your choices while you code. Here’s what strong candidates say:
Data structure justification:
“I’ll use a dictionary to track character frequencies. That gives O(1) lookup per character, so the overall pass is O(n).”
Why deque over list:
“I’m using a deque for BFS because popleft is O(1). A regular list would make this O(n²).”
Heap reasoning:
“I’ll maintain a min-heap of size k. After processing all elements, the heap contains the k largest values. This is O(n log k) instead of O(n log n) for a full sort.”
Edge case awareness:
“Before entering the loop, I’ll check if the input is empty. For a single-element array, both pointers start at the same index, so the while loop won’t execute.”
Complexity explanation:
“Each element enters and leaves the stack at most once, so the total work across all iterations is O(n), even though there’s a while loop inside the for loop.”
The pattern: name the tool → state the complexity → explain why it fits the constraint. Practice saying these sentences out loud. They become natural with repetition.
7. Canonical Python Interview Snippets
Copy-paste-ready templates. Each is clean, correct, and ready to adapt during an interview.
BFS:
from collections import deque
def bfs(graph, start):
queue = deque([start])
visited = {start}
while queue:
node = queue.popleft()
for nei in graph[node]:
if nei not in visited:
visited.add(nei)
queue.append(nei)
DFS Recursive:
def dfs(graph, node, visited):
visited.add(node)
for nei in graph[node]:
if nei not in visited:
dfs(graph, nei, visited)
DFS Iterative:
def dfs_iterative(graph, start):
stack = [start]
visited = {start}
while stack:
node = stack.pop()
for nei in graph[node]:
if nei not in visited:
visited.add(nei)
stack.append(nei)
Sliding Window:
def sliding_window(s, k):
window = {}
left = 0
for right, ch in enumerate(s):
window[ch] = window.get(ch, 0) + 1
while len(window) > k:
window[s[left]] -= 1
if window[s[left]] == 0:
del window[s[left]]
left += 1
Prefix Sum + Hash Map:
def count_subarrays(nums, k):
prefix = {0: 1}
total = count = 0
for num in nums:
total += num
count += prefix.get(total - k, 0)
prefix[total] = prefix.get(total, 0) + 1
return count
Top K Heap:
import heapq
def top_k(nums, k):
heap = []
for num in nums:
heapq.heappush(heap, num)
if len(heap) > k:
heapq.heappop(heap)
return heap
Monotonic Stack:
def next_greater(nums):
result = [-1] * len(nums)
stack = []
for i, num in enumerate(nums):
while stack and nums[stack[-1]] < num:
result[stack.pop()] = num
stack.append(i)
return result
Union Find:
class UF:
def __init__(self, n):
self.par = list(range(n))
self.rnk = [0] * n
def find(self, x):
if self.par[x] != x:
self.par[x] = self.find(self.par[x])
return self.par[x]
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py: return False
if self.rnk[px] < self.rnk[py]: px, py = py, px
self.par[py] = px
if self.rnk[px] == self.rnk[py]: self.rnk[px] += 1
return True
Trie:
class Trie:
def __init__(self):
self.root = {}
def insert(self, word):
node = self.root
for ch in word:
node = node.setdefault(ch, {})
node['#'] = True
def search(self, word):
node = self.root
for ch in word:
if ch not in node: return False
node = node[ch]
return '#' in node
def startsWith(self, prefix):
node = self.root
for ch in prefix:
if ch not in node: return False
node = node[ch]
return True
8. Python Practice Problems by Pattern
Grouped by pattern rather than data structure, because that’s how you’ll recognize them in interviews.
Hash Map Problems
- Two Sum — first-occurrence lookup
- Group Anagrams — grouping by sorted key
- Subarray Sum Equals K — prefix sum + hash map
- LRU Cache — hash map + linked list composition
Sliding Window Problems
- Longest Substring Without Repeating Characters
- Minimum Window Substring
- Find All Anagrams in a String
Heap Problems
- Kth Largest Element in an Array
- Merge K Sorted Lists
- Find Median from Data Stream
- Task Scheduler
Tree DFS Problems
- Invert Binary Tree — basic recursion
- Lowest Common Ancestor — post-order
- Validate BST — range-passing
- Maximum Depth of Binary Tree
Graph BFS Problems
- Number of Islands — grid BFS
- Course Schedule — topological sort
- Word Ladder — implicit graph BFS
Monotonic Stack Problems
- Daily Temperatures — next warmer day
- Largest Rectangle in Histogram — next smaller element
- Trapping Rain Water — (also solvable with two pointers)
Union Find Problems
- Accounts Merge — group by shared emails
- Number of Provinces — connected components
- Redundant Connection — cycle detection
Backtracking Problems
- Combination Sum — choose/explore/unchoose
- Permutations — generate all orderings
- Subsets — power set generation
- Word Search — grid backtracking
For the complete study plan organized by difficulty and topic, see The Grind 75 Pathway.
9. One-Page Python Interview Reference
Pin this. Review it the morning of your interview.
| Category | Structure / Pattern | Python Tool | Complexity / Shape |
|---|---|---|---|
| Array | Array / String | list, str | Index O(1) · Insert O(n) · Append O(1) amortized |
| Lookup | Hash Map | dict | Get / set / in → O(1) average |
| Lookup | Hash Set | set | Add / in / remove → O(1) average |
| LIFO | Stack | list | append() / pop() → O(1) |
| FIFO | Queue | deque | append() / popleft() → O(1) |
| Priority | Heap (min) | heapq | Push / pop → O(log n) · Heapify → O(n) |
| Priority | Heap (max) | heapq (negated) | Negate values on push and pop |
| Pattern | Two Pointers | left, right | Move toward each other on sorted input |
| Pattern | Sliding Window | left, right | right expands · left shrinks on violation |
| Pattern | Prefix Sum | dict + running total | total - k in map → O(n) |
| Pattern | BFS | deque + visited | popleft() loop · mark visited on enqueue |
| Pattern | DFS | Recursion or stack | Mark visited · recurse on neighbors |
| Pattern | Top K Heap | heapq size-k | Push all · pop if len > k |
| Pattern | Monotonic Stack | list stack | Pop while top violates order · push index |
| Pattern | Backtracking | path list | Append → recurse → pop |
| Pattern | Union Find | parent[] + rank[] | find() with compression · union() by rank |
Common Pitfalls at a Glance
| ❌ Mistake | ✅ Fix |
|---|---|
list.pop(0) in BFS | Use deque.popleft() — O(1) vs O(n) |
heapq.heappop() for max | Negate: push -val, pop and negate result |
[[0]*n]*m for 2D grid | Use [[0]*n for _ in range(m)] — independent rows |
Mutating a list during for loop | Build a new list with a comprehension instead |
| No visited set in graph DFS/BFS | Always visited.add(node) before enqueuing |
| Stack overflow on deep recursion | sys.setrecursionlimit(10000) or go iterative |
Practice Under Real Interview Conditions
Reading templates builds familiarity. Writing solutions under pressure builds fluency. Those are different skills.
In a live interview, you need to pick the right data structure, write the Python implementation from memory, explain your choices as you go, and handle follow-ups you haven’t rehearsed. That’s a performance skill that only develops through practice.
Try solving any of the problems listed above as a live mock interview on Intervu. You’ll get real-time feedback on both your code and your communication.
Next Steps for Interview Preparation
You’ve seen the templates. Now practice them under real interview conditions.
- Data Structures for Coding Interviews — the conceptual guide this companion is built on; covers patterns, complexity, and common mistakes for each structure
- Python Refresher for Coding Interviews — a practical, no-fluff guide to the Python syntax, built-ins, and idioms you’ll reach for most during a technical interview
- Two Sum Interview Walkthrough — see the hash map pattern applied end-to-end in a real interview scenario
- Grind 75 Practice Pathway — a structured problem set organized by week and pattern, with Intervu practice links
- How to Prepare for a Coding Interview — the complete roadmap: study schedule, mock interviews, and what interviewers actually evaluate
- Why LeetCode Alone Isn’t Enough — and what to practice instead