Data Structures and Algorithms Interview Questions for 7 Years Experience
40 questions with answers for candidates with 7 years of experience — 15 medium, 25 hard.
What interviewers expect: 7 years experience
Seven-year candidates are evaluated for senior or lead roles. One DSA round may remain, but focus shifts to architecture, scalability, reliability and cross-team influence. You may be asked to choose algorithms for large-scale problems such as routing, search ranking or deduplication, and explain how you balanced delivery, cost and technical debt in past projects.
This set is weighted towards Trees and Binary Search Trees (6), Sorting, Searching and Backtracking (6), Heaps, Priority Queues and Greedy (6), Dynamic Programming (6).
Architecture decisions Large-scale algorithms Cross-team influence Risk and delivery balance
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
What are prefix sums and what problems do they solve?
A prefix sum array stores pre[i] as the sum of the first i elements, built in O(n). The sum of any range from l to r is then pre[r+1] minus pre[l] in O(1). Combined with a hash map of prefix sums, it counts subarrays with sum k in O(n). 2D prefix sums answer rectangle sum queries on grids, and difference arrays apply many range updates efficiently.
02
In a company org chart stored as a tree, how would you find the closest common manager of two employees?
This is the lowest common ancestor problem. If each employee stores a parent pointer, collect the ancestors of the first employee in a set and walk up from the second until a match is found, O(h). Without parent pointers, use the recursive LCA on the tree from the CEO, O(n). For many repeated queries on a large chart, preprocess with binary lifting to answer each query in O(log n).
def merge_sort(a):
if len(a) <= 1:
return a
mid = len(a) // 2
left = merge_sort(a[:mid])
right = merge_sort(a[mid:])
out, i, j = [], 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]: # <= keeps the sort stable
out.append(left[i]); i += 1
else:
out.append(right[j]); j += 1
out.extend(left[i:])
out.extend(right[j:])
return out
# O(n log n) time, O(n) extra space
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.
05
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.
06
What is tail recursion and do Java and Python optimise it?
A call is tail recursive when the recursive call is the very last action, so nothing remains to be done after it returns, as in a factorial that carries an accumulator. Some languages reuse the same stack frame for such calls, turning recursion into a loop. Neither Java nor CPython performs tail call optimisation, so deep tail recursion still overflows; convert it to a loop manually.
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
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
09
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.
10
A hash map lookup in your service suddenly becomes very slow under certain traffic. What could cause it?
If many keys produce the same hash, they pile into a few buckets and operations degrade toward O(n). This can come from a poor custom hashCode, such as returning a constant or using only one field, or from attackers sending crafted keys. Fixes include a better hash function combining all fields, randomised hashing, which Python uses for strings, and tree-based buckets as in Java 8 HashMap, which caps the worst case at O(log n).
11
Serialize a binary tree to a string and deserialize it back.
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.
13
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.
14
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).
15
You must sort a 10 GB file of records on a machine with 1 GB of RAM. How would you do it?
Use external merge sort. Read the file in chunks of about 800 MB, sort each chunk in memory and write it to disk as a sorted run, giving around 13 runs. Then perform a K-way merge: open all runs, keep a min-heap with the current record from each, repeatedly output the smallest and refill from that run, using buffered I/O. Total work is O(n log n) with roughly two passes over the data.
16
Why are you looking for a change from your current job?
Situation: in my current role I have learned a lot maintaining internal tools for two years. Task: I want to grow into harder engineering problems. Action: I have been strengthening my data structures, system design and backend skills through projects and by taking ownership of performance work in my team. Result: I am now ready for a role with larger scale and more technical depth, which is why this position appeals to me.
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.
18
How does merge sort work and what are its properties?
Merge sort splits the array into halves, recursively sorts each half and merges the two sorted halves in linear time. The recurrence T(n) = 2T(n/2) + n gives O(n log n) in every case. It is stable and works well for linked lists and external sorting of large files, but needs O(n) extra space for arrays. It also adapts to counting inversions during the merge step.
19
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.
20
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.
21
How do you prioritise when several tasks have deadlines at the same time?
Situation: in one sprint I had a bug fix, a feature and interview preparation for a new hire panel all due together. Task: deliver without dropping quality. Action: I listed the tasks with impact and deadline, discussed the order with my lead, finished the customer-facing bug first, split the feature into smaller deliverables and blocked calendar time for each. Result: everything was delivered within the week and nothing urgent slipped.
22
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.
23
CPU tasks labelled by type must be scheduled with a cooldown of n slots between two tasks of the same type. How do you minimise total time?
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.
24
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.
25
You must merge two sorted arrays where the first array has enough empty space at the end for the second. How would you do it in place?
Merging from the front would overwrite unread elements, so merge from the back. Use three pointers: the last real element of the first array, the last element of the second, and the last slot of the first array. Repeatedly place the larger of the two candidates at the write position and move pointers left. When the second array is exhausted, the rest is already in place. This takes O(m plus n) time and O(1) space.
26
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.
27
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.
28
How can you implement a queue using two stacks, and what is its complexity?
Use an in-stack for enqueue and an out-stack for dequeue. Enqueue pushes onto the in-stack in O(1). For dequeue, if the out-stack is empty, pop everything from the in-stack and push it onto the out-stack, which reverses the order, then pop from the out-stack. Each element moves at most once between stacks, so dequeue is O(1) amortised even though a single transfer can be O(n).
29
You must build autocomplete for a search box over one million product names. Which data structure would you use?
I would use a trie where each node stores, besides children, the top few most popular completions under that prefix. Then typing a prefix walks L nodes and returns precomputed suggestions instantly, without exploring the whole subtree. Memory can be reduced with a compressed radix trie. For typo tolerance or ranking by many signals, a search engine with prefix indexes is more practical at large scale.
30
An interviewer asks you to reduce your solution's extra space from O(n) to O(1). How do you approach it?
I check what the extra structure stores and whether the input itself can hold that information. Common techniques: use two pointers instead of a hash set on sorted data, keep only the last few DP values instead of a full table, modify the input in place, such as marking visited indices by negating values, or use bit manipulation like XOR to find a missing number. I state any trade-offs, such as mutating input.
31
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.
32
An application needs sorted data with frequent inserts, deletes and range queries such as all orders between two timestamps. Which structure fits?
A balanced BST, such as Java TreeMap or a sorted container in Python, gives O(log n) insert and delete and O(log n plus k) range queries using floor, ceiling or subMap operations. A sorted array has fast range queries but O(n) inserts, and a hash map cannot do ranges at all. If the data lives in a database, a B-tree index on the timestamp column solves the same problem.
33
A game leaderboard with millions of players needs fast score updates and queries like what rank is this player. How would you design it?
Sorting on every query is too slow. I would bucket scores and use a Fenwick tree or segment tree over score values, storing how many players have each score; a player's rank is the count of players with higher scores, found in O(log S). Updates move a player between buckets in O(log S). An order-statistic balanced tree also works, and in production Redis sorted sets, built on skip lists, provide this directly.
34
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.
import heapq
def merge_k_lists(lists):
heap = []
for i, node in enumerate(lists):
if node:
heapq.heappush(heap, (node.val, i, node)) # i breaks ties
dummy = tail = ListNode()
while heap:
val, i, node = heapq.heappop(heap)
tail.next = node
tail = node
if node.next:
heapq.heappush(heap, (node.next.val, i, node.next))
return dummy.next
# O(N log K) for N total nodes
36
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.
37
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).
38
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.
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
40
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.
Frequently asked questions
What is asked in Data Structures and Algorithms interviews for 7 years of experience?
Seven-year candidates are evaluated for senior or lead roles. One DSA round may remain, but focus shifts to architecture, scalability, reliability and cross-team influence. You may be asked to choose algorithms for large-scale problems such as routing, search ranking or deduplication, and explain how you balanced delivery, cost and technical debt in past projects.
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 7 years of experience?
Focus first on Architecture decisions, Large-scale algorithms, Cross-team influence, Risk and delivery balance.