Basic Syntax & Patterns
Built-in Data Structures
Collections Module
String Manipulation
List & Array Operations
Itertools & Functional Programming
Dynamic Programming
Sorting & Searching
Mathematical Algorithms
Advanced Patterns
Interview Tips

Basic Syntax & Patterns

Essential Imports

import collections
import heapq
import bisect
import itertools
import functools
import math
import re
from typing import List, Dict, Set, Tuple, Optional

Input/Output Patterns

# Fast input reading
import sys
input = sys.stdin.readline  # Faster than input() for large inputs
 
# Multiple test cases
t = int(input())
for _ in range(t):
    # Process each test case
    n = int(input())
    arr = list(map(int, input().split()))
 
# Reading matrix
n, m = map(int, input().split())
matrix = []
for _ in range(n):
    row = list(map(int, input().split()))
    matrix.append(row)

Python-Specific Syntax

# Multiple assignment
a, b = b, a  # Swap without temp variable
x, y, z = 1, 2, 3  # Multiple assignment
 
# Conditional expressions (ternary operator)
result = value_if_true if condition else value_if_false
max_val = a if a > b else b
 
# Walrus operator (Python 3.8+) - assignment in expressions
if (n := len(arr)) > 5:
    print(f"Array length {n} is greater than 5")
 
# F-strings for formatting
name, age = "Alice", 25
print(f"Name: {name}, Age: {age}")

Built-in Data Structures

Lists - Dynamic Arrays

# List creation and basic operations - O(1) append, O(n) insert at beginning
arr = [1, 2, 3, 4, 5]
arr.append(6)        # O(1) - add to end
arr.pop()           # O(1) - remove from end
arr.insert(0, 0)    # O(n) - insert at beginning
arr.pop(0)          # O(n) - remove from beginning
 
# List comprehensions - Pythonic and efficient
squares = [x**2 for x in range(10)]  # [0, 1, 4, 9, 16, 25, 36, 49, 64, 81]
evens = [x for x in range(20) if x % 2 == 0]  # [0, 2, 4, 6, 8, 10, 12, 14, 16, 18]
 
# Nested list comprehension for 2D arrays
matrix = [[0 for _ in range(m)] for _ in range(n)]  # n x m matrix
# DON'T do: matrix = [[0] * m] * n  # This creates references to same list!
 
# List slicing - O(k) where k is slice length
arr[1:4]     # Elements at index 1, 2, 3
arr[:3]      # First 3 elements
arr[2:]      # From index 2 to end
arr[::-1]    # Reverse the list - O(n)
arr[::2]     # Every 2nd element

Dictionaries - Hash Maps

# Dictionary operations - Average O(1) for get, set, delete
freq = {}
freq['a'] = freq.get('a', 0) + 1  # Increment count
freq.setdefault('b', 0)            # Set default if key doesn't exist
 
# Dictionary comprehensions
char_count = {char: string.count(char) for char in set(string)}
 
# Useful dictionary methods
dict1.update(dict2)         # Merge dictionaries
keys = list(dict1.keys())   # Get all keys
values = list(dict1.values())  # Get all values
items = list(dict1.items()) # Get key-value pairs
 
# Defaultdict alternative (without collections)
from collections import defaultdict
dd = defaultdict(int)       # Default value is 0
dd = defaultdict(list)      # Default value is empty list
dd = defaultdict(set)       # Default value is empty set

Sets - Hash Sets

# Set operations - Average O(1) for add, remove, contains
s1 = {1, 2, 3, 4}
s2 = {3, 4, 5, 6}
 
s1.add(5)              # Add element
s1.discard(1)          # Remove if exists (no error if not found)
s1.remove(2)           # Remove (raises KeyError if not found)
 
# Set operations
intersection = s1 & s2  # {3, 4, 5}
union = s1 | s2         # {1, 2, 3, 4, 5, 6}
difference = s1 - s2    # {1, 2}
symmetric_diff = s1 ^ s2 # Elements in either but not both
 
# Set comprehensions
unique_lengths = {len(word) for word in words}

Tuples - Immutable Sequences

# Tuples are immutable and hashable (can be dictionary keys)
point = (3, 4)
x, y = point  # Unpacking
 
# Named tuples for structured data
from collections import namedtuple
Point = namedtuple('Point', ['x', 'y'])
p = Point(3, 4)
print(p.x, p.y)  # Access by name

Collections Module

Deque - Double-ended Queue

from collections import deque
 
# Efficient O(1) operations at both ends
dq = deque([1, 2, 3])
dq.appendleft(0)    # Add to left - O(1)
dq.append(4)        # Add to right - O(1)
dq.popleft()        # Remove from left - O(1)
dq.pop()           # Remove from right - O(1)
 
# Rotating elements
dq.rotate(1)       # Rotate right by 1
dq.rotate(-1)      # Rotate left by 1
 
# Use deque for sliding window problems
def sliding_window_maximum(nums, k):
    dq = deque()  # Store indices
    result = []
    
    for i in range(len(nums)):
        # Remove elements outside window
        while dq and dq[0] <= i - k:
            dq.popleft()
        
        # Maintain decreasing order in deque
        while dq and nums[dq[-1]] <= nums[i]:
            dq.pop()
        
        dq.append(i)
        
        if i >= k - 1:
            result.append(nums[dq[0]])
    
    return result

