Why This Chapter Exists

You are fluent in TypeScript and C#. Python is your interview weapon. This chapter is your reference manual — not a "learn Python" tutorial, but a surgical overview of the exact built-in data structures, functions, and idioms you’ll use in algorithm interviews.

Every entry includes:

  • What it does

  • Time and space complexity (Big-O)

  • Does it mutate the original object or create a copy?

  • TS/C# equivalent (to anchor your existing knowledge)

  • Common gotchas in interviews

You don’t need to memorize this chapter front-to-back. Read it once, then come back to it whenever you encounter something unfamiliar in later chapters.

1. Lists (Dynamic Arrays)

Python’s list is a dynamic array — like C#'s List<T> or TypeScript’s Array. Under the hood, it’s a contiguous block of memory holding pointers to objects, with automatic resizing (typically doubles capacity when full).

Creating Lists

# Empty list
empty = []

# List with elements
numbers = [1, 2, 3, 4, 5]

# List of N zeros — O(n) time and space
# This creates a NEW list filled with zeros.
zeros = [0] * 10  # [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

# List comprehension — O(n) time and space
# Creates a NEW list. Like C# LINQ .Select() or TS .map()
squares = [x ** 2 for x in range(5)]  # [0, 1, 4, 9, 16]

# Nested list comprehension — creating a 2D grid
# IMPORTANT: each inner list is a SEPARATE object
rows, cols = 3, 4
grid = [[0] * cols for _ in range(rows)]  # 3 rows × 4 cols

# ⚠️ WRONG WAY to create 2D grid:
# wrong_grid = [[0] * cols] * rows
# This creates 3 references to the SAME inner list!
# Mutating wrong_grid[0][0] would change ALL rows.

Indexing and Slicing

numbers = [10, 20, 30, 40, 50]

# --- Indexing: O(1) time ---
first = numbers[0]     # 10
last  = numbers[-1]    # 50  (negative = count from end)
second_last = numbers[-2]  # 40

# --- Slicing: O(k) time, O(k) space where k = slice length ---
# Slicing ALWAYS creates a NEW list (shallow copy of the slice).
# Syntax: list[start:stop:step] — stop is EXCLUSIVE (like range())

first_three = numbers[0:3]   # [10, 20, 30]
first_three = numbers[:3]    # same — omit start means 0
from_idx_2  = numbers[2:]    # [30, 40, 50] — omit stop means end
copy        = numbers[:]     # [10, 20, 30, 40, 50] — full shallow copy

# Step parameter (third argument)
every_other = numbers[::2]   # [10, 30, 50]
reversed_list = numbers[::-1] # [50, 40, 30, 20, 10] ← NEW list, original unchanged

# TS equivalent:  numbers.slice(0, 3) → creates new array
# C# equivalent:  numbers.GetRange(0, 3) or numbers[0..3] (C# range syntax)

Slicing creates a SHALLOW copy. If your list contains mutable objects (like inner lists in a 2D grid), the slice will reference the same inner objects. Use copy.deepcopy() for a full independent copy.

Common List Methods

Method Big-O Mutates? TS/C# Equivalent

list.append(x)

O(1) amortized

✅ Yes, in-place

TS: arr.push(x) / C#: list.Add(x)

list.pop()

O(1)

✅ Yes, removes + returns last element

TS: arr.pop() / C#: list.RemoveAt(list.Count-1)

list.pop(0)

⚠️ O(n)

✅ Yes, removes + returns first element

TS: arr.shift() — also O(n)

list.insert(i, x)

O(n)

✅ Yes, in-place

TS: arr.splice(i, 0, x) / C#: list.Insert(i, x)

list.extend(iterable)

O(k) where k = length of iterable

✅ Yes, in-place

TS: arr.push(…​other) / C#: list.AddRange(other)

list.remove(x)

O(n)

✅ Yes, removes FIRST occurrence

C#: list.Remove(x)

list.index(x)

