Data Structures and Algorithms Interview Questions for 5 Years Experience
40 questions with answers for candidates with 5 years of experience — 1 easy, 24 medium, 15 hard.
What interviewers expect: 5 years experience
At five years, DSA rounds are fewer but harder, and system design becomes central. Expect problems such as designing leaderboards, autocomplete, schedulers or distributed top K, where you justify data structures at scale. Interviewers also assess mentoring, design reviews and how you guided teams through complex technical decisions and trade-offs.
This set is weighted towards Dynamic Programming (8), Linked Lists, Stacks and Queues (6), Heaps, Priority Queues and Greedy (6), Trees and Binary Search Trees (6).
Scalable data structures System design Technical leadership Trade-off reasoning
Solved at this levelStart practicing
3 QUESTIONS FREESign up to unlock the full question bank and track your progress.Unlock every question and answer, then continue practising company-wise and package-wise.
✓ 3 questions free • Unlock the rest in seconds
01
Implement 0/1 knapsack using a one-dimensional DP array.
def knapsack(weights, values, capacity):
dp = [0] * (capacity + 1) # dp[w] = best value with capacity w
for wt, val in zip(weights, values):
for w in range(capacity, wt - 1, -1): # go downwards: each item once
dp[w] = max(dp[w], dp[w - wt] + val)
return dp[capacity]
# knapsack([1, 3, 4], [15, 20, 30], 4) -> 35
# O(n * W) time, O(W) space
02
Implement topological sort using Kahn's algorithm.
from collections import deque
def topo_sort(n, edges):
adj = [[] for _ in range(n)]
indeg = [0] * n
for u, v in edges: # u must come before v
adj[u].append(v)
indeg[v] += 1
q = deque(i for i in range(n) if indeg[i] == 0)
order = []
while q:
u = q.popleft()
order.append(u)
for v in adj[u]:
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)
return order if len(order) == n else [] # empty means a cycle exists
03
A search box must suggest the closest dictionary words when a user makes a typo. How would you approach it?
Compute edit distance between the typed word and candidate words, suggesting those within distance 1 or 2. Running O(m times n) DP against a whole dictionary is slow, so narrow candidates first using a BK-tree indexed by edit distance, a trie with bounded edit distance search, or n-gram indexes. Then rank candidates by distance and word popularity. Keyboard-aware substitution costs can improve suggestions further.
04
What is a dummy or sentinel node and why is it useful in linked list problems?
A dummy node is an extra node placed before the real head. It removes special cases for operations that may change the head, such as deleting the first element, merging lists or inserting at the start. You build the result after dummy and return dummy.next at the end. This leads to shorter, less error-prone code, which matters a lot when writing linked list solutions under interview pressure.
05
Find the minimum number of coins needed to make an amount.
def coin_change(coins, amount):
INF = amount + 1
dp = [0] + [INF] * amount # dp[x] = min coins for amount x
for x in range(1, amount + 1):
for c in coins:
if c <= x and dp[x - c] + 1 < dp[x]:
dp[x] = dp[x - c] + 1
return dp[amount] if dp[amount] != INF else -1
# coin_change([1, 3, 4], 6) -> 2 (3 + 3)
# O(amount * len(coins)) time, O(amount) space
06
Implement Union-Find with path compression and union by size.
class DSU:
def __init__(self, n):
self.parent = list(range(n))
self.size = [1] * n
def find(self, x):
while self.parent[x] != x:
self.parent[x] = self.parent[self.parent[x]] # path halving
x = self.parent[x]
return x
def union(self, a, b):
ra, rb = self.find(a), self.find(b)
if ra == rb:
return False
if self.size[ra] < self.size[rb]:
ra, rb = rb, ra
self.parent[rb] = ra
self.size[ra] += self.size[rb]
return True
# Nearly O(1) amortised per operation
07
A report generation function loops over all users and, for each user, scans all orders. It was fine at launch but is now very slow. How do you explain and fix it?
The loop is O(users times orders), so when both grow ten times, the work grows a hundred times. I would explain this with numbers and a quick profile. The fix is to group orders by user ID once using a hash map, making the total O(users plus orders), or to push the grouping into a database query with an index. I would add a performance test with production-scale data.
08
Given meeting start and end times for a day, how do you find the minimum number of rooms needed?
Sort meetings by start time and keep a min-heap of end times for rooms in use. For each meeting, if the earliest ending room is free by its start time, pop it; then push this meeting's end time. The heap size at the end, or its maximum, is the answer. This is O(n log n). An alternative sorts start and end times separately and sweeps with two pointers, counting overlaps.
09
How do DFS and BFS differ in memory use on a tree?
DFS uses a stack, either the call stack or an explicit one, holding at most the height of the tree, so O(h) memory: about log n for balanced trees but n for skewed ones. BFS uses a queue holding an entire level, up to about n over 2 nodes in the last level of a complete tree. So DFS is lighter for wide balanced trees, while BFS is natural for shortest paths and level-wise processing.
10
Tell me about a time you explained a technical idea to a non-technical person.
Situation: a product manager asked why a search feature became slow as data grew. Task: explain the cause and the fix without jargon. Action: I compared the current approach to checking every book in a library one by one and the fix to using the catalogue index, then showed a simple chart of response times before and after a prototype. Result: the manager approved two sprints for the change and later reused my analogy with clients.
11
A network has 10 million devices and connections are added continuously. You must answer whether two devices are connected in real time. How?
Running BFS for every query is too slow. Since connections are only added, Union-Find is ideal: each new link is a union, and each query compares find results, both nearly O(1) amortised with path compression and union by size. Memory is two integer arrays of 10 million entries, about 80 MB. If links can also be removed, the problem becomes much harder and needs offline processing or specialised dynamic connectivity structures.
12
Why does greedy work for fractional knapsack but fail for 0/1 knapsack?
In fractional knapsack you may take part of an item, so taking items in decreasing value per weight and filling the remainder with a fraction is optimal. In 0/1 knapsack items are all or nothing; the best ratio item may leave wasted capacity that a combination of other items would fill better. Example: capacity 50 with items of weight 10, 20 and 30 shows greedy by ratio losing. 0/1 knapsack needs DP in O(n times W).
13
Why are linked lists often slower than arrays in practice, and what is a skip list?
Linked list nodes are scattered in memory, so traversal causes cache misses, and each node needs extra memory for pointers. Arrays are contiguous and benefit from CPU caching and prefetching, so even O(n) shifts can be fast for moderate sizes. A skip list is a layered linked list with express lanes chosen randomly, giving O(log n) average search, insert and delete; Redis uses it for sorted sets.
14
How do you handle pressure during a timed online coding test?
Situation: in a 90-minute test I faced three problems, one of them a tough DP. Task: maximise my score. Action: I read all problems first, solved the easiest one quickly to secure marks, wrote a brute-force version of the DP problem for partial credit, then improved it to memoised DP once I spotted the state. I kept an eye on time at fixed checkpoints. Result: I cleared all test cases on two problems and most of the third.
15
How do the KMP and Rabin-Karp string matching algorithms work?
Naive matching is O(n times m). KMP precomputes a longest prefix-suffix array for the pattern, so after a mismatch it shifts the pattern without re-reading text characters, giving O(n plus m) worst case. Rabin-Karp computes a rolling hash of each text window and compares characters only when hashes match, averaging O(n plus m) and extending well to multiple patterns, but collisions can make the worst case O(n times m).
16
How do you find the longest increasing subsequence in O(n log n)?
The simple DP is O(n squared): dp[i] is the LIS ending at i. The faster method keeps an array tails, where tails[k] is the smallest possible last value of an increasing subsequence of length k plus 1. For each number, binary search tails for the first value not less than it and replace it, or append if none. The length of tails is the LIS length. This patience sorting idea also helps in envelope nesting problems.
17
What is the Union-Find data structure and what optimisations make it fast?
Union-Find, or disjoint set union, tracks which elements belong to the same group with find, returning a representative, and union, merging two groups. Path compression makes every node on a find path point directly to the root, and union by rank or size attaches the smaller tree under the larger. Together they give nearly constant amortised time, the inverse Ackermann function. It is used in Kruskal and dynamic connectivity.
18
What are lower bound and upper bound, and what common bugs appear in binary search?
Lower bound returns the first index whose value is not less than the target, and upper bound the first index whose value is greater, so their difference counts occurrences. Common bugs are off-by-one errors in the loop condition, infinite loops when mid does not move, and integer overflow from (low plus high) divided by 2 in Java or C++; use low plus (high minus low) divided by 2. Python's bisect module provides both functions.
19
What is a greedy algorithm and when does it give the optimal answer?
A greedy algorithm builds a solution step by step, always taking the choice that looks best right now and never revisiting it. It is optimal only when the problem has the greedy choice property, meaning a locally best choice is part of some optimal solution, and optimal substructure. Examples where greedy works are activity selection, Huffman coding, Dijkstra and Kruskal. For many problems, such as 0/1 knapsack, it fails.
20
How does a monotonic deque find the maximum of every sliding window in O(n)?
Keep a deque of indices whose values are in decreasing order. For each new element, pop from the back while the back value is smaller, since those elements can never be the maximum again, then push the new index. Pop from the front if its index has left the window. The front is always the maximum of the current window. Every index enters and leaves once, so the total time is O(n) instead of O(n times k).
21
A teammate's BST validation only checks that each node is greater than its left child and smaller than its right child. Why is that wrong?
The BST property applies to entire subtrees, not just direct children. A node deep in the left subtree could be larger than the root and still pass the local check. The correct approach passes a valid range down the recursion: the left child must lie between the lower bound and the node value, the right child between the node value and the upper bound. Alternatively, check that an inorder traversal is strictly increasing.
22
How do you prove that a greedy algorithm is correct?
The common method is an exchange argument: take any optimal solution, show that replacing its first choice with the greedy choice does not make it worse, then apply the same reasoning to the remaining subproblem by induction. Another method is showing greedy stays ahead, meaning after each step its partial solution is at least as good as any other. In interviews, stating the argument briefly and testing small counterexamples builds confidence.
Huffman coding builds an optimal prefix-free binary code for compression. Put each character with its frequency into a min-heap. Repeatedly remove the two least frequent nodes, merge them into a new node whose frequency is their sum, and push it back. The final tree gives codes: left edges are 0 and right edges are 1, so frequent characters get shorter codes. It runs in O(n log n) and is used in ZIP and JPEG.
24
Compute the length of the longest common subsequence of two strings.
Edit distance, or Levenshtein distance, is the minimum number of insertions, deletions and substitutions to turn one string into another. dp[i][j] is the distance between the first i characters of A and the first j of B; if characters match, take dp[i-1][j-1], otherwise 1 plus the minimum of the three neighbouring cells. It runs in O(m times n) and is used in spell checkers, fuzzy search, DNA alignment and plagiarism detection.
26
Explain basic binary tree terminology: root, leaf, height and depth.
The root is the top node with no parent. A leaf has no children. The depth of a node is the number of edges from the root to it, and the height of a node is the number of edges on the longest path down to a leaf; the tree's height is the root's height. In a binary tree each node has at most two children. A tree with n nodes has n minus 1 edges.
27
Print the level order traversal of a binary tree, one list per level.
from collections import deque
def level_order(root):
if not root:
return []
out, q = [], deque([root])
while q:
level = []
for _ in range(len(q)): # process exactly one level
node = q.popleft()
level.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
out.append(level)
return out
28
What is the diameter of a binary tree and how do you compute it efficiently?
The diameter is the number of edges on the longest path between any two nodes, which may not pass through the root. Compute it in one postorder traversal: for each node, get the heights of the left and right subtrees, update a global best with left plus right, and return 1 plus the larger height to the parent. This visits each node once, giving O(n) time instead of O(n squared) from recomputing heights.
29
You have a 100 GB file of integers and only 4 GB of RAM. How would you find the duplicates?
The data does not fit in memory, so I would partition it. Read the file in streaming fashion and write each number to one of, say, 50 bucket files based on hash of the number modulo 50, so equal numbers land in the same bucket. Each bucket of about 2 GB fits in memory, where a hash set finds duplicates. Alternatively use external merge sort and scan adjacent values. A Bloom filter can pre-screen candidates.
def reverse_k_group(head, k):
# check that k nodes are available
node, count = head, 0
while node and count < k:
node = node.next
count += 1
if count < k:
return head # leave the remainder as is
prev, cur = None, head
for _ in range(k): # reverse k nodes
cur.next, prev, cur = prev, cur, cur.next
head.next = reverse_k_group(cur, k) # old head is now the group tail
return prev
# 1-2-3-4-5, k=2 -> 2-1-4-3-5; O(n) time
31
Generate all subsets of a list of distinct numbers.
def subsets(nums):
result = []
current = []
def backtrack(i):
if i == len(nums):
result.append(current[:])
return
current.append(nums[i]) # include nums[i]
backtrack(i + 1)
current.pop() # exclude nums[i]
backtrack(i + 1)
backtrack(0)
return result
# 2^n subsets, each up to n long: O(n * 2^n) time
32
A monitoring service must report the median response time over a live stream of requests. How would you design it?
For an exact all-time median, use two heaps, giving O(log n) per insert and O(1) per query. For the median of only the last N minutes, you need deletions, so use two heaps with lazy deletion or a balanced order-statistic tree. At very high volume, exact medians are costly, so production systems use histograms or sketches such as t-digest or HDR histogram to give accurate percentiles with fixed memory.
33
Design a simple scheduler that gives each job a fixed time slice in turn.
Round-robin scheduling fits a queue. Put all jobs in a FIFO queue. Repeatedly dequeue a job, run it for one time slice, and if it is not finished, enqueue it at the back with its remaining time. Each step is O(1). For priorities, keep one queue per priority level or use a priority queue. A circular buffer works well if the number of jobs is bounded, avoiding allocations.
34
A build system hangs because some services depend on each other in a loop. How would you detect and report the cycle?
Model services as a directed graph and run DFS with three colours. When DFS reaches a node that is still on the current stack, it has found a back edge, and walking the parent pointers from the current node back to that node gives the exact cycle to report, such as A to B to C to A. Running this check in CI before every build prevents the problem, and Kahn's algorithm can list all nodes involved.
35
Why can comparison sorts not beat O(n log n), and how do counting and radix sort get around it?
Any comparison sort can be modelled as a decision tree with n factorial leaves, one per possible ordering, so its height, the number of comparisons, is at least log of n factorial, which is about n log n. Counting sort avoids comparisons by counting occurrences of each key in a small range k, giving O(n plus k). Radix sort applies a stable counting sort digit by digit, O(d times (n plus base)), great for fixed-length integers.
36
What is the Master Theorem and how do you apply it?
The Master Theorem solves recurrences of the form T(n) = a T(n/b) + f(n). Compare f(n) with n to the power log base b of a. If f(n) is smaller, the answer is n to that power; if equal, multiply by log n; if larger, f(n) dominates. Merge sort has a = 2, b = 2, f(n) = n, giving O(n log n). Binary search has a = 1, b = 2, f(n) = 1, giving O(log n).
A trie, or prefix tree, stores strings character by character, with each edge representing a character and a flag marking word ends. Insert and search take O(L) for a word of length L regardless of how many words are stored, and all words sharing a prefix sit under one node. Tries power autocomplete, spell checkers, IP routing with longest prefix match and word search games. Memory use can be high, so compressed tries exist.
38
Packages with given weights must be shipped in order within D days. How do you find the minimum ship capacity?
The capacity lies between the heaviest package and the total weight, and if a capacity works, any larger one also works, so binary search the answer. For a candidate capacity, greedily load packages day by day, starting a new day when the next package does not fit, and count days. If the days are within D, try smaller; otherwise try larger. Time is O(n log of total weight).
39
How is the longest common subsequence computed with DP?
Let dp[i][j] be the LCS length of the first i characters of A and the first j characters of B. If A[i-1] equals B[j-1], dp[i][j] is dp[i-1][j-1] plus 1; otherwise it is the maximum of dp[i-1][j] and dp[i][j-1]. Fill the table row by row in O(m times n) time. Backtracking from dp[m][n] recovers the actual subsequence. LCS underlies diff tools and DNA sequence comparison.
40
You can use an O(n log n) algorithm with high constant factors or a simple O(n squared) one. For what inputs might the O(n squared) choice be better?
Big-O ignores constants, so for small n the simpler algorithm can be faster in practice. Insertion sort beats merge sort for arrays below roughly 16 to 32 elements, which is why library sorts such as Timsort switch to insertion sort for small runs. I would benchmark on realistic input sizes, choose the asymptotically better algorithm when n can grow, and use a hybrid when both ranges occur.
Frequently asked questions
What is asked in Data Structures and Algorithms interviews for 5 years of experience?
At five years, DSA rounds are fewer but harder, and system design becomes central. Expect problems such as designing leaderboards, autocomplete, schedulers or distributed top K, where you justify data structures at scale. Interviewers also assess mentoring, design reviews and how you guided teams through complex technical decisions and trade-offs.
How many questions should I practise before a Data Structures and Algorithms interview?
Work through all 40 questions here, then the company-wise sets for the employers you are targeting. Quality matters more than count: be able to explain why each answer is right.
Which topics matter most for 5 years of experience?
Focus first on Scalable data structures, System design, Technical leadership, Trade-off reasoning.