Ultimate Coding Problems Cheatsheet

      Ankush More

      Complete reference for solving any coding problem – from understanding to optimization

      📋 Table of Contents

      1. Problem-Solving Framework
      2. Pattern Recognition Guide
      3. Data Structure Cheatsheet
      4. Algorithm Cheatsheet
      5. Time & Space Complexity
      6. Python Built-ins Quick Reference
      7. Common Patterns & Templates
      8. Edge Cases Checklist
      9. Optimization Strategies
      10. Interview Workflow

      Problem-Solving Framework

      🎯 The 7-Step Method

      1. UNDERSTAND → Read carefully, identify constraints
2. EXAMPLES → Create test cases (normal, edge, large)
3. PATTERN → Recognize problem type
4. APPROACH → Choose data structure + algorithm
5. PSEUDOCODE → Write high-level solution
6. CODE → Implement with clean code
7. TEST → Verify with examples, optimize
      Bash

      Step 1: UNDERSTAND (5 minutes)

      """
Questions to Ask:
□ What is the input type? (array, string, tree, graph?)
□ What is the output type? (boolean, integer, list?)
□ What are the constraints? (size limits, time limits)
□ Are there duplicates? Negatives? Empty inputs?
□ Is the input sorted? Mutable?
□ What should I return for edge cases?

Example Problem: "Find two numbers that sum to target"

✅ Input: List of integers, target integer
✅ Output: Indices of two numbers
✅ Constraints: Each input has exactly one solution
✅ Follow-up: Can we use same element twice? No
✅ Edge cases: Empty array, single element, no solution
"""
      Python

      Step 2: EXAMPLES (3 minutes)

      """
Create 4 types of test cases:

1. NORMAL CASE - Typical input
   Input: [2, 7, 11, 15], target = 9
   Output: [0, 1]

2. EDGE CASE - Boundary conditions
   Input: [3, 3], target = 6
   Output: [0, 1]

3. LARGE CASE - Performance test
   Input: [1]*10000 + [5, 5], target = 10
   Output: [10000, 10001]

4. INVALID CASE - Error handling
   Input: [], target = 5
   Output: None or raise exception
"""
      Python

      Step 3: PATTERN RECOGNITION (2 minutes)

      """
Identify the pattern from keywords:

KEYWORDS → PATTERN
├─ "subarray/substring" → Sliding Window
├─ "sorted array" → Two Pointers / Binary Search
├─ "find pair/triplet" → Two Pointers / Hash Map
├─ "tree/graph traversal" → BFS / DFS
├─ "optimize/maximize" → Dynamic Programming / Greedy
├─ "all combinations" → Backtracking
├─ "top K elements" → Heap
├─ "frequency count" → Hash Map / Counter
├─ "in O(1) time" → Hash Map / Preprocessing
└─ "recursive structure" → Recursion / DP
"""
      Python

      Pattern Recognition Guide

      🔍 Quick Pattern Identifier

      INPUT TYPE + GOAL = PATTERN

┌─────────────────────────────────────────────────────────┐
│ ARRAY/LIST PROBLEMS                                      │
├─────────────────────────────────────────────────────────┤
│ Sorted + Find pair → Two Pointers                       │
│ Sorted + Search → Binary Search                         │
│ Unsorted + Find pair → Hash Map                         │
│ Subarray sum/max → Sliding Window / Prefix Sum          │
│ Kadane (max subarray) → DP                              │
│ Stock prices → DP / Greedy                              │
│ Merge intervals → Sort + Greedy                         │
│ Two arrays + merge → Two Pointers                       │
└─────────────────────────────────────────────────────────┘

┌─────────────────────────────────────────────────────────┐
│ STRING PROBLEMS                                          │
├─────────────────────────────────────────────────────────┤
│ Palindrome → Two Pointers                               │
│ Anagram → Hash Map / Sorting                            │
│ Substring without repeat → Sliding Window + Hash Map    │
│ Pattern matching → KMP / Rabin-Karp                     │
│ Parentheses validation → Stack                          │
│ Longest common substring → DP                           │
└─────────────────────────────────────────────────────────┘

┌─────────────────────────────────────────────────────────┐
│ TREE PROBLEMS                                            │
├─────────────────────────────────────────────────────────┤
│ Traversal → DFS (recursive) / BFS (iterative)           │
│ Level order → BFS with queue                            │
│ Path sum → DFS with backtracking                        │
│ Lowest common ancestor → Recursive DFS                  │
│ Serialize/deserialize → BFS or DFS                      │
│ Validate BST → DFS with min/max bounds                  │
└─────────────────────────────────────────────────────────┘

