Interview Patterns Recap

Problem aaya ✓ Kya karein?

Array/String hai?
+-- Sorted hai? ✓ Binary Search
+-- Contiguous subarray chahiye?
� +-- Fixed size? ✓ Sliding Window
� +-- Variable size? ✓ Sliding Window / Two Pointer
+-- Pair/Triplet dhundhna hai? ✓ Two Pointers
+-- Subarray sum? ✓ Prefix Sum / Sliding Window
+-- Sorted karna hai? ✓ Sorting

Graph/Tree hai?
+-- Shortest path? ✓ BFS (unweighted) / Dijkstra (weighted)
+-- All paths? ✓ DFS / Backtracking
+-- Cycle hai? ✓ Union-Find / DFS
+-- Topological order? ✓ Kahn's Algorithm
+-- Minimum spanning tree? ✓ Kruskal's / Prim's

DP lag raha hai?
+-- Subsequence? ✓ DP on Strings / LIS
+-- Partition? ✓ Knapsack variants
+-- Grid? ? 2D DP
+-- Optimization? ✓ Binary Search on Answer

Greedy lag raha hai?
+-- Interval scheduling? ✓ Greedy (sort by end)
+-- Minimum cost? ✓ Greedy + Priority Queue
+-- Activity selection? ✓ Greedy

# When: Sorted array, pair/triplet sum, container with water
def two_sum_sorted(arr, target):
 left, right = 0, len(arr) - 1
 while left < right:
 curr = arr[left] + arr[right]
 if curr == target:
 return [left, right]
 elif curr < target:
 left += 1
 else:
 right -= 1
 return [-1, -1]

# Time: O(n), Space: O(1)
# Problems: Two Sum II, 3Sum, Container With Most Water

# When: Contiguous subarray, fixed/variable window size
def max_sum_subarray(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

# Time: O(n), Space: O(1)
# Problems: Max Sum Subarray, Longest Substring K Unique, Min Window Substring

# When: Sorted array, answer space monotonic hai
def binary_search(arr, target):
 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
 return -1

# Time: O(log n), Space: O(1)
# Problems: BS, Search Rotated, Koko Bananas, Ship Packages

# BFS: Shortest path in unweighted graph
from collections import deque
def bfs(graph, start):
 visited = {start}
 queue = deque([start])
 while queue:
 node = queue.popleft()
 for neighbor in graph[node]:
 if neighbor not in visited:
 visited.add(neighbor)
 queue.append(neighbor)

# DFS: All paths, cycle detection, connected components
def dfs(graph, node, visited):
 visited.add(node)
 for neighbor in graph[node]:
 if neighbor not in visited:
 dfs(graph, neighbor, visited)

# When: Overlapping subproblems + optimal substructure
# Template: Define state ✓ Write recurrence ✓ Build bottom-up

# Fibonacci (basic DP)
def fib(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]

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

# When: Local optimal ✓ Global optimal, no backtracking needed
# Activity Selection Problem
def activity_selection(activities):
 # Sort by end time
 activities.sort(key=lambda x: x[1])
 count = 1
 last_end = activities[0][1]
 
 for i in range(1, len(activities)):
 if activities[i][0] >= last_end:
 count += 1
 last_end = activities[i][1]
 
 return count

# Time: O(n log n)
# Problems: Jump Game, Task Scheduler, Gas Station

# When: All combinations/permutations, constraint satisfaction
def subsets(nums):
 result = []
 
 def backtrack(start, current):
 result.append(current[:])
 for i in range(start, len(nums)):
 current.append(nums[i])
 backtrack(i + 1, current)
 current.pop() # Backtrack!
 
 backtrack(0, [])
 return result

# Problems: Subsets, Permutations, N-Queens, Sudoku Solver

# When: Dynamic connectivity, cycle detection in undirected graph
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])
 return self.parent[x]
 
 def union(self, x, y):
 px, py = self.find(x), self.find(y)
 if px == py: return False # Already connected
 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

# Problems: Redundant Connection, Number of Islands II