Counter - Counting Hash Map

from collections import Counter
 
# Efficient counting of elements
text = "hello world"
counter = Counter(text)  # Counter({'l': 3, 'o': 2, 'h': 1, 'e': 1, ...})
 
# Most common elements
most_common = counter.most_common(2)  # [('l', 3), ('o', 2)]
 
# Counter arithmetic
c1 = Counter(['a', 'b', 'c', 'a'])  # Counter({'a': 2, 'b': 1, 'c': 1})
c2 = Counter(['a', 'b', 'b'])       # Counter({'b': 2, 'a': 1})
print(c1 + c2)  # Counter({'a': 3, 'b': 3, 'c': 1})
print(c1 - c2)  # Counter({'c': 1, 'a': 1})
 
# Use Counter for anagram detection
def is_anagram(s1, s2):
    return Counter(s1) == Counter(s2)

DefaultDict - Dictionary with Default Values

from collections import defaultdict
 
# Automatically creates missing keys
graph = defaultdict(list)  # Default value is empty list
graph[1].append(2)  # No KeyError, creates empty list first
 
# Group anagrams example
def group_anagrams(strs):
    groups = defaultdict(list)
    for s in strs:
        key = ''.join(sorted(s))  # Use sorted string as key
        groups[key].append(s)
    return list(groups.values())

String Manipulation

Basic String Operations

s = "Hello World"
 
# String methods - all return new strings (strings are immutable)
s.lower()           # "hello world"
s.upper()           # "HELLO WORLD"
s.strip()           # Remove whitespace from both ends
s.split()           # Split by whitespace -> ['Hello', 'World']
s.split(',')        # Split by comma
s.replace('l', 'x') # "Hexxo Worxd"
s.count('l')        # Count occurrences -> 3
 
# String formatting
name, age = "Alice", 25
formatted = f"Name: {name}, Age: {age}"
formatted = "Name: {}, Age: {}".format(name, age)
formatted = "Name: %s, Age: %d" % (name, age)
 
# String checking methods
s.isdigit()     # True if all digits
s.isalpha()     # True if all letters
s.isalnum()     # True if all alphanumeric
s.startswith("He")  # True
s.endswith("ld")    # True

String Patterns for Interviews

# Palindrome check - O(n) time, O(1) space
def is_palindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True
 
# Character frequency using dictionary
def char_frequency(s):
    freq = {}
    for char in s:
        freq[char] = freq.get(char, 0) + 1
    return freq
 
# String reversal (multiple ways)
def reverse_string(s):
    return s[::-1]              # Pythonic way
    return ''.join(reversed(s)) # Using built-in reversed
    
# Anagram check using sorted strings
def is_anagram(s1, s2):
    return sorted(s1) == sorted(s2)
 
# Longest substring without repeating characters
def length_of_longest_substring(s):
    char_set = set()
    left = max_length = 0
    
    for right in range(len(s)):
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1
        char_set.add(s[right])
        max_length = max(max_length, right - left + 1)
    
    return max_length

Regular Expressions

import re
 
# Common regex patterns for interviews
email_pattern = r'^[a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+\.[a-zA-Z]{2,}$'
phone_pattern = r'^\d{3}-\d{3}-\d{4}$'
 
# Regex functions
re.search(pattern, string)    # Find first match
re.findall(pattern, string)   # Find all matches
re.sub(pattern, replacement, string)  # Replace matches
 
# Example: Extract numbers from string
text = "I have 10 apples and 5 oranges"
numbers = re.findall(r'\d+', text)  # ['10', '5']

List & Array Operations

Two Pointer Technique