┌─────────────────────────────────────────────────────────┐
│ GRAPH PROBLEMS                                           │
├─────────────────────────────────────────────────────────┤
│ Shortest path (unweighted) → BFS                        │
│ Shortest path (weighted) → Dijkstra / Bellman-Ford      │
│ All paths → DFS with backtracking                       │
│ Cycle detection → DFS with visited set                  │
│ Connected components → DFS / Union-Find                 │
│ Topological sort → DFS / Kahn's algorithm               │
└─────────────────────────────────────────────────────────┘

┌─────────────────────────────────────────────────────────┐
│ LINKED LIST PROBLEMS                                     │
├─────────────────────────────────────────────────────────┤
│ Reverse → Iterative with 3 pointers                     │
│ Detect cycle → Floyd's (fast/slow pointers)             │
│ Find middle → Fast/slow pointers                        │
│ Merge sorted lists → Two pointers                       │
│ Remove nth from end → Two pointers with gap             │
└─────────────────────────────────────────────────────────┘

┌─────────────────────────────────────────────────────────┐
│ MATRIX PROBLEMS                                          │
├─────────────────────────────────────────────────────────┤
│ Island problems → DFS / BFS                             │
│ Shortest path → BFS                                     │
│ Dynamic programming → 2D DP table                       │
│ Spiral traversal → Boundary tracking                    │
│ Rotate → In-place manipulation                          │
└─────────────────────────────────────────────────────────┘

┌─────────────────────────────────────────────────────────┐
│ OPTIMIZATION PROBLEMS                                    │
├─────────────────────────────────────────────────────────┤
│ Overlapping subproblems → Dynamic Programming           │
│ Greedy choice property → Greedy Algorithm               │
│ Find all solutions → Backtracking                       │
│ Divide into subproblems → Divide & Conquer              │
└─────────────────────────────────────────────────────────┘
      Bash

      Data Structure Cheatsheet

      📊 Quick Reference Table

      Data StructureAccessSearchInsertDeleteSpaceUse Case
      ArrayO(1)O(n)O(n)O(n)O(n)Index access, iteration
      Hash MapO(1)O(1)O(1)O(1)O(n)Fast lookup, counting
      Set–O(1)O(1)O(1)O(n)Uniqueness, membership
      StackO(n)O(n)O(1)O(1)O(n)LIFO, parentheses, DFS
      QueueO(n)O(n)O(1)O(1)O(n)FIFO, BFS, level order
      Linked ListO(n)O(n)O(1)*O(1)*O(n)Insert/delete frequent
      Binary TreeO(n)O(n)O(n)O(n)O(n)Hierarchical data
      BSTO(log n)O(log n)O(log n)O(log n)O(n)Ordered data, range
      HeapO(1)**O(n)O(log n)O(log n)O(n)Priority queue, top K
      TrieO(L)O(L)O(L)O(L)O(N*L)Prefix matching, autocomplete

      *At known position | **Min/max only | L = string length, N = number of strings

      Python Implementation Quick Reference

      # ARRAY/LIST
arr = []                    # Create
arr = [1, 2, 3]            # Initialize
arr.append(4)              # Add to end - O(1)
arr.insert(0, 0)           # Add to start - O(n)
arr.pop()                  # Remove from end - O(1)
arr.pop(0)                 # Remove from start - O(n)
arr[0]                     # Access - O(1)
arr.index(2)               # Search - O(n)
arr.reverse()              # Reverse in-place
arr.sort()                 # Sort in-place

# HASH MAP (Dictionary)
hash_map = {}              # Create
hash_map = {'a': 1}        # Initialize
hash_map['b'] = 2          # Insert - O(1)
val = hash_map.get('a', 0) # Get with default - O(1)
del hash_map['a']          # Delete - O(1)
'a' in hash_map            # Check existence - O(1)
hash_map.keys()            # All keys
hash_map.values()          # All values
hash_map.items()           # All pairs

# SET
s = set()                  # Create
s = {1, 2, 3}             # Initialize
s.add(4)                   # Add - O(1)
s.remove(3)                # Remove - O(1)
s.discard(5)               # Remove (no error if missing)
1 in s                     # Check - O(1)
s1 & s2                    # Intersection
s1 | s2                    # Union
s1 - s2                    # Difference

# STACK (using list)
stack = []                 # Create
stack.append(1)            # Push - O(1)
top = stack.pop()          # Pop - O(1)
top = stack[-1]            # Peek - O(1)
is_empty = not stack       # Check empty

# QUEUE (using collections.deque)
from collections import deque
queue = deque()            # Create
queue.append(1)            # Enqueue - O(1)
val = queue.popleft()      # Dequeue - O(1)
front = queue[0]           # Peek - O(1)

# HEAP (using heapq - min heap)
import heapq
heap = []                  # Create
heapq.heappush(heap, 5)    # Push - O(log n)
min_val = heapq.heappop(heap)  # Pop min - O(log n)
min_val = heap[0]          # Peek min - O(1)
heapq.heapify(arr)         # Convert list to heap - O(n)

