📖 17 min read
Last updated on

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

StructurePython ToolWhen to UseExample Problem
Array / Stringlist, strIndexed access, in-place manipulation, sequential iterationTwo Sum, sliding window
Hash MapdictO(1) lookup, frequency counting, memoizationLRU Cache, Group Anagrams
Hash SetsetO(1) membership check, deduplication, visited trackingLongest Consecutive Sequence
StacklistLIFO — matching brackets, undo, monotonic patternsValid Parentheses
Queuecollections.dequeFIFO — BFS, level-order traversal, sliding window maxBinary Tree Level Order

Priority and Ordering

StructurePython ToolWhen to Use
Min-HeapheapqTop-K problems, streaming min/max, merge K sorted
Max-Heapheapq (negated values)Kth largest, greedy scheduling
Sorted Outputsorted()One-time sort; not for dynamic ordering

Custom Structures (implement from scratch)

StructurePython ToolWhen to Use
Tree Nodeclass TreeNodeBinary trees, BSTs, recursion problems
Graphdefaultdict(list)Adjacency list for BFS/DFS
Trieclass TrieNodePrefix search, autocomplete, word matching
Union Findparent[] + 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 causing Time 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 find and union run 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

PatternYou’ll see…Template shapeTypical Problems
Two PointersSorted array, pair-finding, partitioningleft and right move toward each otherTwo Sum II, Container With Most Water
Sliding Window”Longest / shortest contiguous subarray”right expands, left shrinks on violationLongest Substring Without Repeating, Minimum Window Substring
Prefix Sum + Hash Map”Subarray sum equals k”, count valid subarraysRunning total + hash map for complement lookupSubarray Sum Equals K, Product of Array Except Self

Graph / Tree Patterns

PatternYou’ll see…Template shapeTypical Problems
BFSShortest path, level-order, “spreading”deque + visited set + popleft() loopNumber of Islands, Binary Tree Level Order
DFSConnectivity, tree traversal, exhaustive searchRecursion or explicit stack + visited setMax Depth of Binary Tree, Clone Graph
Topological SortDependencies, course scheduling, orderingBFS with in-degrees (Kahn’s) or DFS post-orderCourse Schedule

Specialized Patterns

PatternYou’ll see…Template shapeTypical Problems
Top K / Heap”k-th largest”, streaming data, merge sortedSize-k heap — push new, pop smallest if over kMerge K Sorted Lists, Kth Largest Element
Monotonic Stack”Next greater/smaller”, histogram problemsPop while top violates order, push current indexDaily Temperatures, Largest Rectangle in Histogram
BacktrackingAll combinations, permutations, subsetsAppend → recurse → pop (choose/explore/unchoose)Combination Sum, Permutations
Union FindConnected components, dynamic groupingfind() with path compression + union() by rankAccounts 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

Heap Problems

Tree DFS Problems

Graph BFS Problems

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.

CategoryStructure / PatternPython ToolComplexity / Shape
ArrayArray / Stringlist, strIndex O(1) · Insert O(n) · Append O(1) amortized
LookupHash MapdictGet / set / in → O(1) average
LookupHash SetsetAdd / in / remove → O(1) average
LIFOStacklistappend() / pop() → O(1)
FIFOQueuedequeappend() / popleft() → O(1)
PriorityHeap (min)heapqPush / pop → O(log n) · Heapify → O(n)
PriorityHeap (max)heapq (negated)Negate values on push and pop
PatternTwo Pointersleft, rightMove toward each other on sorted input
PatternSliding Windowleft, rightright expands · left shrinks on violation
PatternPrefix Sumdict + running totaltotal - k in map → O(n)
PatternBFSdeque + visitedpopleft() loop · mark visited on enqueue
PatternDFSRecursion or stackMark visited · recurse on neighbors
PatternTop K Heapheapq size-kPush all · pop if len > k
PatternMonotonic Stacklist stackPop while top violates order · push index
PatternBacktrackingpath listAppend → recurse → pop
PatternUnion Findparent[] + rank[]find() with compression · union() by rank

Common Pitfalls at a Glance

❌ Mistake✅ Fix
list.pop(0) in BFSUse deque.popleft() — O(1) vs O(n)
heapq.heappop() for maxNegate: push -val, pop and negate result
[[0]*n]*m for 2D gridUse [[0]*n for _ in range(m)] — independent rows
Mutating a list during for loopBuild a new list with a comprehension instead
No visited set in graph DFS/BFSAlways visited.add(node) before enqueuing
Stack overflow on deep recursionsys.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.

Practice Like It's the Real Interview

Get instant feedback on your approach, communication, and code — powered by AI.

Start a Mock Interview →