Data Structures and Algorithms Interview Questions for 3 Years Experience
40 questions with answers for candidates with 3 years of experience — 3 easy, 31 medium, 6 hard.
What interviewers expect: 3 years experience
Three-year candidates, usually targeting SDE-2, face hard DSA problems along with system design basics. Expect graph algorithms, advanced DP, heaps and tricky binary search, and questions linking data structures to scalability, such as designing an LRU cache or rate limiter. Interviewers look for ownership stories and measurable impact from performance improvements.
This set is weighted towards Heaps, Priority Queues and Greedy (8), Dynamic Programming (7), Trees and Binary Search Trees (6), Complexity Analysis and Recursion (5).
Hard DSA patterns Data structure based design System design basics Performance impact stories
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 is amortised analysis? Explain it with dynamic array append.
Amortised analysis averages the cost of an operation over a long sequence, even if a few individual operations are expensive. A dynamic array such as Java ArrayList or Python list doubles its capacity when full, which costs O(n) for that append. But doubling happens rarely, and the total copying over n appends is under 2n, so each append costs O(1) amortised. Hash table resizing works the same way.
02
Check whether a string is a palindrome, ignoring case and non-alphanumeric characters.
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.
04
How would you check whether two strings are anagrams, and what changes if input can contain any Unicode characters?
For lowercase English letters, compare character counts using an array of 26 integers in O(n) time and O(1) space; sorting both strings also works in O(n log n). With arbitrary Unicode, use a hash map of counts instead of a fixed array. I would also clarify whether case and spaces matter and whether to normalise accented characters, since visually identical text can have different code point sequences.
05
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.
06
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.
07
How does cycle detection differ in directed and undirected graphs?
In an undirected graph, DFS finds a cycle when it reaches an already visited vertex that is not the parent of the current vertex; Union-Find also works by checking whether an edge joins vertices already in the same set. In a directed graph you need three states, unvisited, in the current recursion stack and finished, and a cycle exists when DFS reaches a vertex still on the stack. Kahn's algorithm also detects directed cycles.
08
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
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
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.
11
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).
12
You need to merge K sorted log files from different servers into one sorted output. How would you do it efficiently?
Use a min-heap of size K holding the current smallest line from each file, keyed by timestamp. Pop the smallest, write it out, and push the next line from the same file. Each line is pushed and popped once, so total time is O(N log K) for N lines, and memory is O(K) plus buffers, which works even when files are larger than RAM. Buffered reading and writing keeps I/O efficient.
13
In activity selection, why do we sort by end time rather than start time or duration?
Choosing the activity that finishes earliest leaves the most remaining time for others, and an exchange argument shows that any optimal schedule can swap its first activity for the earliest-finishing one without losing count. Sorting by start time fails when an early activity runs very long, and sorting by duration fails when a short activity overlaps two compatible ones. The algorithm is O(n log n) for sorting plus one pass.
14
How do you handle disagreement with a reviewer about your solution in a code review?
Situation: a reviewer wanted me to replace my BFS solution with a more complex bidirectional search. Task: reach the best decision for the code, not win the argument. Action: I asked about their concern, which was latency on large graphs, then shared measurements showing our graphs were small and the simpler code was faster to maintain, and agreed to add a benchmark that would alert us if size grew. Result: the reviewer approved and we documented the trade-off.
15
How do you find the lowest common ancestor in a BST versus in a general binary tree?
In a BST, start at the root: if both values are smaller go left, if both are larger go right, otherwise the current node is the LCA, taking O(h). In a general binary tree, recurse: if the node is null or matches either target, return it; otherwise search both subtrees. If both sides return non-null, the current node is the LCA; else return the non-null side. That takes O(n).
16
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).
17
Solve jump game: can you reach the last index if nums[i] is the maximum jump from i?
def can_jump(nums):
farthest = 0
for i, step in enumerate(nums):
if i > farthest: # this index is unreachable
return False
farthest = max(farthest, i + step)
if farthest >= len(nums) - 1:
return True
return True
# [2,3,1,1,4] -> True, [3,2,1,0,4] -> False
# Greedy: track the farthest reachable index, O(n) time, O(1) space
18
Tell me about a time you used the right data structure to solve a real problem in a project or job.
Situation: in my internship, a duplicate-detection script for customer records took hours because it compared every pair. Task: make it run within the nightly window. Action: I normalised names and phone numbers into a key and grouped records in a hash map, comparing only records within the same group. Result: runtime dropped from four hours to six minutes, and my mentor asked me to present the approach to the team.
19
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.
20
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
21
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.
22
How can two heaps maintain the running median of a stream?
Keep a max-heap for the smaller half of the numbers and a min-heap for the larger half, balanced so their sizes differ by at most one. Insert each number into the correct heap, then move the top element across if sizes become unbalanced. The median is the top of the larger heap, or the average of both tops when sizes are equal. Insertion is O(log n) and finding the median is O(1).
23
How can you reduce the space used by a DP solution?
If each row of the table depends only on the previous row, keep two rows or even a single array, reducing O(n times m) space to O(m). Fibonacci-like problems need only the last two values, so O(1). For 0/1 knapsack in one array, iterate capacity from high to low so each item is used once; for unbounded knapsack iterate low to high. The trade-off is that reconstructing the actual solution becomes harder.
24
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).
DP on trees computes values for each node from the values of its children, usually in a postorder DFS. For the maximum independent set, where no two chosen nodes are adjacent, each node keeps two values: the best if it is taken, which is its value plus the not-taken values of children, and the best if it is not taken, the sum of each child's better option. This runs in O(n) and also solves house robber on a tree.
26
Find the length of the longest substring without repeating characters.
def length_of_longest_substring(s):
last = {} # char -> last index seen
left = best = 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 best
# 'abcabcbb' -> 3, 'bbbbb' -> 1, 'pwwkew' -> 3; O(n) time
27
Why is naive recursive Fibonacci exponential, and how do you fix it?
fib(n) calls fib(n-1) and fib(n-2), and each of those branches again, so the call tree has roughly 1.6 to the power n nodes and the same subproblems are recomputed many times. fib(40) makes over 300 million calls. Memoisation stores each result after the first computation, reducing it to O(n) time. A bottom-up loop keeping only the last two values gives O(n) time and O(1) space.
28
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.
Both are self-balancing BSTs with O(log n) operations. AVL trees keep the heights of sibling subtrees within one, so they are more strictly balanced and give faster lookups, but need more rotations on insert and delete. Red-black trees allow looser balance using node colours, so updates are cheaper. That is why Java TreeMap and C++ std::map use red-black trees, while AVL suits read-heavy workloads.
30
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).
31
What is a monotonic stack and which problems does it solve?
A monotonic stack keeps its elements in increasing or decreasing order by popping elements that break the order before each push. Each element is pushed and popped at most once, so a full pass is O(n). It solves next greater or next smaller element, daily temperatures, stock span, largest rectangle in a histogram and trapping rain water, replacing O(n squared) nested scans with a single linear scan.
32
What is the difference between Big-O, Big-Omega and Big-Theta?
Big-O is an upper bound: the algorithm grows no faster than this. Big-Omega is a lower bound: it grows at least this fast. Big-Theta is a tight bound, when the upper and lower bounds match. Merge sort is Theta(n log n) because it always does that much work. In interviews people usually say Big-O to mean the tight worst-case bound, but you should know the formal difference.
33
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.
34
You need to build a tool that shows the differences between two versions of a file line by line. What algorithm would you use?
The core is the longest common subsequence over lines: lines in the LCS are unchanged, and the rest are additions or deletions. Hash each line first so comparisons are fast. Classic LCS DP is O(m times n), which is too slow for large files, so real diff tools use Myers' algorithm, which runs in O((m plus n) times d), where d is the number of differences, fast when versions are similar.
35
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.
36
What are the complexities of heap operations, and why does building a heap take O(n)?
Peek at the root is O(1). Insert adds at the end and sifts up, and extract removes the root, moves the last element to the top and sifts down, both O(log n). Building a heap from n elements by sifting down from the last internal node to the root takes O(n), not O(n log n), because most nodes are near the bottom and move only a few levels; the sum of heights is linear.
37
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.
38
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.
39
A recursive DFS in Python crashes with RecursionError on a deep input. How do you fix it?
CPython limits recursion depth to about 1000 by default. Raising the limit with sys.setrecursionlimit works for moderate depth but can crash the interpreter on very deep inputs because the C stack is limited. The reliable fix is to rewrite the DFS iteratively with an explicit stack, pushing nodes and processing them in a loop. In Java the same issue appears as StackOverflowError and has the same solution.
40
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.
Frequently asked questions
What is asked in Data Structures and Algorithms interviews for 3 years of experience?
Three-year candidates, usually targeting SDE-2, face hard DSA problems along with system design basics. Expect graph algorithms, advanced DP, heaps and tricky binary search, and questions linking data structures to scalability, such as designing an LRU cache or rate limiter. Interviewers look for ownership stories and measurable impact from performance improvements.
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 3 years of experience?
Focus first on Hard DSA patterns, Data structure based design, System design basics, Performance impact stories.