# Classic two-pointer for sorted array
def two_sum_sorted(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        current_sum = nums[left] + nums[right]
        if current_sum == target:
            return [left, right]
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    return []
 
# Remove duplicates from sorted array - O(n) time, O(1) space
def remove_duplicates(nums):
    if not nums:
        return 0
    
    write_index = 1
    for read_index in range(1, len(nums)):
        if nums[read_index] != nums[read_index - 1]:
            nums[write_index] = nums[read_index]
            write_index += 1
    return write_index

Sliding Window Patterns

# Fixed window size
def max_sum_subarray(nums, k):
    if len(nums) < k:
        return 0
    
    window_sum = sum(nums[:k])
    max_sum = window_sum
    
    for i in range(k, len(nums)):
        window_sum += nums[i] - nums[i - k]
        max_sum = max(max_sum, window_sum)
    
    return max_sum
 
# Variable window size
def min_window_substring(s, t):
    if not s or not t:
        return ""
    
    dict_t = {}
    for char in t:
        dict_t[char] = dict_t.get(char, 0) + 1
    
    required = len(dict_t)
    formed = 0
    window_counts = {}
    
    l, r = 0, 0
    ans = float("inf"), None, None
    
    while r < len(s):
        char = s[r]
        window_counts[char] = window_counts.get(char, 0) + 1
        
        if char in dict_t and window_counts[char] == dict_t[char]:
            formed += 1
        
        while l <= r and formed == required:
            if r - l + 1 < ans[0]:
                ans = (r - l + 1, l, r)
            
            char = s[l]
            window_counts[char] -= 1
            if char in dict_t and window_counts[char] < dict_t[char]:
                formed -= 1
            l += 1
        
        r += 1
    
    return "" if ans[0] == float("inf") else s[ans[1]:ans[2] + 1]

Array Manipulation

# Rotate array right by k steps - O(n) time, O(1) space
def rotate_array(nums, k):
    k = k % len(nums)
    reverse(nums, 0, len(nums) - 1)
    reverse(nums, 0, k - 1)
    reverse(nums, k, len(nums) - 1)
 
def reverse(nums, start, end):
    while start < end:
        nums[start], nums[end] = nums[end], nums[start]
        start += 1
        end -= 1
 
# Maximum subarray sum - Kadane's algorithm
def max_subarray(nums):
    max_sum = current_sum = nums[0]
    for num in nums[1:]:
        current_sum = max(num, current_sum + num)
        max_sum = max(max_sum, current_sum)
    return max_sum
 
# Product of array except self - O(n) time, O(1) extra space
def product_except_self(nums):
    result = [1] * len(nums)
    
    # Left pass
    for i in range(1, len(nums)):
        result[i] = result[i - 1] * nums[i - 1]
    
    # Right pass
    right = 1
    for i in range(len(nums) - 1, -1, -1):
        result[i] *= right
        right *= nums[i]
    
    return result

Itertools & Functional Programming

Essential Itertools Functions

import itertools
 
# Combinations and permutations
list(itertools.combinations([1, 2, 3], 2))          # [(1, 2), (1, 3), (2, 3)]
list(itertools.permutations([1, 2, 3], 2))          # [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]
list(itertools.combinations_with_replacement([1, 2], 2))  # [(1, 1), (1, 2), (2, 2)]
 
# Cartesian product
list(itertools.product([1, 2], ['a', 'b']))         # [(1, 'a'), (1, 'b'), (2, 'a'), (2, 'b')]
 
# Chain iterables together
list(itertools.chain([1, 2], [3, 4], [5, 6]))      # [1, 2, 3, 4, 5, 6]
 
# Groupby - group consecutive elements by key
data = [1, 1, 2, 2, 2, 3, 1, 1]
for key, group in itertools.groupby(data):
    print(key, list(group))
# Output: 1 [1, 1], 2 [2, 2, 2], 3 [3], 1 [1, 1]
 
# Accumulate - cumulative results
list(itertools.accumulate([1, 2, 3, 4]))           # [1, 3, 6, 10]
list(itertools.accumulate([1, 2, 3, 4], max))      # [1, 2, 3, 4]
 
# Compress - filter based on selectors
list(itertools.compress('ABCDEF', [1, 0, 1, 0, 1, 1]))  # ['A', 'C', 'E', 'F']

Functional Programming with Built-ins

# Map, filter, reduce
numbers = [1, 2, 3, 4, 5]
 
# Map - apply function to all elements
squares = list(map(lambda x: x**2, numbers))        # [1, 4, 9, 16, 25]
squares = [x**2 for x in numbers]                   # List comprehension equivalent
 
# Filter - select elements meeting condition
evens = list(filter(lambda x: x % 2 == 0, numbers)) # [2, 4]
evens = [x for x in numbers if x % 2 == 0]          # List comprehension equivalent
 
# Reduce - cumulative operation
from functools import reduce
product = reduce(lambda x, y: x * y, numbers)       # 120
 
# Zip - parallel iteration
names = ['Alice', 'Bob', 'Charlie']
ages = [25, 30, 35]
for name, age in zip(names, ages):
    print(f"{name}: {age}")
 
# Enumerate - get index and value
for i, value in enumerate(['a', 'b', 'c']):
    print(f"Index {i}: {value}")
 
# Sorted with custom key
words = ['python', 'java', 'c++', 'go']
sorted_by_length = sorted(words, key=len)           # ['go', 'c++', 'java', 'python']
sorted_reverse = sorted(words, reverse=True)        # Reverse alphabetical

Memoization with Functools

from functools import lru_cache
 
# LRU Cache for dynamic programming - O(1) lookup after computation
@lru_cache(maxsize=None)  # Unlimited cache size
def fibonacci(n):
    if n < 2:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)
 
# Cache info
print(fibonacci.cache_info())  # Shows hits, misses, current size
 
# Clear cache
fibonacci.cache_clear()
 
# Manual memoization
def memoize(func):
    cache = {}
    def wrapper(*args):
        if args in cache:
            return cache[args]
        result = func(*args)
        cache[args] = result
        return result
    return wrapper
 
---
 
## Trees & Graphs
 
