Python interview cheat sheet

• list

  A dynamic array: fast at the end, slow at the front.

  list: operation costs

  Operation	Time
  a[i], a[i] = x, len(a)	O(1)
  append(x), pop()	O(1) amortized
  insert(0, x), pop(0)	O(n)
  x in a, a.index(x)	O(n)
  a[i:j] (copies)	O(k)
  sort(), sorted(a)	O(n log n)

  a = [3, 1, 4]
  a.append(1)      # O(1) amortized
  a.insert(0, 9)   # O(n): shifts every item
  print(a)
  print(a.pop(), a.pop(0))  # O(1), O(n)
  print(4 in a)    # O(n) scan

  Output

  [9, 3, 1, 4, 1]
  1 9
  True

  Popping from the front in a loop is O(n²) in total — use a deque.

  Big-O

  Array (dynamic)

  Lesson

  Array Basics · Arrays

• dict

  A hash map. Keys must be hashable; iteration follows insertion order.

  dict: operation costs

  Operation	Time
  d[k], d[k] = v, del d[k]	O(1) avg · O(n) worst
  k in d, d.get(k, default)	O(1) avg
  iterate keys / items	O(n)

  d = {"b": 2}
  d["a"] = 1
  print(d.get("z", 0), "a" in d)
  d.setdefault("c", []).append(3)
  print(d)
  print(list(d))    # insertion order

  Output

  0 True
  {'b': 2, 'a': 1, 'c': [3]}
  ['b', 'a', 'c']

  d[k] on a missing key raises KeyError; get and setdefault do not.

  Big-O

  Hash table (map / set)

  Lesson

  Hash Table Basics · Hash Tables

• set

  “Have I seen this?” in O(1). No order, no duplicates.

  set: operation costs

  Operation	Time
  add, remove, x in s	O(1) avg
  a | b, a & b, a - b (sizes m, n)	O(m + n)

  seen = {3, 1}
  seen.add(2)
  print(2 in seen, len(seen))
  a, b = {1, 2, 3}, {2, 3, 4}
  print(sorted(a & b), sorted(a | b))
  print(sorted(a - b), sorted(a ^ b))

  Output

  True 3
  [2, 3] [1, 2, 3, 4]
  [1] [1, 4]

  Print a set through sorted — its order is not part of the language. {} is an empty dict; an empty set is set().

  Big-O

  Hash table (map / set)

  Lesson

  Hash Table Basics · Hash Tables

• deque

  from collections import deque

  The queue: O(1) at both ends. The BFS structure.

  deque: operation costs

  Operation	Time
  append, appendleft	O(1)
  pop, popleft	O(1)
  q[i] in the middle	O(n)

  from collections import deque
  q = deque([1, 2])
  q.appendleft(0)
  q.append(3)
  print(q.popleft(), q.pop(), q)
  last3 = deque(maxlen=3)
  for x in range(5):
      last3.append(x)
  print(last3)

  Output

  0 3 deque([1, 2])
  deque([2, 3, 4], maxlen=3)

  maxlen drops from the other end: a fixed-size window for free.

  Big-O

  Queue / deque

  Lesson

  Queue Basics · Stacks & Queues

• heapq

  import heapq

  A binary MIN-heap on a plain list. For a max-heap, push negatives.

  heapq: operation costs

  Operation	Time
  heapify(a)	O(n)
  heappush, heappop	O(log n)
  a[0] (peek the min)	O(1)
  nsmallest(k, a), nlargest(k, a)	O(n log k)

  import heapq
  h = [5, 1, 8, 3]
  heapq.heapify(h)
  heapq.heappush(h, 0)
  print(heapq.heappop(h), h[0])
  print(heapq.nsmallest(2, [5, 1, 8, 3]))
  m = []                   # max-heap
  for x in [5, 1, 8]:
      heapq.heappush(m, -x)
  print(-m[0])

  Output

  0 1
  [1, 3]
  8

  Push (priority, count, item) tuples so a tie never compares two items.

  Big-O

  Binary heap

  Lesson

  Heap Basics · Heaps

