DSA course menu
Advanced DSA Interview Questions and Answers
Advanced data structures and algorithms interview questions with Python solutions: dynamic programming vs greedy, Dijkstra vs Bellman-Ford, trie design, median of a data stream, course schedule, word break, edit distance, LRU cache and serialising a binary tree.
On this page
- Concepts
- 1. How do you tell whether a problem needs dynamic programming or greedy?
- 2. Dijkstra, Bellman-Ford or BFS?
- 3. How would you design autocomplete?
- 4. What does "pseudo-polynomial" mean for knapsack?
- Coding questions
- 5. Median of a data stream.
- 6. Course schedule order.
- 7. Serialise and deserialise a binary tree.
- 8. Edit distance.
- 9. Longest increasing subsequence in O(n log n).
- 10. Cheapest flight with at most k stops.
- Key takeaway
Advanced rounds test whether you can pick the right technique for an unfamiliar problem and explain the trade-offs. Talk through your reasoning, start from a correct solution, and improve it.
Concepts#
1. How do you tell whether a problem needs dynamic programming or greedy?#
Show solution
Look for overlapping subproblems (the same smaller question recurs) and optimal substructure (the best answer is built from best sub-answers): that signals DP. Greedy is valid only when a locally best choice can be proven safe, usually with an exchange argument. A quick test: try to break the greedy idea with a small counterexample. Coin change with coins 4 and amount 6 breaks "take the largest coin" (4 + 1 + 1 vs 3 + 3), so it needs DP.
2. Dijkstra, Bellman-Ford or BFS?#
Show solution
- BFS: all edges have the same weight. O(V + E).
- Dijkstra: non-negative weights. O((V + E) log V) with a heap. Wrong with negative edges, because it finalises vertices too early.
- Bellman-Ford: any weights, and detects negative cycles. O(V · E).
For one target on a map with a good distance estimate, A* usually explores far less than Dijkstra.
3. How would you design autocomplete?#
Show solution
Store the vocabulary in a trie, so finding the node for a prefix costs O(prefix length). To return the most popular suggestions quickly, store at each node the top few completions (precomputed, or maintained on insert) instead of searching the whole subtree on every keystroke. Mention trade-offs: memory use of tries, updating popularity counts, and handling typos (edit distance).
4. What does "pseudo-polynomial" mean for knapsack?#
Show solution
0/1 knapsack DP runs in O(n × W), where W is the capacity value, not the size of the input. Writing W takes only about log W digits, so the running time is exponential in the input's size. It is fast for small capacities and hopeless for capacities like 10¹². The general problem is NP-hard.
Coding questions#
5. Median of a data stream.#
Numbers arrive one at a time; after each one, report the median.
Show solution
Keep the smaller half in a max-heap and the larger half in a min-heap, with sizes balanced. The median is at the top of one or both heaps.
import heapq
class MedianFinder:
def __init__(self):
self.low = [] # max-heap (stored negated): the smaller half
self.high = [] # min-heap: the larger half
def add(self, x):
heapq.heappush(self.low, -x)
heapq.heappush(self.high, -heapq.heappop(self.low)) # keep halves ordered
if len(self.high) > len(self.low):
heapq.heappush(self.low, -heapq.heappop(self.high))
def median(self):
if len(self.low) > len(self.high):
return -self.low[0]
return (-self.low[0] + self.high[0]) / 2
m = MedianFinder()
for x in [5, 15, 1, 3, 8]:
m.add(x)
print(x, "->", m.median())5 -> 5
15 -> 10.0
1 -> 5
3 -> 4.0
8 -> 5Each add is O(log n); median is O(1).
6. Course schedule order.#
Given prerequisite pairs [course, before], return an order to take all courses, or an empty list if impossible.
Show solution
from collections import deque
def course_order(n, pairs):
graph = [[] for _ in range(n)]
indegree = [0] * n
for course, before in pairs:
graph[before].append(course)
indegree[course] += 1
queue = deque(i for i in range(n) if indegree[i] == 0)
order = []
while queue:
c = queue.popleft()
order.append(c)
for nxt in graph[c]:
indegree[nxt] -= 1
if indegree[nxt] == 0:
queue.append(nxt)
return order if len(order) == n else []
print(course_order(4, [[1, 0], [2, 0], [3, 1], [3, 2]]))
print(course_order(2, [[0, 1], [1, 0]]))[0, 1, 2, 3]
[]Kahn's topological sort: O(V + E). A cycle leaves some courses unprocessed.
7. Serialise and deserialise a binary tree.#
Show solution
Write a preorder traversal with a marker for empty children; reading it back in the same order rebuilds the tree.
class Node:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def serialize(node):
if node is None:
return "#"
return f"{node.val},{serialize(node.left)},{serialize(node.right)}"
def deserialize(data):
values = iter(data.split(","))
def build():
v = next(values)
if v == "#":
return None
return Node(int(v), build(), build())
return build()
root = Node(1, Node(2), Node(3, Node(4), Node(5)))
text = serialize(root)
print(text)
print(serialize(deserialize(text)) == text)1,2,#,#,3,4,#,#,5,#,#
TrueBoth directions are O(n). The # markers make the shape unambiguous, which a plain preorder list would not be.
8. Edit distance.#
Show solution
def edit_distance(a, b):
prev = list(range(len(b) + 1))
for i in range(1, len(a) + 1):
cur = [i] + [0] * len(b)
for j in range(1, len(b) + 1):
if a[i - 1] == b[j - 1]:
cur[j] = prev[j - 1]
else:
cur[j] = 1 + min(prev[j], cur[j - 1], prev[j - 1])
prev = cur
return prev[-1]
print(edit_distance("intention", "execution"), edit_distance("abc", "abc"))5 0The 2D DP with only two rows kept: O(m × n) time, O(n) space.
9. Longest increasing subsequence in O(n log n).#
Show solution
from bisect import bisect_left
def lis(nums):
tails = []
for x in nums:
i = bisect_left(tails, x)
if i == len(tails):
tails.append(x)
else:
tails[i] = x
return len(tails)
print(lis([10, 9, 2, 5, 3, 7, 101, 18]), lis([0, 1, 0, 3, 2, 3]))4 4tails[k] is the smallest possible last value of an increasing subsequence of length k + 1. Each number either extends the longest one or improves a tail, found by binary search.
10. Cheapest flight with at most k stops.#
Show solution
Plain Dijkstra ignores the stop limit. Bellman-Ford limited to k + 1 rounds does exactly what is needed: after round r, the distances use at most r flights. Copy the distances each round so one round cannot chain several flights.
def cheapest_flight(n, flights, src, dst, k):
INF = float("inf")
cost = [INF] * n
cost[src] = 0
for _ in range(k + 1):
new = cost[:]
for u, v, price in flights:
if cost[u] + price < new[v]:
new[v] = cost[u] + price
cost = new
return -1 if cost[dst] == INF else cost[dst]
flights = [(0, 1, 100), (1, 2, 100), (2, 3, 100), (0, 2, 500), (1, 3, 600)]
print(cheapest_flight(4, flights, 0, 3, 1))
print(cheapest_flight(4, flights, 0, 3, 2))600
300With one stop the best is 0 → 2 → 3 (500 + 100 = 600, cheaper than 0 → 1 → 3 at 700); two stops allow 0 → 1 → 2 → 3 (300). O(k · E).
Key takeaway#
Next: full problems to solve end to end, in Coding Challenges.
Finished this lesson?