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)]

# Single integer
n = int(input())

# Multiple integers on one line
a, b, c = map(int, input().split())

# List of integers
arr = list(map(int, input().split()))

# N×M integer matrix
n, m = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(n)]

# Character grid (no spaces)
grid = [list(input()) for _ in range(n)]

# Transpose a matrix
transposed = [list(row) for row in zip(*matrix)]

# Rotate 90° clockwise
rotated = [list(row) for row in zip(*matrix[::-1])]

# Flatten a matrix
flat = [x for row in matrix for x in row]

# Safe matrix init (NOT [[0]*m]*n!)
mat = [[0] * m for _ in range(n)]

# Fast I/O (competitive programming)
import sys
input = sys.stdin.readline   # much faster than input()

# Read all input at once
data = sys.stdin.read().split()
idx = 0
n = int(data[idx]); idx += 1

# Fast output (batch print)
out = []
for _ in range(n):
    out.append(str(result))
print("\n".join(out))

# List comprehension with condition
evens = [x for x in range(20) if x % 2 == 0]

# Nested comprehension (flatten)
flat = [x for sub in nested for x in sub]

# Dict / Set comprehension
sq = {x: x**2 for x in range(10)}
unique_lens = {len(w) for w in words}

# Ternary
result = "even" if n % 2 == 0 else "odd"

# Swap without temp
a, b = b, a

# Chain comparisons
if 1 <= x <= 10:  # Pythonic!

# Any / All with generator
has_neg = any(x < 0 for x in nums)
all_pos = all(x > 0 for x in nums)

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

# Zip longest
from itertools import zip_longest
list(zip_longest(a, b, fillvalue=0))

# Multiple assignment
x = y = z = 0

from collections import Counter, defaultdict, deque, namedtuple

# Counter — frequency counting
c = Counter("abracadabra")
c.most_common(2)       # [('a', 5), ('b', 2)]
c + Counter("abc")    # add counts
c - Counter("abc")    # subtract counts

# defaultdict — no KeyError
d = defaultdict(list)
d["key"].append(1)   # auto-creates list
d = defaultdict(int)
d["key"] += 1         # auto-starts at 0

# deque — O(1) append/pop both ends
dq = deque([1, 2, 3])
dq.appendleft(0)      # [0, 1, 2, 3]
dq.popleft()          # 0 — O(1) unlike list.pop(0)
dq.rotate(1)          # right rotate
dq = deque(maxlen=3)  # fixed-size sliding window

# namedtuple — lightweight immutable record
Point = namedtuple("Point", ["x", "y"])
p = Point(3, 4); p.x, p.y  # 3, 4

from itertools import permutations, combinations, product, chain, groupby, accumulate

# Permutations & Combinations
list(permutations([1,2,3]))         # 6 tuples
list(combinations([1,2,3], 2))      # [(1,2),(1,3),(2,3)]

# Cartesian product
list(product("AB", "12"))            # [('A','1'),('A','2')...]
list(product(range(3), repeat=2))    # all pairs (0,0)→(2,2)

# Chain + groupby
list(chain([1,2], [3,4]))           # [1,2,3,4]
# groupby needs sorted input!
for grade, grp in groupby(sorted(students, key=lambda s: s.grade), key=lambda s: s.grade):
    print(grade, list(grp))

# Accumulate — running totals
list(accumulate([1,2,3,4]))   # [1, 3, 6, 10]

# ── Functools ──────────────
from functools import lru_cache, reduce, partial, cache

# LRU Cache / @cache — great for DP memoization
@lru_cache(maxsize=None)
def fib(n): return n if n < 2 else fib(n-1) + fib(n-2)

# reduce
product_val = reduce(lambda a, b: a * b, [1,2,3,4])  # 24

# partial — freeze args
add_ten = partial(lambda a, b: a + b, 10)
add_ten(5)  # 15

# Reverse & palindrome check
s[::-1]
s == s[::-1]

# Split & join
words = s.split()
" ".join(words)
",".join(map(str, nums))   # "1,2,3"

# f-string formatting
f"{val:.2f}"               # "3.14"
f"{val:08b}"               # "00001010" (binary)
f"{val:,}"                 # "1,000,000"
f"{name!r}"                # repr: "'hello'"
f"{val:>10}"               # right-align, width 10
f"{val:^10}"               # center-align

# Character ↔ int
ord('a')                   # 97
chr(97)                    # 'a'
chr(ord('a') + 3)          # 'd'

# Useful checks
s.isalpha()  s.isdigit()  s.isalnum()  s.isspace()

# Translate table (fast char replacement)
table = str.maketrans("aeiou", "12345")
"hello".translate(table)   # "h2ll4"

# Operators
a & b   # AND      a | b  # OR
a ^ b   # XOR     ~a     # NOT
a << n  # ×2^n    a >> n # ÷2^n

# Check power of 2
n > 0 and (n & (n - 1)) == 0

# Bit manipulation
bool(n & (1 << i))      # check bit i
n | (1 << i)            # set bit i
n & ~(1 << i)           # clear bit i
n ^ (1 << i)            # toggle bit i
bin(n).count("1")       # count set bits

