01 — Data Structures, Algorithms & Coding Interviews

Priority: HIGHEST — This is the make-or-break round in most interviews. Target: Solve LeetCode Medium problems confidently in 20-30 minutes.

Table of Contents

  1. Mindset & Strategy
  2. Big-O Complexity Cheat Sheet
  3. Core Data Structures
  4. The 15 Essential Coding Patterns
  5. Pattern-to-Problem Mapping
  6. The NeetCode 150 Roadmap
  7. Problem-Solving Framework
  8. Python-Specific Tips for Coding Interviews
  9. Practice Schedule
  10. Resources

Mindset & Strategy

You don’t need to solve 500 problems. You need to:

  1. Recognize which pattern a problem uses
  2. Know the template for that pattern
  3. Adapt the template to the specific problem
  4. Write clean, bug-free code under time pressure

In the interview:

Big-O Complexity Cheat Sheet

Time Complexity (sorted best → worst)

NotationNameExample
O(1)ConstantHash table lookup, array index access
O(log n)LogarithmicBinary search, balanced BST operations
O(n)LinearSingle loop through array, linear search
O(n log n)LinearithmicMerge sort, heap sort, efficient sorting
O(n²)QuadraticNested loops, bubble sort, insertion sort
O(2ⁿ)ExponentialRecursive Fibonacci, power set
O(n!)FactorialPermutations, traveling salesman brute force

Space Complexity Quick Rules

Core Data Structures

1. Arrays & Strings

What to know:
- Indexing, slicing, iteration
- In-place operations (two pointers, swapping)
- Subarray/substring problems
- Sorting-based solutions

Python specifics:
- Lists are dynamic arrays: append O(1) amortized, insert O(n)
- Strings are immutable: concatenation creates new string
- Use list(s) to manipulate characters, then ''.join()

Key problems:

2. Hash Maps & Hash Sets

What to know:
- O(1) average lookup, insert, delete
- Collision resolution (chaining vs open addressing)
- When to use: frequency counting, deduplication, lookup table
- Counter, defaultdict in Python

Python specifics:
- dict preserves insertion order (Python 3.7+)
- collections.Counter for frequency counting
- collections.defaultdict to avoid KeyError
- set for O(1) membership testing

Key problems:

3. Linked Lists

What to know:
- Singly vs Doubly linked
- In-place operations (no random access)
- Pointer manipulation (next, prev)
- Dummy head node trick

Common patterns:
- Fast/slow pointer (cycle detection, middle of list)
- Reversing a linked list (iterating 3 pointers)
- Merge two sorted lists

Key problems:

4. Stacks & Queues

Stack (LIFO):
- Push/Pop O(1)
- Use for: matching brackets, monotonic stack, DFS, undo operations
- Python: list (append/pop) or collections.deque

Queue (FIFO):
- Enqueue/Dequeue O(1)
- Use for: BFS, level-order traversal, scheduling
- Python: collections.deque (appendleft/pop or append/popleft)

Monotonic Stack:
- Maintains elements in sorted order
- Use for: next greater element, largest rectangle in histogram

Key problems:

5. Trees

Binary Tree:
- Traversals: inorder, preorder, postorder (recursive + iterative)
- Level-order traversal (BFS with queue)
- Height, depth, diameter

Binary Search Tree (BST):
- Search, insert, delete: O(h) where h = height
- Inorder traversal gives sorted order
- Validate BST: pass min/max bounds

Trie (Prefix Tree):
- For string prefix problems
- Insert/Search: O(word length)

Key problems:

6. Heaps (Priority Queues)

What to know:
- Min-heap: smallest element at top
- Max-heap: largest element at top (negate values in Python)
- Insert: O(log n), Extract min/max: O(log n)
- Build heap: O(n)
- Use for: top K elements, merge K sorted lists, median finding

Python specifics:
- heapq module (min-heap only)
- For max-heap: push -val, pop and negate
- heapq.nlargest(k, iterable) and heapq.nsmallest(k, iterable)

Key problems:

7. Graphs

Representations:
- Adjacency list: dict[node] = [neighbors] (most common in interviews)
- Adjacency matrix: 2D array (less common, dense graphs)
- Edge list: [(u, v, weight)]

Traversals:
- BFS: level-by-level, shortest path in unweighted graph
- DFS: explores deep first, good for path finding, cycle detection

