Python for Coding Interviews: The Complete Cheat Sheet (collections, heapq, bisect and More)

Python is the language most candidates pick for coding interviews, and it saves real time: hash maps, heaps, queues and binary search are one import away. It also hides costs. A slice copies, an in test on a list scans, and recursion stops at about 1000 calls. This cheat sheet lists what each built-in costs, which module fits which problem, and the traps that make a correct solution slow. Every snippet was run and checked before it went on the page.

Why Python works well in interviews

The advantages are concrete. Python has built-in hash maps and sets, so you rarely need to implement them. Integers never overflow, which removes a whole class of bugs that Java and C++ candidates must discuss. The standard library gives you queues, heaps, binary search and frequency counters ready to use. The trade-off is that Python hides costs: a slice copies data, a membership test on a list scans it, and recursion has a hard depth limit. Knowing these details is what separates a smooth solution from a slow one.

Know the cost of every built-in

Interviewers expect you to state the time complexity of your whole solution, and that depends on the cost of each operation you use. Memorise this table.

The official Python documentation keeps a page on time complexity of the built-in types, so bookmark it. For deeper background on how these costs combine into a final answer, read our guide to Big O notation for coding interviews.

Lists and strings

Lists are your default array. Slicing is convenient, but s[::-1] reverses a string by building a new one, and nums[1:] copies everything after the first element. Inside a recursive function, copying a slice at every call can turn an O(n) idea into O(n²). Pass indexes instead.

s = 'hello'
print(s[::-1])      # 'olleh'  (new string, O(n))
print(s[1:3])       # 'el'
print(ord('c') - ord('a'))   # 2, handy for letter counting
print(chr(98))      # 'b'

Strings are immutable. Building a long string by repeated += inside a loop can be slow, so collect the pieces in a list and call ''.join(parts) once at the end.

Dictionaries, sets, defaultdict and Counter

A dictionary is the single most useful structure for interview problems because it turns a search into a lookup. Use a set when you only care whether something exists. Two helpers from the collections module remove most of the boilerplate.

Counter counts items. Looking up a missing key returns 0 instead of raising an error, and most_common(k) returns the k most frequent items.

from collections import Counter

c = Counter('abracadabra')
print(c.most_common(2))   # [('a', 5), ('b', 2)]
print(c['z'])             # 0

defaultdict creates a default value for missing keys, so you can group items without checking whether the key exists. This is the standard way to solve Group Anagrams, using the sorted letters as the key.

from collections import defaultdict

def group_anagrams(words):
    groups = defaultdict(list)
    for w in words:
        groups[''.join(sorted(w))].append(w)
    return list(groups.values())

print(group_anagrams(['eat', 'tea', 'tan', 'ate', 'nat', 'bat']))
# [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

The time is O(n x k log k) for n words of length k, because every word is sorted once. For the classic complement lookup pattern, see our walkthrough of Two Sum with a hash map.

deque for queues and sliding windows

Never use a list as a queue. list.pop(0) shifts every remaining element, so each removal costs O(n). The deque from collections removes from either end in constant time, which is what breadth-first search needs.

from collections import deque

d = deque([1, 2, 3])
d.appendleft(0)
print(d.popleft())   # 0
print(d.pop())       # 3

last3 = deque(maxlen=3)   # keeps only the 3 newest items
for i in range(5):
    last3.append(i)
print(list(last3))   # [2, 3, 4]

Setting maxlen gives you a fixed-size window for free. Indexing into the middle of a deque is O(n), so use it for the ends only. You can see a deque powering a full traversal in our guide to DFS and BFS in Python.

heapq for top-K and priority queues

The heapq module turns an ordinary list into a min-heap: the smallest item is always at index 0. Push and pop cost O(log n). Python has no built-in max-heap, so the standard trick is to store negative numbers.

import heapq

max_heap = []
heapq.heappush(max_heap, -7)
heapq.heappush(max_heap, -2)
print(-heapq.heappop(max_heap))        # 7

tasks = [(2, 'write'), (1, 'read')]
heapq.heapify(tasks)
print(heapq.heappop(tasks))            # (1, 'read')

print(heapq.nlargest(2, [4, 9, 1, 7]))  # [9, 7]

Heaps are the right tool for the family of problems that ask for the k largest, k smallest or k most frequent items. Here are two classics.

def top_k_frequent(nums, k):
    counts = Counter(nums)
    return heapq.nlargest(k, counts.keys(), key=counts.get)

def kth_largest(nums, k):
    heap = []                      # min-heap that holds the k largest seen
    for n in nums:
        heapq.heappush(heap, n)
        if len(heap) > k:
            heapq.heappop(heap)    # drop the smallest
    return heap[0]

print(top_k_frequent([1, 1, 1, 2, 2, 3], 2))   # [1, 2]
print(kth_largest([3, 2, 1, 5, 6, 4], 2))      # 5