O(n)

❌ No

TS: arr.indexOf(x) / C#: list.IndexOf(x)

list.reverse()

O(n)

✅ Yes, in-place

TS: arr.reverse() — also in-place!

list.sort()

O(n log n)

✅ Yes, in-place

TS: arr.sort() — also in-place!

list.count(x)

O(n)

❌ No

C#: list.Count(item ⇒ item == x)

len(list)

O(1)

❌ No

TS: arr.length / C#: list.Count

x in list

O(n)

❌ No

TS: arr.includes(x) / C#: list.Contains(x)

list.pop(0) is O(n)! It must shift all remaining elements left. If you need O(1) removal from both ends, use collections.deque (covered below). This is a classic interview trap — using list.pop(0) in a BFS loop makes it O(n²) instead of O(n).

Unpacking (Destructuring)

# Like JS destructuring: const [a, b, c] = [1, 2, 3]
a, b, c = [1, 2, 3]

# Swap two variables — O(1) time, no temp variable needed
# This is a Python idiom. Under the hood, Python packs them into a tuple
# and then unpacks. No extra memory allocated (compiler optimizes it).
a, b = b, a

# Underscore _ is a convention for "I don't care about this value"
first, _, third = [10, 20, 30]  # Ignore the middle element

# Star unpacking (rest pattern) — like JS spread: const [first, ...rest] = arr
first, *rest = [1, 2, 3, 4, 5]  # first=1, rest=[2, 3, 4, 5]
*beginning, last = [1, 2, 3, 4, 5]  # beginning=[1, 2, 3, 4], last=5

2. Dictionaries (Hash Maps)

Python’s dict is a hash map — like C#'s Dictionary<K,V> or TypeScript’s Map (NOT plain objects, though objects work similarly).

Since Python 3.7+, dict maintains insertion order (like Map in JS/TS).

Basic Operations

# All basic dict operations are O(1) average time (hash table).
# Worst case is O(n) due to hash collisions, but this is extremely rare
# with Python's built-in hashing.

phone_book = {"Alice": "555-0100", "Bob": "555-0200"}

# Access — O(1) average. Raises KeyError if key doesn't exist.
alice_phone = phone_book["Alice"]  # "555-0100"

# Safe access — O(1). Returns default if key missing (no exception).
# Like C#'s TryGetValue or TS's map.get(key)
charlie_phone = phone_book.get("Charlie", "Unknown")  # "Unknown"

# Insert / Update — O(1) average. Mutates the dict in place.
phone_book["Charlie"] = "555-0300"

# Delete — O(1) average. Mutates in place. Raises KeyError if missing.
del phone_book["Bob"]

# Safe delete — O(1). Returns removed value, or default if key missing.
removed = phone_book.pop("Bob", None)  # None (Bob already deleted)

# Check membership — O(1) average
# ⚡ This is a CRUCIAL difference from lists where `in` is O(n)!
exists = "Alice" in phone_book  # True

Iteration

scores = {"math": 95, "science": 88, "english": 92}

# Iterate over keys — O(n). Default iteration gives keys.
for subject in scores:          # same as: for subject in scores.keys()
    print(subject)

# Iterate over values — O(n)
for score in scores.values():
    print(score)

# Iterate over key-value pairs — O(n)
# Like TS: for (const [key, value] of map.entries())
for subject, score in scores.items():
    print(f"{subject}: {score}")

defaultdict — Auto-initializing Dict

from collections import defaultdict

# defaultdict automatically creates a default value for missing keys.
# When you access a missing key, it calls the factory function and stores it.
# This is like C#'s GetOrAdd pattern or TS's: map.get(key) ?? initAndSet()

# defaultdict(list) → missing keys get an empty list []
graph = defaultdict(list)
graph["A"].append("B")  # No KeyError! Auto-creates graph["A"] = []
graph["A"].append("C")
# graph = {"A": ["B", "C"]}

