DSA Interview Checklist: 75 Must-Know Problems

Preparing for coding interviews without a checklist is like studying for an exam without a syllabus. You end up solving random problems, spending weeks on niche topics, and missing the patterns that actually show up. This post gives you the complete checklist: 75 problems, organized by pattern, with study schedules and a framework for tackling problems you have never seen before.

---

The 75 Must-Know Problems

These problems are curated for maximum coverage. Each one teaches a reusable pattern. Solving all 75 means you have seen every major pattern that appears in FAANG-level interviews.

Arrays and Hashing (10 problems)

#	Problem	Difficulty	LeetCode	Key Pattern
1	Two Sum	Easy	#1	Hash map lookup
2	Valid Anagram	Easy	#242	Frequency count
3	Group Anagrams	Medium	#49	Sorted key + hash map
4	Top K Frequent Elements	Medium	#347	Bucket sort / heap
5	Product of Array Except Self	Medium	#238	Prefix/suffix products
6	Longest Consecutive Sequence	Medium	#128	Hash set + sequence start
7	Contains Duplicate	Easy	#217	Hash set
8	Encode and Decode Strings	Medium	#271	Length prefix encoding
9	Maximum Subarray	Medium	#53	Kadane’s algorithm
10	Subarray Sum Equals K	Medium	#560	Prefix sum + hash map

Two Pointers (5 problems)

#	Problem	Difficulty	LeetCode	Key Pattern
11	Valid Palindrome	Easy	#125	Two pointers inward
12	3Sum	Medium	#15	Sort + two pointers
13	Container With Most Water	Medium	#11	Shrink the shorter side
14	Trapping Rain Water	Hard	#42	Left/right max pointers
15	Two Sum II (Sorted)	Medium	#167	Two pointers on sorted

Sliding Window (5 problems)

#	Problem	Difficulty	LeetCode	Key Pattern
16	Best Time to Buy/Sell Stock	Easy	#121	Track min so far
17	Longest Substring Without Repeating	Medium	#3	Expand/shrink window
18	Longest Repeating Character Replacement	Medium	#424	Window + max freq
19	Minimum Window Substring	Hard	#76	Two hash maps + window
20	Sliding Window Maximum	Hard	#239	Monotonic deque

Stack (5 problems)

#	Problem	Difficulty	LeetCode	Key Pattern
21	Valid Parentheses	Easy	#20	Stack matching
22	Min Stack	Medium	#155	Auxiliary min stack
23	Daily Temperatures	Medium	#739	Monotonic stack
24	Largest Rectangle in Histogram	Hard	#84	Monotonic stack
25	Evaluate Reverse Polish Notation	Medium	#150	Stack evaluation

Binary Search (5 problems)

#	Problem	Difficulty	LeetCode	Key Pattern
26	Binary Search	Easy	#704	Classic template
27	Search in Rotated Sorted Array	Medium	#33	Find sorted half
28	Find Minimum in Rotated Sorted Array	Medium	#153	Pivot detection
29	Koko Eating Bananas	Medium	#875	BS on answer
30	Search a 2D Matrix	Medium	#74	Flatten to 1D

Linked Lists (6 problems)

#	Problem	Difficulty	LeetCode	Key Pattern
31	Reverse Linked List	Easy	#206	Three-pointer reversal
32	Merge Two Sorted Lists	Easy	#21	Dummy head + merge
33	Linked List Cycle	Easy	#141	Fast/slow pointers
34	Remove Nth Node From End	Medium	#19	Two-pass or gap pointers
35	Reorder List	Medium	#143	Split + reverse + merge
36	LRU Cache	Medium	#146	Hash map + doubly linked list

Trees (10 problems)

#	Problem	Difficulty	LeetCode	Key Pattern
37	Invert Binary Tree	Easy	#226	Recursive swap
38	Maximum Depth of Binary Tree	Easy	#104	DFS depth
39	Same Tree	Easy	#100	Simultaneous DFS
40	Subtree of Another Tree	Easy	#572	DFS + same tree check
41	Lowest Common Ancestor of BST	Medium	#235	BST property split
42	Binary Tree Level Order Traversal	Medium	#102	BFS with queue
43	Validate BST	Medium	#98	In-order or range check
44	Kth Smallest Element in BST	Medium	#230	In-order traversal
45	Binary Tree from Preorder/Inorder	Medium	#105	Recursive construction
46	Serialize and Deserialize Binary Tree	Hard	#297	BFS or preorder + null markers