• Counter

  from collections import Counter

  A dict of counts: frequencies, anagrams, “top k most common”.

  Counter: operation costs

  Operation	Time
  Counter(iterable)	O(n)
  c[x] (0 when missing)	O(1) avg
  most_common(k)	O(n log k)

  from collections import Counter
  c = Counter("banana")
  print(c)
  print(c["a"], c["z"])     # missing -> 0
  print(c.most_common(2))
  print(Counter("listen") == Counter("silent"))

  Output

  Counter({'a': 3, 'n': 2, 'b': 1})
  3 0
  [('a', 3), ('n', 2)]
  True

  Big-O

  Hash table (map / set)

  Lesson

  Frequency Counting · Hash Tables

• defaultdict

  from collections import defaultdict

  A dict that builds a missing value on first read — grouping in one line.

  defaultdict: operation costs

  Operation	Time
  d[k] (creates when missing)	O(1) avg
  everything else	as dict

  from collections import defaultdict
  groups = defaultdict(list)
  for w in ["eat", "tea", "tan"]:
      groups["".join(sorted(w))].append(w)
  print(dict(groups))
  print(groups["zzz"], len(groups))

  Output

  {'aet': ['eat', 'tea'], 'ant': ['tan']}
  [] 3

  Merely reading groups["zzz"] inserted it. Test membership with in.

  Big-O

  Hash table (map / set)

  Lesson

  Group Anagrams · Hash Tables

• OrderedDict

  from collections import OrderedDict

  A dict with O(1) reordering: the LRU cache in a few lines.

  OrderedDict: operation costs

  Operation	Time
  move_to_end(k)	O(1)
  popitem(last=False)	O(1)
  everything else	as dict

  from collections import OrderedDict
  lru = OrderedDict()
  for k in "abc":
      lru[k] = k.upper()
  lru.move_to_end("a")      # a is now newest
  lru.popitem(last=False)   # evict the oldest
  print(list(lru.items()))

  Output

  [('c', 'C'), ('a', 'A')]

  A plain dict keeps insertion order too (3.7+), but has no move_to_end.

  Big-O

  Hash table (map / set)

  Lesson

  LRU Cache · Low-Level Design

• Slices

  a = [0, 1, 2, 3, 4, 5]
  print(a[1:4], a[-2:], a[:2])
  print(a[::2], a[::-1])
  print(a[10:], a[4:1])   # no IndexError

  Output

  [1, 2, 3] [4, 5] [0, 1]
  [0, 2, 4] [5, 4, 3, 2, 1, 0]
  [] []

• A slice is a copy

  a = [1, 2, 3]
  b = a[:]          # new list, O(n)
  b.append(4)
  print(a, b)
  s = "interview"
  print(s[::-1], s[2:5])
  a[1:3] = [7]      # slice assignment
  print(a)

  Output

  [1, 2, 3] [1, 2, 3, 4]
  weivretni ter
  [1, 7]

  The copy is shallow: nested lists are shared (see Common traps).

• List, dict and set comprehensions

  nums = [3, 8, 1, 6]
  print([x * x for x in nums if x % 2 == 0])
  print({x: x % 3 for x in nums})
  print(sorted({x % 3 for x in nums}))
  print([x if x > 2 else 0 for x in nums])
  print(sum(x for x in nums))  # generator

  Output

  [64, 36]
  {3: 0, 8: 2, 1: 1, 6: 0}
  [0, 1, 2]
  [3, 8, 0, 6]
  18

  The filter if goes after the loop; the choice a if c else b goes before it.

• Grids: build, flatten, transpose

  rows, cols = 2, 3
  grid = [[0] * cols for _ in range(rows)]
  grid[0][0] = 1
  print(grid)
  print([v for row in grid for v in row])
  print([list(c) for c in zip(*grid)])

  Output

  [[1, 0, 0], [0, 0, 0]]
  [1, 0, 0, 0, 0, 0]
  [[1, 0], [0, 0], [0, 0]]

  Nested loops read left to right, outer first — the order you would write them.