# defaultdict(int) → missing keys get 0
word_count = defaultdict(int)
for word in ["hello", "world", "hello"]:
    word_count[word] += 1  # No need to check if key exists first
# word_count = {"hello": 2, "world": 1}

# defaultdict(set) → missing keys get an empty set
connections = defaultdict(set)
connections["A"].add("B")
connections["A"].add("C")

Counter — Frequency Counting

from collections import Counter

# Counter is a specialized dict subclass for counting.
# It counts occurrences of each element. O(n) time, O(k) space
# where k = number of unique elements.

letters = Counter("abracadabra")
# Counter({'a': 5, 'b': 2, 'r': 2, 'c': 1, 'd': 1})

# Most common elements — O(k log k) because it sorts
top_two = letters.most_common(2)  # [('a', 5), ('b', 2)]

# You can use it like a normal dict
print(letters['a'])     # 5
print(letters['z'])     # 0 (not KeyError — Counter returns 0 for missing keys!)

# Arithmetic operations
c1 = Counter("aab")     # Counter({'a': 2, 'b': 1})
c2 = Counter("abc")     # Counter({'a': 1, 'b': 1, 'c': 1})
print(c1 + c2)          # Counter({'a': 3, 'b': 2, 'c': 1})
print(c1 - c2)          # Counter({'a': 1}) — only positive counts kept

3. Sets

Python’s set is a hash set — like C#'s HashSet<T> or TS’s Set. Unordered, no duplicates, O(1) average membership test.

# Creating sets
fruits = {"apple", "banana", "cherry"}  # Set literal
empty_set = set()  # ⚠️ NOT {} — that creates an empty DICT!
from_list = set([1, 2, 2, 3])  # {1, 2, 3} — duplicates removed, O(n)

# --- All O(1) average ---
fruits.add("date")              # Mutates in place
fruits.discard("banana")        # Mutates. No error if missing.
fruits.remove("banana")         # Mutates. ⚠️ Raises KeyError if missing!
exists = "apple" in fruits      # O(1) — the main reason to use sets!

# --- Set operations — O(min(len(a), len(b))) ---
a = {1, 2, 3}
b = {2, 3, 4}
print(a & b)    # Intersection: {2, 3}
print(a | b)    # Union: {1, 2, 3, 4}
print(a - b)    # Difference: {1}        (in a but not in b)
print(a ^ b)    # Symmetric difference: {1, 4}  (in one but not both)

# Frozen set — immutable set (can be used as a dict key or in another set)
frozen = frozenset([1, 2, 3])

When to use set vs list for "visited" tracking:

In BFS/DFS algorithms, you track visited nodes. Use a set, because x in my_set is O(1), while x in my_list is O(n). This can turn an O(V+E) algorithm into O(V²+E).

4. collections.deque — Double-Ended Queue

This is arguably the most important data structure for interview algorithms that most people miss when coming from TS/C#.

from collections import deque

# deque (pronounced "deck") is a double-ended queue implemented as a
# doubly-linked list of fixed-size blocks. It provides O(1) operations
# on BOTH ends — unlike list which is O(n) for left-side operations.

# TS equivalent:  NO built-in equivalent! You'd need a custom implementation.
# C# equivalent:  LinkedList<T> (but deque is more memory-efficient)
#                 .NET 8 has System.Collections.Generic.Queue which is similar.

d = deque()

# --- All O(1) time ---
d.append(1)         # Add to right:  [1]
d.append(2)         # Add to right:  [1, 2]
d.appendleft(0)     # Add to left:   [0, 1, 2]

right_val = d.pop()       # Remove from right: returns 2, deque = [0, 1]
left_val  = d.popleft()   # Remove from left:  returns 0, deque = [1]

# --- O(1) access to ends, O(n) to middle ---
front = d[0]         # O(1) — first element
back  = d[-1]        # O(1) — last element
middle = d[3]        # ⚠️ O(n) — random access is slow! Not a contiguous array.