Heap / Priority Queue (3 problems)

#	Problem	Difficulty	LeetCode	Key Pattern
47	Find Median from Data Stream	Hard	#295	Two heaps
48	Merge K Sorted Lists	Hard	#23	Min-heap of heads
49	Top K Frequent Words	Medium	#692	Min-heap of size k

Backtracking (5 problems)

#	Problem	Difficulty	LeetCode	Key Pattern
50	Subsets	Medium	#78	Include/exclude
51	Combination Sum	Medium	#39	Backtrack with reuse
52	Permutations	Medium	#46	Swap-based backtrack
53	Word Search	Medium	#79	Grid DFS + visited
54	Letter Combinations of Phone	Medium	#17	Cartesian product

Graphs (8 problems)

#	Problem	Difficulty	LeetCode	Key Pattern
55	Number of Islands	Medium	#200	BFS/DFS flood fill
56	Clone Graph	Medium	#133	BFS + hash map
57	Pacific Atlantic Water Flow	Medium	#417	Reverse BFS from edges
58	Course Schedule	Medium	#207	Topological sort (cycle)
59	Course Schedule II	Medium	#210	Topological sort (order)
60	Graph Valid Tree	Medium	#261	Union-Find or DFS
61	Number of Connected Components	Medium	#323	Union-Find
62	Word Ladder	Hard	#127	BFS shortest path

Dynamic Programming (10 problems)

#	Problem	Difficulty	LeetCode	Key Pattern
63	Climbing Stairs	Easy	#70	Fibonacci DP
64	House Robber	Medium	#198	Take/skip DP
65	House Robber II	Medium	#213	Circular array DP
66	Longest Increasing Subsequence	Medium	#300	DP + binary search
67	Coin Change	Medium	#322	Unbounded knapsack
68	Word Break	Medium	#139	DP + hash set
69	Unique Paths	Medium	#62	Grid DP
70	Decode Ways	Medium	#91	1D DP with conditions
71	Longest Common Subsequence	Medium	#1143	2D string DP
72	Edit Distance	Medium	#72	2D string DP

Intervals and Greedy (3 problems)

#	Problem	Difficulty	LeetCode	Key Pattern
73	Merge Intervals	Medium	#56	Sort + merge overlaps
74	Non-Overlapping Intervals	Medium	#435	Greedy earliest end
75	Meeting Rooms II	Medium	#253	Min-heap or sweep line

---

Study Schedules

4-Week Sprint (Tight Deadline)

For those with < 1 month to prepare. Solve 3-4 problems per day, focusing on the most common patterns.

schedule_4_week = {
    "Week 1: Foundations": [
        "Day 1-2: Arrays + Hashing (#1-10)",
        "Day 3: Two Pointers (#11-15)",
        "Day 4: Sliding Window (#16-20)",
        "Day 5: Stack (#21-25)",
        "Day 6: Binary Search (#26-30)",
        "Day 7: Review + revisit weak spots",
    ],
    "Week 2: Data Structures": [
        "Day 1: Linked Lists (#31-36)",
        "Day 2-3: Trees (#37-46)",
        "Day 4: Heaps (#47-49)",
        "Day 5: Backtracking (#50-54)",
        "Day 6-7: Review + mock interview",
    ],
    "Week 3: Graphs + DP": [
        "Day 1-2: Graphs (#55-62)",
        "Day 3-5: Dynamic Programming (#63-72)",
        "Day 6: Intervals (#73-75)",
        "Day 7: Review all patterns",
    ],
    "Week 4: Polish": [
        "Day 1-3: Redo problems you struggled with",
        "Day 4-5: Timed mock interviews (45 min each)",
        "Day 6: System design review (if applicable)",
        "Day 7: Rest and light review",
    ],
}

8-Week Standard Plan

The sweet spot for most candidates. Solve 2 problems per day with deeper understanding.

schedule_8_week = {
    "Weeks 1-2": "Arrays, Hashing, Two Pointers, Sliding Window (20 problems)",
    "Weeks 3-4": "Stack, Binary Search, Linked Lists, Trees (21 problems)",
    "Weeks 5-6": "Heaps, Backtracking, Graphs (16 problems)",
    "Weeks 7-8": "DP, Intervals, review, and mock interviews (18 problems)",
}