# For max heap, negate values
heapq.heappush(heap, -val)
max_val = -heapq.heappop(heap)

# COUNTER (frequency counting)
from collections import Counter
c = Counter([1, 2, 2, 3, 3, 3])  # Counter({3: 3, 2: 2, 1: 1})
c.most_common(2)                  # [(3, 3), (2, 2)]
c[1]                              # Get count

# DEFAULTDICT (auto-initialization)
from collections import defaultdict
dd = defaultdict(list)     # Default value: []
dd = defaultdict(int)      # Default value: 0
dd['key'].append(1)        # No KeyError

# ORDERED DICT (maintains insertion order - Python 3.7+ dict does this)
from collections import OrderedDict
od = OrderedDict()
od['a'] = 1
od.move_to_end('a')        # Move to end
      Python

      Algorithm Cheatsheet

      🔧 Essential Algorithms & Templates

      1. TWO POINTERS

      # Pattern: Sorted array, find pair
def two_pointers(arr, target):
    left, right = 0, len(arr) - 1

    while left < right:
        current = arr[left] + arr[right]
        if current == target:
            return [left, right]
        elif current < target:
            left += 1
        else:
            right -= 1
    return None

# Variations:
# - Same direction: for removing duplicates
# - Opposite direction: for palindrome check
# - Fast/slow: for linked list cycle
      Python

      2. SLIDING WINDOW

      # Pattern: Subarray/substring problems

# Fixed size window
def fixed_window(arr, k):
    window_sum = sum(arr[:k])
    max_sum = window_sum

    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i-k]
        max_sum = max(max_sum, window_sum)

    return max_sum

# Variable size window
def variable_window(s):
    left = 0
    result = 0
    window = set()

    for right in range(len(s)):
        while s[right] in window:
            window.remove(s[left])
            left += 1
        window.add(s[right])
        result = max(result, right - left + 1)

    return result
      Python
      # Pattern: Sorted array, search in O(log n)

# Basic binary search
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 first/last occurrence
def find_first(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

# Search in rotated array
def search_rotated(arr, target):
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = (left + right) // 2

        if arr[mid] == target:
            return mid

        # Left half sorted
        if arr[left] <= arr[mid]:
            if arr[left] <= target < arr[mid]:
                right = mid - 1
            else:
                left = mid + 1
        # Right half sorted
        else:
            if arr[mid] < target <= arr[right]:
                left = mid + 1
            else:
                right = mid - 1

    return -1
      Python
      # Recursive DFS
def dfs_recursive(graph, node, visited):
    if node in visited:
        return

    visited.add(node)
    # Process node

    for neighbor in graph[node]:
        dfs_recursive(graph, neighbor, visited)

# Iterative DFS (using stack)
def dfs_iterative(graph, start):
    visited = set()
    stack = [start]

    while stack:
        node = stack.pop()
        if node in visited:
            continue

        visited.add(node)
        # Process node

        for neighbor in graph[node]:
            if neighbor not in visited:
                stack.append(neighbor)

# Tree DFS (inorder, preorder, postorder)
def inorder(root):
    if not root:
        return []
    return inorder(root.left) + [root.val] + inorder(root.right)

def preorder(root):
    if not root:
        return []
    return [root.val] + preorder(root.left) + preorder(root.right)

def postorder(root):
    if not root:
        return []
    return postorder(root.left) + postorder(root.right) + [root.val]
      Python
      from collections import deque

# Graph BFS
def bfs(graph, start):
    visited = set([start])
    queue = deque([start])

    while queue:
        node = queue.popleft()
        # Process node

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

# Tree level-order traversal
def level_order(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

# Shortest path in unweighted graph
def shortest_path(graph, start, end):
    queue = deque([(start, 0)])  # (node, distance)
    visited = {start}

    while queue:
        node, dist = queue.popleft()

        if node == end:
            return dist

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, dist + 1))

    return -1
      Python

      6. DYNAMIC PROGRAMMING

      # Bottom-up (tabulation)
def dp_bottom_up(n):
    if n <= 1:
        return n

    dp = [0] * (n + 1)
    dp[1] = 1

    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]

    return dp[n]

# Top-down (memoization)
def dp_top_down(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n

    memo[n] = dp_top_down(n-1, memo) + dp_top_down(n-2, memo)
    return memo[n]

# With @lru_cache
from functools import lru_cache

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

# 2D DP template
def dp_2d(m, n):
    dp = [[0] * n for _ in range(m)]

    # Initialize base cases
    for i in range(m):
        dp[i][0] = 1
    for j in range(n):
        dp[0][j] = 1

    # Fill table
    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]
      Python

      7. BACKTRACKING

      # Template
