Python Cheat Sheet for Coding Interviews

This page lists the Python you need in a 45-minute coding interview. It covers the built-in data structures and what each operation costs. It also covers the standard-library modules that implement common patterns, the idioms that save typing, and the traps that produce wrong answers.

Python code is short, and a short line can still be a slow operation. A list membership test is one word long and scans the whole list.

Each section below gives a short code block and the cost of each call.

The cost of each built-in data structure

The table uses two words for cost. "Constant" means the time does not change with the size of the container. "Linear" means the time grows in proportion to the size.

Dict and set costs are averages, because both use a hash table, an array indexed by a number computed from the key. "By key" means the position does not matter.

A list append is constant on average, because Python reserves extra space at the end of the list.

Tuples and strings are immutable, which means they cannot change after creation, so every edit builds a new object in linear time. The notation for these costs is explained in Big-O algorithm complexity explained.

Lists and slicing

A list is a resizable array. Index reads, appends, and pops from the back are constant. Any insert or delete at the front shifts every other item, so it is linear.

The block below shows the common list operations.

nums = [3, 1, 4, 1, 5]
nums.append(9)           # constant
last = nums.pop()        # constant
first = nums.pop(0)      # linear: every remaining item shifts left
head = nums[:2]          # a new list, linear in the slice length
rev = nums[::-1]         # a reversed copy, linear
nums[1:3] = []           # delete a range in place, linear

Two of these are slower than they appear. A slice is a copy, so a function that slices its input on every call does linear work per call.

pop(0) inside a loop makes the loop quadratic, meaning the time grows with the square of the size. Use collections.deque and its popleft instead.

Dicts and sets

A dict maps keys to values, and a set holds keys alone. Both use a hash table, so membership, insert, and delete are constant on average. The same membership test on a list is linear, so every "have we seen this" check should use a set.

The block below covers the dict and set calls that appear in most solutions.

from collections import defaultdict, Counter

count = {}
count["a"] = count.get("a", 0) + 1    # a default when the key is missing

groups = defaultdict(list)            # a missing key starts as an empty list
groups["even"].append(2)

freq = Counter("banana")              # Counter({'a': 3, 'n': 2, 'b': 1})
freq.most_common(1)                   # [('a', 3)]

seen = set()
seen.add(4)
4 in seen                             # constant

dict.get with a default replaces an if-statement. defaultdict creates the missing value for you, which is the usual way to group items. Counter counts in one linear pass, and most_common(k) returns the k largest counts in order.

Strings

A string is immutable. Adding one character with += builds a whole new string, so a loop that does this is quadratic. Collect the pieces in a list and join them once at the end.

The block below shows the string calls that appear most often.

parts = []
for ch in "abc":
    parts.append(ch.upper())
result = "".join(parts)             # "ABC", one linear pass

ord("a")                            # 97, the code of the character
chr(98)                             # "b", the character for a code
words = "two words here".split()    # ["two", "words", "here"]
key = "".join(sorted("listen"))     # "eilnst", the same key as "silent"

ord and chr convert between a character and its number, which is how you index a 26-slot array by letter. split turns a sentence into a list of words, and join does the reverse. A sorted string is a cheap key for anagrams, which are words made from the same letters in a different order.

Sorting

sorted returns a new list, and list.sort sorts in place. Both take n log n time, which is a little slower than linear. Both are stable, which means items that compare equal keep their original order.

The key argument names the value to sort by, and reverse=True reverses the order. The block below sorts a list of tuples four ways.

from functools import cmp_to_key

people = [("bob", 25), ("amy", 30), ("cat", 25)]
by_age = sorted(people, key=lambda p: p[1])         # stable: bob stays before cat
oldest_first = sorted(people, key=lambda p: -p[1])
by_age_then_name = sorted(people, key=lambda p: (p[1], p[0]))

def compare(a, b):                                   # negative means a comes first
    return a[1] - b[1]

custom = sorted(people, key=cmp_to_key(compare))

Tuples compare element by element. So a tuple key sorts by the first field and uses the second only when the first is equal. Negate a number in the key to sort that field in descending order.

Use functools.cmp_to_key only when the order cannot be written as a key, which is rare.

heapq for heaps and priority queues

A priority queue is a container that returns the smallest item next. A heap is the array-backed tree that implements it. Python's heapq module works on a plain list and gives only a min-heap.

Push and pop are logarithmic, which means that doubling the size adds only one more step. The block below shows a min-heap, a max-heap made by negating values, and a priority tuple.

import heapq

heap = [5, 1, 3]
heapq.heapify(heap)                  # linear, turns the list into a heap
heapq.heappush(heap, 2)              # logarithmic
smallest = heapq.heappop(heap)       # 1

max_heap = []
heapq.heappush(max_heap, -7)         # store the negative
largest = -heapq.heappop(max_heap)   # 7