### Binary Tree Implementation
```python
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
# Tree traversals - all O(n) time, O(h) space where h is height
def inorder_traversal(root):
    """Left -> Root -> Right"""
    result = []
    def inorder(node):
        if node:
            inorder(node.left)
            result.append(node.val)
            inorder(node.right)
    inorder(root)
    return result
 
def preorder_traversal(root):
    """Root -> Left -> Right"""
    result = []
    def preorder(node):
        if node:
            result.append(node.val)
            preorder(node.left)
            preorder(node.right)
    preorder(root)
    return result
 
def postorder_traversal(root):
    """Left -> Right -> Root"""
    result = []
    def postorder(node):
        if node:
            postorder(node.left)
            postorder(node.right)
            result.append(node.val)
    postorder(root)
    return result
 
# Level-order traversal (BFS) - O(n) time, O(w) space where w is max width
def level_order_traversal(root):
    if not root:
        return []
    
    result = []
    queue = deque([root])
    
    while queue:
        level_size = len(queue)
        level = []
        
        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        result.append(level)
    
    return result

Binary Search Tree Operations

# BST insertion - O(h) time where h is height
def insert_bst(root, val):
    if not root:
        return TreeNode(val)
    
    if val < root.val:
        root.left = insert_bst(root.left, val)
    else:
        root.right = insert_bst(root.right, val)
    
    return root
 
# BST search - O(h) time
def search_bst(root, val):
    if not root or root.val == val:
        return root
    
    if val < root.val:
        return search_bst(root.left, val)
    else:
        return search_bst(root.right, val)
 
# Validate BST - O(n) time
def is_valid_bst(root, min_val=float('-inf'), max_val=float('inf')):
    if not root:
        return True
    
    if root.val <= min_val or root.val >= max_val:
        return False
    
    return (is_valid_bst(root.left, min_val, root.val) and 
            is_valid_bst(root.right, root.val, max_val))
 
# Lowest Common Ancestor in BST - O(h) time
def lca_bst(root, p, q):
    if not root:
        return None
    
    if p.val < root.val and q.val < root.val:
        return lca_bst(root.left, p, q)
    elif p.val > root.val and q.val > root.val:
        return lca_bst(root.right, p, q)
    else:
        return root

Graph Representations & Traversals

# Graph representation using adjacency list
from collections import defaultdict, deque
 
class Graph:
    def __init__(self):
        self.graph = defaultdict(list)
    
    def add_edge(self, u, v):
        self.graph[u].append(v)
    
    def add_undirected_edge(self, u, v):
        self.graph[u].append(v)
        self.graph[v].append(u)
 
# DFS - O(V + E) time, O(V) space
def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    
    visited.add(start)
    print(start, end=' ')
    
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)
 
# DFS iterative using stack
def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            print(node, end=' ')
            
            # Add neighbors to stack (reverse order for consistent traversal)
            for neighbor in reversed(graph[node]):
                if neighbor not in visited:
                    stack.append(neighbor)
 
# BFS - O(V + E) time, O(V) space
def bfs(graph, start):
    visited = set([start])
    queue = deque([start])
    
    while queue:
        node = queue.popleft()
        print(node, end=' ')
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
 
# Detect cycle in undirected graph using DFS
def has_cycle_undirected(graph, n):
    visited = [False] * n
    
    def dfs_cycle(node, parent):
        visited[node] = True
        
        for neighbor in graph[node]:
            if not visited[neighbor]:
                if dfs_cycle(neighbor, node):
                    return True
            elif parent != neighbor:
                return True
        
        return False
    
    for i in range(n):
        if not visited[i]:
            if dfs_cycle(i, -1):
                return True
    
    return False
 
# Topological sort using DFS - O(V + E) time
def topological_sort(graph, n):
    visited = [False] * n
    stack = []
    
    def dfs_topo(node):
        visited[node] = True
        
        for neighbor in graph[node]:
            if not visited[neighbor]:
                dfs_topo(neighbor)
        
        stack.append(node)
    
    for i in range(n):
        if not visited[i]:
            dfs_topo(i)
    
    return stack[::-1]  # Reverse to get correct order

Shortest Path Algorithms

import heapq
 
# Dijkstra's algorithm - O((V + E) log V) time
def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    pq = [(0, start)]  # (distance, node)
    
    while pq:
        current_dist, current = heapq.heappop(pq)
        
        if current_dist > distances[current]:
            continue
        
        for neighbor, weight in graph[current]:
            distance = current_dist + weight
            
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))
    
    return distances
 
# BFS for unweighted graph shortest path - O(V + E) time
def shortest_path_bfs(graph, start, end):
    if start == end:
        return 0
    
    visited = set([start])
    queue = deque([(start, 0)])  # (node, distance)
    
    while queue:
        node, dist = queue.popleft()
        
        for neighbor in graph[node]:
            if neighbor == end:
                return dist + 1
            
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, dist + 1))
    
    return -1  # Path not found

Dynamic Programming

Classic DP Patterns

1. Fibonacci & Linear DP

# Bottom-up approach - O(n) time, O(1) space
def fibonacci(n):
    if n <= 1:
        return n
    
    prev, curr = 0, 1
    for _ in range(2, n + 1):
        prev, curr = curr, prev + curr
    
    return curr
 
# Climbing stairs - O(n) time, O(1) space
def climb_stairs(n):
    if n <= 2:
        return n
    
    prev2, prev1 = 1, 2
    for _ in range(3, n + 1):
        current = prev1 + prev2
        prev2, prev1 = prev1, current
    
    return prev1

2. Longest Increasing Subsequence

# O(n²) DP solution
def length_of_lis(nums):
    if not nums:
        return 0
    
    dp = [1] * len(nums)
    
    for i in range(1, len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    
    return max(dp)
 
# O(n log n) solution using binary search
def length_of_lis_optimized(nums):
    import bisect
    
    tails = []
    
    for num in nums:
        pos = bisect.bisect_left(tails, num)
        if pos == len(tails):
            tails.append(num)
        else:
            tails[pos] = num
    
    return len(tails)

3. Knapsack Problems

# 0/1 Knapsack - O(n * W) time and space
def knapsack_01(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):
            if weights[i-1] <= w:
                dp[i][w] = max(
                    dp[i-1][w],  # Don't include item
                    dp[i-1][w - weights[i-1]] + values[i-1]  # Include item
                )
            else:
                dp[i][w] = dp[i-1][w]
    
    return dp[n][capacity]
 
# Space-optimized knapsack - O(W) space
def knapsack_optimized(weights, values, capacity):
    dp = [0] * (capacity + 1)
    
    for i in range(len(weights)):
        # Traverse backwards to avoid using updated values
        for w in range(capacity, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    
    return dp[capacity]
 
# Unbounded knapsack (unlimited items) - O(n * W) time
def knapsack_unbounded(weights, values, capacity):
    dp = [0] * (capacity + 1)
    
    for w in range(1, capacity + 1):
        for i in range(len(weights)):
            if weights[i] <= w:
                dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    
    return dp[capacity]

4. String DP Problems

# Longest Common Subsequence - O(m * n) time and space
def longest_common_subsequence(text1, text2):
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i-1] == text2[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]
 
# Edit Distance (Levenshtein) - O(m * n) time and space
def min_distance(word1, word2):
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # Initialize base cases
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i-1] == word2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = min(
                    dp[i-1][j] + 1,     # Delete
                    dp[i][j-1] + 1,     # Insert
                    dp[i-1][j-1] + 1    # Replace
                )
    
    return dp[m][n]
 
# Word Break - O(n²) time where n is string length
def word_break(s, word_dict):
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True
    word_set = set(word_dict)
    
    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and s[j:i] in word_set:
                dp[i] = True
                break
    
    return dp[n]

5. Matrix DP

# Unique Paths - O(m * n) time and space
def unique_paths(m, n):
    dp = [[1] * n for _ in range(m)]
    
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
    
    return dp[m-1][n-1]
 
# Space-optimized unique paths - O(n) space
def unique_paths_optimized(m, n):
    dp = [1] * n
    
    for _ in range(1, m):
        for j in range(1, n):
            dp[j] += dp[j-1]
    
    return dp[n-1]
 
# Maximum Path Sum in Triangle - O(n²) time, O(1) space
def minimum_total(triangle):
    # Bottom-up approach, modify triangle in-place
    for row in range(len(triangle) - 2, -1, -1):
        for col in range(len(triangle[row])):
            triangle[row][col] += min(
                triangle[row + 1][col],
                triangle[row + 1][col + 1]
            )
    
    return triangle[0][0]
 
### DP Problem Recognition Patterns
```python
# 1. Optimization problems (min/max)
# 2. Counting problems (number of ways)
# 3. Decision problems (possible/impossible)
# 4. String matching problems
# 5. Game theory problems
 
