Algorithmic Problem-Solving and Data Structure Selection Questions
The higher-order meta-skill of attacking an unfamiliar problem: recognizing problem archetypes and mapping them to known techniques, decomposing under constraints, and choosing, composing, or designing the right data structures to meet specified operation costs (LRU cache, min-stack, ordered maps, disjoint-set/union-find). Covers reasoning about trade-offs between competing structures and approaches, working through medium-to-hard problems methodically, handling problem variations, and communicating an approach before coding. The connective-tissue topic that ties the individual structure and algorithm topics together, rather than any single structure or algorithm.
You have k sorted sequences (log streams, sorted linked lists, or sorted files too large to fit in memory together) and need to merge them into one sorted output under limited memory. Implement the merge and explain why a heap keyed on 'next element per source' beats repeatedly scanning all k sources for the minimum.
Sample Answer
Direct answer
Keep a min-heap (a priority queue: a tree-shaped structure that keeps the smallest element accessible at the root in logarithmic time) holding one candidate element from each of the k sources, tagged with which source it came from. Repeatedly pop the smallest, emit it, then pull the next element from that same source and push it back in. This touches every element exactly once and never holds more than k elements in the heap at a time, unlike scanning all k sources for the minimum on every step, which redoes that comparison work from scratch each time.
Structured elaboration
Maintain, per source, an iterator (or a buffered read-ahead block if the source is a file or network stream) rather than loading the whole source into memory. The heap holds at most one (value, source_id) pair per still-active source:
- Prime the heap: pull the first element from each source and push all k pairs in.
- Loop while the heap is non-empty: pop the smallest pair, emit its value, then pull the next element from that same source; if one exists, push it back onto the heap.
- Stop when the heap empties, meaning every source is exhausted.
Why the heap beats scanning all k sources for the minimum: a linear scan over k sources costs O(k) per output element, for O(N⋅k) total across N elements. The heap instead pays O(logk) per push and pop, for O(Nlogk) total. Once k grows past a small constant (which it does for genuinely large fan-in, like merging thousands of shards), logk is dramatically cheaper than k, and the heap only ever holds k items regardless of how large each individual source is, which is what makes this work under a fixed memory budget.
Worked example
import heapq
from typing import Iterable, Iterator
def k_way_merge(sources: list[Iterable[int]]) -> Iterator[int]:
heap: list[tuple[int, int, Iterator[int]]] = []
for i, source in enumerate(sources):
it = iter(source)
first = next(it, None)
if first is not None:
heap.append((first, i, it))
heapq.heapify(heap)
while heap:
value, i, it = heapq.heappop(heap)
yield value
nxt = next(it, None)
if nxt is not None:
heapq.heappush(heap, (nxt, i, it))
stream_a = [1, 4, 9, 15]
stream_b = [2, 3, 8]
stream_c = [0, 5, 6, 7, 20]
merged = list(k_way_merge([stream_a, stream_b, stream_c]))
print(merged)
print(merged == sorted(stream_a + stream_b + stream_c))
Running this prints:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 15, 20]
True
Key points
- The heap never grows past k elements no matter how large each source is, which is exactly what makes this work when sources are too large to fit in memory together.
- Each source only needs to expose "give me the current head" and "advance to the next element," which is why the same code works whether a source is a Python list, a sorted linked list, or a buffered file reader.
Complexity
O(Nlogk) time,O(k) heap spacewhere N is the total number of elements across all sources. If sources are read from disk in blocks rather than streamed one element at a time, add O(k⋅block_size) for the read-ahead buffers.
Edge cases
- An empty source: simply contributes nothing to the initial heap priming, handled by the
if first is not Noneguard. - Duplicate values across sources: the heap comparison ties are broken by insertion order in this implementation (via the source index in the tuple), so output remains stable and well-defined.
- All sources exhausted simultaneously: the loop ends naturally when the heap empties.
Trade-offs & pitfalls
For disk-resident or over-the-network sources, reading one element at a time is usually the wrong granularity: buffering a block per source amortizes I/O overhead, at the cost of O(k * block_size) memory instead of O(k). This is the same "k-way-merge" primitive whether the k inputs are k sorted arrays, k sorted linked lists (pop the head node instead of an array iterator), or k disk-resident sorted files too large to hold together, and it generalizes further to an external top-K query across those files by simply stopping the loop after K pops instead of draining the heap. A common mistake is reaching for a full sort of the concatenated data instead of a merge: since each source is already sorted, a merge is O(Nlogk) while re-sorting everything from scratch is O(NlogN), strictly worse whenever k≪N, which is the normal case.
You need the shortest path in a weighted graph. Walk through how you would choose between BFS, Dijkstra, Bellman-Ford, and A*, based on whether edges are weighted, whether negative weights are possible, and whether you need single-source or all-pairs distances. When would A*'s heuristic actually help over plain Dijkstra, and what property must that heuristic have?
Sample Answer
Direct answer
Pick based on two properties of the graph and one property of the query: if every edge has the same weight, breadth-first search (BFS) alone gives shortest paths in linear time; if weights differ but are never negative, Dijkstra's algorithm is the standard single-source choice; if a negative weight is possible (but no negative cycle), Dijkstra can give a wrong answer and Bellman-Ford is required instead; and if you need distances between every pair rather than from one source, Floyd-Warshall (a dynamic-programming algorithm that considers every node in turn as a possible shortcut between every pair) is the natural fit for all-pairs, or equivalently running Dijkstra from every node. A* only changes single-source, non-negative-weight search: it adds a heuristic estimate of remaining distance to prioritize expansion toward a specific goal, and it only helps, versus plain Dijkstra, when that heuristic is admissible (it never overestimates the true remaining cost), since an inadmissible heuristic can cause A* to return a path that is not actually shortest.
Structured elaboration
Decision order:
- Are all edge weights equal (or is the graph unweighted)? Use BFS: O(V+E), no priority queue needed at all.
- Do you need distances between every pair of nodes, not just from one source? Use Floyd-Warshall, O(V3), or repeat Dijkstra from every source if the graph is sparse and there are no negative weights.
- Otherwise, single-source with weights: are negative edge weights possible? If yes, use Bellman-Ford, O(V⋅E), which also detects a negative cycle if one exists (a cycle whose total weight is negative, which makes "shortest path" undefined, since you could loop it forever to keep decreasing the cost). If no, use Dijkstra, O((V+E)logV) with a binary heap.
- If you additionally have a single, known goal node (not "distances to everywhere"), and a decent estimate of remaining distance, layer A* on top of Dijkstra's non-negative-weight assumption to reduce how much of the graph gets explored.
Why Dijkstra breaks under negative weights: once Dijkstra pops a node off its priority queue, it treats that node's distance as final and never revisits it, on the assumption that nothing already queued could possibly offer a shorter path, since all remaining edges only add non-negative weight. A negative edge violates that assumption directly: a longer-looking path discovered later can still turn out shorter once a negative edge is added to it.
What A's heuristic must guarantee*: admissibility, never overestimating the true remaining cost to the goal. Given an admissible heuristic, A* is guaranteed to still find a shortest path, exactly like Dijkstra, but it explores fewer nodes when the heuristic is informative, because it prioritizes nodes that look closer to the goal rather than merely closer to the start. (A stronger property, consistency, additionally guarantees a node is never re-expanded after being finalized, which is what lets A* implementations skip the "revisit and relax an already-closed node" bookkeeping that a merely admissible-but-inconsistent heuristic would otherwise require.) A straight-line (Euclidean) distance heuristic on a road network or grid is a classic admissible choice, since no real route can be shorter than the straight line.
Worked example
Bellman-Ford correctness under a negative edge, where Dijkstra gets it wrong:
import math
def dijkstra(adj, src):
import heapq
dist = {src: 0}
finalized = set()
pq = [(0, src)]
while pq:
d, u = heapq.heappop(pq)
if u in finalized:
continue
finalized.add(u)
for v, w in adj.get(u, []):
if v in finalized:
continue
nd = d + w
if nd < dist.get(v, math.inf):
dist[v] = nd
heapq.heappush(pq, (nd, v))
return dist
def bellman_ford(edges, nodes, src):
dist = {n: math.inf for n in nodes}
dist[src] = 0
for _ in range(len(nodes) - 1):
for u, v, w in edges:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
for u, v, w in edges:
if dist[u] + w < dist[v]:
raise ValueError("negative cycle detected")
return dist
# True shortest A->B is via C: 1 -> 4 + (-10) = -6, but Dijkstra finalizes
# B at distance 1 (direct edge) before C is even processed.
adj = {"A": [("B", 1), ("C", 4)], "C": [("B", -10)]}
edges = [("A", "B", 1), ("A", "C", 4), ("C", "B", -10)]
nodes = ["A", "B", "C"]
print("dijkstra:", dijkstra(adj, "A"))
print("bellman_ford:", bellman_ford(edges, nodes, "A"))
Running this prints:
dijkstra: {'A': 0, 'B': 1, 'C': 4}
bellman_ford: {'A': 0, 'B': -6, 'C': 4}
Dijkstra reports B at distance 1 (wrong: it finalized B via the direct edge before discovering the cheaper route through C), while Bellman-Ford correctly finds -6 via A to C to B.
A exploring fewer nodes than Dijkstra given an admissible heuristic*, on an open 20x20 grid from (0,0) to (5,5), using Manhattan distance as the heuristic:
import heapq
def neighbors(pos, size):
x, y = pos
for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nx, ny = x + dx, y + dy
if 0 <= nx < size and 0 <= ny < size:
yield (nx, ny)
def manhattan(a, b):
return abs(a[0] - b[0]) + abs(a[1] - b[1])
def search(start, goal, size, use_heuristic):
h = (lambda n: manhattan(n, goal)) if use_heuristic else (lambda n: 0)
g = {start: 0}
pq = [(h(start), start)]
visited = set()
expansions = 0
while pq:
_, node = heapq.heappop(pq)
if node in visited:
continue
visited.add(node)
expansions += 1
if node == goal:
break
for nb in neighbors(node, size):
ng = g[node] + 1
if ng < g.get(nb, float("inf")):
g[nb] = ng
heapq.heappush(pq, (ng + h(nb), nb))
return g[goal], expansions
size = 20
start, goal = (0, 0), (5, 5)
dist_astar, exp_astar = search(start, goal, size, use_heuristic=True)
dist_dij, exp_dij = search(start, goal, size, use_heuristic=False)
print("A* distance:", dist_astar, "nodes expanded:", exp_astar)
print("Dijkstra distance:", dist_dij, "nodes expanded:", exp_dij)
Running this prints:
A* distance: 10 nodes expanded: 36
Dijkstra distance: 10 nodes expanded: 61
Both find the same correct shortest distance (10), but A* reaches it having expanded 36 nodes against Dijkstra's 61, because the heuristic steered expansion toward the goal instead of outward in every direction equally.
Trade-offs & pitfalls
A common mistake is treating A* as "a different algorithm" from Dijkstra rather than as Dijkstra with a heuristic added to the priority; with a heuristic of zero everywhere (as in the comparison above), A* degenerates to exactly Dijkstra, which is a good way to check an A* implementation for bugs. A second pitfall is picking a heuristic that overestimates in some region "because it prunes more nodes": an inadmissible heuristic can make A* return a path that is not actually shortest, so any heuristic must be checked against the admissibility property, not just judged by how much it speeds things up. Practically, Dijkstra's own implementation constant matters too: with a binary heap, each edge relaxation that improves a distance costs O(logV) to sift, which under many decrease-key-style relaxations is the dominant cost; the common fix is not switching to a Fibonacci or pairing heap (both have amortized O(1) or near-O(1) decrease-key but carry higher constant factors and more complex implementations) but instead allowing duplicate, stale entries in a plain binary heap and lazily discarding them on pop, which is what the Dijkstra implementation above already does and is the standard practical choice.
Implement a prefix-tree structure that supports insert(word), search(word), and startsWith(prefix). Then explain why this beats a plain hash set of words when the workload is dominated by prefix queries rather than exact-match lookups.
Sample Answer
Direct answer
A trie (prefix tree) stores strings by sharing common prefixes as a path through a tree of characters: each node holds child pointers keyed by the next character, plus a marker for "a word ends here". insert, search, and startsWith all walk that path one character at a time, so each costs O(L) where L is the length of the word or prefix, independent of how many other words are stored. That's exactly what beats a hash set once the workload shifts to prefix queries: a hash set can tell you whether one exact string is a member in O(L), but it has no way to answer "give me everything starting with pre" except scanning every stored string.
Approach
- Each
TrieNodeholds a dictionary of child nodes keyed by character, plus anis_wordflag. insert(word): walk from the root, creating a child node for each character not already present, then mark the final node'sis_wordas true.search(word): walk the same path; if any character is missing, the word isn't stored. If the path exists, the word is present only if the final node'sis_wordis true (this is what distinguishes an exact match from merely being a prefix of something else).startsWith(prefix): identical walk, but the answer is simply whether the path exists at all;is_wordis irrelevant.
class TrieNode:
__slots__ = ("children", "is_word")
def __init__(self):
self.children: dict[str, "TrieNode"] = {}
self.is_word = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word: str) -> None:
node = self.root
for ch in word:
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
node.is_word = True
def _walk(self, prefix: str):
node = self.root
for ch in prefix:
if ch not in node.children:
return None
node = node.children[ch]
return node
def search(self, word: str) -> bool:
node = self._walk(word)
return node is not None and node.is_word
def startsWith(self, prefix: str) -> bool:
return self._walk(prefix) is not None
if __name__ == "__main__":
trie = Trie()
trie.insert("apple")
print(trie.search("apple")) # True
print(trie.search("app")) # False: "app" was never inserted as a word
print(trie.startsWith("app")) # True: it's a valid prefix path
trie.insert("app")
print(trie.search("app")) # True: now it's an inserted word too
Running this prints True, False, True, True, showing the exact distinction between a prefix existing in the tree and a full word being marked at that node.
Key points
- Sharing prefixes is the whole benefit: "app", "apple", and "application" only pay for the divergent suffixes once "app" has been walked.
- Trie versus hash table, concretely: reach for a trie when the workload needs prefix queries, autocomplete, or longest-prefix matching (for example IP routing or URL routing tables), since a hash set has no ordering by prefix at all. Reach for a hash set when you only ever need exact-match membership and words rarely share prefixes, since a trie pays a real per-character node overhead that a flat hash set avoids.
- Deletion (not shown above) needs care: unmark
is_wordat the target node, then optionally prune nodes back up toward the root, but only while a node has no children and isn't itself marking a shorter stored word.
Complexity
insert: O(L) time, up to O(L) new nodes in the worst case (no shared prefix). search: O(L) time, O(1) extra space. startsWith(prefix): O(P) time where P is the prefix length. Overall trie space is O(total characters across all stored words) in the worst case, less whenever words share prefixes.
Edge cases
- Empty string:
insert("")marks the root itself as a word;search("")andstartsWith("")should both be true afterward. - A prefix longer than any stored word simply fails the walk partway through and returns the correct negative.
- Re-inserting the same word is idempotent (no duplicate storage,
is_wordjust gets set again). - Large alphabets (Unicode) increase the practical memory cost per node since the child dictionary can hold far more distinct keys; a compressed trie (radix/PATRICIA tree, collapsing single-child chains) reduces node count when words rarely branch.
You are given a list of courses and prerequisite pairs: to take course A you must first take course B. Determine whether it is possible to finish all courses, and if so, produce one valid order to take them in. What should your algorithm do if the prerequisites contain a cycle?
Sample Answer
Direct answer
Model the courses as a directed graph where an edge from a prerequisite B to a course A means "B must come before A", then run Kahn's algorithm: repeatedly take any course whose remaining prerequisite count (its indegree) is zero, add it to the order, and decrement the indegree of everything it unlocks. If every course gets processed this way, the resulting order is valid. If the queue empties while courses still have a nonzero indegree, those courses form a cycle, a prerequisite loop that can never be satisfied, and finishing all courses is impossible.
Approach
- Build an adjacency list (prerequisite to course) and an indegree array (how many unprocessed prerequisites each course still has).
- Seed a queue with every course that already has indegree zero.
- Repeatedly pop a course, append it to the output order, and for every course it unlocks, decrement that course's indegree; if it hits zero, enqueue it.
- If the final order's length equals the number of courses, it's a valid full order; otherwise the remaining, never-enqueued courses are exactly the ones stuck in a cycle.
from collections import deque
from typing import List, Tuple
def find_order(num_courses: int, prerequisites: List[Tuple[int, int]]) -> List[int]:
"""prerequisites: list of (course, prereq) pairs meaning 'course'
depends on 'prereq'. Returns a valid order, or [] if a cycle makes
finishing all courses impossible."""
adj: list[list[int]] = [[] for _ in range(num_courses)]
indeg = [0] * num_courses
for course, prereq in prerequisites:
adj[prereq].append(course)
indeg[course] += 1
queue = deque(c for c in range(num_courses) if indeg[c] == 0)
order: list[int] = []
while queue:
node = queue.popleft()
order.append(node)
for nxt in adj[node]:
indeg[nxt] -= 1
if indeg[nxt] == 0:
queue.append(nxt)
return order if len(order) == num_courses else []
if __name__ == "__main__":
# course 1 needs 0, course 2 needs 0, course 3 needs 1 and 2
print(find_order(4, [(1, 0), (2, 0), (3, 1), (3, 2)]))
# cycle: 0 needs 1, 1 needs 0
print(find_order(2, [(0, 1), (1, 0)]))
Running this prints [0, 1, 2, 3] for the first case (course 0 has no prerequisites, unlocks 1 and 2, which both unlock 3) and [] for the second (a two-course cycle where neither course ever reaches indegree zero).
Key points
- The indegree count is exactly "how many prerequisites this course is still waiting on"; a course only becomes eligible once that count hits zero.
- Multiple valid orders can exist whenever more than one course is simultaneously eligible; if a canonical, reproducible order matters (for example a deterministic build or test replay), swap the queue for a min-heap to always take the smallest eligible course id next, which costs O(logk) per pop instead of O(1), where k is the number of currently eligible courses.
- A directed acyclic graph (DAG) is the name for the acyclic case that always has at least one valid topological order; the moment a cycle exists, no such order can exist for the courses on that cycle.
Complexity
Time: O(V+E) where V is the number of courses and E is the number of prerequisite pairs (each course and each edge is processed exactly once). Space: O(V+E) for the adjacency list and indegree array.
Edge cases
- Disconnected components or isolated courses (no prerequisites and nothing depends on them) are scheduled immediately, since their indegree starts at zero.
- A course listed as its own prerequisite is a one-node cycle and is caught by the same length check.
- Duplicate prerequisite pairs inflate the indegree count but don't change correctness, since the count still reaches zero at the same logical point (one extra decrement per duplicate, which the duplicate edge itself supplies).
- An empty prerequisite list means every order of the courses is valid.
- Checking only "did the queue run empty" without also checking that the output length equals the course count is the most common bug: a graph can have one small cycle alongside many unrelated, fully resolvable courses, and skipping the length check silently returns an incomplete, invalid order.
Rotate an array to the right by k steps in-place, using O(1) extra space (k may exceed the array's length). Explain your approach, and how the same in-place three-reversal trick generalizes: reversing a string in place, or rotating a 2D matrix in place.
Sample Answer
Direct answer
Reverse the whole array, then reverse the first k elements and the remaining n-k elements separately; three linear passes compose into the fully rotated result with no auxiliary array. The same reversal trick generalizes directly: reversing a string in place is the identical two-pointer, swap-from-both-ends routine, and rotating a square matrix 90 degrees in place is a transpose followed by reversing each row, both built on the same in-place-swap primitive as the array rotation.
Structured elaboration
Why three reversals produce a rotation. Reversing the entire array puts every element in fully reversed order. Reversing the first k elements of that reversed array un-reverses exactly the block that should now sit at the front, restoring its original relative order; reversing the remaining n-k elements does the same for the remainder. Normalizing with k %= n handles k values larger than the array's length or equal to zero.
Generalizing to a string. The same in-place two-pointer swap from both ends is exactly what reverses a string, provided the string is held in a mutable container (a list of characters, for example, since Python's own string type is immutable and cannot be reversed truly in place without first converting it).
Generalizing to a square matrix. Transposing swaps matrix[i][j] with matrix[j][i] for every i < j, turning rows into columns. Reversing each row afterward flips left to right. Combined, what was the first column read top to bottom becomes the first row read left to right, which is exactly a 90-degree clockwise turn.
Related in-place-preprocessing techniques (with an honest space caveat). Prefix-sum preprocessing builds an auxiliary array once, in O(n) time, so that any later range-sum query answers in O(1); this trades O(n) extra space for fast queries, so it is not itself an O(1)-extra-space technique, even though it shares this family's "one linear pass, reuse the result" character. Product-except-self, by contrast, genuinely can be done with O(1) extra space beyond the required output array: a first pass fills the output with the running product of everything to each index's left, and a second pass multiplies in the running product of everything to that index's right, needing no separate auxiliary array at all.
Worked example
def rotate_array(nums: list[int], k: int) -> None:
n = len(nums)
if n <= 1:
return
k %= n
if k == 0:
return
def reverse(i, j):
while i < j:
nums[i], nums[j] = nums[j], nums[i]
i += 1
j -= 1
reverse(0, n - 1)
reverse(0, k - 1)
reverse(k, n - 1)
def reverse_string_inplace(chars: list[str]) -> None:
i, j = 0, len(chars) - 1
while i < j:
chars[i], chars[j] = chars[j], chars[i]
i += 1
j -= 1
def rotate_matrix_90_cw_inplace(matrix: list[list[int]]) -> None:
n = len(matrix)
for i in range(n):
for j in range(i + 1, n):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
for row in matrix:
row.reverse()
if __name__ == "__main__":
arr = [1, 2, 3, 4, 5, 6, 7]
rotate_array(arr, 3)
print(arr)
chars = list("hello")
reverse_string_inplace(chars)
print("".join(chars))
m = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
rotate_matrix_90_cw_inplace(m)
print(m)
Running this prints [5, 6, 7, 1, 2, 3, 4], then olleh, then [[7, 4, 1], [8, 5, 2], [9, 6, 3]].
Complexity
rotate_array: time O(n) for the three reversal passes, since they compose additively into a single linear scan rather than multiplying; space O(1) extra, using only the two index pointers inside each reversal call.
reverse_string_inplace: time O(n), one pass with two pointers closing in from both ends; space O(1) extra beyond the mutable character list itself.
rotate_matrix_90_cw_inplace: time O(n2) for an n-by-n matrix, since the transpose visits each of the n2 cells once; space O(1) extra, since both the transpose and the row reversals swap in place with no auxiliary matrix.
Edge cases
- k = 0, or k a multiple of the array's length once normalized via
k %= n:rotate_arraydetects this and returns immediately without performing any reversals, since the array is already in its correct rotated position. - Empty or single-element array or string: both
rotate_array(via itsn <= 1guard) andreverse_string_inplace(viawhile i < jnever firing) return immediately with nothing to do. - A non-square matrix passed to
rotate_matrix_90_cw_inplace: this implementation assumes a square matrix, and a non-square transpose changes the matrix's dimensions, so it cannot be rotated true in place this way.
Trade-offs & pitfalls
Forgetting k %= n for a k larger than the array's length either wastes work or, in a careless implementation, indexes out of range. The transpose-then-reverse-rows trick only works for a square matrix: transposing a non-square matrix changes its dimensions, so a genuinely non-square rotation needs a separate output buffer rather than a true in-place transform. Python's string immutability means a real in-place string reversal needs a mutable container (a list of characters, or a bytearray) first; there is no way to mutate a str object's characters directly.
Unlock Full Question Bank
Get access to all Algorithmic Problem-Solving and Data Structure Selection interview questions and detailed answers.
Sign in to ContinueJoin thousands of developers preparing for their dream job.