# Create from iterable — O(n)
d = deque([1, 2, 3, 4, 5])

# Bounded deque — auto-discards from opposite end when full
# Useful for "sliding window" patterns
last_three = deque(maxlen=3)
last_three.append(1)  # deque([1])
last_three.append(2)  # deque([1, 2])
last_three.append(3)  # deque([1, 2, 3])
last_three.append(4)  # deque([2, 3, 4]) — 1 was auto-discarded!

BFS = deque. Period. Every BFS implementation uses a queue. If you use a list with list.pop(0), you’re writing O(n²) BFS instead of O(V+E). Always use deque for BFS queues.

5. heapq — Priority Queue / Min-Heap

import heapq

# Python's heapq module implements a MIN-HEAP on top of a regular list.
# The heap property: parent <= children. Smallest element is always at index 0.
#
# C# equivalent:  PriorityQueue<TElement, TPriority> (.NET 6+)
# TS equivalent:  No built-in. Need a library or custom implementation.

# --- Create a heap from a list ---
# heapify transforms a list IN PLACE into a heap. O(n) time, O(1) space.
numbers = [5, 3, 8, 1, 2]
heapq.heapify(numbers)  # numbers is now a heap: [1, 2, 8, 5, 3]
# Note: the list order looks weird — it's a heap, not a sorted list!
# The only guarantee is: numbers[0] is the MINIMUM.

# --- Push: O(log n) time. Mutates the list. ---
heapq.heappush(numbers, 0)   # Adds 0 to the heap

# --- Pop: O(log n) time. Mutates the list. Returns smallest. ---
smallest = heapq.heappop(numbers)  # Returns 0 (the minimum)

# --- Push then Pop (optimized): O(log n) ---
result = heapq.heappushpop(numbers, 7)  # Push 7, then pop smallest

# --- Peek at minimum: O(1) ---
minimum = numbers[0]  # The smallest element without removing it

# --- MAX-HEAP TRICK ---
# Python has NO built-in max-heap. The trick: negate all values.
max_heap = []
for val in [5, 3, 8, 1, 2]:
    heapq.heappush(max_heap, -val)   # Push negated values

largest = -heapq.heappop(max_heap)   # Pop and negate back: 8

# --- Top-K pattern: O(n log k) ---
# Find the 3 largest elements
top_3 = heapq.nlargest(3, [5, 3, 8, 1, 2])   # [8, 5, 3]
# Find the 3 smallest elements
bot_3 = heapq.nsmallest(3, [5, 3, 8, 1, 2])  # [1, 2, 3]

# --- Custom comparison with tuples ---
# heapq compares tuples element by element. Use (priority, data).
task_queue = []
heapq.heappush(task_queue, (3, "low priority"))
heapq.heappush(task_queue, (1, "high priority"))
heapq.heappush(task_queue, (2, "medium priority"))

priority, task = heapq.heappop(task_queue)  # (1, "high priority")

Heap is NOT sorted. Don’t iterate over a heap expecting sorted order. The only guarantee is heap[0] is the minimum. To get sorted order, keep calling heappop() — that’s literally what heapsort does: O(n log n).

6. Sorting

# Python uses Timsort — a hybrid of merge sort and insertion sort.
# Time: O(n log n) average and worst case.
# Space: O(n) — Timsort needs auxiliary space.
# Timsort is STABLE — equal elements maintain their original order.

numbers = [5, 2, 8, 1, 9]

# --- sorted(): O(n log n). Creates a NEW list. Does NOT mutate original. ---
sorted_nums = sorted(numbers)  # [1, 2, 5, 8, 9]. numbers unchanged.
# TS equivalent: [...arr].sort((a,b) => a-b) — note TS sort is in-place!
# C# equivalent: list.OrderBy(x => x).ToList() — also creates new