LessonsArray Basics·In-Place Reversal

• sorted() vs .sort()

  a = [3, 1, 2]
  b = sorted(a)     # new list
  print(a, b)
  r = a.sort()      # in place
  print(a, r)
  print(sorted("cab"), sorted((3, 1)))

  Output

  [3, 1, 2] [1, 2, 3]
  [1, 2, 3] None
  ['a', 'b', 'c'] [1, 3]

  a = a.sort() is the classic bug: a is now None.

• key= and reverse=

  words = ["kiwi", "fig", "banana", "apple"]
  print(sorted(words, key=len))
  print(sorted(words, key=len, reverse=True))
  print(max(words, key=len))

  Output

  ['fig', 'kiwi', 'apple', 'banana']
  ['banana', 'apple', 'kiwi', 'fig']
  banana

  The key is computed once per item, not once per comparison.

• Several keys, mixed directions

  people = [("ana", 31), ("ben", 25),
            ("cy", 31)]
  # age descending, then name ascending
  key = lambda p: (-p[1], p[0])
  print(sorted(people, key=key))
  from operator import itemgetter
  print(sorted(people, key=itemgetter(1)))

  Output

  [('ana', 31), ('cy', 31), ('ben', 25)]
  [('ben', 25), ('ana', 31), ('cy', 31)]

  Negate a number to flip its direction inside a tuple key; strings cannot be negated — sort twice instead.

• Stability: sort twice, secondary key first

  rows = [("b", 2), ("a", 1), ("c", 2),
          ("d", 1)]
  print(sorted(rows, key=lambda r: r[1]))
  rows.sort(key=lambda r: r[0], reverse=True)
  rows.sort(key=lambda r: r[1])
  print(rows)

  Output

  [('a', 1), ('d', 1), ('b', 2), ('c', 2)]
  [('d', 1), ('a', 1), ('c', 2), ('b', 2)]

  Ties keep input order, so the second pass keeps the first pass's order within each number.

• functools.cmp_to_key

  from functools import cmp_to_key
  def cmp(a, b):
      if a + b > b + a:
          return -1          # a goes first
      return 1 if a + b < b + a else 0
  nums = ["3", "30", "34", "5", "9"]
  nums.sort(key=cmp_to_key(cmp))
  print("".join(nums))

  Output

  9534330

  For an order no key can express (“largest number”). Negative means a first, positive b first, 0 equal.

LessonsSorting Basics·Which Sort When?

• join vs +=

  parts = ["a", "b", "c"]
  s = ""
  for p in parts:
      s += p        # may copy s every time
  print(s, "-".join(parts))
  print(",".join(str(n) for n in [1, 2, 3]))

  Output

  abc a-b-c
  1,2,3

  += in a loop can be O(n²): CPython sometimes extends in place, but nothing promises it. join is one O(n) pass.

• f-stringsPython 3.8+

  name, score = "ana", 7 / 3
  print(f"{name!r} scored {score:.2f}")
  print(f"[{name:>6}] [{name:<6}] [{42:05d}]")
  print(f"{255:b} {255:x} {1234567:,}")
  x = 5
  print(f"{x=}, {x * 2=}")

  Output

  'ana' scored 2.33
  [   ana] [ana   ] [00042]
  11111111 ff 1,234,567
  x=5, x * 2=10

  {x=} prints the expression and its value — handy for debugging on a whiteboard run.

• The methods interviewers expect

  s = "  Hello, World  "
  print(s.strip().lower())
  print("a,b,,c".split(","), "a b  c".split())
  print("abc123".isalnum(), "123".isdigit())
  print("level".startswith("le"))
  print("banana".count("an"))
  print("banana".find("x"), "banana".index("n"))
  print("a-b-c".replace("-", ""), "ab" * 3)

  Output

  hello, world
  ['a', 'b', '', 'c'] ['a', 'b', 'c']
  True True
  True
  2
  -1 2
  abc ababab

  split() with no argument splits on runs of whitespace and drops empty pieces. find returns -1; index raises ValueError.