# Template for memoized recursion
def dp_memoized(problem_params):
    memo = {}
    
    def solve(state):
        if state in memo:
            return memo[state]
        
        if base_case(state):
            return base_result
        
        result = float('inf')  # or 0, depending on problem
        for next_state in get_next_states(state):
            result = optimize(result, solve(next_state))
        
        memo[state] = result
        return result
    
    return solve(initial_state)

Sorting & Searching

Built-in Sorting

# Python's Timsort - O(n log n) average/worst case, O(n) best case
arr = [3, 1, 4, 1, 5, 9, 2, 6]
arr.sort()  # In-place sorting
sorted_arr = sorted(arr)  # Returns new sorted list
 
# Custom sorting with key function
words = ['apple', 'pie', 'Washington', 'book']
words.sort(key=len)  # Sort by length
words.sort(key=str.lower)  # Case-insensitive sort
words.sort(reverse=True)  # Descending order
 
# Sort with multiple criteria
students = [('Alice', 85), ('Bob', 90), ('Charlie', 85)]
students.sort(key=lambda x: (-x[1], x[0]))  # Sort by grade desc, then name asc
 
# Sort 2D array/list
intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
intervals.sort(key=lambda x: x[0])  # Sort by start time

Binary Search Implementation

import bisect
 
# Standard binary search - O(log n) time
def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = left + (right - left) // 2  # Avoid overflow
        
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1
 
# Find insertion position (leftmost)
def search_insert(arr, target):
    left, right = 0, len(arr)
    
    while left < right:
        mid = left + (right - left) // 2
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid
    
    return left
 
# Find first and last occurrence
def search_range(nums, target):
    def find_bound(is_left):
        left, right = 0, len(nums)
        
        while left < right:
            mid = left + (right - left) // 2
            
            if nums[mid] == target:
                if is_left:
                    right = mid
                else:
                    left = mid + 1
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid
        
        return left
    
    left_bound = find_bound(True)
    if left_bound >= len(nums) or nums[left_bound] != target:
        return [-1, -1]
    
    right_bound = find_bound(False) - 1
    return [left_bound, right_bound]
 