# --- list.sort(): O(n log n). Mutates the list IN PLACE. Returns None. ---
numbers.sort()  # numbers is now [1, 2, 5, 8, 9]. Returns None!
# ⚠️ Common mistake: result = numbers.sort() → result is None!

# --- Sorting with a key function ---
# The key function is called once per element: O(n) calls.
# Total: O(n log n) comparisons + O(n) key evaluations.
words = ["banana", "apple", "cherry"]
sorted_words = sorted(words, key=len)  # Sort by length: ["apple", "banana", "cherry"]

# --- Reverse sorting ---
descending = sorted(numbers, reverse=True)  # [9, 8, 5, 2, 1]

# --- Sorting with lambda ---
# Sort list of tuples by second element
pairs = [(1, 'b'), (3, 'a'), (2, 'c')]
sorted_pairs = sorted(pairs, key=lambda pair: pair[1])
# [(3, 'a'), (1, 'b'), (2, 'c')]

# --- Sorting strings ---
# Strings compare lexicographically (character by character, by Unicode value)
names = ["Charlie", "Alice", "Bob"]
sorted_names = sorted(names)  # ["Alice", "Bob", "Charlie"]

7. bisect — Binary Search on Sorted Lists

import bisect

# bisect module provides binary search on ALREADY SORTED lists.
# All operations are O(log n) for the search part.

sorted_list = [1, 3, 5, 7, 9]

# --- bisect_left: find insertion point (leftmost position) ---
# Returns index where x would be inserted to keep list sorted.
# If x already exists, returns the index BEFORE (left of) existing entries.
idx = bisect.bisect_left(sorted_list, 5)   # 2 (index OF the 5)
idx = bisect.bisect_left(sorted_list, 6)   # 3 (where 6 would go)

# --- bisect_right / bisect: insertion point AFTER existing entries ---
idx = bisect.bisect_right(sorted_list, 5)  # 3 (index AFTER the 5)

# --- insort: insert while maintaining sorted order ---
# O(log n) search + O(n) insertion (because list.insert is O(n))
bisect.insort(sorted_list, 4)  # sorted_list = [1, 3, 4, 5, 7, 9]
# ⚠️ insort MUTATES the list in place.

# --- Using bisect_left as a "binary search" function ---
def binary_search(sorted_list, target):
    """Returns index of target if found, else -1. O(log n) time."""
    index = bisect.bisect_left(sorted_list, target)
    if index < len(sorted_list) and sorted_list[index] == target:
        return index
    return -1

8. Strings

# Strings in Python are IMMUTABLE — just like C# and TS/JS.
# Every "modification" creates a NEW string.

s = "hello world"

# --- Indexing and slicing: same as lists ---
first_char = s[0]      # 'h' — O(1)
last_char = s[-1]      # 'd' — O(1)
sub = s[0:5]           # 'hello' — O(k), creates NEW string

# --- Common methods (all return NEW strings, original unchanged) ---
upper = s.upper()                # 'HELLO WORLD' — O(n)
lower = s.lower()                # 'hello world' — O(n)
stripped = "  hi  ".strip()      # 'hi' — O(n), removes whitespace from both ends
words = s.split(" ")             # ['hello', 'world'] — O(n), returns list of NEW strings
joined = ", ".join(["a", "b"])   # 'a, b' — O(total length of all strings)
replaced = s.replace("world", "python")  # 'hello python' — O(n)

# --- String building (concatenation) ---
# ⚠️ DON'T do this in a loop — each += creates a NEW string: O(n²) total!
result = ""
for char in "abc":
    result += char  # Creates new string each time!

# ✅ DO this instead — O(n) total:
chars = []
for char in "abc":
    chars.append(char)  # O(1) amortized
result = "".join(chars) # One allocation: O(n)

# --- f-strings (formatted string literals) ---
name = "Cristian"
age = 30
greeting = f"Hello, {name}! You are {age} years old."

# --- Character codes ---
code = ord('a')    # 97 — Unicode code point. Like C#'s (int)'a'
char = chr(97)     # 'a' — reverse of ord()