Keeping a heap of size k makes kth_largest run in O(n log k) time and O(k) space, which beats sorting the whole array when k is small. One more trap: when two heap entries tie on the first value, Python compares the next tuple element. If that element is a dictionary or custom object, you get a TypeError. Add a unique counter as the second element, such as (priority, next(counter), item), to break ties safely.

bisect for ready-made binary search

The bisect module is a tested binary search, and it matches the lower-bound template from our binary search guide. bisect_left returns the first index whose value is at least the target, and bisect_right returns the first index whose value is greater than the target.

import bisect

a = [1, 3, 3, 5, 7]
print(bisect.bisect_left(a, 3))    # 1
print(bisect.bisect_right(a, 3))   # 3
print(bisect.bisect_left(a, 4))    # 3  (insertion point)

b = [1, 3, 5]
bisect.insort(b, 4)
print(b)                           # [1, 3, 4, 5]

The number of occurrences of a value is simply bisect_right - bisect_left. Note that insort still has to shift elements, so inserting is O(n) even though finding the position is O(log n). In an interview it is wise to say you know how the binary search works inside, and only then use the library call.

Sorting with key functions

Both sorted() and list.sort() accept a key function. Python’s sort is stable, meaning items that compare equal keep their original order, which is useful for multi-step sorting. Use tuples to sort by several rules at once.

words = ['pear', 'fig', 'apple', 'kiwi']
print(sorted(words, key=lambda w: (len(w), w)))
# ['fig', 'kiwi', 'pear', 'apple']

intervals = [[8, 10], [1, 3], [2, 6]]
intervals.sort(key=lambda x: x[0])
print(intervals)   # [[1, 3], [2, 6], [8, 10]]

Sorting intervals by start time is the first step of Merge Intervals and Meeting Rooms. Sorting costs O(n log n), and it often enables a simple linear scan afterwards.

itertools and prefix sums

itertools.accumulate builds running totals, which is the fastest way to create a prefix-sum array. With a prefix array, the sum of any range is a single subtraction.

from itertools import accumulate, permutations, combinations

prefix = [0] + list(accumulate([1, 2, 3, 4]))
print(prefix)                    # [0, 1, 3, 6, 10]
print(prefix[4] - prefix[1])     # sum of nums[1:4] = 9

print(len(list(permutations([1, 2, 3]))))   # 6
print(list(combinations([1, 2, 3], 2)))     # [(1, 2), (1, 3), (2, 3)]

Permutations and combinations are fine for small inputs, but they grow factorially and exponentially, so use them as a brute-force baseline, not as your final answer. When a problem asks about contiguous ranges, also consider the sliding window pattern.

Python traps that cost points

• The shared-row grid bug. Writing [[0] * 3] * 2 creates two references to the same row. Changing one cell changes both rows. Use [[0] * 3 for _ in range(2)] instead.
• Floor division with negatives. -7 // 2 equals -4, not -3, because Python rounds toward negative infinity. Use int(-7 / 2) if you need truncation toward zero, and remember -7 % 3 equals 2.
• The recursion limit. The default depth is 1000 calls. A deep recursion on a long linked list or a skewed tree will crash. Mention an iterative approach, or raise the limit with sys.setrecursionlimit and explain the risk.
• Mutable default arguments. A default such as def f(x, lst=[]) shares one list across all calls. Use None and create the list inside the function.
• Using a list as a queue or a stack of tuples. Prefer deque for queues, and a plain list with append and pop for stacks.
• Modifying a collection while looping over it. Iterate over a copy, or build a new list.

Small idioms that save time

Use float('inf') as a starting value for minimum searches, divmod(a, b) to get a quotient and remainder together, math.gcd and math.isqrt for number problems, and multiple assignment such as a, b = b, a + b to swap or advance two values at once. Use enumerate when you need both the index and the value, and zip to walk two sequences together. These small choices make your code shorter and your intent clearer.

Which tool for which problem

How to state costs in the interview

Do not just write the code. Say the cost of the key operations out loud: for example, I use a set for membership, which is O(1) on average, and a heap of size k, so the whole solution is O(n log k). If you use a library call such as sorted or bisect, mention its complexity. If the interviewer asks you to implement something yourself, such as a binary search or a heap, you should be able to do that too. Libraries are tools for speed, not a replacement for understanding.

What interviewers accept from the standard library

Most interviewers are glad to see Counter, heapq or sorted, because working engineers use them every day. The line is drawn by the point of the question. If the task is “implement binary search”, calling bisect_left skips the thing being tested. If the task is “find the k-th largest”, a library heap is the expected tool, but be ready to explain how a heap behaves. A ten-second question settles it: “Is it fine to use the standard library for the heap, or would you like me to write it?”

Judge-style rounds are a different matter, because the way you read input changes the answer. The TCS NQT and Infosys practice guide covers that side of Python.

A week of drills, one tool a day

If you are starting from zero, run this week alongside the 30-day study plan, and see the heap guide and the bit manipulation tricks for the two areas where Python behaves least like other languages.