DSA Quick Reference Cheat Sheet
For SDE Interviews - 4+ Years Experience
🎯 Pattern Recognition Guide
Input Characteristics → Algorithm Choice
✅ Sorted Array → Binary Search, Two Pointers
✅ Unsorted Array → Hash Map, Sorting first
✅ Subarray/Substring → Sliding Window, Two Pointers
✅ Tree → DFS (recursion), BFS (queue)
✅ Graph → DFS, BFS, Topological Sort
✅ Linked List → Two Pointers, Fast/Slow
✅ Intervals → Sort + Merge, Sweep Line
✅ Matrix → DFS/BFS, Dynamic Programming
✅ Duplicates allowed → Hash Map, Sorting
✅ In-place required → Two Pointers, Swapping
⚡ Time Complexity Quick Lookup
O(1) → Hash table operations, array access
O(log n) → Binary search, balanced tree operations
O(n) → Linear scan, DFS/BFS
O(n log n)→ Efficient sorting, heap operations
O(n²) → Nested loops, bubble sort
O(2^n) → Backtracking, subsets
🔧 Essential Code Templates
Two Pointers
def two_sum_sorted(arr, target):
l, r = 0, len(arr) - 1
while l < r:
if arr[l] + arr[r] == target: return [l, r]
elif arr[l] + arr[r] < target: l += 1
else: r -= 1
Sliding Window
def max_subarray_size_k(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
Binary Search
def binary_search(arr, target):
l, r = 0, len(arr) - 1
while l <= r:
mid = (l + r) // 2
if arr[mid] == target: return mid
elif arr[mid] < target: l = mid + 1
else: r = mid - 1
return -1
DFS Tree
def dfs(root):
if not root: return
# Process node
dfs(root.left)
dfs(root.right)
BFS
def bfs(root):
queue = deque([root])
while queue:
node = queue.popleft()
# Process node
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
Dynamic Programming
def dp_template(n):
dp = [0] * (n + 1)
dp[0] = base_case
for i in range(1, n + 1):
dp[i] = recurrence(dp[i-1], dp[i-2], ...)
return dp[n]
🏆 Top 20 Must-Know Problems
Arrays (6)
1. Two Sum - Hash map
2. Maximum Subarray - Kadane's algorithm
3. Merge Intervals - Sort then merge
4. 3Sum - Sort + two pointers
5. Container With Most Water - Two pointers
6. Product of Array Except Self - Prefix/suffix
Trees (4)
7. Maximum Depth - DFS/BFS
8. Validate BST - Inorder/bounds
9. Level Order Traversal - BFS
10. Lowest Common Ancestor - DFS
Linked Lists (3)
11. Reverse Linked List - Iterative
12. Merge Two Sorted Lists - Two pointers
13. Linked List Cycle - Fast/slow pointers
Strings (3)
14. Longest Substring Without Repeating - Sliding window
15. Valid Anagram - Sorting/counting
16. Valid Parentheses - Stack
Dynamic Programming (2)
17. Climbing Stairs - Basic DP
18. Coin Change - Unbounded knapsack
Graphs (2)
19. Number of Islands - DFS/BFS
20. Course Schedule - Topological sort
🎨 Problem-Solving Framework
Step 1: Understand (2-3 minutes)
Read problem carefully
Identify inputs, outputs, constraints
Ask clarifying questions
Step 2: Examples (2-3 minutes)
Work through 2-3 examples manually
Identify edge cases
Understand the pattern
Step 3: Approach (5-10 minutes)
Start with brute force
Identify bottlenecks
Optimize using patterns
Choose data structures
Step 4: Code (15-20 minutes)
Write clean, readable code
Handle edge cases
Use meaningful variable names
Step 5: Test & Debug (3-5 minutes)
Walk through examples
Check edge cases
Analyze time/space complexity
💡 Common Optimizations
🔄 Replace nested loops → Hash maps, Two pointers
📊 Sort first → Enable binary search, two pointers
🪟 Sliding window → For subarray problems
🗂️ Memoization → For recursive solutions with overlap
📈 Early termination → When answer found
🔍 Binary search → On answer space
🚨 Red Flags to Avoid
❌ Not asking clarifying questions
❌ Jumping to code immediately
❌ Not considering edge cases
❌ Poor variable naming
❌ Not explaining approach
❌ Ignoring time/space complexity
❌ Not testing solution
🎯 Company Focus Areas
Google: Algorithms, Math, System Design
Amazon: Arrays, Strings, Trees, Leadership
Microsoft: Trees, Graphs, System Design
Meta: Hash Maps, Trees, System Design
Apple: Arrays, Strings, Algorithms
📋 Final Checklist
Before Interview:
☐ Practice 10+ problems daily for 2-3 months
☐ Master all 16 patterns
☐ Time yourself (30-45 mins per problem)
☐ Practice explaining solutions aloud
☐ Review system design basics
☐ Prepare behavioral questions
During Interview:
☐ Think aloud throughout
☐ Start with brute force
☐ Optimize step by step
☐ Handle edge cases
☐ Test with examples
☐ Discuss time/space complexity
Remember: Patterns > Memorization