# --- Check if string contains substring: O(n*m) worst case ---
has_world = "world" in s   # True
index = s.find("world")    # 6 — returns -1 if not found (unlike index() which throws)

# --- Useful checks ---
"123".isdigit()     # True
"abc".isalpha()     # True
"abc123".isalnum()  # True

Interview tip: When building strings character by character, always use a list + "".join(). Mentioning this to the interviewer shows you understand immutability and its Big-O implications. In C# you’d use StringBuilder — Python’s equivalent is the list-join pattern.

9. Useful Built-in Functions

range()

# range(stop) or range(start, stop) or range(start, stop, step)
# Creates a lazy sequence — O(1) space regardless of size!
# Does NOT create a list in memory. It's a generator-like object.
# Like C#'s Enumerable.Range() or TS's... nothing built-in.

for i in range(5):           # 0, 1, 2, 3, 4
    pass

for i in range(2, 7):        # 2, 3, 4, 5, 6
    pass

for i in range(10, 0, -1):   # 10, 9, 8, ..., 1 (countdown, stop is exclusive)
    pass

for i in range(0, 10, 2):    # 0, 2, 4, 6, 8 (even numbers)
    pass

# To get an actual list: list(range(5)) → [0, 1, 2, 3, 4] — O(n) space

enumerate()

# enumerate() gives you (index, element) pairs — O(1) extra space.
# Like TS: arr.forEach((val, idx) => ...) but more Pythonic.

fruits = ["apple", "banana", "cherry"]

for index, fruit in enumerate(fruits):
    print(f"{index}: {fruit}")
# Output:
# 0: apple
# 1: banana
# 2: cherry

# Start from a different index
for index, fruit in enumerate(fruits, start=1):
    print(f"{index}: {fruit}")
# 1: apple, 2: banana, 3: cherry

zip()

# zip() pairs up elements from multiple iterables — O(1) extra space (lazy).
# Stops at the shortest iterable.
# Like TS's... lodash _.zip() or manually iterating with index.

names = ["Alice", "Bob", "Charlie"]
scores = [90, 85, 95]

for name, score in zip(names, scores):
    print(f"{name}: {score}")

# Create a dict from two lists in one line:
name_to_score = dict(zip(names, scores))
# {"Alice": 90, "Bob": 85, "Charlie": 95}

map(), filter(), and Comprehensions

# In Python, list comprehensions are preferred over map/filter.
# Both approaches are O(n) time.

numbers = [1, 2, 3, 4, 5]

# --- map() with list() — functional style ---
doubled = list(map(lambda x: x * 2, numbers))  # [2, 4, 6, 8, 10]

# --- List comprehension — Pythonic style (PREFERRED) ---
doubled = [x * 2 for x in numbers]  # [2, 4, 6, 8, 10]

# --- filter() vs comprehension ---
evens_functional = list(filter(lambda x: x % 2 == 0, numbers))  # [2, 4]
evens_pythonic = [x for x in numbers if x % 2 == 0]  # [2, 4]

# --- Dict comprehension ---
squared = {x: x**2 for x in range(5)}  # {0: 0, 1: 1, 2: 4, 3: 9, 4: 16}

# --- Set comprehension ---
unique_lengths = {len(word) for word in ["hi", "hello", "hey"]}  # {2, 3, 5}

min(), max(), sum()

numbers = [3, 1, 4, 1, 5]

# All are O(n) — they iterate through the entire iterable.
smallest = min(numbers)  # 1
largest  = max(numbers)  # 5
total    = sum(numbers)  # 14

# With key function — O(n)
words = ["banana", "apple", "cherry"]
longest = max(words, key=len)  # "banana" (length 6)

# min/max of two values — O(1)
smaller = min(3, 7)  # 3
bigger  = max(3, 7)  # 7

any() and all()