• Characters as numbers; editing a string

  print(ord("a"), chr(ord("a") + 2))
  counts = [0] * 26
  for ch in "abca":
      counts[ord(ch) - ord("a")] += 1
  print(counts[:3])
  s = "cat"
  try:
      s[0] = "b"
  except TypeError:
      print("immutable")
  chars = list(s)
  chars[0] = "b"
  print("".join(chars))

  Output

  97 c
  [2, 1, 1]
  immutable
  bat

LessonsString Basics·Reverse Words

• enumerate and zip

  for i, ch in enumerate("ab", start=1):
      print(i, ch)
  names, ages = ["ana", "ben", "cy"], [31, 25]
  print(list(zip(names, ages)))  # shortest wins
  print(dict(zip(names, ages)))

  Output

  1 a
  2 b
  [('ana', 31), ('ben', 25)]
  {'ana': 31, 'ben': 25}

  zip stops silently at the shorter input. zip(..., strict=True) raises instead, but only from 3.10.

• Transpose and neighbouring pairs

  m = [[1, 2, 3], [4, 5, 6]]
  print(list(zip(*m)))       # transpose
  a = [1, 4, 9, 16]
  print([y - x for x, y in zip(a, a[1:])])

  Output

  [(1, 4), (2, 5), (3, 6)]
  [3, 5, 7]

  itertools.pairwise does the second line from 3.10; zip(a, a[1:]) works everywhere.

• product, permutations, combinations

  import itertools as it
  print(list(it.product("ab", repeat=2)))
  print(list(it.permutations([1, 2, 3], 2)))
  print(list(it.combinations([1, 2, 3], 2)))
  print(len(list(it.permutations(range(5)))))

  Output

  [('a', 'a'), ('a', 'b'), ('b', 'a'), ('b', 'b')]
  [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]
  [(1, 2), (1, 3), (2, 3)]
  120

  n! permutations and C(n, k) combinations: fine for n ≤ 10, never for n = 30.

• accumulate: running sums, maxes, productsPython 3.8+

  from itertools import accumulate
  import operator
  a = [3, 1, 4, 1, 5]
  print(list(accumulate(a)))
  print(list(accumulate(a, max)))
  print(list(accumulate(a, operator.mul)))
  print(list(accumulate(a, initial=0)))

  Output

  [3, 4, 8, 9, 14]
  [3, 3, 4, 4, 5]
  [3, 3, 12, 12, 60]
  [0, 3, 4, 8, 9, 14]

  initial=0 gives the prefix-sum array with its leading zero.

• groupby: runs of equal keys

  from itertools import groupby
  s = "aaabccdd"
  print([(k, len(list(g)))
         for k, g in groupby(s)])
  words = ["bob", "amy", "bill", "al"]
  for k, g in groupby(sorted(words), key=len):
      print(k, list(g))

  Output

  [('a', 3), ('b', 1), ('c', 2), ('d', 2)]
  2 ['al']
  3 ['amy']
  4 ['bill']
  3 ['bob']

  It groups ADJACENT items only: 3 appears twice because the list was sorted by name, not by length. Sort by the same key you group by.

LessonsPermutations vs Combinations·Subsets

• The limit, hit

  def depth(n):
      return 0 if n == 0 else 1 + depth(n - 1)
  print(depth(500))
  try:
      depth(100_000)
  except RecursionError:
      print("RecursionError")

  Output

  500
  RecursionError

  The default is 1000 frames in CPython; the exact number is an implementation detail, so do not print it in an answer.

