Python Interview Cheatsheet

s = "hello world"

# Common methods
s.upper()          # "HELLO WORLD"
s.lower()          # "hello world"
s.strip()          # remove whitespace
s.split()          # ["hello", "world"]
s.split(",")       # split by delimiter
",".join(["a", "b"])  # "a,b"
s.replace("hello", "hi")  # "hi world"
s.startswith("he")  # True
s.find("world")     # 6 (-1 if not found)
s.count("l")        # 3
s.isalpha()         # False (has space)
s.isdigit()         # False
s.isalnum()         # False

# Slicing
s[0]               # "h"
s[-1]              # "d"
s[0:5]             # "hello"
s[::-1]            # "dlrow olleh" (reverse)

# String is IMMUTABLE — create new strings
# For heavy concatenation, use list + join
parts = []
for ch in s:
    parts.append(ch.upper())
result = "".join(parts)

# Character operations
ord("a")   # 97
chr(97)    # "a"

# f-strings
name = "Bob"
f"Hello {name}, age {25 + 1}"  # "Hello Bob, age 26"

# Check palindrome
def is_palindrome(s):
    s = s.lower().replace(" ", "")
    return s == s[::-1]

# Check anagram
from collections import Counter
def is_anagram(a, b):
    return Counter(a) == Counter(b)

# Creation
arr = [1, 2, 3, 4, 5]
zeros = [0] * 10           # [0, 0, 0, ...]
grid = [[0] * 3 for _ in range(3)]  # 3x3 matrix

# Common methods
arr.append(6)          # add to end — O(1)
arr.pop()              # remove last — O(1)
arr.pop(0)             # remove first — O(n) ⚠️
arr.insert(0, val)     # insert at index — O(n)
arr.remove(val)        # remove first occurrence — O(n)
arr.extend([7, 8])    # add multiple
arr.reverse()          # in-place reverse
arr.sort()             # in-place sort
arr.sort(key=lambda x: -x)  # sort descending
arr.index(val)         # find index of val

# Slicing (creates new list)
arr[1:3]              # [2, 3]
arr[::-1]             # reversed copy
arr[:]                 # shallow copy

# List comprehension
squares = [x**2 for x in range(10)]
evens = [x for x in arr if x % 2 == 0]
flat = [x for row in grid for x in row]  # flatten 2D

# Useful built-ins
len(arr)              # length
sum(arr)              # sum all
min(arr), max(arr)   # min/max
sorted(arr)           # returns new sorted list
enumerate(arr)        # (index, value) pairs
zip(arr1, arr2)       # pair elements
any(arr), all(arr)   # any/all truthy
map(lambda x: x*2, arr)  # apply function
filter(lambda x: x > 0, arr)  # filter elements

# Unpack
a, *rest, z = [1, 2, 3, 4, 5]
# a=1, rest=[2,3,4], z=5

# ===== DICT =====
d = {"a": 1, "b": 2}

d["c"] = 3                # set
d.get("x", 0)             # get with default (0 if missing)
d.pop("a")                # remove & return
d.keys()                  # dict_keys(["a", "b"])
d.values()                # dict_values([1, 2])
d.items()                 # dict_items([("a", 1), ...])
"a" in d                  # True — O(1) key lookup

# Iterate
for k, v in d.items():
    print(k, v)

# defaultdict — auto-initialize missing keys
from collections import defaultdict
graph = defaultdict(list)
graph["a"].append("b")    # no KeyError

counter = defaultdict(int)
for ch in "hello":
    counter[ch] += 1       # auto 0 + 1

# Counter — frequency counting
from collections import Counter
freq = Counter("abracadabra")  # Counter({'a': 5, 'b': 2, ...})
freq.most_common(2)            # [('a', 5), ('b', 2)]

# Dict comprehension
squared = {x: x**2 for x in range(5)}

# ===== SET =====
s = {1, 2, 3}
s.add(4)
s.remove(1)       # KeyError if missing
s.discard(99)     # no error if missing
2 in s             # O(1) lookup

# Set operations
a = {1, 2, 3}
b = {2, 3, 4}
a | b              # union: {1, 2, 3, 4}
a & b              # intersection: {2, 3}
a - b              # difference: {1}
a ^ b              # symmetric diff: {1, 4}

# ===== STACK (LIFO) — use list =====
stack = []
stack.append(1)     # push
stack.append(2)
stack[-1]            # peek → 2
stack.pop()          # pop → 2