# any() — True if ANY element is truthy. Short-circuits. O(n) worst case.
# all() — True if ALL elements are truthy. Short-circuits. O(n) worst case.

numbers = [0, 1, 2, 3]
print(any(numbers))   # True (1 is truthy) — short-circuits after finding 1
print(all(numbers))   # False (0 is falsy) — short-circuits after finding 0

# Useful with generators for O(1) space:
has_even = any(x % 2 == 0 for x in [1, 3, 4, 7])  # True, stops at 4
all_positive = all(x > 0 for x in [1, 2, 3])       # True

10. Operators and Tricks

Arithmetic Operators

# Floor division — rounds DOWN (toward negative infinity)
print(7 // 2)     # 3 (not 3.5)
print(-7 // 2)    # -4 (rounds DOWN, not toward zero!)
# ⚠️ C# and TS truncate toward zero: -7 / 2 = -3

# Modulo
print(7 % 3)      # 1
print(-7 % 3)     # 2 ← Python modulo is always non-negative when divisor is positive
# ⚠️ In C# and JS: -7 % 3 = -1 (result has sign of dividend)

# Power
print(2 ** 10)     # 1024 — like Math.pow(2, 10) in JS, or Math.Pow() in C#

# Infinity — useful for initial min/max comparisons
positive_inf = float('inf')
negative_inf = float('-inf')
print(5 < positive_inf)   # True
print(-5 > negative_inf)  # True

Boolean and Comparison Tricks

# Chained comparisons — Python-exclusive, very readable
x = 5
print(1 < x < 10)     # True — equivalent to: 1 < x and x < 10
print(1 < x < 3)      # False

# Ternary expression — like TS's condition ? a : b
age = 20
status = "adult" if age >= 18 else "minor"

# Truthy/Falsy values in Python:
# Falsy: None, False, 0, 0.0, "", [], {}, set(), ()
# Everything else is truthy.

# or / and for default values (like JS's ?? and &&)
name = "" or "Anonymous"  # "Anonymous" (empty string is falsy)
# ⚠️ Unlike JS's ??, this catches ALL falsy values, not just None/undefined

Walrus Operator := (Python 3.8+)

# Assigns a value AND returns it in a single expression.
# Useful in while loops and conditions to avoid duplicate computation.

import re

# Without walrus — compute twice or use temp variable:
line = "hello world"
match = re.search(r'\d+', line)
if match:
    print(match.group())

# With walrus — assign and check in one step:
if match := re.search(r'\d+', line):
    print(match.group())

# Common in while loops:
# while (chunk := file.read(8192)):
#     process(chunk)

11. itertools — Combinatorial Tools

from itertools import permutations, combinations, product

# --- permutations(iterable, r) ---
# All ordered arrangements of r elements. O(n!/(n-r)!) results.
perms = list(permutations([1, 2, 3], 2))
# [(1,2), (1,3), (2,1), (2,3), (3,1), (3,2)] — 6 results

# All permutations (r = len):
all_perms = list(permutations([1, 2, 3]))
# [(1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1)] — 6 results

# --- combinations(iterable, r) ---
# All unordered selections of r elements. O(n choose r) results.
combos = list(combinations([1, 2, 3, 4], 2))
# [(1,2), (1,3), (1,4), (2,3), (2,4), (3,4)] — 6 results

# --- product(iterables, repeat=) ---
# Cartesian product. Like nested for loops.
pairs = list(product([0, 1], repeat=3))
# [(0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0), (1,1,1)]
# 8 results = 2^3

# Cross product of two different iterables:
cross = list(product("AB", [1, 2]))
# [('A',1), ('A',2), ('B',1), ('B',2)]

12. Helpful Patterns for Interviews

Matrix (2D Grid) Traversal

# Grids/matrices are represented as list of lists in Python.
# This is THE most common representation in Google interviews.

grid = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9],
]

rows = len(grid)        # 3
cols = len(grid[0])     # 3 — assumes non-empty, uniform grid