tasks = [(2, "write"), (1, "read")]
heapq.heapify(tasks)                 # (1, "read") comes out first
top_two = heapq.nlargest(2, [4, 9, 1, 7])   # [9, 7]

For a max-heap, push the negated value and negate it again after popping. heapify on n items is linear, and nlargest(k) and nsmallest(k) cost n log k.

For a priority with a payload, push a tuple with the priority first. A payload is the item attached to the priority, like a task name. Add a counter as the second element when payloads cannot be compared.

The problem families that use a heap are in heaps and priority queues for coding interviews. Grokking the Coding Interview teaches those patterns one at a time, with runnable Python solutions.

bisect for sorted arrays

bisect is a binary search that is already tested. Binary search finds a position in a sorted list in logarithmic time by halving the range at each step. bisect_left returns the first position where a value could go, and bisect_right returns the position after any equal values.

The block below shows both calls.

import bisect

sorted_nums = [1, 3, 3, 5]
bisect.bisect_left(sorted_nums, 3)    # 1, the position of the first 3
bisect.bisect_right(sorted_nums, 3)   # 3, one past the last 3
count_of_3 = 3 - 1                    # right minus left counts the 3s
bisect.insort(sorted_nums, 4)         # [1, 3, 3, 4, 5]

Subtracting the two results counts how many times a value appears. insort finds the position in logarithmic time, but the list insert is linear, so many inserts into a large list are slow.

collections.deque for BFS and sliding windows

A deque is a double-ended queue with constant-time append and pop at both ends. It is the right queue for breadth-first search (BFS), which visits a graph one layer at a time.

The block below is a BFS over a graph stored as a dict of neighbor lists.

from collections import deque

def bfs(graph, start):
    seen = {start}
    queue = deque([start])
    while queue:
        node = queue.popleft()        # constant
        for nxt in graph[node]:
            if nxt not in seen:
                seen.add(nxt)
                queue.append(nxt)
    return seen

Each node enters the queue once and leaves once, so the search is linear in nodes plus edges.

The same structure solves the sliding-window maximum. A window is a range of k consecutive items that moves one step at a time. The block below keeps indexes in the deque in decreasing order of value, so the front is always the current maximum.

from collections import deque

def window_max(nums, k):
    out, dq = [], deque()
    for i, x in enumerate(nums):
        while dq and nums[dq[-1]] <= x:  # drop smaller values from the back
            dq.pop()
        dq.append(i)
        if dq[0] <= i - k:               # drop the index outside the window
            dq.popleft()
        if i >= k - 1:
            out.append(nums[dq[0]])
    return out

Each index is appended once and removed at most once, so the whole pass is linear.

functools.cache for memoization

Memoization stores the result of a function call so that a repeat call with the same arguments returns at once. functools.cache adds it to a recursive function in one line. On Python versions before 3.9, use functools.lru_cache(maxsize=None) instead.

The block below counts the ways to climb n stairs taking one or two steps at a time.

import sys
from functools import cache

sys.setrecursionlimit(10_000)

@cache
def ways(n):
    if n <= 1:
        return 1
    return ways(n - 1) + ways(n - 2)

ways(50)                                # 20365011074, each n computed once

Without the cache, the call tree doubles at every level and the function is exponential. With it, each n is computed once, so time and space are both linear.

Python stops recursion at about 1,000 frames by default. Raise the limit with sys.setrecursionlimit, or rewrite the deepest recursions as loops. The arguments must be hashable, which means usable as dict keys, so pass tuples rather than lists.

itertools.accumulate for prefix sums

A prefix sum array stores the running total up to each index. With it, the sum of any range is one subtraction instead of a loop. itertools.accumulate builds the array in one linear pass.

The block below adds a leading zero so the range formula never needs a special case.

from itertools import accumulate

nums = [2, 4, 1, 3]
prefix = [0] + list(accumulate(nums))    # [0, 2, 6, 7, 10]
range_sum = prefix[3] - prefix[1]        # nums[1] + nums[2] = 5

The sum of the items from index i up to but not including j is prefix[j] - prefix[i]. The leading zero makes that formula correct when i is 0.

Integers, division, and infinity

Python integers never overflow, so a product of two large numbers is exact. A question that asks for the answer modulo a large prime still needs the % call. Floor division with // rounds toward negative infinity, and % returns a result with the sign of the divisor.

The block below shows the division rules and the usual starting value for a minimum search.

2 ** 100                # exact, no overflow
7 // 2                  # 3
-7 // 2                 # -4, rounds down, not toward zero
int(-7 / 2)             # -3, when you need truncation
-7 % 3                  # 2, the sign of the divisor
best = float("inf")     # larger than every number
best = min(best, 42)    # 42