Key algorithms:
- Topological sort: DAG ordering (Kahn's BFS or DFS-based)
- Dijkstra's: shortest path with positive weights
- Union-Find: connected components, cycle detection in undirected
- Bellman-Ford: shortest path with negative weights (less common)

Key problems:

8. Dynamic Programming

What to know:
- Identify overlapping subproblems + optimal substructure
- Top-down (memoization) vs Bottom-up (tabulation)
- State definition: what variables define a subproblem?
- Transition: how does a state relate to smaller states?
- Base cases: what are the smallest subproblems?

Common DP categories:
- 1D: climbing stairs, house robber, coin change
- 2D: longest common subsequence, edit distance, unique paths
- Knapsack: 0/1 knapsack, unbounded knapsack
- String matching: regex, wildcard matching
- Interval: matrix chain multiplication, burst balloons

Key problems:

The 15 Essential Coding Patterns

Pattern 1: Two Pointers

When to use:
- Sorted array/list problems
- Finding pairs with a target sum
- Removing duplicates in-place
- Comparing elements from both ends

Template:
  left, right = 0, len(arr) - 1
  while left < right:
      # compare arr[left] and arr[right]
      # move left++ or right-- based on condition

Must-solve: Two Sum II, 3Sum, Container With Most Water, Trapping Rain Water

Pattern 2: Sliding Window

When to use:
- Contiguous subarray/substring problems
- "Maximum/minimum subarray of size K"
- "Longest substring with condition"

Template (variable-size window):
  left = 0
  for right in range(len(arr)):
      # expand: add arr[right] to window state
      while window_condition_violated:
          # shrink: remove arr[left] from window state
          left += 1
      # update answer

Must-solve: Max Sum Subarray of Size K, Longest Substring Without Repeating Characters, Minimum Window Substring, Permutation in String

Pattern 3: Fast & Slow Pointers

When to use:
- Cycle detection in linked list or array
- Finding middle of linked list
- Finding start of cycle

Template:
  slow = fast = head
  while fast and fast.next:
      slow = slow.next
      fast = fast.next.next
      if slow == fast:  # cycle detected
          break

Must-solve: Linked List Cycle, Happy Number, Find the Duplicate Number, Middle of Linked List

Pattern 4: Merge Intervals

When to use:
- Overlapping intervals
- Merging, inserting, or scheduling intervals

Template:
  intervals.sort(key=lambda x: x[0])
  merged = [intervals[0]]
  for current in intervals[1:]:
      if current[0] <= merged[-1][1]:
          merged[-1][1] = max(merged[-1][1], current[1])
      else:
          merged.append(current)

Must-solve: Merge Intervals, Insert Interval, Non-overlapping Intervals, Meeting Rooms I & II

When to use:
- Sorted array
- "Find target" or "find boundary"
- Search space reduction problems (search on answer)

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

Advanced — Binary search on answer:
  left, right = min_possible, max_possible
  while left < right:
      mid = (left + right) // 2
      if condition(mid):
          right = mid
      else:
          left = mid + 1

Must-solve: Binary Search, Search in Rotated Sorted Array, Find Minimum in Rotated Sorted Array, Koko Eating Bananas, Median of Two Sorted Arrays

When to use:
- Shortest path in unweighted graph
- Level-order traversal
- Exploring neighbors level by level
- Grid/matrix traversal

Template:
  from collections import deque
  queue = deque([start])
  visited = {start}
  while queue:
      node = queue.popleft()
      for neighbor in get_neighbors(node):
          if neighbor not in visited:
              visited.add(neighbor)
              queue.append(neighbor)

Must-solve: Number of Islands, Binary Tree Level Order Traversal, Word Ladder, Rotting Oranges, Walls and Gates

When to use:
- Path finding
- Cycle detection
- Tree traversals
- Connected components
- Exhaustive search

Template (recursive):
  def dfs(node, visited):
      visited.add(node)
      for neighbor in get_neighbors(node):
          if neighbor not in visited:
              dfs(neighbor, visited)

Template (iterative with stack):
  stack = [start]
  visited = set()
  while stack:
      node = stack.pop()
      if node in visited:
          continue
      visited.add(node)
      for neighbor in get_neighbors(node):
          stack.append(neighbor)

Must-solve: Max Area of Island, Clone Graph, Pacific Atlantic Water Flow, Course Schedule, Number of Connected Components

Pattern 8: Backtracking

When to use:
- Generate all combinations/permutations/subsets
- Constraint satisfaction (Sudoku, N-Queens)
- Path finding with constraints

Template:
  def backtrack(candidates, path, result):
      if is_solution(path):
          result.append(path[:])
          return
      for candidate in candidates:
          if is_valid(candidate, path):
              path.append(candidate)
              backtrack(next_candidates, path, result)
              path.pop()  # undo choice

Must-solve: Subsets, Permutations, Combination Sum, Word Search, N-Queens, Letter Combinations of Phone Number

Pattern 9: Topological Sort

When to use:
- Ordering tasks with dependencies
- Detecting cycles in directed graphs
- Course scheduling

Template (Kahn's BFS):
  from collections import deque
  in_degree = {node: 0 for node in graph}
  for node in graph:
      for neighbor in graph[node]:
          in_degree[neighbor] += 1
  queue = deque([n for n in in_degree if in_degree[n] == 0])
  order = []
  while queue:
      node = queue.popleft()
      order.append(node)
      for neighbor in graph[node]:
          in_degree[neighbor] -= 1
          if in_degree[neighbor] == 0:
              queue.append(neighbor)
  # If len(order) != len(graph), there's a cycle

Must-solve: Course Schedule, Course Schedule II, Alien Dictionary, Task Scheduler

Pattern 10: Union-Find (Disjoint Set Union)

When to use:
- Connected components
- Cycle detection in undirected graphs
- Grouping/clustering

Template:
  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
          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

Must-solve: Number of Connected Components, Redundant Connection, Accounts Merge, Graph Valid Tree

Pattern 11: Monotonic Stack

When to use:
- Next greater/smaller element
- Largest rectangle in histogram
- Stock span problems

Template (next greater element):
  stack = []  # stores indices
  result = [-1] * len(arr)
  for i in range(len(arr)):
      while stack and arr[i] > arr[stack[-1]]:
          result[stack.pop()] = arr[i]
      stack.append(i)

Must-solve: Daily Temperatures, Next Greater Element, Largest Rectangle in Histogram, Trapping Rain Water

Pattern 12: Top-K Elements (Heap)

When to use:
- "Find K largest/smallest/most frequent"
- Running median
- Merging K sorted things

Template:
  import heapq
  # Top K largest
  heap = []
  for val in stream:
      heapq.heappush(heap, val)
      if len(heap) > k:
          heapq.heappop(heap)
  # heap now contains k largest elements

Must-solve: Kth Largest Element, Top K Frequent Elements, Find Median from Data Stream, Merge K Sorted Lists

Pattern 13: Dynamic Programming

When to use:
- "Count ways to..." / "Minimum/maximum of..."
- Overlapping subproblems
- Optimal substructure

Approach:
  1. Define state: dp[i] = ...
  2. Find transition: dp[i] = f(dp[i-1], dp[i-2], ...)
  3. Set base cases: dp[0] = ..., dp[1] = ...
  4. Determine iteration order
  5. Optimize space if possible (often only need last 1-2 rows/values)

Must-solve: Coin Change, House Robber, LIS, LCS, Word Break, 0/1 Knapsack, Edit Distance, Decode Ways

Pattern 14: Bit Manipulation

When to use:
- Single number problems (XOR)
- Counting bits
- Power of 2 checks
- Subsets generation

Key operations:
  x & (x - 1)  # removes lowest set bit
  x & (-x)     # isolates lowest set bit
  x ^ x = 0    # XOR with self = 0
  x ^ 0 = x    # XOR with 0 = x

Must-solve: Single Number, Number of 1 Bits, Counting Bits, Reverse Bits, Missing Number

Pattern 15: Greedy

When to use:
- Local optimal choice leads to global optimal
- Scheduling, interval problems
- When DP is overkill

Key insight:
  Prove greedy works by showing local optimal → global optimal
  (or use exchange argument)

Must-solve: Jump Game, Gas Station, Task Scheduler, Partition Labels

Pattern-to-Problem Mapping

Use this to quickly identify which pattern to apply:

If the problem says…Consider…
”Sorted array”Two Pointers, Binary Search
”Subarray/substring of size K”Sliding Window
”Linked list cycle”Fast & Slow Pointers
”Overlapping intervals”Merge Intervals
”Find position/boundary”Binary Search
”Shortest path (unweighted)“BFS
”Path exists” / “connected”DFS, Union-Find
”All combinations/permutations”Backtracking
”Task ordering/dependencies”Topological Sort
”Connected components”Union-Find, DFS
”Next greater/smaller”Monotonic Stack
”Top K / Kth largest”Heap
”Count ways / min-max cost”Dynamic Programming
”Single/missing number”Bit Manipulation
”Optimal scheduling”Greedy
”Matrix traversal”BFS/DFS
”Tree”DFS (recursive), BFS (level-order)
“Trie/prefix”Trie data structure
”Stream of data”Heap, Running statistics

The NeetCode 150 Roadmap

Follow this order. Solve at least the starred (★) problems.

Arrays & Hashing (9 problems)

Two Pointers (5 problems)

Sliding Window (6 problems)

Stack (7 problems)

Binary Search (7 problems)

Linked List (11 problems)

Trees (15 problems)

Tries (3 problems)

Heap / Priority Queue (7 problems)

Backtracking (9 problems)

Graphs (13 problems)

Dynamic Programming (12 problems)

Intervals (5 problems)

Greedy (8 problems)

Math & Geometry (8 problems)

Bit Manipulation (7 problems)

Problem-Solving Framework

Use this in every interview:

1. UNDERSTAND (2-3 min)
   - Restate the problem in your own words
   - Ask: What are the inputs? Outputs? Constraints?
   - Ask: What about edge cases? Empty input? Single element? Negative numbers?
   - Ask: Can I modify the input? Is it sorted?

2. PLAN (3-5 min)
   - Identify the pattern (use the mapping table above)
   - State your approach: "I'm going to use a sliding window because..."
   - Walk through your approach with a small example
   - State expected time/space complexity

3. CODE (15-20 min)
   - Write clean, readable code
   - Use meaningful variable names
   - Handle edge cases first (early returns)
   - Talk while you code — narrate your decisions

4. TEST (3-5 min)
   - Trace through your code with the given example
   - Test edge cases: empty input, single element, all same elements
   - Test boundary conditions
   - Fix any bugs found

5. OPTIMIZE (if time)
   - Can you reduce time complexity?
   - Can you reduce space complexity?
   - Are there Python-specific optimizations?

Python-Specific Tips for Coding Interviews

Essential Python for Interviews

# --- Collections ---
from collections import defaultdict, Counter, deque, OrderedDict
from heapq import heappush, heappop, heapify, nlargest, nsmallest
from itertools import combinations, permutations, product, accumulate
from functools import lru_cache
from bisect import bisect_left, bisect_right, insort
from math import inf, ceil, floor, gcd, log2
from typing import List, Optional, Tuple, Dict, Set

# --- Frequency counting ---
freq = Counter("hello")  # {'l': 2, 'h': 1, 'e': 1, 'o': 1}
freq.most_common(2)       # [('l', 2), ('h', 1)]

# --- Default dict ---
graph = defaultdict(list)
graph['a'].append('b')    # no KeyError

# --- Deque (O(1) both ends) ---
q = deque([1, 2, 3])
q.appendleft(0)           # [0, 1, 2, 3]
q.popleft()               # 0
q.append(4)               # [1, 2, 3, 4]

# --- Heap ---
heap = [3, 1, 2]
heapify(heap)              # [1, 3, 2]
heappush(heap, 0)          # [0, 1, 2, 3]
smallest = heappop(heap)   # 0

# --- Binary search ---
sorted_arr = [1, 3, 5, 7, 9]
bisect_left(sorted_arr, 5)   # 2 (index where 5 is / would be inserted)
bisect_right(sorted_arr, 5)  # 3

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

# --- Sorting ---
arr.sort(key=lambda x: x[1])           # sort by 2nd element
arr.sort(key=lambda x: (-x[1], x[0]))  # sort by 2nd desc, then 1st asc

# --- String manipulation ---
s = "hello world"
s.split()          # ['hello', 'world']
'_'.join(['a','b']) # 'a_b'
s[::-1]             # reverse string
ord('a')            # 97
chr(97)             # 'a'

# --- List comprehension ---
squares = [x*x for x in range(10)]
flat = [item for sublist in matrix for item in sublist]
filtered = [x for x in arr if x > 0]

# --- Infinity ---
float('inf')    # positive infinity
float('-inf')   # negative infinity

# --- Tuple unpacking ---
for i, (key, val) in enumerate(pairs):
    pass

Common Gotchas

# WRONG: Mutable default argument
def add(item, lst=[]):  # lst is shared across calls!
    lst.append(item)
    return lst

# RIGHT:
def add(item, lst=None):
    if lst is None:
        lst = []
    lst.append(item)
    return lst

# WRONG: Shallow copy of nested list
grid = [[0] * 3] * 3  # all 3 rows are the SAME list!
grid[0][0] = 1         # changes ALL rows!

# RIGHT:
grid = [[0] * 3 for _ in range(3)]

# WRONG: Modifying list while iterating
for item in lst:
    if condition:
        lst.remove(item)  # skips elements!

# RIGHT:
lst = [item for item in lst if not condition]

Practice Schedule

Week 1: Foundations (Arrays, Strings, Hash Maps)

Week 2: Core Patterns (Sliding Window, Binary Search, Stacks)

Week 3: Trees & Graphs

Week 4: Advanced Patterns

Week 5-6: Integration & Timed Practice

Resources

Primary

Video Explanations

Books

Practice Platforms

My Notes

Use this space to track your progress, write down patterns you keep forgetting, and note problems that tripped you up.

Problems I struggled with:
-

Patterns I need to review:
-

Key insights:
-

Next: 02-system-design.md