# ===== QUEUE (FIFO) — use deque =====
from collections import deque
q = deque()
q.append(1)         # enqueue right
q.append(2)
q.popleft()         # dequeue left → 1 — O(1)
q[0]                # peek front

# ===== HEAP (Min-Heap by default) =====
import heapq
heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 2)
heapq.heappop(heap)      # → 1 (smallest)
heap[0]                   # peek min

# Max-heap trick: negate values
heapq.heappush(heap, -val)
-heapq.heappop(heap)       # get max

# Heapify existing list
arr = [5, 3, 8, 1]
heapq.heapify(arr)         # O(n) — arr is now a heap

# Top-K elements
heapq.nlargest(3, arr)    # 3 largest
heapq.nsmallest(3, arr)   # 3 smallest

# ===== MONOTONIC STACK (common pattern) =====
# Next greater element
def next_greater(nums):
    result = [-1] * len(nums)
    stack = []  # store indices
    for i, num in enumerate(nums):
        while stack and nums[stack[-1]] < num:
            result[stack.pop()] = num
        stack.append(i)
    return result

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# Reverse Linked List
def reverse(head):
    prev, curr = None, head
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    return prev

# Detect Cycle (Floyd's)
def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

# Find Middle
def find_middle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

# Merge Two Sorted Lists
def merge(l1, l2):
    dummy = ListNode(0)
    curr = dummy
    while l1 and l2:
        if l1.val < l2.val:
            curr.next = l1
            l1 = l1.next
        else:
            curr.next = l2
            l2 = l2.next
        curr = curr.next
    curr.next = l1 or l2
    return dummy.next

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# ===== DFS Traversals =====
# Inorder (Left → Root → Right) — gives sorted for BST
def inorder(root):
    if not root: return []
    return inorder(root.left) + [root.val] + inorder(root.right)

# Preorder (Root → Left → Right)
def preorder(root):
    if not root: return []
    return [root.val] + preorder(root.left) + preorder(root.right)

# ===== BFS (Level Order) =====
from collections import deque
def level_order(root):
    if not root: return []
    result, q = [], deque([root])
    while q:
        level = []
        for _ in range(len(q)):
            node = q.popleft()
            level.append(node.val)
            if node.left: q.append(node.left)
            if node.right: q.append(node.right)
        result.append(level)
    return result

# Max Depth
def max_depth(root):
    if not root: return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

# Validate BST
def is_valid_bst(root, lo=float("-inf"), hi=float("inf")):
    if not root: return True
    if root.val <= lo or root.val >= hi: return False
    return is_valid_bst(root.left, lo, root.val) and \
           is_valid_bst(root.right, root.val, hi)

# Lowest Common Ancestor (BST)
def lca(root, p, q):
    while root:
        if p.val < root.val and q.val < root.val:
            root = root.left
        elif p.val > root.val and q.val > root.val:
            root = root.right
        else:
            return root

# Adjacency list representation
graph = defaultdict(list)
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)  # undirected

# BFS
def bfs(graph, start):
    visited = {start}
    q = deque([start])
    while q:
        node = q.popleft()
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                q.append(neighbor)

# DFS (iterative)
def dfs(graph, start):
    visited = set()
    stack = [start]
    while stack:
        node = stack.pop()
        if node in visited: continue
        visited.add(node)
        for neighbor in graph[node]:
            stack.append(neighbor)

# DFS (recursive)
def dfs_rec(node, visited):
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs_rec(neighbor, visited)

# Number of Islands (grid BFS)
def num_islands(grid):
    rows, cols = len(grid), len(grid[0])
    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1":
                count += 1
                q = deque([(r, c)])
                grid[r][c] = "0"
                while q:
                    row, col = q.popleft()
                    for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
                        nr, nc = row+dr, col+dc
                        if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == "1":
                            grid[nr][nc] = "0"
                            q.append((nr, nc))
    return count

# Topological Sort (Kahn's / BFS)
def topo_sort(num_nodes, edges):
    indegree = [0] * num_nodes
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        indegree[v] += 1
    q = deque(i for i in range(num_nodes) if indegree[i] == 0)
    order = []
    while q:
        node = q.popleft()
        order.append(node)
        for nei in graph[node]:
            indegree[nei] -= 1
            if indegree[nei] == 0:
                q.append(nei)
    return order if len(order) == num_nodes else []

# Built-in (Timsort — O(n log n))
arr.sort()                        # in-place
new = sorted(arr)                 # returns new list
sorted(arr, reverse=True)        # descending
sorted(arr, key=lambda x: x[1])  # sort by 2nd element