float("inf") is a sentinel, a starting value that any real result will replace. Use it for a running minimum and float("-inf") for a running maximum. Both compare correctly with integers.

enumerate, zip, swaps, and comprehensions

These idioms save typing and remove index bugs. enumerate gives the index and the value together. zip pairs items from two sequences by position and stops at the shorter one.

The block below shows each one.

nums = [5, 8, 2]
for i, x in enumerate(nums):              # index and value together
    pass
pairs = list(zip(nums, nums[1:]))         # neighbors: [(5, 8), (8, 2)]
nums[0], nums[2] = nums[2], nums[0]       # swap with no temporary variable
squares = [x * x for x in nums if x > 2]  # a filtered list in one line
grid = [[0] * 3 for _ in range(2)]        # two separate rows
index_of = {x: i for i, x in enumerate(nums)}

A comprehension is a loop written as one expression that builds a list, set, or dict. The tuple swap works because the right side is evaluated before the assignment. The grid line is the safe way to build a 2D array, for the reason given below.

Python traps in coding interviews

Six mistakes appear again and again in Python solutions, and most of them run without an error message.

Mutable default arguments. A default value is created once, when the function is defined, not on every call. So def f(path=[]) shares one list across every call.

The block below shows the shared list and the fix.

def add(item, bucket=[]):     # one list, shared by every call
    bucket.append(item)
    return bucket

add(1)                        # [1]
add(2)                        # [1, 2], not [2]

def add_fixed(item, bucket=None):
    if bucket is None:
        bucket = []
    bucket.append(item)
    return bucket

This mistake matters most in backtracking, where a shared path list makes every result identical.

Aliasing when copying a list of lists. Aliasing means two names refer to the same object. [[0] * 3] * 2 creates two names for one row, so a write to row 0 also appears in row 1.

grid[:] copies only the outer list, and the rows are still shared. Build rows with a comprehension, or use copy.deepcopy on an existing structure.

Modifying a dict while iterating over it. Adding or deleting keys inside for key in d raises a RuntimeError. Iterate over list(d), which is a copy of the keys, and edit the original freely.

Comparing floats with ==. 0.1 + 0.2 == 0.3 is False, because binary floats cannot store most decimal fractions exactly. Compare with math.isclose, or keep the arithmetic in integers when the question allows it.

Using a list as a queue. pop(0) shifts every remaining item, so a BFS on n nodes does n squared work. Use collections.deque and popleft.

Forgetting that range excludes the end. range(1, 4) produces 1, 2, and 3. To count down to and including 0, write range(n, -1, -1).

How to state the cost of each built-in in the interview

Interviewers ask about the cost of the built-ins you use. The answer should be one sentence per call: the operation, its cost, and the reason. "This is a set lookup, constant on average, because a set is a hash table."

State the cost before the interviewer asks, because it shows that you chose the structure on purpose. These sentences cover most solutions:

• "Sorting is n log n, and Python's sort is stable."
• "Each heap push and pop is logarithmic, and heapify is linear."
• "The slice copies, so this call is linear in the slice length."
• "The deque gives constant pops from the front, so the BFS is linear in nodes plus edges."
• "The cache computes each state once, so time equals the number of states."

One warning belongs in the same sentence: dict and set costs are averages, not worst cases.

For Two Sum, which asks for two numbers that add to a target, the solution loops once and stores each number's index in a dict. The sentence to say is: "One pass with one constant dict lookup per item, so linear time and linear space."

Frequently asked questions

Is Python allowed in coding interviews at big tech companies? Yes. Meta, Google, Amazon, Microsoft, and most smaller companies let you pick, and Python is one of the most common choices. The exceptions are roles that need a specific language, as which language is best for coding interviews explains.

Is Python too slow for coding interviews? No. Interviewers evaluate the cost of the algorithm, not the speed of the language. Some online assessments with tight time limits do reject slow code, and the fix is a better algorithm.

Can I use heapq, Counter, and sorted in an interview? Yes, the standard library is expected. Be ready to state the cost of each call and to explain how the structure works. The one thing to avoid is a library call that is the whole answer to the question.

How do I make a max-heap in Python? Push the negated value into a heapq min-heap and negate it again after popping. For items with a priority and a payload, push a tuple with the negated priority first. The full answer is in what to use for a max-heap in Python.

Should I switch to Python for interviews if I work in Java? If the interview is more than a month away, yes, because the interview subset of Python takes a week or two to learn. If it is closer than that, keep the language you think in. Python vs Java for coding interviews compares the two in detail.

Grokking Data Structures for Coding Interviews explains how each of these structures works internally and what every operation costs.

Related reading

• Python vs Java for coding interviews
• Big-O algorithm complexity explained
• The coding interview cheat sheet
• Heaps and priority queues for coding interviews
• What Python coding interview questions to prepare
• What to use for a max-heap in Python