• sys.setrecursionlimit — with care

  import sys
  sys.setrecursionlimit(3_000)
  def depth(n):
      return 0 if n == 0 else 1 + depth(n - 1)
  print(depth(2_000))

  Output

  2000

  It raises Python's counter, not the C stack under it. On the Windows machine this sheet was run on, the same function 3,000 deep killed the process with a stack overflow — no RecursionError to catch. Say so, then offer the iterative version.

• functools.lru_cache

  from functools import lru_cache
  @lru_cache(maxsize=None)
  def fib(n):
      if n < 2:
          return n
      return fib(n - 1) + fib(n - 2)
  print(fib(80))
  print(fib.cache_info())
  fib.cache_clear()   # between test cases

  Output

  23416728348467685
  CacheInfo(hits=78, misses=81, maxsize=None, currsize=81)

  81 distinct calls instead of about 8 × 10¹⁶. @functools.cache is the same thing, spelled shorter, from 3.9.

• Cached arguments must be hashable

  from functools import lru_cache
  @lru_cache(maxsize=None)
  def total(items):
      return sum(items)
  try:
      total([1, 2])
  except TypeError:
      print("list: unhashable")
  print(total((1, 2)))   # pass a tuple

  Output

  list: unhashable
  3

  Convert lists to tuples (or indices) before they reach a cached function.

LessonsRecursion Basics·The Call Stack·Your Own Call Stack·Tail Calls and Loops

