Data Structures and Algorithms Interview Questions for 10 Years Experience
40 questions with answers for candidates with 10+ years of experience — 11 medium, 29 hard.
What interviewers expect: 10 years experience
At ten years and beyond, candidates are assessed as principal engineers, architects or engineering managers. Coding may be light, but you must reason clearly about complexity and data structures in large systems. Discussions cover technical strategy, platform evolution, hiring and growing engineers, and how you raised the problem-solving and code quality bar across multiple teams.
This set is weighted towards Sorting, Searching and Backtracking (8), Linked Lists, Stacks and Queues (7), Dynamic Programming (6), Graphs and Graph Algorithms (5).
Technical strategy System architecture Engineering culture Hiring and mentoring
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
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
02
Find the first and last position of a target in a sorted array.
from bisect import bisect_left, bisect_right
def search_range(nums, target):
lo = bisect_left(nums, target) # first index >= target
if lo == len(nums) or nums[lo] != target:
return [-1, -1]
hi = bisect_right(nums, target) - 1 # last index <= target
return [lo, hi]
# [5,7,7,8,8,10], 8 -> [3, 4]; two binary searches: O(log n)
It sorts an array of three distinct values, such as 0, 1 and 2, in one pass with O(1) space. It keeps three pointers: low, mid and high. If arr[mid] is 0, swap it with arr[low] and advance both; if 1, advance mid; if 2, swap it with arr[high] and decrease high without advancing mid. It runs in O(n) and is the basis of three-way partitioning in quicksort.
04
A Sudoku solver using plain backtracking is too slow on hard puzzles. How would you speed it up?
Add stronger pruning and better choice ordering. Keep bitmasks of used digits for each row, column and box, so validity checks are O(1). Always fill the empty cell with the fewest candidates first, the minimum remaining values heuristic, which shrinks the search tree dramatically. Apply constraint propagation, filling cells with a single candidate before guessing. For the hardest cases, exact cover with Dancing Links is very fast.
05
What is quickselect and when is it better than sorting?
Quickselect finds the kth smallest element by partitioning like quicksort but recursing only into the side that contains position k. On average it does about n plus n over 2 plus n over 4 work, which is O(n), compared with O(n log n) for sorting. The worst case is O(n squared), reduced by random pivots or median of medians for guaranteed O(n). C++ nth_element uses this idea.
06
A recursive tree traversal crashes on a skewed tree with one million nodes. How do you fix it?
A skewed tree has height about n, so recursion needs a million stack frames and overflows. Rewrite the traversal iteratively with an explicit stack stored on the heap, or use Morris traversal, which threads temporary links through the tree to achieve O(1) extra space. If the tree is built by our code, also consider why it is skewed and switch to a self-balancing tree so height stays O(log n).
07
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.
08
Serialize a binary tree to a string and deserialize it back.
Both answer range queries with point updates in O(log n). A Fenwick tree, or binary indexed tree, is compact, simple to code and ideal for prefix sums and counts, but supports mainly invertible operations. A segment tree stores an aggregate for each segment, handles any associative operation such as min, max or gcd, and supports range updates with lazy propagation, at the cost of about 4n memory and longer code.
10
Detect whether a linked list has a cycle and return the node where the cycle begins.
def detect_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast: # cycle found
slow = head
while slow is not fast: # move both one step
slow = slow.next
fast = fast.next
return slow # start of the cycle
return None
# O(n) time, O(1) space
11
Find the cheapest flight from one city to another using at most K stops. Why does plain Dijkstra not work directly?
Plain Dijkstra finalises the cheapest path to a city, but that path may use too many stops, while a costlier path with fewer stops could still lead to a valid answer. One fix is Bellman-Ford limited to K plus 1 rounds, copying distances each round, O(K times E). Another is Dijkstra on states of city and stops used, or a BFS by levels that tracks cost, pruning states that are worse in both cost and stops.
12
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).
13
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
14
What is a B-tree and why do databases use it for indexes?
A B-tree is a balanced search tree where each node holds many keys and has many children, often hundreds. This keeps the tree very shallow, so a lookup among millions of rows touches only three or four nodes. Each node is sized to a disk or memory page, minimising expensive I/O. B+ trees, used by MySQL InnoDB and PostgreSQL, keep all values in linked leaves, making range scans efficient.
15
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.
16
What is interval DP? Explain with matrix chain multiplication.
Interval DP defines states over a range i to j and combines smaller ranges. In matrix chain multiplication, dp[i][j] is the minimum scalar multiplications to multiply matrices i through j. Try every split point k between i and j: dp[i][k] plus dp[k+1][j] plus the cost of multiplying the two results. Fill by increasing interval length, O(n cubed). Similar patterns solve burst balloons and palindrome partitioning.
17
Compare Kruskal's and Prim's algorithms for minimum spanning trees.
Both find a minimum spanning tree, the cheapest set of edges connecting all vertices. Kruskal sorts all edges by weight and adds each edge if it joins two different components, checked with Union-Find, O(E log E); it suits sparse graphs given as edge lists. Prim grows the tree from a start vertex, always adding the cheapest edge leaving the tree using a min-heap, O(E log V), which suits dense graphs with adjacency lists.
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.
19
Implement a data structure that returns the median of all numbers added so far.
Greedily run the most frequent available task each slot. Use a max-heap of remaining counts and a queue of tasks cooling down with the time they become available. Each slot, move ready tasks back to the heap, pop the most frequent, decrement and enqueue it with time plus n. A closed formula also exists: max of total tasks and (maxFreq minus 1) times (n plus 1) plus the number of tasks with maxFreq.
Bitmask DP represents a subset of up to about 20 items as the bits of an integer, so the state can be the set of items already used plus perhaps the last item. The travelling salesman problem uses dp[mask][last], the minimum cost to visit the cities in mask ending at last, giving O(2 to the power n times n squared) instead of n factorial. It is used for assignment, scheduling and covering problems with small n.
22
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.
23
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 search_rotated(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
return mid
if nums[lo] <= nums[mid]: # left half sorted
if nums[lo] <= target < nums[mid]:
hi = mid - 1
else:
lo = mid + 1
else: # right half sorted
if nums[mid] < target <= nums[hi]:
lo = mid + 1
else:
hi = mid - 1
return -1
# [4,5,6,7,0,1,2], 0 -> 4; O(log n)
25
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.
def edit_distance(a, b):
m, n = len(a), len(b)
prev = list(range(n + 1)) # distances from empty prefix of a
for i in range(1, m + 1):
cur = [i] + [0] * n
for j in range(1, n + 1):
if a[i - 1] == b[j - 1]:
cur[j] = prev[j - 1]
else:
cur[j] = 1 + min(prev[j], # delete
cur[j - 1], # insert
prev[j - 1]) # replace
prev = cur
return prev[n]
# edit_distance('horse', 'ros') -> 3; O(m * n) time, O(n) space
27
Explain best, average and worst case complexity using quicksort.
Best case is the minimum work over inputs of size n, worst case the maximum and average case the expected work over typical inputs. Quicksort averages O(n log n) because random pivots split arrays reasonably evenly. Its worst case is O(n squared) when the pivot is always the smallest or largest element, such as sorted input with a first-element pivot. Random pivots or median-of-three make the worst case very unlikely.
Bellman-Ford finds single-source shortest paths with negative weights by relaxing all edges V minus 1 times, O(V times E), and one more pass detects negative cycles. Floyd-Warshall finds shortest paths between all pairs using dynamic programming over intermediate vertices, O(V cubed) time and O(V squared) space, suitable for small dense graphs of a few hundred nodes. For all pairs on large sparse graphs, running Dijkstra from each vertex is faster.
29
A company has a fixed budget and several projects with costs and expected returns. How would you choose projects to maximise return?
If each project is all or nothing, this is the 0/1 knapsack problem: budget is capacity, cost is weight and return is value, solved with DP in O(projects times budget), and tracking choices lets me list selected projects. If the budget is very large, I would scale costs to units such as lakhs to keep the table small, or use DP over value instead. Extra constraints like dependencies change the state design.
30
Tell me about a time you received critical feedback on your code.
Situation: a senior reviewer rejected my pull request because my queue processing code was O(n squared) and had no tests. Task: fix it and learn from it. Action: I asked for a short walkthrough, replaced repeated list removals with a deque, added unit tests for edge cases and asked for a second review. Result: the change merged with a ten times speed-up, and I now self-review complexity and tests before raising any pull request.
31
Your knapsack DP has n equal to 100 items but capacity up to 10 to the power 9, so the table does not fit in memory. What do you do?
A table indexed by capacity is impossible, so I change the state. If item values are small, use dp[v] as the minimum weight needed to achieve value v, then pick the largest v whose weight fits the capacity; that is O(n times total value). If n is about 40, meet in the middle: enumerate subsets of each half, sort one side and binary search. Otherwise approximation or branch and bound are options.
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
33
How does quicksort work and why does pivot choice matter?
Quicksort picks a pivot, partitions the array so smaller elements go left and larger go right, then recursively sorts both sides. It sorts in place with O(log n) stack space on average and is very cache friendly, averaging O(n log n). A bad pivot, such as always the first element on sorted input, gives unbalanced partitions and O(n squared). Random pivots, median-of-three and three-way partitioning for duplicates avoid this.
34
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.
35
Design a rate limiter that allows at most 100 requests per user in any rolling 60-second window.
For each user keep a deque of request timestamps. On a request, pop timestamps older than now minus 60 seconds from the front, then allow the request only if fewer than 100 remain, pushing the new timestamp at the back. This sliding window log is exact but uses memory per request. At scale I would use a sliding window counter or token bucket stored in Redis with atomic operations to save memory and work across servers.
36
What is Timsort and why do Python and Java use it?
Timsort is a hybrid of merge sort and insertion sort. It scans the data for already sorted runs, extends short runs with insertion sort and merges runs using a stack with balancing rules and galloping mode. Real data is often partially sorted, so Timsort is close to O(n) on such input while keeping O(n log n) worst case and stability. Python uses it for all sorts and Java for sorting objects.
37
How does heap sort work and how does it compare with quicksort and merge sort?
Heap sort builds a max-heap in O(n), then repeatedly swaps the root with the last element, shrinks the heap and sifts down, giving O(n log n) in all cases with O(1) extra space. It is not stable and has poor cache locality, so in practice it is slower than quicksort. Merge sort is stable but needs O(n) space. Introsort switches from quicksort to heap sort to guarantee O(n log n).
38
Implement Union-Find with path compression and union by size.
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.
40
Tell me about a time you made slow code significantly faster at work.
Situation: a search API for our catalogue took two seconds because it filtered and sorted all items on every request. Task: bring p95 latency under 200 milliseconds. Action: I profiled it, pre-sorted items by the main key at load time, replaced linear filtering with binary search on sorted ranges and cached popular queries, validating results against the old code. Result: p95 dropped to 120 milliseconds and server costs fell by about a third.
Frequently asked questions
What is asked in Data Structures and Algorithms interviews for 10+ years of experience?
At ten years and beyond, candidates are assessed as principal engineers, architects or engineering managers. Coding may be light, but you must reason clearly about complexity and data structures in large systems. Discussions cover technical strategy, platform evolution, hiring and growing engineers, and how you raised the problem-solving and code quality bar across multiple teams.
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 10+ years of experience?
Focus first on Technical strategy, System architecture, Engineering culture, Hiring and mentoring.