Data Structures and Algorithms Roadmap
Data structures and algorithms sit at the centre of most software engineering interviews. Front-end, back-end, mobile and machine learning candidates alike usually face at least one round of solving a problem in code while explaining their thinking.
This roadmap starts with complexity analysis and the basic structures, then moves through sorting and searching, and spends most of its time on interview patterns: hashing, two pointers, sliding window, intervals, monotonic stacks, fast and slow pointers, heaps, tree traversal, BFS and DFS, topological sort, union-find, shortest paths, backtracking, greedy and dynamic programming. Each pattern lists the clues that point to it and the well-known problems that use it.
By the end you will be able to recognise the right pattern quickly, write a correct solution in your chosen language, state its cost and talk through trade-offs. Solve problems in coding practice and turn this page into a weekly schedule with study plan.
- Level
- Beginner to advanced
- Time
- 16–22 weeks at about 8 hours a week; less if you already program daily
- Scope
- 58 topics in 10 stages
- Before you start
- Basic programming in one language such as Python Roadmap, Java Roadmap or Modern C++ Roadmap; School-level algebra: exponents and logarithms; Comfort running code from an editor or terminal
What you will be able to do
- State the time and space complexity of any solution you write and explain the trade-off.
- Choose the right data structure for a task and know the cost of each of its operations.
- Recognise the main interview patterns from the wording of a problem.
- Solve medium problems in 25–35 minutes with clean, tested code.
- Model problems as graphs and apply BFS, DFS, topological sort, union-find and Dijkstra.
- Build dynamic programming solutions from a recursive idea, then optimise their memory.
- Communicate clearly in a live coding interview: clarify, plan, code, test.
The roadmap at a glance
- Stage 1Foundations: Language, Complexity and RecursionBeginner · 2–3 weeks · 9 topics
- Stage 2Basic Data StructuresBeginner · 2 weeks · 5 topics
- Stage 3Searching, Sorting and Divide and ConquerBeginner · 2 weeks · 7 topics
- Stage 4Array and String PatternsIntermediate · 3 weeks · 7 topics
- Stage 5Linked List and Heap PatternsIntermediate · 1–2 weeks · 4 topics
- Stage 6Trees and TriesIntermediate · 2–3 weeks · 6 topics
- Stage 7GraphsIntermediate · 3 weeks · 7 topics
- Stage 8Backtracking and Greedy AlgorithmsIntermediate · 2 weeks · 3 topics
- Stage 9Dynamic Programming and Bit ManipulationAdvanced · 3–4 weeks · 4 topics
- Stage 10Advanced Data Structures and Interview ReadinessAdvanced · 2–3 weeks, then ongoing · 6 topics
Stage 1 Foundations: Language, Complexity and Recursion
Goal. Write clean code in one language and state the time and space cost of any simple function.
Pick a Language Core
Choose one language and use it for every problem; C works but makes you build every container yourself. Python is the common choice for interviews because it is short to write and has a built-in hash map, set, deque and heap. Java and C++ are equally accepted and make you think about types and memory. JavaScript, Go, C#, Ruby and Rust are fine as long as you know the standard library cold.
What matters is fluency: you should never pause to remember how to sort a list of pairs, take a slice or pop from a priority queue. Learn the language syntax for collections, string handling and integer limits. In Java and C++, watch for overflow; in Python, integers grow without limit, which hides overflow bugs the interviewer may ask about.
Practice. Write a cheat sheet of the ten collection operations you use most, with their cost, in your chosen language.
Programming Fundamentals Core
Before data structures, make sure the basics are automatic. Control structures (if, loops, early return, break and continue), functions with parameters and return values, and OOP basics such as classes, fields and methods are enough. Interviewers often ask you to design a small class, for example a MinStack or an LRUCache, so you must be able to write one with a constructor and a few methods without fuss.
Practice. Write a small BankAccount class with deposit, withdraw and a history list, then test it with five calls.
Pseudo Code and Problem Solving Techniques Core
Strong candidates do not start typing straight away. They restate the problem, ask about input size and edge cases, work through one small example by hand, and then write short pseudo code: plain numbered steps that show the idea without syntax. Only then do they code.
A dependable routine for any problem:
- Clarify inputs, outputs and limits (empty input, duplicates, negative numbers).
- State the brute force solution and its cost.
- Look for the repeated work and pick a pattern that removes it.
- Write pseudo code and check it on the example.
- Code, then test with an edge case out loud.
Practice. Take any easy problem and write only the five steps above on paper before touching a keyboard.
What are Data Structures? Core
A data structure is a way of arranging values in memory so that the operations you care about are cheap. An array keeps items side by side, so reading index 500 is instant but inserting at the front means shifting everything. A hash table finds a key in about one step but keeps no order. A heap always knows its smallest item but cannot search quickly.
The importance of data structures in interviews is simple: most optimal solutions are a brute force idea plus the right structure. Turning a nested loop into one pass usually means storing what you have seen in a set or map. Learn each structure as a list of operations and their costs, not as a definition.
Practice. For array, linked list, hash table and heap, write the cost of insert, delete, search and find-min in a table.
Big O Notation and Asymptotic Notation Core
Algorithmic complexity is the study of how much time and memory code needs. Asymptotic notation describes how running time or memory grows as the input size n grows, ignoring constant factors. Big O Notation gives an upper bound: the algorithm grows no faster than this. Big-Ω Notation gives a lower bound, and Big-θ Notation gives a tight bound when the upper and lower bounds match.
In interviews, people say "Big O" and mean the tight worst case, so "binary search is O(log n)" is the expected answer. Drop constants and lower terms: 3n² + 5n + 2 is O(n²). Be ready to give best, average and worst cases separately for quick sort and hash tables, because that is where the distinction matters.
Practice. Write the Big O of five snippets from your own past code and justify each in one sentence.
How to Calculate Complexity? Core
Count how many times the innermost work runs, as a function of the input size. Rules that cover most interview code:
- Sequential blocks add: O(n) followed by O(n log n) is O(n log n).
- Nested loops over the same input multiply: O(n²).
- A loop that halves the range each time is O(log n).
- Recursion: count calls times work per call. A function that calls itself twice on n − 1 is O(2ⁿ).
- Amortised cost: appending to a dynamic array is O(1) on average, even though a resize sometimes copies everything.
Two inputs need two variables. Comparing every word in list A with list B is O(a · b), not O(n²).
Practice. For the recursive Fibonacci function, draw the call tree for n = 5 and count the calls.
Common Complexity Classes Core
Know these growth rates and an example of each, from fastest to slowest:
- Constant, O(1): hash map lookup, array index.
- Logarithmic, O(log n): binary search, heap push.
- Linear, O(n): one pass over an array.
- O(n log n): good comparison sorts.
- Polynomial, O(n²) or O(n³): nested loops, simple DP on two strings.
- Exponential, O(2ⁿ): all subsets.
- Factorial, O(n!): all permutations.
Use the input limits as a hint. If n can be 100,000, the interviewer expects O(n log n) or better. If n is at most 20, an exponential search over subsets is probably intended.
Practice. Given limits n ≤ 10, n ≤ 1,000 and n ≤ 1,000,000, write which complexity class each one suggests.
Time vs Space Complexity Core
Space complexity counts the extra memory an algorithm needs beyond the input. A hash set of seen values costs O(n) space; two index variables cost O(1). Recursion uses space too: each active call sits on the call stack, so a recursive DFS on a tree of height h uses O(h) space.
Many interview problems are a trade between the two. Two Sum with nested loops costs O(n²) time but no memory; with a hash map it drops to O(n) time while storing up to n entries. Say both out loud, pick one, and mention the other. If the interviewer asks for constant space, look for two pointers, in-place swaps or a sorted input.
Practice. Solve "find a duplicate in an array" once with a set and once by sorting, and state the time and space of each.
Recursion Core
A recursive function solves a problem by calling itself on a smaller version. It must have a stopping condition, and each call must shrink the input towards that condition. Trees, backtracking, divide and conquer and top-down DP are all built on recursion, so it must feel natural.
def power(x, n):
if n == 0:
return 1
half = power(x, n // 2)
return half * half if n % 2 == 0 else half * half * xThis is the idea behind the Pow(x, n) problem: halve the exponent each call, so it runs in O(log n). Watch the recursion depth limit (around 1,000 frames by default in Python) on long inputs; convert to a loop with an explicit stack if needed.
Practice. Write recursive functions for sum of a list, reverse a string and fast power, each with a clear base case.
Stage 2 Basic Data Structures
Goal. Pick between the five everyday containers and quote the cost of every operation on them.
Array Core
An array stores items in one contiguous block, so reading or writing by index is O(1). Dynamic arrays (Python list, Java ArrayList, C++ vector) grow by allocating a bigger block and copying, which keeps appends O(1) amortised. Inserting or deleting in the middle shifts later items and costs O(n).
Strings behave like arrays of characters. In Python and Java they are immutable, so building a string with += in a loop can be O(n²); collect pieces in a list and join once. Two-dimensional arrays (grids) are common: know how to loop over rows and columns and how to check the four neighbours of a cell without going out of bounds.
Practice. Implement a tiny dynamic array class with append and get that doubles its capacity when full.
Linked Lists Core
A linked list is a chain of small node objects; every node carries its data plus a reference to its successor, and in a doubly linked list also its predecessor. Inserting or removing a node you already hold is O(1), but reaching the k-th node is O(k) because you must walk from the head.
Interviews use linked lists to test pointer handling. Use a dummy head node to avoid special cases when the first node changes. Draw boxes and arrows before you code. The classic problems: Reverse Linked List, Merge Two Sorted Lists, Reorder List, removing the n-th node from the end, and detecting a cycle.
def reverse(head):
prev = None
while head:
head.next, prev, head = prev, head, head.next
return prev
Practice. Reverse a linked list both iteratively and recursively, then merge two sorted lists using a dummy head.
Stacks Core
A stack is last in, first out: push and pop at the top in O(1). Use a list in Python, ArrayDeque in Java. Stacks appear whenever the most recent unfinished item must be handled first: matching brackets, undo, evaluating expressions and iterative DFS.
Valid Parentheses is the starter problem: push opening brackets, and on a closing bracket check that the top matches. Min Stack asks for O(1) getMin; keep a second stack of the minimum so far. Generate Parentheses is really backtracking, but the "open count must stay ahead of close count" rule is stack thinking.
Practice. Solve Valid Parentheses and Min Stack, then evaluate a postfix expression such as 3 4 + 2 *.
Queues Core
A queue is first in, first out: add at the back, remove from the front. Use collections.deque in Python or ArrayDeque in Java; removing from the front of a plain Python list is O(n). A deque (double-ended queue) allows O(1) operations at both ends, which the monotonic queue pattern needs.
Queues drive breadth first search, level order traversal of trees and simple scheduling. A priority queue is different: it removes the smallest (or largest) item rather than the oldest, and is built on a heap, covered later.
Practice. Implement a queue using two stacks and explain why each operation is O(1) amortised.
Hash Tables Core
A hash table maps keys to values. A hash function turns the key into a bucket index, so insert, delete and lookup take O(1) on average. Collisions are handled by chaining (a list per bucket) or open addressing (probe for the next free slot). When the table fills past a load factor it resizes, which is why the cost is amortised. In the worst case, with many collisions, operations degrade to O(n).
Keys must be immutable and hashable: tuples work in Python, lists do not. Hash sets are the same idea without values. Plain hash maps give no ordering; if you need sorted keys use a balanced tree map such as Java TreeMap.
Practice. Write a hash map with chaining from scratch with put, get and remove, and a resize at load factor 0.75.
Stage 3 Searching, Sorting and Divide and Conquer
Goal. Implement the main search algorithms and sorting algorithms and explain their trade-offs.
Linear Search and Brute Force Core
Linear search checks each item in turn until it finds the target: O(n), works on any data, needs no sorting. Brute force is the same mindset applied to a whole problem: try every candidate. Brute force is your starting point in every interview, not a failure. Say it, give its cost, and then improve it.
Often the brute force for a pair problem is two nested loops, O(n²). Ask what the inner loop is searching for. If it is a value, a hash set finds it in O(1). If the data is sorted, binary search or two pointers find it faster.
Practice. For Contains Duplicate, write the O(n²) brute force first, then the O(n) set version, and compare.
Binary Search Core
Binary search finds a target in a sorted array by comparing with the middle item and discarding half the range each step: O(log n). Off-by-one bugs are the main risk, so learn one template and stick to it.
def lower_bound(a, target):
lo, hi = 0, len(a) # answer is in [lo, hi]
while lo < hi:
mid = (lo + hi) // 2
if a[mid] < target:
lo = mid + 1
else:
hi = mid
return lo # first index with a[mid] >= targetThe bigger idea is searching on the answer: if a yes/no test is monotonic, binary search the smallest value that passes. Koko Eating Bananas is the classic: binary search the eating speed. Also practise Search in Rotated Sorted Array, Find Minimum in Rotated Sorted Array and, for a hard one, Median of Two Sorted Arrays.
Practice. Solve Koko Eating Bananas and Find Minimum in Rotated Sorted Array with the template above.
Simple Sorts: Bubble, Selection and Insertion Recommended
These O(n²) sorts are rarely used in practice but interviewers ask about them to check your basics.
- Bubble Sort swaps neighbouring items that are out of order, pass after pass, until no swaps happen.
- Selection Sort finds the smallest remaining item and puts it at the front; it does few swaps but is never fast.
- Insertion Sort takes each item and slides it left into place. It is O(n) on nearly sorted data and is fast for tiny arrays, which is why real library sorts switch to it for small ranges.
Know which are stable (bubble and insertion keep equal items in their original order; selection does not).
Practice. Implement insertion sort and count comparisons on a sorted, a reversed and a random array of 1,000 items.
Merge Sort and Divide and Conquer Core
Divide and conquer splits a problem into independent halves, solves each recursively and combines the results. Merge Sort is the model example: split the array in two, sort each half, then merge the two sorted halves in linear time. Total cost is O(n log n) in every case, it is stable, and it needs O(n) extra space.
The merge step is a two-pointer technique you will reuse in Merge Two Sorted Lists and Merge K Sorted Lists. Divide and conquer also counts inversions, finds the closest pair of points and powers fast exponentiation.
Practice. Implement merge sort, then change it to count the number of inversions in the array.
Quick Sort and Randomised Algorithms Core
Quick Sort picks a pivot, partitions the array so smaller items go left and larger items go right, and recurses on each side. It sorts in place and is very fast in practice, with O(n log n) average time. A bad pivot on already sorted data gives O(n²). Picking the pivot at random makes that worst case extremely unlikely for any input; this is the simplest example of randomised algorithms.
The partition step alone solves Kth Largest Element in an Array in O(n) average time (quickselect). Know that Python and Java sort objects with Timsort, a stable merge and insertion hybrid, while many C++ libraries use introsort, a quick sort that falls back to heap sort.
Practice. Implement quickselect with a random pivot and use it to find the median of an unsorted array.
Heap Sort Recommended
Heap Sort builds a max-heap from the array in O(n), then repeatedly swaps the largest item to the end and restores the heap. It runs in O(n log n) in the worst case and uses O(1) extra space, but it is not stable and has poor cache behaviour, so it is slower than quick sort in practice.
Practice. Write a table comparing merge, quick and heap sort on worst-case time, extra space and stability.
Cyclic Sort Recommended
Cyclic sort is a pattern for arrays that hold numbers in a known range such as 1 to n. Each value has a home index (value − 1). Walk the array and keep swapping the current value into its home until the current slot holds the right value. Every swap places one number for good, so the whole pass is O(n) with O(1) space.
After the pass, any index whose value does not match is a clue. This solves "find the missing number", "find all duplicates" and "first missing positive" without extra memory.
Practice. Use cyclic sort to find the smallest missing positive integer with one pass of swaps and no extra array.
Stage 4 Array and String Patterns
Goal. Recognise and apply the hashing, two pointer, sliding window, interval and monotonic stack patterns.
What are Coding Patterns? Core
A coding pattern is a reusable shape of solution that fits many problems. Instead of memorising hundreds of answers, you learn about fifteen patterns and the clues that point to each. "Sorted array and a pair that sums to a target" points to two pointers. "Longest substring with a condition" points to sliding window. "Number of ways" or "minimum cost" with overlapping choices points to dynamic programming.
Group your practice by pattern, solve three to five problems per pattern, then mix them so you also practise recognising which pattern applies. The plan builder in study plan orders patterns this way, and coding practice lets you solve them with tests.
Practice. For ten problems you have already solved, write the clue in the statement that pointed to the pattern.
Arrays & Hashing Core
The most common first pattern: store what you have seen in a hash map or set so later lookups are O(1). Two Sum keeps a map from value to index and checks whether target - x is already there. Contains Duplicate and Valid Anagram are counting problems. Group Anagrams uses the sorted word (or a tuple of 26 letter counts) as a key. Top K Frequent Elements counts with a map, then uses a heap or bucket sort by frequency. Longest Common Prefix compares characters column by column.
def two_sum(nums, target):
seen = {}
for i, x in enumerate(nums):
if target - x in seen:
return [seen[target - x], i]
seen[x] = iPrefix sums belong here too: a running total plus a map of earlier totals counts subarrays that sum to k in O(n).
Practice. Solve Two Sum, Group Anagrams and Top K Frequent Elements, each in O(n) or O(n log k).
Two Pointer Technique Core
Two pointers move through a sequence from both ends, or at different speeds, to avoid a nested loop. On a sorted array, put one pointer at each end: if the sum is too small move the left pointer right, if too large move the right pointer left. That solves Two Sum II in O(n) with O(1) space.
3Sum fixes one number, then runs two pointers on the rest, skipping duplicates: O(n²). Valid Palindrome compares characters from both ends. Container With Most Water always moves the shorter side, because the taller side can never give a bigger area with a narrower width. Trapping Rain Water tracks the highest wall seen from each side and moves the lower side inwards.
Practice. Solve Valid Palindrome, 3Sum and Container With Most Water, and explain why moving the shorter side is safe.
Sliding Window Technique Core
A sliding window keeps a range [left, right] over an array or string. Extend the right edge one step at a time, and shrink from the left whenever the window breaks the rule. Each index enters and leaves once, so the scan is O(n).
def longest_unique(s):
last, left, best = {}, 0, 0
for right, ch in enumerate(s):
if ch in last and last[ch] >= left:
left = last[ch] + 1
last[ch] = right
best = max(best, right - left + 1)
return bestThis is Longest Substring Without Repeating Characters. Longest Repeating Character Replacement keeps letter counts and shrinks when window length minus the top count exceeds k. Minimum Window Substring shrinks while the window still covers every needed letter. Best Time to Buy and Sell Stock is a one-pass window over the lowest price so far. Sliding Window Maximum needs a deque, shown in the next topic.
Practice. Solve Longest Repeating Character Replacement and Minimum Window Substring with the grow-then-shrink template.
Monotonic Stack and Queue Core
A monotonic stack keeps its items in increasing or decreasing order. When a new item breaks the order, you pop, and each pop answers a question about the popped item, such as "what is my next greater value". Every index is pushed and popped once, so it is O(n).
Daily Temperatures keeps a stack of days still waiting for a warmer day. Largest Rectangle in Histogram keeps increasing heights; when a shorter bar arrives, each popped bar knows its width. A monotonic deque solves Sliding Window Maximum: keep indices with decreasing values, drop the front when it leaves the window, and the front is always the maximum.
Practice. Solve Daily Temperatures, then Sliding Window Maximum with a deque, and explain why both are O(n).
Merge Intervals Core
Interval problems give you pairs [start, end]. Almost all of them start by sorting by start time. Merge Intervals then walks the list and extends the last merged interval while the next one overlaps. Insert Interval adds one interval to a sorted, non-overlapping list in three phases: before, overlapping, after.
Non-overlapping Intervals asks for the fewest removals; sort by end time and greedily keep the interval that finishes first. Meeting Rooms asks whether one person can attend everything (check neighbours after sorting); the follow-up asks how many rooms are needed (a min-heap of end times, or a sweep over sorted starts and ends). Minimum Interval to Include Each Query combines sorting queries with a heap.
Practice. Solve Merge Intervals, Insert Interval and the "how many meeting rooms" follow-up.
Matrix Problems: Math and Geometry Recommended
Grid manipulation questions test careful indexing more than clever ideas. Rotate Image rotates an n × n matrix 90 degrees in place: transpose it, then reverse each row. Spiral Matrix walks the boundary with four shrinking limits (top, bottom, left, right). Set Matrix Zeroes avoids extra memory by recording which rows and columns to clear inside row 0 and column 0 themselves.
Other math and geometry items: greatest common divisor with Euclid's algorithm, checking for primes up to √n, modular arithmetic to keep numbers small, Happy Number (detect a cycle in digit-square sums) and Pow(x, n).
Practice. Solve Rotate Image and Spiral Matrix, testing on 1 × 1, 2 × 3 and 4 × 4 inputs.
Stage 5 Linked List and Heap Patterns
Goal. Solve pointer problems with fast and slow pointers and use heaps for top-k, merging and running medians.
Fast and Slow Pointers Core
Move one pointer one step and another two steps. If there is a cycle, the fast pointer eventually lands on the slow one (Floyd's algorithm). Without a cycle, the fast pointer reaches the end. When the fast pointer reaches the end of a list, the slow pointer is in the middle.
Linked List Cycle is the direct use. Happy Number applies it to a number sequence instead of nodes. Reorder List combines three steps you already know: find the middle with fast and slow pointers, reverse the second half, then weave the two halves together. Finding the start of a cycle uses one more trick: after they meet, reset one pointer to the head and move both one step at a time.
Practice. Solve Linked List Cycle, Happy Number and Reorder List.
Heap Core
A binary heap is a complete binary tree stored in an array where every parent is smaller than its children (a min-heap). Children of index i live at 2i + 1 and 2i + 2. Peeking at the minimum is O(1); push and pop are O(log n) because an item moves up or down one level at a time. Building a heap from n items is O(n).
Python's heapq is a min-heap only; push negated values for a max-heap, and push tuples to sort by a key. Java has PriorityQueue, C++ has priority_queue (a max-heap by default).
Practice. Implement a min-heap from scratch with push and pop, then compare its output with your language's built-in heap.
Heaps and Priority Queue: Kth Element Core
To find the k largest items, keep a min-heap of size k: push each item and pop when the size exceeds k. The heap top is then the k-th largest. This is O(n log k) and works on streams. Kth Largest Element in an Array, K Closest Points to Origin (heap on distance) and Top K Frequent Elements all use it.
Merge K Sorted Lists pushes the head of each list into a min-heap and repeatedly pops the smallest, pushing its successor: O(N log k). Task Scheduler can be solved with a max-heap of remaining counts plus a cooldown queue, or with a short counting formula.
Practice. Solve K Closest Points to Origin with a heap of size k, then Merge K Sorted Lists.
Two Heaps Recommended
Keep a max-heap for the smaller half of the numbers and a min-heap for the larger half, with sizes differing by at most one. The median is the top of the larger heap, or the average of both tops. Each insert is O(log n) and each median query is O(1).
Find Median from Data Stream is the classic. The same idea solves sliding window medians (with lazy deletion) and scheduling problems where you pick the cheapest available project that fits your current capital.
import heapq
lo, hi = [], [] # lo is a max-heap via negatives
def add(x):
heapq.heappush(lo, -x)
heapq.heappush(hi, -heapq.heappop(lo))
if len(hi) > len(lo):
heapq.heappush(lo, -heapq.heappop(hi))
Practice. Solve Find Median from Data Stream and test it with an even and an odd number of values.
Stage 6 Trees and Tries
Goal. Traverse binary trees recursively and iteratively, reason about binary search trees and build tries.
Tree Data Structures and Binary Trees Core
A tree is a set of nodes connected without cycles, with one root. In binary trees each node has at most two children. Terms to know: depth (distance from the root), height (longest path down to a leaf), leaf, subtree, and balanced (heights of subtrees differ by little). A tree with n nodes has n − 1 edges.
Most tree problems are solved by asking: "if I knew the answer for the left and right subtrees, how would I build the answer for this node?" Maximum Depth of Binary Tree is 1 + max(depth(left), depth(right)). Same Tree, Invert Tree and Subtree of Another Tree all follow this shape.
Practice. Write maximum depth, invert tree and "are two trees identical" recursively in under ten lines each.
Tree Traversals Core
Depth-first orders differ only in when you visit the node:
- Pre-Order Traversal: node, left, right. Good for copying or serialising a tree.
- In-Order Traversal: left, node, right. On a binary search tree it gives sorted order.
- Post-Order Traversal: left, right, node. Good when a node needs its children's results first, such as deleting a tree or computing heights.
Binary Tree Level Order Traversal is breadth-first: use a queue and process one level at a time by reading the queue length before the inner loop.
Practice. Write all three depth-first traversals recursively and in-order iteratively, then level order with a queue.
Depth-First Problems on Trees Core
Harder tree questions return more than one value from each call. Binary Tree Maximum Path Sum computes, for each node, the best downward path through it (returned to the parent) and the best path that bends at it (compared against a global maximum). Diameter of a tree uses the same split.
Serialize and Deserialize Binary Tree writes a pre-order list with a marker for empty children, such as 1,2,#,#,3,#,#, and rebuilds it by reading tokens in the same order. Validating a binary search tree passes down a lower and upper bound rather than comparing only with direct children.
Practice. Solve Binary Tree Maximum Path Sum and Serialize and Deserialize Binary Tree.
Binary Search Trees Core
In a binary search tree every key in the left subtree is smaller than the node and every key on the right is larger. Search, insert and delete follow one path down, so they cost O(h): O(log n) when balanced and O(n) when the tree degenerates into a line, for example after inserting sorted keys.
Lowest Common Ancestor of a BST walks down from the root: if both values are smaller go left, if both are larger go right, otherwise the current node is the answer. Kth smallest element is an in-order traversal that stops after k nodes. Deletion of a node with two children replaces it with its in-order successor.
Practice. Solve Lowest Common Ancestor of a BST and Kth Smallest Element in a BST, then implement delete.
Balanced Trees: AVL Trees and B-Trees Recommended
Self-balancing trees keep height at O(log n) after every change. AVL Trees store a height per node and rotate when the left and right heights differ by more than one; they are strictly balanced and fast to search. Red-black trees allow a little more imbalance with fewer rotations and back many library tree maps.
B-Trees are wide trees designed for disks: each node holds many sorted keys and many children, so a lookup touches few pages. B/B+ Trees, the variant where all values sit in linked leaves, are the default index structure in relational databases because range scans just walk the leaves. You will rarely implement these in interviews, but you should explain rotations and why databases use B+ trees.
Practice. Insert 1 to 7 in order into an AVL tree on paper and draw each rotation.
Trie Core
A trie (prefix tree) stores strings character by character. Each node has a map of children and a flag marking the end of a word. Insert and lookup cost O(L) for a word of length L, independent of how many words are stored, and every prefix query is natural.
class Trie:
def __init__(self):
self.root = {}
def insert(self, word):
node = self.root
for ch in word:
node = node.setdefault(ch, {})
node['$'] = TruePractise Implement Trie, Design Add and Search Words Data Structure (a dot matches any letter, so branch with DFS), Replace Words (swap each word for its shortest root) and Word Search II (walk the grid and the trie together, pruning finished words).
Practice. Solve Implement Trie, then Word Search II, and remove found words from the trie to speed it up.
Stage 7 Graphs
Goal. Model problems as graphs and apply BFS, DFS, topological sort, union-find, shortest paths and spanning trees.
Graph Data Structure Core
A graph is a set of vertices joined by edges. In a Directed Graph edges have a direction (A follows B); in an Undirected Graph they go both ways (A and B are friends). Edges may carry weights such as distance or cost.
Store graphs as an adjacency list (a map from each vertex to its neighbours), which uses O(V + E) memory and suits sparse graphs. An adjacency matrix uses O(V²) and suits dense graphs or quick edge checks. Many interview graphs are hidden: a grid is a graph whose cells link to four neighbours, and a word puzzle is a graph whose words link when they differ by one letter.
Practice. Build an adjacency list from an edge list and print each vertex's neighbours, for both directed and undirected input.
Breadth First Search and Depth First Search Core
Depth First Search goes as deep as possible before backing up; write it recursively or with a stack. Breadth First Search visits vertices in rings of increasing distance using a queue, so in an unweighted graph it finds the shortest path. Both run in O(V + E). Always keep a visited set, and mark a node when you add it to the queue, not when you pop it, to avoid duplicates.
from collections import deque
def bfs(start, graph):
dist, q = {start: 0}, deque([start])
while q:
u = q.popleft()
for v in graph[u]:
if v not in dist:
dist[v] = dist[u] + 1
q.append(v)
return distClone Graph uses either, with a map from old node to copy. Word Ladder is BFS over words.
Practice. Solve Clone Graph with DFS and Word Ladder with BFS.
Island Traversal Core
Grid flood fill is one of the most frequent interview patterns. Number of Islands loops over every cell; when it finds unvisited land it starts a DFS or BFS that marks the whole island, and adds one to the count. The cost is O(rows × columns).
Variations change the start point or what you track. Max Area of Island returns the size of each fill. Pacific Atlantic Water Flow runs the search backwards, from each ocean's edge uphill, and returns cells reached from both. Rotting Oranges is multi-source BFS: put every rotten orange in the queue at time zero. Surrounded Regions marks border-connected cells first, then flips the rest.
Practice. Solve Number of Islands, then Pacific Atlantic Water Flow by searching from the edges inwards.
Topological Sort Core
A topological order lists the vertices of a directed acyclic graph so that every edge points forward. Kahn's algorithm counts incoming edges, starts a queue with every vertex that has none, and removes vertices one by one, decrementing their neighbours' counts. If some vertices are never removed, the graph has a cycle.
Course Schedule asks whether all courses can be finished, which is exactly cycle detection in a prerequisite graph; the follow-up asks for an order. Alien Dictionary builds the graph from adjacent words. Reconstruct Itinerary is different: it needs an Euler path using every edge once, found with a DFS that adds airports after exploring their tickets (Hierholzer's algorithm).
Practice. Solve Course Schedule with Kahn's algorithm and again with DFS three-colour cycle detection.
Disjoint Set (Union-Find) Core
Union-find tracks which items belong to the same group. find returns a group's representative; union merges two groups. Add path compression (or halving) and union by size, and each call costs almost nothing amortised.
parent = list(range(n))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]] # path halving
x = parent[x]
return x
def union(a, b):
ra, rb = find(a), find(b)
if ra == rb: return False # already joined: a cycle
parent[ra] = rb; return TrueUse it for counting connected components, detecting a cycle in an undirected graph (Redundant Connection) and Kruskal's algorithm.
Practice. Solve Number of Connected Components and Redundant Connection with union-find.
Shortest Paths: Dijkstra's Algorithm, Bellman-Ford and A* Core
For weighted graphs with non-negative weights, Dijkstra's Algorithm repeatedly takes the closest unsettled vertex from a min-heap and relaxes its edges: O((V + E) log V). Network Delay Time is a direct application. Swim in Rising Water is Dijkstra where the path cost is the maximum height seen.
Bellman-Ford relaxes every edge V − 1 times, so it is O(V · E), but it handles negative weights and detects negative cycles. Cheapest Flights Within K Stops is a Bellman-Ford variant limited to k + 1 rounds. The A* Algorithm is Dijkstra guided by a heuristic estimate of remaining distance, such as straight-line distance on a map; with an admissible heuristic it still finds the shortest path while exploring far fewer vertices.
Practice. Solve Network Delay Time with Dijkstra and Cheapest Flights Within K Stops with limited Bellman-Ford rounds.
Minimum Spanning Trees: Prim's Algorithm and Kruskal's Algorithm Recommended
A minimum spanning tree connects every vertex of a weighted undirected graph with the smallest total edge weight. Kruskal's Algorithm sorts edges by weight and adds each one unless union-find says it would form a cycle: O(E log E). Prim's Algorithm grows one tree from a start vertex, always adding the cheapest edge leaving it, using a min-heap.
Min Cost to Connect All Points is the standard interview version, where every pair of points is an edge weighted by Manhattan distance. With a dense graph, Prim with a simple array is O(V²) and avoids building all the edges. These problems sit in the Advanced Graphs group with shortest paths.
Practice. Solve Min Cost to Connect All Points once with Kruskal and once with Prim, and compare speed.
Stage 8 Backtracking and Greedy Algorithms
Goal. Generate all valid combinations with pruning, and recognise when a greedy choice is provably safe.
Backtracking Core
Backtracking builds a solution one choice at a time, recurses, then undoes the choice and tries the next. It explores a tree of decisions and prunes branches that cannot succeed. The cost is usually exponential, so the input sizes are small.
def subsets(nums):
out, path = [], []
def go(i):
if i == len(nums):
out.append(path[:]); return
path.append(nums[i]); go(i + 1) # take
path.pop(); go(i + 1) # skip
go(0)
return outLearn three templates: Subsets (take or skip), Permutations (pick any unused item) and Combination Sum (reuse allowed, start index stays). Generate Parentheses prunes when close count would exceed open count.
Practice. Solve Subsets, Permutations and Combination Sum, writing the decision tree for a tiny input first.
Backtracking on Grids and Boards Core
Word Search runs DFS from each cell, marks the cell as used while exploring, and restores it on the way back. N-Queens places one queen per row and keeps sets of used columns and both diagonals (row − col and row + col) so each placement check is O(1).
The same structure solves Sudoku and the knight's tour. Pruning is what makes them practical: check constraints before recursing, not after.
Practice. Solve Word Search and N-Queens, and count how many recursive calls your pruning saves.
Greedy Algorithms Core
A greedy algorithm makes the best local choice at each step and never revisits it. It is correct only when you can argue that a local choice never blocks the best overall answer; this is usually shown with an exchange argument ("swapping my choice into any optimal solution keeps it optimal").
- Jump Game: track the furthest reachable index.
- Jump Game II: BFS by ranges, count how many times you must extend the range.
- Gas Station: if total gas covers total cost, start after the point where the running tank went negative.
- Partition Labels: record each letter's last index and cut when the current index reaches the furthest last index seen.
- Maximum Subarray (Kadane): drop the running sum when it goes negative.
If you cannot justify the greedy choice, it is probably a DP problem. Coin Change is the classic trap.
Practice. Solve Jump Game, Gas Station and Partition Labels, and write one sentence proving each greedy step is safe.
Stage 9 Dynamic Programming and Bit Manipulation
Goal. Turn recursive solutions with overlapping subproblems into memoised or tabulated DP, and use bit tricks confidently.
Dynamic Programming Core
Dynamic programming applies when a problem breaks into subproblems that repeat. Instead of recomputing them, you store each answer once. Two styles: top-down memoisation (write the recursion, cache results) and bottom-up tabulation (fill a table from the smallest cases).
A reliable recipe: define the state in words ("dp[i] is the best answer using the first i items"), write the transition, set base cases, decide the order to fill, and find the answer cell. Then check whether you only need the last row or two values, which reduces space.
from functools import cache
@cache
def ways(n): # Climbing Stairs
return 1 if n <= 1 else ways(n - 1) + ways(n - 2)
Practice. Write Climbing Stairs top-down, then bottom-up, then with two variables.
1-D Dynamic Programming Core
One index describes the state. Typical problems:
- House Robber:
dp[i] = max(dp[i-1], dp[i-2] + nums[i]). - Coin Change: fewest coins for each amount from 0 up, trying every coin.
- Word Break:
dp[i]is true if some dictionary word ends at i anddp[start]is true. - Longest Increasing Subsequence: O(n²) DP, or O(n log n) with a list of smallest tails and binary search.
- Decode Ways and Maximum Product Subarray are good extra drills.
Coin Change shows why greedy fails: with coins 1, 3 and 4, making 6 greedily gives 4+1+1, while DP finds 3+3.
Practice. Solve House Robber, Coin Change and Word Break, writing the state definition in a comment first.
2-D Dynamic Programming Core
Two indices describe the state, usually positions in two strings or a grid. Unique Paths fills a grid: the count for a cell adds the counts arriving from above and from its left neighbour. Longest Common Subsequence uses dp[i][j] for prefixes of both strings: if the characters match, add one to the diagonal; otherwise take the better of dropping one character.
Edit Distance adds insert, delete and replace to the same table. Regular Expression Matching handles * by either using zero copies of the previous pattern character or consuming one text character. Burst Balloons is interval DP: choose the balloon burst last in a range, so the left and right parts become independent. 0/1 knapsack is the template for "choose items under a capacity".
Practice. Solve Unique Paths, Longest Common Subsequence and Edit Distance, then reduce one of them to O(n) space.
Bit Manipulation Recommended
Bitwise operators work on the binary form of integers: AND &, OR |, XOR ^, NOT ~, and shifts << and >>. Useful facts: x & (x - 1) clears the lowest set bit; x ^ x is 0; x & 1 tests odd.
Single Number XORs every value so pairs cancel. Number of 1 Bits clears the lowest bit until zero. Counting Bits uses bits[i] = bits[i >> 1] + (i & 1). Reverse Bits shifts bits out of one number into another 32 times. Sum of Two Integers adds without + using XOR for the sum and AND plus shift for the carry; in Python you must mask to 32 bits because integers are unbounded. Bitmasks also represent subsets in DP over small sets.
Practice. Solve Single Number, Counting Bits and Sum of Two Integers.
Stage 10 Advanced Data Structures and Interview Readiness
Goal. Know the specialised structures interviewers mention, and run a timed practice routine until you are ready.
Segment Trees and Fenwick Trees Optional
Both answer range queries on an array that also changes. A Fenwick tree (binary indexed tree) stores partial sums in a clever array layout so that both a point update and a prefix sum take O(log n), in very little code. Segment Trees store an answer for each range in a binary tree, so they handle range minimum, maximum or sum, and with lazy propagation they support range updates too.
These complex data structures appear in harder interviews and in competitive programming. If a problem says "many updates and many range queries" and n is large, mention them. Know that a prefix sum array is enough when there are no updates.
Practice. Implement a Fenwick tree for prefix sums and use it to count, for each item, how many smaller items come after it.
Skip List Optional
A skip list is a sorted linked list with extra express lanes. Each node is promoted to the next level up with probability one half, so the top levels skip over long runs. Search, insert and delete take O(log n) expected time, much like a balanced tree, but the code is simpler and it is easier to make concurrent.
Redis uses skip lists for sorted sets. In interviews it appears as a design question ("design a skip list") or as a follow-up when you mention balanced trees.
Practice. Implement a skip list with search and insert, using random level promotion.
Suffix Trees and Arrays Optional
A suffix array is the sorted list of every suffix of a string, stored as starting indices. With a companion LCP array (longest common prefix of neighbours) it answers substring search by binary search, finds the longest repeated substring and counts distinct substrings. A suffix tree is a compressed trie of all suffixes and does the same in linear time but uses much more memory. They are rare in interviews; rolling hashes or KMP solve most string questions you will meet.
Practice. Build a suffix array naively by sorting suffixes and use it to find the longest repeated substring of "banana".
Indexing: Linear, ISAM and Tree-Based Optional
Indexing is how large data sets support fast lookups. Linear Indexing keeps a sorted list of (key, position) pairs, small enough to binary search, that points into a larger file. ISAM (indexed sequential access method) is an older static scheme: a fixed multi-level index over sorted data, with overflow areas for inserts; it degrades as data changes, which is why it was replaced.
Tree-Based Indexing with B+ trees adjusts itself on every insert and delete and is the modern default in databases and file systems. This topic links data structures to real systems and comes up when interviewers ask why a database index makes a query fast.
Practice. Explain in five sentences why a B+ tree index beats a sorted file with a linear index when rows are inserted often.
Multi-threaded Algorithms Optional
Some interviews add concurrency questions: print numbers in order from three threads, build a bounded blocking queue, or implement a thread-safe LRU cache. You need locks (mutexes), condition variables or semaphores, and you must explain race conditions and deadlock. Keep it simple: lock around shared state, keep critical sections short and always take multiple locks in the same order.
Practice. Implement a bounded blocking queue with a lock and two condition variables.
Platforms for Practice and a Study Plan Core
Knowledge without timed practice does not pass interviews. Use coding practice to solve problems against tests in your chosen language, and study plan to build a schedule ordered by pattern. A practical routine: one new pattern each few days, three to five problems per pattern, and a weekly mixed set of more exercises under a 45-minute timer.
Keep a log of every problem you failed with the clue you missed, and redo it a week later. Talk aloud while solving, even alone, because interviews grade communication. Do several mock interviews before the real ones. Quality beats volume: 150 problems understood deeply prepare you better than 500 rushed ones.
Practice. Create a four-week plan in study plan and complete the first week's problems with notes on each.
Projects to build
Build these in order. Each one should end up in a public repository with a short README that explains your decisions.
- Personal algorithms libraryBeginner
Write your own implementations of a dynamic array, linked list, stack, queue, hash map and binary heap, each with unit tests. Add a short note on the cost of every method. This becomes your revision sheet before interviews.
Arrays · Hash tables · Heaps · Testing
- Autocomplete serviceIntermediate
Load a word list with frequencies into a trie. Return the top five completions for a prefix using a heap. Add fuzzy matching that allows one typo by branching in the trie, and measure lookup time as the list grows.
Trie · Heap · DFS
- Route planner on a grid mapIntermediate
Represent a city as a weighted grid with blocked cells. Find shortest routes with BFS for equal costs, Dijkstra for weighted roads and A* with Manhattan distance, and show how many cells each one explores.
Graphs · BFS · Dijkstra's Algorithm · A* Algorithm
- Course plannerAdvanced
Read courses and prerequisites from a file, detect impossible plans with topological sort, and schedule courses into the fewest terms with a credit limit per term. Explain which part is greedy and which needs search.
Topological sort · Greedy · Backtracking
- Text diff toolAdvanced
Compare two text files line by line using longest common subsequence and print a diff with added and removed lines. Reduce memory to two rows for large files, and add a word-level edit distance score.
2-D dynamic programming · Edit distance · Space optimisation
Interview questions
Try to answer each question out loud before you open the answer.
What is the difference between an array and a linked list, and when would you choose each?Junior
An array stores items next to each other, so index access is O(1) and it is cache friendly, but inserting in the middle shifts items, O(n). A linked list gives O(1) insert and delete at a node you already hold, but access by position is O(n) and each node costs extra memory for pointers. I pick arrays by default; I pick a linked list when I splice often at known positions, for example the recency list inside an LRU cache.
How does a hash table give O(1) lookups, and when does it not?Junior
The key is hashed to a bucket index, so lookup goes straight to one small bucket. Collisions are handled by chaining or open addressing, and the table resizes when the load factor grows, which keeps buckets short on average. It degrades to O(n) when many keys collide, through a poor hash function or deliberate attack, and a single resize costs O(n), though that is amortised across inserts. It also gives no ordering, so range queries need a tree.
Explain Big O, and what is the complexity of binary search and why?Junior
Big O describes how cost grows with input size, ignoring constants, usually for the worst case. Binary search is O(log n) because each comparison discards half of the remaining range, so after k steps n / 2ᵏ items remain, which reaches one after about log₂ n steps. It needs sorted, randomly accessible data, so it does not help on a linked list.
How do you recognise a sliding window problem?Mid
The question asks about a contiguous subarray or substring, often the longest or shortest one meeting a condition, and the condition can be updated as one element enters or leaves. I keep left and right pointers, extend right each step, and shrink left while the window is invalid, tracking counts in a map. Each index moves at most twice, so the scan is O(n). If elements can be negative and the condition is a sum, a window may not work and I switch to prefix sums.
When does two pointers work, and why is it correct for Two Sum II?Mid
It works when the data is sorted or has an order I can exploit, and moving one pointer rules out a whole set of candidates. In Two Sum II, if the sum of the ends is too small, the left item cannot pair with anything, since the right item is already the largest, so I move left. The symmetric argument applies on the right. Every step discards one item safely, so it is O(n) time with O(1) space.
BFS or DFS: how do you choose?Mid
BFS explores by distance, so I use it for shortest paths in unweighted graphs, level-by-level tree work and multi-source spreading such as Rotting Oranges. DFS goes deep first, and suits exhaustive search, connected components, cycle detection, topological sort and backtracking. Both are O(V + E). DFS recursion can overflow on very deep graphs, so I switch to an explicit stack, and BFS can use a lot of memory on wide graphs.
How would you detect a cycle in a directed graph and in an undirected graph?Mid
Directed: DFS with three colours, unvisited, in progress and done; reaching an in-progress node means a back edge, so a cycle. Alternatively, Kahn's algorithm: if the topological sort cannot remove every node, a cycle exists. Undirected: union-find, where an edge joining two nodes already in the same set closes a cycle, or DFS that ignores the edge back to the parent.
Explain how Dijkstra works and when it fails.Mid
It keeps a min-heap of tentative distances, repeatedly settles the closest vertex and relaxes its outgoing edges. Once a vertex is popped, its distance is final, because all weights are non-negative so no later path can be shorter. With a heap it is O((V + E) log V). It fails with negative edge weights, since a settled vertex could later be improved; then I use Bellman-Ford, which also detects negative cycles.
How do you find the k-th largest element, and what are the trade-offs?Mid
Sorting is O(n log n) and simple. A min-heap of size k is O(n log k) and works on a stream. Quickselect partitions around a random pivot and recurses into one side only, O(n) on average but O(n²) in the worst case and it modifies the array. I would pick the heap for streams or small k, and quickselect for one-off queries on a large array.
Walk me through solving a problem with dynamic programming.Mid
First I write a recursive solution and check whether the same arguments repeat; if so, DP fits. I define the state in words, for example dp[i][j] as the edit distance between the first i and j characters, write the transition from smaller states, set base cases, and choose top-down memoisation or bottom-up order. Then I check the answer cell and see whether only the previous row is needed, cutting space from O(n·m) to O(m).
Greedy or dynamic programming for Coin Change?Mid
DP. Greedy takes the largest coin that fits, which is optimal for some coin systems but not in general: with coins 1, 3 and 4 and amount 6, greedy gives three coins and the answer is two. I fill dp[a] as the fewest coins for amount a, trying each coin, in O(amount × coins). I would use greedy only after proving an exchange argument holds.
Design an LRU cache with O(1) get and put.Mid
Combine a hash map from key to node with a doubly linked list ordered by recent use. Get looks up the node, moves it to the front and returns the value. Put updates or inserts at the front, and if capacity is exceeded, removes the tail node and its map entry. Dummy head and tail nodes avoid edge cases. Python's OrderedDict or Java's LinkedHashMap can do this, but interviewers usually want the manual version.
How would you find the median of a stream of numbers?Senior
I split the numbers across two heaps. Small values live in a max-heap, large values in a min-heap, and I rebalance so the sizes never differ by more than one. Each insert goes through one heap to the other to keep order, then rebalances, O(log n). The median is the top of the larger heap or the average of both tops, O(1). If values are small integers in a known range, a counting array is simpler.
How do you approach a problem you have never seen in an interview?Junior
I restate it, ask about input size and edge cases, and work a small example by hand. I give a brute force with its cost, then look at where it repeats work and which structure or pattern removes that: sorting, hashing, two pointers, a heap, a graph model or DP. I agree the approach with the interviewer before coding, code in small functions, and test with a normal case and an edge case out loud.
Common mistakes
- Jumping into code before clarifying the problem; spend the first few minutes on examples, limits and edge cases.
- Memorising solutions to individual problems; learn the pattern and the clue that triggers it instead.
- Ignoring the input limits, which usually tell you the complexity the interviewer expects.
- Forgetting the visited set in graph searches, causing infinite loops; mark nodes when you enqueue them.
- Off-by-one errors in binary search; use one template with a clear invariant every time.
- Applying a greedy idea without proof; test it on a small counterexample or switch to DP.
- Writing DP tables without defining the state in words first; write the definition as a comment before coding.
- Staying silent while thinking; narrate your reasoning so the interviewer can follow and help.
- Only practising without a timer; do regular timed sessions to build speed under pressure.
Ready-for-interview checklist
- I can state time and space complexity for any solution I write.
- I can implement a hash map, heap, trie and union-find from scratch.
- I can write binary search, including search on the answer, without off-by-one bugs.
- I can solve sliding window and two pointer problems in under 25 minutes.
- I can write tree traversals recursively and iteratively, and level order with a queue.
- I can run BFS and DFS on grids and adjacency lists and explain when each fits.
- I can detect cycles and produce a topological order.
- I can implement Dijkstra and explain why it fails with negative weights.
- I can write backtracking for subsets, permutations and combinations.
- I can define a DP state, transition and base case and reduce its memory.
- I can explain why a greedy choice is safe, or show a counterexample.
- I have solved at least 150 problems across all patterns, with notes.
- I talk through clarify, plan, code and test in every mock interview.
Related roadmaps
- Computer Science RoadmapTheory every engineer leans on: complexity, memory, OS, networks, compilers.
- System Design RoadmapScalability, caching, queues, consistency and the classic designs.
- Python RoadmapSyntax to packaging: data model, typing, async, testing.
- Java RoadmapCore language, collections, concurrency, JVM and build tools.
- Modern C++ RoadmapModern C++, RAII, templates, STL, memory and performance.
FAQ
How long does it take to get ready for coding interviews?
With some programming experience, about four to six months at eight hours a week is typical to reach confident medium-level solving. If you already know the basic structures, two to three months of focused pattern practice can be enough. Track progress by how quickly you recognise patterns, not by problem count.
Which programming language should I use for DSA interviews?
Use the language you are fastest and most accurate in. Python is popular because solutions are short and its standard library has heaps, deques and counters. Java and C++ are equally accepted. Switching language just for interviews usually costs more time than it saves.
How many problems should I solve?
Around 150 to 250 well-chosen problems spread across every pattern is enough for most candidates. Redo the ones you failed after a week. Solving many easy problems in one pattern helps less than a balanced set of mediums.
Should I learn DSA or system design first?
For junior and mid roles, DSA first, because coding rounds appear at every level and screen most candidates. Start system design once you can solve mediums reliably, or in parallel if you target senior roles. The System Design Roadmap roadmap covers it.