• // and % with negatives

  print(7 // 2, -7 // 2)
  print(int(-7 / 2), -7 % 2)
  print(divmod(-7, 2))
  a, b = 7, 2
  print(-(-a // b), (a + b - 1) // b)  # ceil

  Output

  3 -4
  -3 1
  (-4, 1)
  4 4

  -7 // 2 is -4 (floor); int(-7 / 2) is -3 (truncate, through a float — wrong for big numbers). The ceil idioms stay in integers.

• Integers never overflow

  print(2 ** 100)
  print(10 ** 18 + 1 == 10 ** 18)
  MOD = 10 ** 9 + 7
  print(2 ** 64 % MOD)
  print(pow(3, 200, MOD))     # fast modular pow

  Output

  1267650600228229401496703205376
  False
  582344008
  136318165

  When a problem says “return it modulo 10⁹+7”, reduce as you go anyway: big-int arithmetic is not O(1).

• math.inf as a sentinel

  import math
  best = math.inf
  for x in [5, 3, 8]:
      best = min(best, x)
  print(best, -math.inf < -10 ** 100)
  print(float("inf") == math.inf)
  nan = math.inf - math.inf
  print(nan, nan == nan)

  Output

  3 True
  True
  nan False

  math.inf is a float: return -1 (or an int) when the answer must be an integer.

• Float equality and rounding

  import math
  print(0.1 + 0.2 == 0.3, 0.1 + 0.2)
  print(math.isclose(0.1 + 0.2, 0.3))
  print(round(2.5), round(3.5), round(2.675, 2))
  print(int("42") + int(3.9), 7 / 7)

  Output

  False 0.30000000000000004
  True
  2 4 2.67
  45 1.0

  round rounds halves to even, and 2.675 is really 2.67499…. / always returns a float.

LessonsModular Arithmetic·Fast Exponentiation

• The core tricks

  x = 0b10110
  print(bin(x), x & 1, x >> 1, x << 2)
  print(bin(x & (x - 1)))  # drop lowest 1
  print(x & -x)             # lowest set bit
  print(bin(x).count("1"))  # set bits

  Output

  0b10110 0 11 88
  0b10100
  2
  3

  x.bit_count() counts set bits from 3.10; bin(x).count("1") works everywhere.

• Powers of two and bit masks

  def is_pow2(n):
      return n > 0 and n & (n - 1) == 0
  print([n for n in range(1, 20) if is_pow2(n)])
  mask = 0
  for i in [0, 3]:
      mask |= 1 << i           # set bit i
  print(bin(mask), (mask >> 3) & 1)
  print(bin(mask & ~1))        # clear bit 0

  Output

  [1, 2, 4, 8, 16]
  0b1001 1
  0b1000

  In Python & binds tighter than == — the opposite of C and Java — so n & (n - 1) == 0 works. Parenthesise anyway: the reader may think in C.

• XOR and every subset

  from functools import reduce
  from operator import xor
  print(reduce(xor, [4, 1, 2, 1, 2]))
  items = ["a", "b", "c"]
  n = len(items)
  subsets = []
  for m in range(1 << n):
      picked = [items[i] for i in range(n)
                if m >> i & 1]
      subsets.append("".join(picked))
  print(subsets)

  Output

  4
  ['', 'a', 'b', 'ab', 'c', 'ac', 'bc', 'abc']

  x ^ x = 0 cancels every pair. Masks 0 … 2ⁿ−1 are the 2ⁿ subsets.

• Negative numbers and 32-bit views

  print(~5, -5 >> 1)
  print(bin(-5 & 0xFFFFFFFF))
  print((5).bit_length(), (255).bit_length())

  Output

  -6 -3
  0b11111111111111111111111111111011
  3 8

  -5 >> 1 is -3: right shift floors, like //.

LessonsBinary and Bitwise Ops·Masks and Power of Two·XOR Tricks·Bitmask as a Set

• Mutable default arguments

  def add(x, into=[]):     # one list, shared
      into.append(x)
      return into
  print(add(1), add(2))
  def add_fixed(x, into=None):
      into = [] if into is None else into
      into.append(x)
      return into
  print(add_fixed(1), add_fixed(2))

  Output

  [1, 2] [1, 2]
  [1] [2]

  The default is evaluated once, when def runs. Use None and build the list inside.

• Late-binding closures

  fs = [lambda: i for i in range(3)]
  print([f() for f in fs])  # all see last i
  fs = [lambda i=i: i for i in range(3)]
  print([f() for f in fs])

  Output

  [2, 2, 2]
  [0, 1, 2]

  A closure reads the variable when it is CALLED. Bind the current value as a default argument.

• is vs ==

  a = [1, 2]
  b = [1, 2]
  print(a == b, a is b)  # equal, not same
  c = a
  c.append(3)
  print(a, a is c)
  x = None
  print(x is None)        # the right use of is

  Output

  True False
  [1, 2, 3] True
  True

  is asks “the same object?”. It can look right on small ints and short strings only because CPython caches them — never compare values with it.

• Shallow copies and [[0] * n] * m

  import copy
  grid = [[0] * 2] * 2     # two refs, ONE row
  grid[0][0] = 1
  print(grid)
  a = [[1], [2]]
  b = a[:]         # = list(a) = a.copy()
  c = copy.deepcopy(a)
  a[0].append(9)
  print(b, c)

  Output

  [[1, 0], [1, 0]]
  [[1, 9], [2]] [[1], [2]]

  Build grids with a comprehension. a[:], list(a) and a.copy() copy the outer list only.

• Dict order is guaranteed; set order is not

  d = {}
  for k in ["b", "c", "a"]:
      d[k] = True
  print(list(d))          # insertion order
  d.pop("c")
  d["c"] = 1              # now last
  print(list(d))
  print(sorted({"b", "c", "a"}))

  Output

  ['b', 'c', 'a']
  ['b', 'a', 'c']
  ['a', 'b', 'c']

  Insertion order is part of the language from 3.7. Updating an existing key keeps its place; deleting and re-adding moves it to the end.

• Changing a dict while looping over it

  d = {"a": 1, "b": 2}
  try:
      for k in d:
          del d[k]
  except RuntimeError:
      print("RuntimeError")
  d = {"a": 1, "b": 2}
  for k in list(d):       # loop over a copy
      del d[k]
  print(d)

  Output

  RuntimeError
  {}

  A list does not raise — it silently skips items. Loop over a copy, or build a new collection.

• Two pointers

  A sorted array and a pair, a partition or a palindrome decided from both ends.

  Cost: O(n) time, O(1) space

  def pair_sum(a, target):    # a is sorted
      i, j = 0, len(a) - 1
      while i < j:
          s = a[i] + a[j]
          if s == target:
              return i, j
          if s < target:
              i += 1
          else:
              j -= 1
      return None
  print(pair_sum([1, 3, 4, 6, 9], 10))

  Output

  (0, 4)

  Lesson

  Two Pointers · Arrays

  Practice

  • Drop Sorted DuplicatesEasy
  • Three Values Summing to ZeroMedium

• Sliding window

  The answer is a contiguous run, and moving one end updates the state cheaply.

  Cost: O(n) time, O(k) space

  def longest_unique(s):
      last = {}
      start = best = 0
      for i, ch in enumerate(s):
          if last.get(ch, -1) >= start:
              start = last[ch] + 1
          last[ch] = i
          best = max(best, i - start + 1)
      return best
  print(longest_unique("abcabcbb"))

  Output

  3

  Lesson

  Sliding Window · Arrays

  Practice

  • Requests in the Last WindowEasy
  • Longest Distinct RunMedium

• BFS with a deque

  Fewest steps in an unweighted graph or grid; level by level.

  Cost: O(V + E) time, O(V) space

  from collections import deque
  def bfs(graph, src):
      dist = {src: 0}
      q = deque([src])
      while q:
          u = q.popleft()
          for v in graph[u]:
              if v not in dist:  # on push
                  dist[v] = dist[u] + 1
                  q.append(v)
      return dist
  g = {1: [2, 3], 2: [4], 3: [4], 4: []}
  print(bfs(g, 1))

  Output

  {1: 0, 2: 1, 3: 1, 4: 2}

  list.pop(0) would make this O(V²). Mark a node when it is queued, not when it is popped.

  Lesson

  Breadth-First Search · Graphs

  Practice

  • Shallowest Leaf DepthEasy
  • Right Edge ViewMedium

• DFS, recursive and iterative

  Reach everything connected; flood fill, islands, cycle checks, paths.

  Cost: O(V + E) time, O(V) space

  g = {1: [2, 3], 2: [4], 3: [4], 4: []}
  def dfs(u, seen, order):
      seen.add(u)
      order.append(u)
      for v in g[u]:
          if v not in seen:
              dfs(v, seen, order)
      return order
  print(dfs(1, set(), []))
  def dfs_iter(src):   # no depth limit
      seen, order, stack = set(), [], [src]
      while stack:
          u = stack.pop()
          if u in seen:
              continue
          seen.add(u)
          order.append(u)
          stack.extend(reversed(g[u]))
      return order
  print(dfs_iter(1))

  Output

  [1, 2, 4, 3]
  [1, 2, 4, 3]

  Pushing the neighbours reversed makes the stack visit them in the recursive order.

  Lesson

  Depth-First Search · Graphs

  Practice

  • Open Every Locked RoomEasy
  • Deep Copy A GraphMedium

• Binary search with bisect

  A sorted list: insert position, first/last occurrence, count in a range.

  Cost: O(log n) per search

  from bisect import bisect_left, bisect_right
  from bisect import insort
  a = [1, 2, 4, 4, 4, 7]
  print(bisect_left(a, 4), bisect_right(a, 4))
  print(bisect_right(a, 4) - bisect_left(a, 4))
  i = bisect_left(a, 5)
  print(i < len(a) and a[i] == 5)  # found?
  insort(a, 5)                # O(n) insert
  print(a)

  Output

  2 5
  3
  False
  [1, 2, 4, 4, 4, 5, 7]

  bisect_left: first index with a[i] ≥ x; bisect_right: first with a[i] > x. The key= argument needs 3.10.

  Lesson

  Binary Search · Searching

  Practice

  • Integer Square RootEasy
  • First And Last OccurrenceMedium

• Prefix sums

  Many range sums over one array, or subarrays that sum to k.

  Cost: O(n) build, O(1) per query

  from itertools import accumulate
  a = [2, 4, 1, 3]
  pre = [0, *accumulate(a)]  # sum(a[:i])
  print(pre, pre[3] - pre[1])  # sum(a[1:3])
  def count_k(nums, k):  # sums equal to k
      seen = {0: 1}
      total = count = 0
      for x in nums:
          total += x
          count += seen.get(total - k, 0)
          seen[total] = seen.get(total, 0) + 1
      return count
  print(count_k([1, 2, 1, -1, 2], 3))

  Output

  [0, 2, 6, 7, 10] 5
  3

  The leading 0 is what makes pre[j] - pre[i] the sum of a[i:j] with no special case.

  Lesson

  Prefix Sums · Arrays

  Practice

  • Balance Point IndexEasy
  • Product Of OthersMedium

• Monotonic stack

  Next greater / smaller element, spans, the largest rectangle.

  Cost: O(n) time, O(n) space

  def next_greater(a):
      ans = [-1] * len(a)
      stack = []   # indices, values falling
      for i, x in enumerate(a):
          while stack and a[stack[-1]] < x:
              ans[stack.pop()] = x
          stack.append(i)
      return ans
  print(next_greater([2, 1, 2, 4, 3]))

  Output

  [4, 2, 4, -1, -1]

  Each index is pushed once and popped at most once: O(n) despite the inner while.

  Lesson

  Monotonic Stack · Stacks & Queues

  Practice

  • Next Greater Value LookupEasy
  • Days Until WarmerMedium

• Heap top-k

  The k largest, smallest, closest or most frequent of n items.

  Cost: O(n log k) time, O(k) space

  import heapq
  def top_k(nums, k):
      h = []            # min-heap, <= k
      for x in nums:
          heapq.heappush(h, x)
          if len(h) > k:
              heapq.heappop(h)
      return sorted(h, reverse=True)
  print(top_k([5, 1, 9, 3, 7, 2], 3))
  print(heapq.nlargest(3, [5, 1, 9, 3, 7, 2]))

  Output

  [9, 7, 5]
  [9, 7, 5]

  To keep the k LARGEST, evict from a MIN-heap: its top is the weakest of the k kept.

  Lesson

  Top K Elements · Heaps

  Practice

  • K Weakest SquadsEasy
  • Kth Largest ValueMedium

• Union-find

  Connected components that only ever merge; cycle detection in an undirected graph.

  Cost: ≈ O(1) per operation, O(n) space

  parent = list(range(5))
  size = [1] * 5
  def find(x):
      while parent[x] != x:
          parent[x] = parent[parent[x]]  # halve
          x = parent[x]
      return x
  def union(a, b):
      ra, rb = find(a), find(b)
      if ra == rb:
          return False       # already joined
      if size[ra] < size[rb]:
          ra, rb = rb, ra
      parent[rb] = ra
      size[ra] += size[rb]
      return True
  print(union(0, 1), union(1, 2), union(0, 2))
  print(len({find(x) for x in range(5)}))

  Output

  True True False
  3

  find is iterative on purpose: a recursive one hits the recursion limit on a long chain.

  Lesson

  Disjoint Sets Basics · Union-Find

  Practice

  • Reachable Pair CheckEasy
  • Count ProvincesMedium

• Memoized DPPython 3.9+

  Overlapping subproblems: write the recurrence, then cache it.

  Cost: O(states × choices) time, O(states) space

  from functools import cache
  coins = (1, 2, 5)
  @cache
  def fewest(amount):
      if amount == 0:
          return 0
      best = float("inf")
      for c in coins:
          if c <= amount:
              best = min(best,
                         fewest(amount - c) + 1)
      return best
  print(fewest(11), fewest(3))

  Output

  3 2

  Depth is the amount: past a few thousand, turn it bottom-up (see Recursion limits).

  Lesson

  Memoization · Recursion

  Practice

  • Exact Change With Unlimited CoinsEasy
  • Every Way To BracketMedium