def backtrack(result, path, choices):
    if is_solution(path):
        result.append(path[:])  # Important: copy path
        return

    for choice in choices:
        # Choose
        path.append(choice)

        # Explore
        backtrack(result, path, get_next_choices(choices, choice))

        # Un-choose (backtrack)
        path.pop()

# Permutations
def permute(nums):
    result = []

    def backtrack(path, remaining):
        if not remaining:
            result.append(path[:])
            return

        for i in range(len(remaining)):
            backtrack(path + [remaining[i]], 
                     remaining[:i] + remaining[i+1:])

    backtrack([], nums)
    return result

# Combinations
def combine(n, k):
    result = []

    def backtrack(start, path):
        if len(path) == k:
            result.append(path[:])
            return

        for i in range(start, n + 1):
            path.append(i)
            backtrack(i + 1, path)
            path.pop()

    backtrack(1, [])
    return result

# Subsets
def subsets(nums):
    result = []

    def backtrack(start, path):
        result.append(path[:])

        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()

    backtrack(0, [])
    return result
      Python

      8. SORTING ALGORITHMS

      # Quick Sort - O(n log n) average, O(n²) worst
def quick_sort(arr):
    if len(arr) <= 1:
        return arr

    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]

    return quick_sort(left) + middle + quick_sort(right)

# Merge Sort - O(n log n) always
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(left, right):
    result = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    result.extend(left[i:])
    result.extend(right[j:])
    return result

# Counting Sort - O(n + k) where k is range
def counting_sort(arr):
    if not arr:
        return arr

    min_val, max_val = min(arr), max(arr)
    count = [0] * (max_val - min_val + 1)

    for num in arr:
        count[num - min_val] += 1

    result = []
    for i, freq in enumerate(count):
        result.extend([i + min_val] * freq)

    return result
      Python

      Time & Space Complexity

      📈 Big O Cheatsheet

      BEST TO WORST:
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)

┌─────────────┬──────────────────┬─────────────────────────┐
│ Complexity  │ Name             │ Example                 │
├─────────────┼──────────────────┼─────────────────────────┤
│ O(1)        │ Constant         │ Array access, hash get  │
│ O(log n)    │ Logarithmic      │ Binary search           │
│ O(n)        │ Linear           │ Linear search, traverse │
│ O(n log n)  │ Linearithmic     │ Merge sort, quick sort  │
│ O(n²)       │ Quadratic        │ Nested loops, bubble    │
│ O(n³)       │ Cubic            │ Triple nested loops     │
│ O(2ⁿ)       │ Exponential      │ Fibonacci (naive)       │
│ O(n!)       │ Factorial        │ Permutations            │
└─────────────┴──────────────────┴─────────────────────────┘
      Bash

      Common Operations Complexity

      # ARRAY/LIST
arr[i]                    # O(1) - access
arr.append(x)             # O(1) - append
arr.insert(0, x)          # O(n) - insert at start
arr.pop()                 # O(1) - remove from end
arr.pop(0)                # O(n) - remove from start
arr.remove(x)             # O(n) - remove by value
x in arr                  # O(n) - search
arr.sort()                # O(n log n) - sort
min(arr), max(arr)        # O(n) - min/max
arr.reverse()             # O(n) - reverse

# DICTIONARY
d[key]                    # O(1) - access
d[key] = val              # O(1) - insert
del d[key]                # O(1) - delete
key in d                  # O(1) - membership
d.keys(), d.values()      # O(n) - iterate

# SET
s.add(x)                  # O(1) - add
s.remove(x)               # O(1) - remove
x in s                    # O(1) - membership
s1 & s2                   # O(min(len(s1), len(s2))) - intersection
s1 | s2                   # O(len(s1) + len(s2)) - union

# STRING (immutable)
s[i]                      # O(1) - access
s + t                     # O(n + m) - concatenation
s * k                     # O(n * k) - repeat
s.replace(old, new)       # O(n) - replace
s.split()                 # O(n) - split
s in t                    # O(n * m) - substring search

# HEAP
heapq.heappush(h, x)      # O(log n) - insert
heapq.heappop(h)          # O(log n) - remove min
heapq.heapify(arr)        # O(n) - build heap
h[0]                      # O(1) - peek min

# SORTING
sorted(arr)               # O(n log n) - Timsort
arr.sort()                # O(n log n) - in-place

# GRAPH/TREE
BFS/DFS                   # O(V + E) - vertices + edges
      Python

      Space Complexity Patterns

      # O(1) - Constant space
def swap(a, b):
    return b, a

# O(n) - Linear space
def copy_array(arr):
    return arr[:]

# O(log n) - Logarithmic space (recursion depth)
def binary_search_recursive(arr, target, left, right):
    if left > right:
        return -1
    mid = (left + right) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, right)
    else:
        return binary_search_recursive(arr, target, left, mid - 1)