# Using bisect module
def bisect_operations(arr, target):
    # Find insertion point for target (leftmost)
    left_pos = bisect.bisect_left(arr, target)
    
    # Find insertion point for target (rightmost)
    right_pos = bisect.bisect_right(arr, target)
    
    # Insert element maintaining sorted order
    bisect.insort(arr, target)
    
    return left_pos, right_pos

Heap Operations

import heapq
 
# Min heap operations - all O(log n) except heapify which is O(n)
heap = [3, 1, 4, 1, 5, 9, 2, 6]
heapq.heapify(heap)  # Convert list to heap in-place
 
heapq.heappush(heap, 0)  # Add element
min_element = heapq.heappop(heap)  # Remove and return smallest
 
# Peek at smallest element without removing
smallest = heap[0]
 
# Push and pop in one operation
heapq.heapreplace(heap, 7)  # More efficient than separate push/pop
 
# Get k largest/smallest elements
k_largest = heapq.nlargest(3, arr)
k_smallest = heapq.nsmallest(3, arr)
 
# Max heap using negative values
max_heap = [-x for x in arr]
heapq.heapify(max_heap)
 
# Custom comparison using tuples
# Heap sorts by first element, then second, etc.
task_heap = []
heapq.heappush(task_heap, (priority, task_id, task_data))
 
# Top K Frequent Elements
def top_k_frequent(nums, k):
    count = {}
    for num in nums:
        count[num] = count.get(num, 0) + 1
    
    # Use min heap to keep only k elements
    heap = []
    for num, freq in count.items():
        heapq.heappush(heap, (freq, num))
        if len(heap) > k:
            heapq.heappop(heap)
    
    return [num for freq, num in heap]
 
# Merge K Sorted Lists
def merge_k_sorted_lists(lists):
    heap = []
    
    # Initialize heap with first element from each list
    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(heap, (lst[0], i, 0))  # (value, list_index, element_index)
    
    result = []
    
    while heap:
        val, list_idx, elem_idx = heapq.heappop(heap)
        result.append(val)
        
        # Add next element from the same list
        if elem_idx + 1 < len(lists[list_idx]):
            next_val = lists[list_idx][elem_idx + 1]
            heapq.heappush(heap, (next_val, list_idx, elem_idx + 1))
    
    return result

Mathematical Algorithms

Number Theory

import math
 
# Greatest Common Divisor - O(log min(a, b))
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
 
# Using built-in (Python 3.5+)
gcd_builtin = math.gcd(a, b)
 
# Least Common Multiple
def lcm(a, b):
    return abs(a * b) // gcd(a, b)
 