12-Week Deep Dive

For career changers or those starting from scratch. 1-2 problems per day with time for theory.

schedule_12_week = {
    "Weeks 1-3": "Learn data structures + solve Easy problems",
    "Weeks 4-6": "Arrays, Strings, Linked Lists, Trees (patterns + Medium)",
    "Weeks 7-9": "Graphs, DP, Binary Search (core Medium/Hard)",
    "Weeks 10-11": "Mock interviews, company-specific problems",
    "Week 12": "Review, rest, confidence building",
}

---

Pattern Recognition Framework

When you see an unknown problem, run through this decision tree.

Step 1: What Are You Given?

def identify_input(problem):
    """
    First, classify the input type.
    """
    input_patterns = {
        "Sorted array": "Binary search or two pointers",
        "Unsorted array": "Hash map, sorting, or sliding window",
        "String": "Hash map, two pointers, or DP",
        "Linked list": "Two pointers (fast/slow)",
        "Tree": "DFS or BFS",
        "Graph": "BFS, DFS, or Union-Find",
        "Matrix/Grid": "BFS/DFS or DP",
        "Set of choices": "Backtracking or DP",
    }
    return input_patterns

Step 2: What Are You Asked For?

Asked For	Likely Pattern
”Find a pair/triplet”	Two pointers or hash map
”Longest/shortest substring”	Sliding window
”All permutations/subsets”	Backtracking
”Minimum/maximum of something”	DP, binary search, or greedy
”Is it possible?”	BFS/DFS or DP
”Count the number of ways”	DP
”Shortest path”	BFS (unweighted) or Dijkstra (weighted)
“Connected components”	Union-Find or DFS
”Top K elements”	Heap
”Order of tasks”	Topological sort

Step 3: Recognize Sub-Patterns

def recognize_pattern(problem_clues):
    """
    Common clue words and their patterns.
    """
    clue_to_pattern = {
        "contiguous subarray": "Sliding window or prefix sum",
        "subsequence": "DP (often 2D)",
        "parentheses/brackets": "Stack",
        "next greater/smaller": "Monotonic stack",
        "k-th largest/smallest": "Heap or quickselect",
        "intervals overlap": "Sort by start, merge or sweep line",
        "minimize the maximum": "Binary search on answer",
        "maximize the minimum": "Binary search on answer",
        "at most k distinct": "Sliding window + hash map",
        "all paths/combinations": "Backtracking (DFS)",
        "optimal substructure": "DP",
    }
    return clue_to_pattern

The 5-Minute Rule

If you cannot identify the pattern in 5 minutes:

1. Try brute force first — write the O(n^2) or O(2^n) solution
2. Ask: what work is repeated? — that reveals the optimization
3. Ask: is there a monotonic property? — that reveals binary search or stack
4. Ask: can I break this into subproblems? — that reveals DP

---

Common Mistakes That Cost Offers

Mistake 1: Jumping to Code Too Fast

Wrong: Read problem, immediately start coding.

Right: Spend 3-5 minutes on examples, edge cases, and approach discussion before writing a single line.

# The interview framework:
# 1. Clarify (1-2 min): constraints, edge cases, input format
# 2. Examples (2-3 min): walk through 2-3 examples by hand
# 3. Approach (2-3 min): explain your algorithm, state complexity
# 4. Code (15-20 min): write clean code
# 5. Test (5 min): trace through your code with examples
# 6. Optimize (if time): discuss improvements

Mistake 2: Not Handling Edge Cases

Always check these before submitting:

• Empty input ([], "", None)
• Single element
• All elements the same
• Already sorted / reverse sorted
• Negative numbers
• Integer overflow (less common in Python)
• Input at constraint boundaries

def safe_solution(nums):
    # ALWAYS handle edge cases first
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]
    # ... main logic

Mistake 3: Ignoring Time Complexity

Wrong: “My solution works!” (but it is O(n^3) on n = 10^5)

Right: Check constraints first.

# Rough guide for what passes in ~1 second:
# n <= 10:       O(n!) or O(2^n) is fine
# n <= 20:       O(2^n) is fine
# n <= 500:      O(n^3) is fine
# n <= 5000:     O(n^2) is fine
# n <= 10^5:     O(n log n) needed
# n <= 10^6:     O(n) needed
# n <= 10^8:     O(log n) or O(1) needed