# O(n) - Recursion stack for tree
def tree_height(root):
    if not root:
        return 0
    return 1 + max(tree_height(root.left), tree_height(root.right))

# O(n²) - 2D matrix
def create_matrix(n):
    return [[0] * n for _ in range(n)]
      Python

      Python Built-ins Quick Reference

      🐍 Most Useful Built-ins for Coding Problems

      # MATH
abs(-5)                   # 5
min(1, 2, 3)             # 1
max(1, 2, 3)             # 3
sum([1, 2, 3])           # 6
pow(2, 3)                # 8
divmod(10, 3)            # (3, 1) - quotient and remainder

import math
math.ceil(4.2)           # 5
math.floor(4.8)          # 4
math.sqrt(16)            # 4.0
math.gcd(48, 18)         # 6
math.factorial(5)        # 120
math.inf                 # Infinity
math.isclose(a, b)       # Float comparison

# STRING
s.upper(), s.lower()     # Case conversion
s.strip()                # Remove whitespace
s.split(',')             # Split by delimiter
','.join(['a', 'b'])     # 'a,b'
s.startswith('pre')      # True/False
s.endswith('suf')        # True/False
s.isalnum()              # Alphanumeric check
s.isdigit()              # Digit check
s.isalpha()              # Alphabetic check
s.count('a')             # Count occurrences
s.replace('old', 'new')  # Replace substring
s.find('sub')            # Find index (-1 if not found)

# LIST
arr.append(x)            # Add to end
arr.extend([1, 2])       # Add multiple
arr.insert(i, x)         # Insert at index
arr.pop()                # Remove from end
arr.pop(i)               # Remove at index
arr.remove(x)            # Remove first occurrence
arr.reverse()            # Reverse in-place
arr.sort()               # Sort in-place
arr.count(x)             # Count occurrences
arr.index(x)             # Find index

sorted(arr)              # Return sorted copy
reversed(arr)            # Return reversed iterator
list(range(5))           # [0, 1, 2, 3, 4]
list(range(1, 5))        # [1, 2, 3, 4]
list(range(0, 10, 2))    # [0, 2, 4, 6, 8]

# ITERATION
enumerate(['a', 'b'])    # [(0, 'a'), (1, 'b')]
zip([1, 2], ['a', 'b'])  # [(1, 'a'), (2, 'b')]
map(str, [1, 2, 3])      # ['1', '2', '3']
filter(lambda x: x > 0, [-1, 0, 1])  # [1]

all([True, True])        # True if all True
any([False, True])       # True if any True

# TYPE CONVERSION
int('123')               # 123
str(123)                 # '123'
float('3.14')            # 3.14
list('abc')              # ['a', 'b', 'c']
tuple([1, 2])            # (1, 2)
set([1, 2, 2])           # {1, 2}
dict([('a', 1)])         # {'a': 1}

# COMPREHENSIONS
[x**2 for x in range(5)]                    # List comp
{x: x**2 for x in range(5)}                 # Dict comp
{x for x in [1, 2, 2, 3]}                   # Set comp
(x**2 for x in range(5))                    # Generator

[x for x in range(10) if x % 2 == 0]        # With filter
[x if x > 0 else 0 for x in range(-2, 3)]   # With condition

# ITERTOOLS (import itertools)
from itertools import *

list(islice([1,2,3,4,5], 2, 4))            # [3, 4]
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([1,2], ['a','b']))             # [(1,'a'), (1,'b'), ...]
list(chain([1,2], [3,4]))                   # [1, 2, 3, 4]
list(accumulate([1,2,3,4]))                 # [1, 3, 6, 10]
list(zip_longest([1,2], [3,4,5], fillvalue=0))  # [(1,3), (2,4), (0,5)]

# COLLECTIONS
from collections import *

Counter([1,2,2,3,3,3])                      # Counter({3: 3, 2: 2, 1: 1})
defaultdict(list)                           # Dict with default values
deque([1,2,3])                             # Double-ended queue
OrderedDict([('a', 1)])                     # Ordered dictionary

# FUNCTOOLS
from functools import *

lru_cache(maxsize=128)                      # Memoization decorator
reduce(lambda x,y: x+y, [1,2,3,4])         # 10

# BISECT (for sorted lists)
from bisect import *

bisect_left([1,3,5,7], 5)                  # 2 (insert position)
bisect_right([1,3,5,7], 5)                 # 3
insort(sorted_list, 4)                      # Insert maintaining order

# HEAPQ (min heap)
from heapq import *