# --- 4-directional neighbors (up, down, left, right) ---
# This pattern is used in almost every grid problem (islands, shortest path, etc.)
DIRECTIONS = [(0, 1), (0, -1), (1, 0), (-1, 0)]

row, col = 1, 1  # Center cell (value 5)
for delta_row, delta_col in DIRECTIONS:
    neighbor_row = row + delta_row
    neighbor_col = col + delta_col
    # Always check bounds!
    if 0 <= neighbor_row < rows and 0 <= neighbor_col < cols:
        print(grid[neighbor_row][neighbor_col])  # 2, 8, 4, 6

# --- 8-directional neighbors (including diagonals) ---
DIRECTIONS_8 = [
    (-1, -1), (-1, 0), (-1, 1),
    ( 0, -1),          ( 0, 1),
    ( 1, -1), ( 1, 0), ( 1, 1),
]

Hash a List (for memoization or as dict key)

# Lists are NOT hashable (because they're mutable).
# You can't use a list as a dict key or add it to a set.
# Convert to tuple first — tuples ARE hashable (immutable).

my_list = [1, 2, 3]
# my_set.add(my_list)    # ❌ TypeError: unhashable type: 'list'
my_set = set()
my_set.add(tuple(my_list))  # ✅ Works! (1, 2, 3)

# For 2D grids that need to be used as dict keys (e.g., memoization):
grid = [[1, 2], [3, 4]]
grid_key = tuple(tuple(row) for row in grid)  # ((1, 2), (3, 4))

Integer Limits and Math

import math

# Python integers have UNLIMITED size — no overflow!
# Unlike C#'s int (32-bit) or JS's Number (53-bit mantissa).
big = 2 ** 1000  # This works! No overflow.

# But if you need "infinity" for comparisons:
INF = float('inf')
NEG_INF = float('-inf')

# Math functions
math.sqrt(16)      # 4.0
math.ceil(3.2)     # 4
math.floor(3.8)    # 3
math.log2(8)       # 3.0
math.gcd(12, 8)    # 4 (greatest common divisor)
abs(-5)            # 5 (built-in, not math module)

Common Python Gotchas in Interviews

  1. list.sort() returns None, not the sorted list. Use sorted() if you need the result.

  2. dict iteration order is insertion order (Python 3.7+), but don’t rely on it for algorithmic correctness.

  3. Default mutable arguments are shared: def f(arr=[]) — the list is created ONCE and shared across all calls!

  4. Integer division // rounds toward negative infinity, not toward zero.

  5. is vs ==: is checks identity (same object in memory), == checks equality. Use == for value comparison, is only for None: if x is None.

  6. Shallow vs deep copy: list[:], list.copy(), dict.copy() are shallow. Use copy.deepcopy() for nested structures.

13. Quick Reference Card

Operation Structure Time Mutates?

lst.append(x)

list

O(1)*

✅

lst.pop()

list

O(1)

✅

lst.pop(0)

list

⚠️ O(n)

✅

lst[i]

list

O(1)

❌

x in lst

list

O(n)

❌

lst.sort()

list

O(n log n)

✅

sorted(lst)

list

O(n log n)

❌ new list

lst[::-1]

list

O(n)

❌ new list

d[key]

dict

O(1)*

❌

d[key] = val

dict

O(1)*

✅

key in d

dict

O(1)*

❌

s.add(x)

set

O(1)*

✅

x in s

set

O(1)*

❌

dq.append(x)

deque

O(1)

✅

dq.appendleft(x)

deque

O(1)

✅

dq.popleft()

deque

O(1)

✅

heappush(h, x)

heapq

O(log n)

✅

heappop(h)

heapq

O(log n)

✅

heapify(lst)

heapq

O(n)

✅

bisect_left(lst, x)

bisect

O(log n)

❌

* = amortized / average case. Worst case O(n) for hash-based structures due to collisions.