# XOR cancellation trick
a ^ a == 0             # self-cancel → find unique!
a ^ b ^ b == a         # undo XOR

# Find missing number (1..n)
missing = 0
for i in range(1, n+1): missing ^= i
for x in arr:          missing ^= x

# Sort by key
arr.sort(key=lambda x: x[1])
arr.sort(key=lambda x: (-x[1], x[0]))  # desc then asc

# Custom comparator
from functools import cmp_to_key
arr.sort(key=cmp_to_key(lambda a, b: -1 if a+b > b+a else 1))

# Min-heap
import heapq
heapq.heapify(arr)
heapq.heappush(arr, val)
smallest = heapq.heappop(arr)

# Max-heap (negate values)
heapq.heappush(heap, -val)
largest = -heapq.heappop(heap)

# K largest / smallest
heapq.nlargest(3, arr)
heapq.nsmallest(3, arr, key=lambda x: x[1])

# Bisect — O(log n) insert into sorted list
import bisect
bisect.bisect_left(arr, target)   # leftmost position
bisect.bisect_right(arr, target)  # rightmost position
bisect.insort(arr, val)            # insert in order

# Star unpacking
first, *rest = [1, 2, 3, 4]
first, *mid, last = [1, 2, 3, 4]

# Merge dicts
merged = {**dict1, **dict2}    # dict2 wins on conflicts
merged = dict1 | dict2         # Python 3.9+

# Spread into function args
func(*args, **kwargs)

# Walrus operator := (Python 3.8+)
if (n := len(arr)) > 10:
    print(f"Large: {n}")       # n reused without recompute

while (line := input()) != "quit":
    process(line)

[y for x in data if (y := transform(x)) > 0]

# Stack (use list)
stack = []; stack.append(x); stack.pop(); stack[-1]  # peek

# Queue (use deque for O(1) left pop)
from collections import deque
q = deque()
q.append(x)     # enqueue right
q.popleft()     # dequeue left — O(1)

# Set operations
a | b  # union    a & b  # intersect
a - b  # diff     a ^ b  # symmetric diff
a <= b # subset check

# Dict patterns
d.get(key, default)
d.setdefault(key, []).append(v)
d.pop(key, None)
{v: k for k, v in d.items()}  # invert dict

# SortedList (pip install sortedcontainers)
from sortedcontainers import SortedList
sl = SortedList([3, 1, 2])
sl.add(4)              # O(log n)
sl.bisect_left(3)     # find index

# Pattern → When to use
Two Pointers     sorted array / pair sum / remove dups
Sliding Window   subarray/substring of size k or variable
HashMap          frequency count / two-sum / anagram check
Binary Search    sorted data / min-max answer search
BFS              shortest path / level-order / closest
DFS              all paths / cycle detect / connected
DP               overlapping subproblems / optimal substructure
Backtracking     all permutations / combinations / decision tree
Monotonic Stack  next greater/smaller element
Union-Find       connected components / cycle detection
Trie             prefix search / autocomplete / word exists
Heap / PQ        k-th largest / merge k lists / streaming median

# Two pointers template
l, r = 0, n - 1
while l < r:
    if arr[l] + arr[r] == target: return [l, r]
    elif arr[l] + arr[r] < target: l += 1
    else: r -= 1

# Sliding window template
l = total = 0; best = float("inf")
for r in range(len(arr)):
    total += arr[r]
    while total >= target:
        best = min(best, r - l + 1); total -= arr[l]; l += 1

# Binary search on answer
lo, hi = 0, 10**9
while lo < hi:
    mid = (lo + hi) // 2
    if condition(mid): hi = mid
    else: lo = mid + 1

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

# ❌ [[0]*m]*n creates N references to SAME inner list
grid = [[0] * 3] * 3  # grid[0][0]=1 changes ALL rows!
# ✅ Fix:  [[0]*m for _ in range(n)]

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

# ❌ Use == not is for value comparison
a = 257; b = 257
a is b  # May be False — integers >256 not cached

# ❌ Float precision
0.1 + 0.2 == 0.3  # False!
# ✅  abs(0.1 + 0.2 - 0.3) < 1e-9

# ❌ Late binding closures
fns = [lambda: i for i in range(3)]  # all return 2!
# ✅  lambda i=i: i  (capture with default arg)

# Recursion limit fix (competitive programming)
import sys; sys.setrecursionlimit(10**6)

max(arr)                         # max value
min(arr)                         # min value
sum(arr)                         # sum
sorted(arr, reverse=True)        # desc sort
list(set(arr))                   # unique (unordered)
list(dict.fromkeys(arr))         # unique (ordered)
[x for row in mat for x in row] # flatten 2D
Counter(arr)                     # frequency map
float('inf')                     # infinity
float('-inf')                    # negative infinity
sys.maxsize                      # max int
if not arr:                      # check empty
list(map(int, strs))             # map to int
[int(d) for d in str(n)]        # digits of number
math.gcd(a, b)                   # GCD
math.lcm(a, b)                   # LCM (Python 3.9+)
-(-a // b)                       # ceiling division
math.isqrt(n)                    # integer square root
divmod(a, b)                     # (quotient, remainder)
abs(x)                           # absolute value
round(x, 2)                      # round to 2 decimals