# Extended Euclidean Algorithm
def extended_gcd(a, b):
    if a == 0:
        return b, 0, 1
    
    gcd, x1, y1 = extended_gcd(b % a, a)
    x = y1 - (b // a) * x1
    y = x1
    
    return gcd, x, y
 
# Fast Exponentiation - O(log n)
def power(base, exp, mod=None):
    result = 1
    base = base % mod if mod else base
    
    while exp > 0:
        if exp & 1:  # If exp is odd
            result = (result * base) % mod if mod else result * base
        
        exp >>= 1  # exp = exp // 2
        base = (base * base) % mod if mod else base * base
    
    return result
 
# Prime checking - O(√n)
def is_prime(n):
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    
    for i in range(3, int(math.sqrt(n)) + 1, 2):
        if n % i == 0:
            return False
    
    return True
 
# Sieve of Eratosthenes - O(n log log n)
def sieve_of_eratosthenes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    
    for i in range(2, int(math.sqrt(n)) + 1):
        if is_prime[i]:
            for j in range(i * i, n + 1, i):
                is_prime[j] = False
    
    return [i for i in range(n + 1) if is_prime[i]]

Bit Manipulation

# Basic bit operations
def bit_operations(n):
    # Check if i-th bit is set
    def is_set(num, i):
        return (num & (1 << i)) != 0
    
    # Set i-th bit
    def set_bit(num, i):
        return num | (1 << i)
    
    # Clear i-th bit
    def clear_bit(num, i):
        return num & ~(1 << i)
    
    # Toggle i-th bit
    def toggle_bit(num, i):
        return num ^ (1 << i)
    
    return is_set, set_bit, clear_bit, toggle_bit
 
# Count set bits (Brian Kernighan's algorithm)
def count_set_bits(n):
    count = 0
    while n:
        n &= n - 1  # Remove rightmost set bit
        count += 1
    return count
 
# Built-in bit count
count_builtin = bin(n).count('1')
 
# Check if power of 2
def is_power_of_two(n):
    return n > 0 and (n & (n - 1)) == 0
 
# Find single number (all others appear twice)
def single_number(nums):
    result = 0
    for num in nums:
        result ^= num  # XOR cancels out pairs
    return result
 
# Find two numbers that appear once (all others appear twice)
def single_numbers_two(nums):
    xor = 0
    for num in nums:
        xor ^= num
    
    # Find rightmost set bit
    rightmost_set_bit = xor & -xor
    
    num1 = num2 = 0
    for num in nums:
        if num & rightmost_set_bit:
            num1 ^= num
        else:
            num2 ^= num
    
    return [num1, num2]
 
# Generate all subsets using bit manipulation
def subsets_bit(nums):
    n = len(nums)
    result = []
    
    for i in range(1 << n):  # 2^n subsets
        subset = []
        for j in range(n):
            if i & (1 << j):  # If j-th bit is set
                subset.append(nums[j])
        result.append(subset)
    
    return result

Combinatorics

import math
 
# Factorial
def factorial(n):
    return math.factorial(n)  # Built-in
    # Or iterative: result = 1; for i in range(1, n+1): result *= i
 
# Combinations (nCr) - n choose r
def combinations(n, r):
    if r > n or r < 0:
        return 0
    return math.factorial(n) // (math.factorial(r) * math.factorial(n - r))
 
# Optimized combinations to avoid large factorials
def combinations_optimized(n, r):
    if r > n - r:  # Take advantage of symmetry
        r = n - r
    
    result = 1
    for i in range(r):
        result = result * (n - i) // (i + 1)
    
    return result
 
# Permutations (nPr)
def permutations(n, r):
    return math.factorial(n) // math.factorial(n - r)
 
# Pascal's Triangle for combinations
def pascal_triangle(num_rows):
    triangle = []
    
    for i in range(num_rows):
        row = [1] * (i + 1)
        for j in range(1, i):
            row[j] = triangle[i-1][j-1] + triangle[i-1][j]
        triangle.append(row)
    
    return triangle
 
# Catalan Numbers - O(n²) using DP
def catalan_numbers(n):
    if n <= 1:
        return 1
    
    catalan = [0] * (n + 1)
    catalan[0] = catalan[1] = 1
    
    for i in range(2, n + 1):
        for j in range(i):
            catalan[i] += catalan[j] * catalan[i - 1 - j]
    
    return catalan[n]

Advanced Patterns

Union-Find (Disjoint Set)

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.components = n
    
    def find(self, x):
        # Path compression
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        
        if root_x == root_y:
            return False
        
        # Union by rank
        if self.rank[root_x] < self.rank[root_y]:
            self.parent[root_x] = root_y
        elif self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x
        else:
            self.parent[root_y] = root_x
            self.rank[root_x] += 1
        
        self.components -= 1
        return True
    
    def connected(self, x, y):
        return self.find(x) == self.find(y)
    
    def get_components(self):
        return self.components
 
# Example: Number of Connected Components
def count_components(n, edges):
    uf = UnionFind(n)
    
    for u, v in edges:
        uf.union(u, v)
    
    return uf.get_components()

Trie (Prefix Tree)

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_word = False
 
class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word):
        """Insert word into trie - O(m) where m is word length"""
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end_word = True
    
    def search(self, word):
        """Search for complete word - O(m)"""
        node = self._search_prefix(word)
        return node is not None and node.is_end_word
    
    def starts_with(self, prefix):
        """Check if any word starts with prefix - O(m)"""
        return self._search_prefix(prefix) is not None
    
    def _search_prefix(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return None
            node = node.children[char]
        return node
    
    def get_all_words_with_prefix(self, prefix):
        """Get all words with given prefix"""
        node = self._search_prefix(prefix)
        if not node:
            return []
        
        words = []
        self._dfs_words(node, prefix, words)
        return words
    
    def _dfs_words(self, node, current_word, words):
        if node.is_end_word:
            words.append(current_word)
        
        for char, child_node in node.children.items():
            self._dfs_words(child_node, current_word + char, words)
 
# Word Search II using Trie
def find_words(board, words):
    trie = Trie()
    for word in words:
        trie.insert(word)
    
    result = []
    m, n = len(board), len(board[0])
    
    def dfs(i, j, node, path):
        if node.is_end_word:
            result.append(path)
            node.is_end_word = False  # Avoid duplicates
        
        if i < 0 or i >= m or j < 0 or j >= n:
            return
        
        char = board[i][j]
        if char not in node.children:
            return
        
        board[i][j] = '#'  # Mark as visited
        
        for di, dj in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
            dfs(i + di, j + dj, node.children[char], path + char)
        
        board[i][j] = char  # Restore
    
    for i in range(m):
        for j in range(n):
            dfs(i, j, trie.root, "")
    
    return result

Segment Tree

class SegmentTree:
    def __init__(self, arr):
        self.n = len(arr)
        self.tree = [0] * (4 * self.n)
        self.build(arr, 0, 0, self.n - 1)
    
    def build(self, arr, node, start, end):
        if start == end:
            self.tree[node] = arr[start]
        else:
            mid = (start + end) // 2
            self.build(arr, 2 * node + 1, start, mid)
            self.build(arr, 2 * node + 2, mid + 1, end)
            self.tree[node] = self.tree[2 * node + 1] + self.tree[2 * node + 2]
    
    def update(self, idx, val):
        self._update(0, 0, self.n - 1, idx, val)
    
    def _update(self, node, start, end, idx, val):
        if start == end:
            self.tree[node] = val
        else:
            mid = (start + end) // 2
            if idx <= mid:
                self._update(2 * node + 1, start, mid, idx, val)
            else:
                self._update(2 * node + 2, mid + 1, end, idx, val)
            self.tree[node] = self.tree[2 * node + 1] + self.tree[2 * node + 2]
    
    def query(self, l, r):
        return self._query(0, 0, self.n - 1, l, r)
    
    def _query(self, node, start, end, l, r):
        if r < start or end < l:
            return 0  # No overlap
        if l <= start and end <= r:
            return self.tree[node]  # Complete overlap
        
        # Partial overlap
        mid = (start + end) // 2
        left_sum = self._query(2 * node + 1, start, mid, l, r)
        right_sum = self._query(2 * node + 2, mid + 1, end, l, r)
        return left_sum + right_sum

Backtracking Template

def backtrack_template(candidates, target):
    result = []
    
    def backtrack(start, path, remaining):
        # Base case - solution found
        if is_solution(remaining):
            result.append(path[:])  # Make a copy
            return
        
        # Try each candidate
        for i in range(start, len(candidates)):
            candidate = candidates[i]
            
            # Skip invalid candidates
            if not is_valid(candidate, remaining):
                continue
            
            # Make choice
            path.append(candidate)
            
            # Recurse
            backtrack(i + 1, path, remaining - candidate)
            
            # Backtrack (undo choice)
            path.pop()
    
    backtrack(0, [], target)
    return result
 
# N-Queens problem
def solve_n_queens(n):
    result = []
    board = [['.' for _ in range(n)] for _ in range(n)]
    
    def is_safe(row, col):
        # Check column
        for i in range(row):
            if board[i][col] == 'Q':
                return False
        
        # Check diagonals
        for i, j in zip(range(row - 1, -1, -1), range(col - 1, -1, -1)):
            if board[i][j] == 'Q':
                return False
        
        for i, j in zip(range(row - 1, -1, -1), range(col + 1, n)):
            if board[i][j] == 'Q':
                return False
        
        return True
    
    def backtrack(row):
        if row == n:
            result.append([''.join(row) for row in board])
            return
        
        for col in range(n):
            if is_safe(row, col):
                board[row][col] = 'Q'
                backtrack(row + 1)
                board[row][col] = '.'
    
    backtrack(0)
    return result

Interview Tips

Python-Specific Optimizations

# Use built-in functions when possible
sum(nums)                    # Instead of manual loop
max(nums)                    # Instead of manual comparison
any(condition for x in nums) # Instead of manual boolean logic
all(condition for x in nums) # Check if all satisfy condition
 
# List comprehensions are faster than loops
squares = [x**2 for x in range(10)]  # Faster than append in loop
 
# Use enumerate instead of range(len())
for i, val in enumerate(nums):  # Instead of for i in range(len(nums))
 
# Use zip for parallel iteration
for x, y in zip(list1, list2):  # Instead of index-based access
 
# Set operations for membership testing
if item in set_collection:  # O(1) instead of O(n) for lists
 
# Use collections.Counter for frequency counting
from collections import Counter
freq = Counter(nums)  # Instead of manual dictionary counting

Common Pitfalls to Avoid

Off-by-one errors: Carefully check loop bounds and array indices
Integer overflow: Consider using appropriate data types
Modifying list while iterating: Use reverse iteration or create new list
Shallow vs deep copy: Use copy.deepcopy() for nested structures
Mutable default arguments: Use None and initialize inside function

Memory-Efficient Techniques

# Use generators for large datasets
def fibonacci_generator():
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a + b
 
# Use itertools for memory-efficient iteration
import itertools
for combo in itertools.combinations(large_list, 2):
    process(combo)  # Process one at a time instead of generating all
 
# Use slots for memory-efficient classes
class Point:
    __slots__ = ['x', 'y']
    def __init__(self, x, y):
        self.x = x
        self.y = y

Avi's Notes

Explorer

Python Coding Interview Cheat-sheet

Table of Contents

Basic Syntax & Patterns

Essential Imports

Input/Output Patterns

Python-Specific Syntax

Built-in Data Structures

Lists - Dynamic Arrays

Dictionaries - Hash Maps

Sets - Hash Sets

Tuples - Immutable Sequences

Collections Module

Deque - Double-ended Queue

Counter - Counting Hash Map

DefaultDict - Dictionary with Default Values

String Manipulation

Basic String Operations

String Patterns for Interviews

Regular Expressions

List & Array Operations

Two Pointer Technique

Sliding Window Patterns

Array Manipulation

Itertools & Functional Programming

Essential Itertools Functions

Functional Programming with Built-ins

Memoization with Functools

Binary Search Tree Operations

Graph Representations & Traversals

Shortest Path Algorithms

Dynamic Programming

Classic DP Patterns

1. Fibonacci & Linear DP

2. Longest Increasing Subsequence

3. Knapsack Problems

4. String DP Problems

5. Matrix DP

Sorting & Searching

Built-in Sorting

Binary Search Implementation

Heap Operations

Mathematical Algorithms

Number Theory

Bit Manipulation

Combinatorics

Advanced Patterns

Union-Find (Disjoint Set)

Trie (Prefix Tree)

Segment Tree

Backtracking Template

Interview Tips

Python-Specific Optimizations

Common Pitfalls to Avoid

Memory-Efficient Techniques

Graph View

Table of Contents