Mistake 4: Poor Variable Names

# BAD — what do i, j, t mean?
def f(a, k):
    t = 0
    for i in range(len(a)):
        t += a[i]
        if t > k:
            return i
    return -1

# GOOD — self-documenting
def find_first_prefix_exceeding(nums, target):
    running_sum = 0
    for idx in range(len(nums)):
        running_sum += nums[idx]
        if running_sum > target:
            return idx
    return -1

Mistake 5: Not Testing Your Code

# After coding, trace through at least:
# 1. The given example
# 2. An edge case (empty/single element)
# 3. A tricky case (duplicates, negatives, boundary)

# Do this OUT LOUD in the interview:
# "Let me trace through [2, 7, 11, 15] with target 9..."
# "i=0, complement = 9-2 = 7, not in map, add 2->0"
# "i=1, complement = 9-7 = 2, found in map at index 0!"
# "Return [0, 1]. Correct."

---

What Interviewers Actually Look For

1. Problem-Solving Process (40% of evaluation)

• Do you ask clarifying questions?
• Do you consider multiple approaches before committing?
• Can you reason about trade-offs?

2. Code Quality (25% of evaluation)

• Is your code clean, readable, and well-structured?
• Do you use meaningful names?
• Do you handle edge cases?

3. Communication (20% of evaluation)

• Do you think out loud?
• Can you explain your reasoning clearly?
• Do you respond well to hints?

4. Correctness (15% of evaluation)

• Does your code actually work?
• Do you test it yourself before declaring “done”?

Surprising truth: Many candidates who write correct but messy code with no communication get rejected. Candidates who communicate well, write clean code, but need one small hint often get hired.

# What interviewers want to hear:
good_communication = [
    "Let me make sure I understand the problem...",
    "My initial thought is brute force O(n^2), but I think we can do better",
    "I'll use a hash map because we need O(1) lookups",
    "The key insight is that if we sort first...",
    "Let me trace through this example to verify...",
    "The time complexity is O(n log n) because of the sort",
    "An edge case to consider: what if the array is empty?",
]

---

Quick Reference: Pattern to Complexity

Pattern	Typical Time	Typical Space
Hash map lookup	O(n)	O(n)
Two pointers (sorted)	O(n)	O(1)
Sliding window	O(n)	O(k)
Binary search	O(log n)	O(1)
BS on answer	O(n log M)	O(1)
BFS/DFS	O(V + E)	O(V)
Topological sort	O(V + E)	O(V)
Backtracking	O(2^n) or O(n!)	O(n)
DP (1D)	O(n) or O(n * k)	O(n)
DP (2D)	O(n * m)	O(n * m) or O(m)
Heap (top K)	O(n log k)	O(k)
Union-Find	O(n * alpha(n))	O(n)

---

Your Action Plan

1. Bookmark this page. Use the 75-problem table as your checklist.
2. Pick a schedule. 4 weeks if you are in a rush, 8 weeks for balanced prep, 12 weeks if starting from zero.
3. Track your progress. For each problem, note: solved independently (green), needed hint (yellow), needed solution (red). Revisit yellow/red problems weekly.
4. Do mock interviews. Solving problems alone is not enough. Practice explaining your thought process under time pressure.
5. Review patterns, not solutions. After solving a problem, ask: “What pattern did this use? Where else can I apply it?”

# Track your progress
progress = {
    "two_sum": "green",           # solved independently
    "trapping_rain_water": "yellow",  # needed hint about two pointers
    "serialize_tree": "red",      # needed to see the solution
}

# Revisit yellows after 3 days, reds after 1 day
# A problem isn't "done" until it's green

---

Key Takeaways

1. 75 problems are enough if you understand the patterns. Random grinding of 500 problems is less effective.
2. Pattern recognition > memorization. Learn to map problem clues to techniques.
3. Communication matters more than perfection. A clean O(n log n) solution explained well beats an O(n) solution with no explanation.
4. Edge cases show maturity. Handling empty input, single elements, and boundary conditions signals an experienced engineer.
5. Practice under pressure. Set a 25-minute timer. If you cannot solve it, study the solution and re-solve in 3 days.