heappush(heap, 5)                          # Add element
heappop(heap)                              # Remove min
heapify(list)                              # Convert to heap
nlargest(3, [1,5,2,8,3])                  # [8, 5, 3]
nsmallest(3, [1,5,2,8,3])                 # [1, 2, 3]
      Python

      Common Patterns & Templates

      🎨 Copy-Paste Ready Templates

      Pattern 1: Hash Map for Two Sum

      def two_sum(nums, target):
    """Find indices of two numbers that sum to target"""
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []
      Python

      Pattern 2: Fast & Slow Pointers (Cycle Detection)

      def has_cycle(head):
    """Detect cycle in linked list"""
    if not head:
        return False

    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False
      Python

      Pattern 3: Prefix Sum

      def range_sum_query(nums):
    """Precompute prefix sums for O(1) range queries"""
    prefix = [0]
    for num in nums:
        prefix.append(prefix[-1] + num)

    def query(left, right):
        return prefix[right + 1] - prefix[left]

    return query
      Python

      Pattern 4: Monotonic Stack

      def next_greater_element(nums):
    """Find next greater element for each element"""
    result = [-1] * len(nums)
    stack = []  # Store indices

    for i, num in enumerate(nums):
        while stack and nums[stack[-1]] < num:
            idx = stack.pop()
            result[idx] = num
        stack.append(i)

    return result
      Python

      Pattern 5: Trie (Prefix Tree)

      class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True

    def search(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end

    def startsWith(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True
      Python

      Pattern 6: Union-Find (Disjoint Set)

      class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # Path compression
        return self.parent[x]

    def union(self, x, y):
        px, py = self.find(x), self.find(y)

        if px == py:
            return False

        # Union by rank
        if self.rank[px] < self.rank[py]:
            px, py = py, px

        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1

        return True

    def connected(self, x, y):
        return self.find(x) == self.find(y)
      Python

      Pattern 7: Kadane’s Algorithm (Max Subarray)

      def max_subarray(nums):
    """Find maximum sum of contiguous subarray"""
    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
      Python

      Pattern 8: Topological Sort

      def topological_sort(n, prerequisites):
    """Kahn's algorithm for topological sorting"""
    from collections import deque

    # Build graph and in-degree
    graph = {i: [] for i in range(n)}
    in_degree = [0] * n

    for course, prereq in prerequisites:
        graph[prereq].append(course)
        in_degree[course] += 1

    # Start with courses having no prerequisites
    queue = deque([i for i in range(n) if in_degree[i] == 0])
    result = []

    while queue:
        course = queue.popleft()
        result.append(course)

        for next_course in graph[course]:
            in_degree[next_course] -= 1
            if in_degree[next_course] == 0:
                queue.append(next_course)

    return result if len(result) == n else []
      Python

      Edge Cases Checklist

      ✅ Always Test These

      """
INPUT EDGE CASES:
□ Empty input: [], "", None, {}
□ Single element: [1], "a"
□ Two elements: [1, 2]
□ All same elements: [5, 5, 5, 5]
□ Sorted: [1, 2, 3, 4, 5]
□ Reverse sorted: [5, 4, 3, 2, 1]
□ Duplicates: [1, 2, 2, 3, 3, 3]
□ Negative numbers: [-5, -1, 0, 3, 7]
□ Zero: [0], 0, [0, 0, 0]
□ Large numbers: 10**9, sys.maxsize
□ Float precision: 0.1 + 0.2 != 0.3

ARRAY/LIST:
□ Empty array: []
□ Single element: [1]
□ All negative: [-1, -2, -3]
□ Mixed positive/negative: [-1, 0, 1]
□ Out of bounds access
□ Modification during iteration

STRING:
□ Empty string: ""
□ Single character: "a"
□ All same character: "aaaa"
□ Special characters: "!@#$%"
□ Spaces: " ", "a b c"
□ Case sensitivity: "ABC" vs "abc"
□ Unicode characters

TREE/GRAPH:
□ Null/None root
□ Single node
□ Skewed tree (all left or all right)
□ Complete binary tree
□ Disconnected graph
□ Self-loop
□ Duplicate edges
□ Cyclic graph

LINKED LIST:
□ Null head
□ Single node
□ Two nodes
□ Cycle
□ Palindrome

NUMERIC:
□ Integer overflow
□ Division by zero
□ Negative numbers
□ Float precision
□ Max/min int values

MATRIX:
□ Empty matrix: []
□ Single row: [[1, 2, 3]]
□ Single column: [[1], [2], [3]]
□ Square matrix: 3x3, 4x4
□ Non-square: 2x3, 3x5
"""
      Python

      Optimization Strategies

      🚀 From Brute Force to Optimal

      Strategy 1: Hash Map for O(1) Lookup

      # ❌ O(n²) - Nested loops
def two_sum_brute(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]

# ✅ O(n) - Hash map
def two_sum_optimal(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        if target - num in seen:
            return [seen[target - num], i]
        seen[num] = i
      Python

      Strategy 2: Two Pointers for Sorted Data

      # ❌ O(n²) - Brute force
def three_sum_brute(nums):
    result = []
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            for k in range(j + 1, len(nums)):
                if nums[i] + nums[j] + nums[k] == 0:
                    result.append([nums[i], nums[j], nums[k]])
    return result

# ✅ O(n²) - Sort + two pointers
def three_sum_optimal(nums):
    nums.sort()
    result = []

    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i-1]:
            continue

        left, right = i + 1, len(nums) - 1
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            if total == 0:
                result.append([nums[i], nums[left], nums[right]])
                left += 1
                right -= 1
            elif total < 0:
                left += 1
            else:
                right -= 1

    return result
      Python

      Strategy 3: Prefix/Suffix Arrays

      # ❌ O(n²) - Recalculate for each query
def range_sum_brute(nums, queries):
    result = []
    for left, right in queries:
        result.append(sum(nums[left:right+1]))
    return result

# ✅ O(n + q) - Precompute prefix sum
def range_sum_optimal(nums, queries):
    prefix = [0]
    for num in nums:
        prefix.append(prefix[-1] + num)

    result = []
    for left, right in queries:
        result.append(prefix[right+1] - prefix[left])
    return result
      Python

      Strategy 4: Memoization for Recursion

      # ❌ O(2ⁿ) - Naive recursion
def fib_slow(n):
    if n <= 1:
        return n
    return fib_slow(n-1) + fib_slow(n-2)

# ✅ O(n) - Memoization
from functools import lru_cache

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

      Strategy 5: Binary Search for Sorted Data

      # ❌ O(n) - Linear search
def search_linear(arr, target):
    for i, num in enumerate(arr):
        if num == target:
            return i
    return -1

# ✅ O(log n) - Binary search (if sorted)
def search_binary(arr, target):
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1
      Python

      Strategy 6: Greedy over DP (when applicable)

      # Jump Game: Can reach last index?

# DP approach - O(n²)
def can_jump_dp(nums):
    n = len(nums)
    dp = [False] * n
    dp[0] = True

    for i in range(n):
        if dp[i]:
            for j in range(i + 1, min(i + nums[i] + 1, n)):
                dp[j] = True

    return dp[-1]

# Greedy - O(n)
def can_jump_greedy(nums):
    max_reach = 0
    for i in range(len(nums)):
        if i > max_reach:
            return False
        max_reach = max(max_reach, i + nums[i])
    return True
      Python

      Interview Workflow

      💼 Step-by-Step Interview Process

      STEP 1: CLARIFY (2-3 minutes)
├─ Repeat problem in own words
├─ Ask clarifying questions
├─ Confirm input/output types
├─ Ask about constraints
└─ Discuss edge cases

STEP 2: EXAMPLES (2-3 minutes)
├─ Create 2-3 test cases
├─ Include edge cases
├─ Walk through expected output
└─ Confirm understanding

STEP 3: APPROACH (5-7 minutes)
├─ Think out loud
├─ Discuss multiple approaches
├─ Analyze time/space complexity
├─ Choose best approach
└─ Get interviewer buy-in

STEP 4: CODE (10-15 minutes)
├─ Start with function signature
├─ Write clean, readable code
├─ Use meaningful variable names
├─ Add comments for complex logic
└─ Think out loud while coding

STEP 5: TEST (3-5 minutes)
├─ Walk through code with examples
├─ Check edge cases
├─ Look for bugs
├─ Trace through execution
└─ Fix any issues

STEP 6: OPTIMIZE (5 minutes)
├─ Discuss improvements
├─ Better time complexity?
├─ Better space complexity?
├─ Cleaner code?
└─ Handle more edge cases?

STEP 7: DISCUSS (Remaining time)
├─ Alternative approaches
├─ Trade-offs
├─ Real-world considerations
├─ Scalability
└─ Questions for interviewer
      Bash

      Communication Tips

      """
DO:
✅ Think out loud
✅ Explain your reasoning
✅ Ask questions when stuck
✅ Use clear variable names
✅ Write clean, organized code
✅ Test your code
✅ Discuss trade-offs

DON'T:
❌ Jump straight into coding
❌ Stay silent
❌ Ignore edge cases
❌ Use cryptic variable names
❌ Assume constraints
❌ Give up easily
❌ Argue with interviewer
"""
      Python

      Quick Problem-Solving Checklist

      📝 Before Coding

      □ Understand the problem completely
□ Identify input and output types
□ Note all constraints
□ Think of edge cases
□ Choose appropriate data structure
□ Select best algorithm/pattern
□ Estimate time and space complexity
□ Discuss approach with interviewer
□ Get confirmation to proceed
      Bash

      📝 While Coding

      □ Write function signature first
□ Handle edge cases early
□ Use descriptive variable names
□ Add comments for complex parts
□ Keep code clean and organized
□ Think out loud
□ Check for off-by-one errors
□ Avoid unnecessary complexity
      Bash

      📝 After Coding

      □ Walk through code with example
□ Test with edge cases
□ Check for bugs
□ Analyze time complexity
□ Analyze space complexity
□ Discuss optimizations
□ Explain trade-offs
□ Ask if anything is unclear
      Bash

      Common Mistakes to Avoid

      ⚠️ Pitfalls Checklist

      # 1. OFF-BY-ONE ERRORS
# ❌ Wrong
for i in range(len(arr) - 1):  # Misses last element

# ✅ Correct
for i in range(len(arr)):

# 2. MODIFYING COLLECTION DURING ITERATION
# ❌ Wrong
for item in lst:
    if condition:
        lst.remove(item)  # Undefined behavior

# ✅ Correct
lst = [item for item in lst if not condition]

# 3. INTEGER DIVISION
# ❌ Wrong (Python 2 style)
mid = (left + right) / 2  # Returns float

# ✅ Correct
mid = (left + right) // 2

# 4. MUTABLE DEFAULT ARGUMENTS
# ❌ Wrong
def func(lst=[]):
    lst.append(1)
    return lst

# ✅ Correct
def func(lst=None):
    if lst is None:
        lst = []
    lst.append(1)
    return lst

# 5. SHALLOW VS DEEP COPY
# ❌ Wrong
matrix_copy = matrix  # Same reference

# ✅ Correct
matrix_copy = [row[:] for row in matrix]

# 6. FORGOT TO RETURN
# ❌ Wrong
def binary_search(arr, target):
    # ... code ...
    # Forgot return statement

# ✅ Correct
def binary_search(arr, target):
    # ... code ...
    return result

# 7. NOT HANDLING EMPTY INPUT
# ❌ Wrong
def func(arr):
    return arr[0]  # IndexError if empty

# ✅ Correct
def func(arr):
    if not arr:
        return None
    return arr[0]

# 8. USING == FOR FLOATS
# ❌ Wrong
if 0.1 + 0.2 == 0.3:  # False!

# ✅ Correct
import math
if math.isclose(0.1 + 0.2, 0.3):

# 9. INCORRECT BOOLEAN CHECKS
# ❌ Wrong
if len(arr) > 0:  # Verbose

# ✅ Correct
if arr:  # Pythonic

# 10. FORGOT PATH COPY IN BACKTRACKING
# ❌ Wrong
result.append(path)  # All point to same list

# ✅ Correct
result.append(path[:])  # Create copy
      Python

      Final Tips & Tricks

      💡 Pro Tips

      1. READ THE PROBLEM TWICE
   - Don't miss important details

2. START WITH BRUTE FORCE
   - Get a working solution first
   - Then optimize

3. USE EXAMPLES
   - Walk through small examples
   - Identify patterns

4. THINK OUT LOUD
   - Shows your thought process
   - Helps identify issues early

5. WRITE CLEAN CODE
   - Clear variable names
   - Proper indentation
   - Logical structure

6. TEST AS YOU GO
   - Don't wait until the end
   - Catch bugs early

7. KNOW YOUR COMPLEXITIES
   - Always mention Big O
   - Justify your approach

8. PRACTICE COMMON PATTERNS
   - Two pointers
   - Sliding window
   - BFS/DFS
   - Dynamic programming

9. LEARN FROM MISTAKES
   - Review failed problems
   - Understand why you failed

10. TIME MANAGEMENT
    - Don't get stuck on one approach
    - Move on if stuck for 5+ minutes
      Bash

      Resources & Next Steps

      📚 Practice Platforms

      1. LeetCode - Most popular, organized by topic
2. HackerRank - Good for beginners
3. Codeforces - Competitive programming
4. Project Euler - Mathematical problems
5. CodeSignal - Interview prep
      Bash
      WEEK 1-2: Arrays & Strings
- Two pointers
- Sliding window
- Hash maps

WEEK 3-4: Linked Lists & Stacks/Queues
- Fast/slow pointers
- Stack problems
- Queue problems

WEEK 5-6: Trees & Graphs
- DFS/BFS
- Binary trees
- Graph traversal

WEEK 7-8: Dynamic Programming
- 1D DP
- 2D DP
- Memoization

WEEK 9-10: Advanced Topics
- Backtracking
- Greedy
- Tries
- Union-Find

WEEK 11-12: Review & Mock Interviews
- Practice mixed problems
- Time yourself
- Mock interviews
      Bash

      Remember: Consistency beats intensity. Practice 1-2 problems daily!

      Good luck! 🚀

      Discover more from Altgr Blog

      Subscribe to get the latest posts sent to your email.

      Related Posts

      Leave a Reply

      Your email address will not be published. Required fields are marked *