# Sort objects by multiple keys
people.sort(key=lambda p: (p.age, p.name))

# Merge Sort (interview classic)
def merge_sort(arr):
    if len(arr) <= 1: return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(a, b):
    result, i, j = [], 0, 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            result.append(a[i]); i += 1
        else:
            result.append(b[j]); j += 1
    result.extend(a[i:])
    result.extend(b[j:])
    return result

# Quick Sort
def quick_sort(arr):
    if len(arr) <= 1: return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    mid = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + mid + quick_sort(right)

# Standard binary search
def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

# bisect module
import bisect
bisect.bisect_left(arr, target)   # leftmost insert position
bisect.bisect_right(arr, target)  # rightmost insert position
bisect.insort(arr, val)           # insert keeping sorted

# Find first True (generalized binary search)
def first_true(lo, hi, condition):
    while lo < hi:
        mid = (lo + hi) // 2
        if condition(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

# Binary search on answer (e.g., minimum capacity)
def min_capacity(weights, days):
    lo, hi = max(weights), sum(weights)
    while lo < hi:
        mid = (lo + hi) // 2
        if can_ship(weights, days, mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

# ===== Framework =====
# 1. Define state: dp[i] = ...
# 2. Recurrence: dp[i] = f(dp[i-1], ...)
# 3. Base case: dp[0] = ...
# 4. Order: bottom-up or top-down

# Fibonacci (bottom-up)
def fib(n):
    if n <= 1: return n
    prev, curr = 0, 1
    for _ in range(2, n + 1):
        prev, curr = curr, prev + curr
    return curr

# Fibonacci (top-down with memoization)
from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n <= 1: return n
    return fib(n-1) + fib(n-2)

# Climbing Stairs
def climb(n):
    dp = [0] * (n + 1)
    dp[0] = dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

# 0/1 Knapsack
def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for w in range(capacity + 1):
            dp[i][w] = dp[i-1][w]
            if weights[i-1] <= w:
                dp[i][w] = max(dp[i][w], dp[i-1][w - weights[i-1]] + values[i-1])
    return dp[n][capacity]

# Longest Common Subsequence
def lcs(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]

# Coin Change
def coin_change(coins, amount):
    dp = [float("inf")] * (amount + 1)
    dp[0] = 0
    for coin in coins:
        for a in range(coin, amount + 1):
            dp[a] = min(dp[a], dp[a - coin] + 1)
    return dp[amount] if dp[amount] != float("inf") else -1

# ===== Two Pointers =====
# Two Sum (sorted array)
def two_sum_sorted(arr, target):
    l, r = 0, len(arr) - 1
    while l < r:
        s = arr[l] + arr[r]
        if s == target: return [l, r]
        elif s < target: l += 1
        else: r -= 1

# Two Sum (unsorted — use hashmap)
def two_sum(nums, target):
    seen = {}
    for i, n in enumerate(nums):
        comp = target - n
        if comp in seen:
            return [seen[comp], i]
        seen[n] = i

# ===== Fixed Sliding Window =====
# Max sum subarray of size k
def max_sum_k(arr, k):
    window = sum(arr[:k])
    best = window
    for i in range(k, len(arr)):
        window += arr[i] - arr[i - k]
        best = max(best, window)
    return best

# ===== Variable Sliding Window =====
# Longest substring without repeating chars
def length_of_longest(s):
    seen = {}
    l = best = 0
    for r, ch in enumerate(s):
        if ch in seen and seen[ch] >= l:
            l = seen[ch] + 1
        seen[ch] = r
        best = max(best, r - l + 1)
    return best

# Minimum window substring
def min_window(s, t):
    need = Counter(t)
    missing = len(t)
    l = start = 0
    best = float("inf")
    for r, ch in enumerate(s):
        if need[ch] > 0:
            missing -= 1
        need[ch] -= 1
        while missing == 0:
            if r - l + 1 < best:
                best = r - l + 1
                start = l
            need[s[l]] += 1
            if need[s[l]] > 0:
                missing += 1
            l += 1
    return s[start:start + best] if best != float("inf") else ""

# Template
def backtrack(path, choices):
    if is_solution(path):
        result.append(path[:])
        return
    for choice in choices:
        if is_valid(choice):
            path.append(choice)      # make choice
            backtrack(path, ...)    # recurse
            path.pop()              # undo choice

# Subsets
def subsets(nums):
    result = []
    def bt(start, path):
        result.append(path[:])
        for i in range(start, len(nums)):
            path.append(nums[i])
            bt(i + 1, path)
            path.pop()
    bt(0, [])
    return result

# Permutations
def permutations(nums):
    result = []
    def bt(path, remaining):
        if not remaining:
            result.append(path[:])
            return
        for i in range(len(remaining)):
            path.append(remaining[i])
            bt(path, remaining[:i] + remaining[i+1:])
            path.pop()
    bt([], nums)
    return result

# Combination Sum
def combination_sum(candidates, target):
    result = []
    def bt(start, path, remaining):
        if remaining == 0:
            result.append(path[:])
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remaining: break
            path.append(candidates[i])
            bt(i, path, remaining - candidates[i])
            path.pop()
    candidates.sort()
    bt(0, [], target)
    return result

# Infinity
float("inf"), float("-inf")

# Multiple assignment
a, b = b, a                    # swap
a = b = c = 0                  # all zero

# Ternary
x = a if condition else b

# Walrus operator (:=) — assign inside expression
while (line := f.readline()):
    process(line)

# Enumerate with start
for i, v in enumerate(arr, start=1):
    print(i, v)

# Zip longest
from itertools import zip_longest
list(zip_longest([1,2], [3,4,5], fillvalue=0))

# itertools essentials
from itertools import combinations, permutations, product, accumulate
list(combinations([1,2,3], 2))  # [(1,2), (1,3), (2,3)]
list(permutations([1,2,3], 2))  # [(1,2), (1,3), (2,1), ...]
list(product([0,1], repeat=3))   # all 3-bit combos
list(accumulate([1,2,3,4]))    # prefix sums [1,3,6,10]

# functools
from functools import lru_cache, reduce
reduce(lambda a, b: a + b, [1,2,3])  # 6

# Bit manipulation
n & 1          # check odd
n >> 1         # divide by 2
n << 1         # multiply by 2
n & (n - 1)    # clear lowest set bit
bin(n).count("1")  # popcount
n ^ n          # 0 (XOR with self)

class Animal:
    species_count = 0           # class variable

    def __init__(self, name, age):
        self.name = name         # instance variable
        self._age = age          # convention: "private"
        Animal.species_count += 1

    def speak(self):            # instance method
        return f"{self.name} makes a sound"

    @property                   # getter
    def age(self):
        return self._age

    @age.setter
    def age(self, value):
        if value < 0: raise ValueError
        self._age = value

    @classmethod
    def get_count(cls):
        return cls.species_count

    @staticmethod
    def is_valid_name(name):
        return isinstance(name, str) and len(name) > 0

    def __repr__(self):
        return f"Animal({self.name!r}, {self._age})"

    def __eq__(self, other):
        return self.name == other.name

    def __hash__(self):
        return hash(self.name)

    def __lt__(self, other):     # enables sorting
        return self._age < other._age

# Inheritance
class Dog(Animal):
    def __init__(self, name, age, breed):
        super().__init__(name, age)
        self.breed = breed

    def speak(self):             # override
        return f"{self.name} barks"

# Abstract class
from abc import ABC, abstractmethod
class Shape(ABC):
    @abstractmethod
    def area(self): ...

# Dataclass (Python 3.7+)
from dataclasses import dataclass
@dataclass
class Point:
    x: float
    y: float
    def distance(self):
        return (self.x**2 + self.y**2) ** 0.5

# ❌ Mutable default argument
def bad(lst=[]):       # shared across calls!
    lst.append(1)
    return lst
# ✅ Fix:
def good(lst=None):
    lst = lst or []
    lst.append(1)
    return lst

# ❌ 2D array creation
grid = [[0] * 3] * 3   # rows are same reference!
# ✅ Fix:
grid = [[0] * 3 for _ in range(3)]

# ❌ Modifying list while iterating
for item in lst:
    if condition: lst.remove(item)  # skips elements!
# ✅ Fix:
lst = [x for x in lst if not condition]

# ❌ Integer identity vs equality
a = 256; b = 256; a is b   # True (cached)
a = 257; b = 257; a is b   # False! (not cached)
# ✅ Always use == for value comparison

# ❌ Late binding closures
fns = [lambda: i for i in range(3)]
[f() for f in fns]  # [2, 2, 2] not [0, 1, 2]!
# ✅ Fix:
fns = [lambda i=i: i for i in range(3)]