Algorithmic Problem-Solving and Data Structure Selection Questions

Direct answer

Reach for a self-balancing tree over a hash table specifically when ordered iteration, range queries, or a worst-case (not just average-case) time guarantee is needed; a hash table's O(1) average lookup has no built-in notion of order and can degrade to O(n) in the worst case, while a balanced tree guarantees O(log n) for every operation and keeps keys in sorted order at all times. When only point lookups are ever needed, and order, range, and worst-case behavior never matter, the balancing overhead of a tree buys nothing and a hash table is strictly cheaper.

Structured elaboration

What a hash table fundamentally cannot give you

• Ordered iteration: walking a hash table's contents comes out in whatever order the hash function and internal layout produced, not sorted order; a balanced tree's in-order traversal is always sorted.
• Range queries: "give me every key between A and B," or "find the next key after X" (predecessor/successor), requires either scanning the entire hash table or maintaining a second sorted structure; a balanced tree answers both in O(log n + m), where m is the number of results returned.
• Worst-case guarantees: a hash table's O(1) average case relies on the hash function spreading keys evenly. A pathological input, or an attacker deliberately choosing keys (a hash-flooding attack), can degrade every operation to O(n) in the worst case. A balanced tree's O(log n) bound holds for every input, not just typical ones, because it comes from the tree's structural invariant, not from statistical spread.

AVL vs red-black: two ways to bound the height

Because AVL keeps a tighter height bound, point lookups are on average slightly faster (fewer comparisons); because red-black tolerates more imbalance before rotating, insert and delete are on average cheaper. Neither difference is large in practice, and both are asymptotically O(log n); the choice matters more in workloads with extreme read/write ratios than in typical applications.

When the balancing overhead isn't worth paying

• Point-lookup-only workloads (caches, sets, deduplication) with no ordering or range needs: use a hash table.
• On-disk storage, such as database indexes: neither AVL nor red-black trees are the right structure at all. A B-tree (a tree with a much higher branching factor than a binary tree, so each node holds many keys) is preferred for on-disk indexes because it minimizes the number of disk-block reads: each node read is one I/O, and a wide branching factor means far fewer levels than a binary tree for the same key count. An in-memory red-black or AVL tree assumes uniformly cheap pointer-chasing, which doesn't hold once each node access might be a disk seek.

Worked example

For n = 1,000,000 keys, the exact minimum-node recurrence for AVL trees (the same Fibonacci-like relation used to derive the roughly 1.44 log2 n bound) gives a provable worst-case height of 27: an AVL tree needs at least 832,039 nodes to reach height 27, so 1,000,000 nodes cannot exceed height 27. The classical red-black bound, $2 \log_2(n+1)$, evaluates to about 39.86 for the same n, so at most 39. For comparison, an ideal perfectly balanced binary tree has height floor(log2(1,000,000)) = 19, and a plain unbalanced binary search tree (BST, a tree where every node's left subtree holds smaller keys and its right subtree holds larger keys) built from sorted-order inserts degrades to height 999,999 (a straight chain).

import math

def max_avl_height_for_n(n):
    min_nodes = {-1: 0, 0: 1}
    h = 0
    while min_nodes[h] <= n:
        h += 1
        min_nodes[h] = min_nodes[h - 1] + min_nodes[h - 2] + 1
    return h - 1, min_nodes[h - 1]

n = 1_000_000
avl_h, avl_min_nodes = max_avl_height_for_n(n)
rb_bound = 2 * math.log2(n + 1)
print(f"ideal height: {math.floor(math.log2(n))}")
print(f"AVL worst-case height: {avl_h} (needs >= {avl_min_nodes:,} nodes)")
print(f"red-black worst-case height bound: {rb_bound:.2f} -> at most {math.floor(rb_bound)}")
print(f"unbalanced BST worst case: {n - 1:,}")

prints:

ideal height: 19
AVL worst-case height: 27 (needs >= 832,039 nodes)
red-black worst-case height bound: 39.86 -> at most 39
unbalanced BST worst case: 999,999

All four numbers describe worst-case comparisons for a single lookup on the same one million keys; the practical takeaway is that both AVL and red-black stay within roughly 2x of the theoretical minimum even in their worst case, while an unbalanced BST has no such guarantee at all.

Trade-offs & pitfalls

A hash table with open addressing or chaining still needs periodic resizing to keep its average O(1) guarantee, and a resize is an O(n) operation, though amortized (its cost spread evenly across the many O(1) inserts that led to it) over the sequence of inserts that triggered it, similar in spirit to how a dynamic array's occasional resize is amortized across its appends.

Concurrent access: red-black trees are generally easier to adapt to concurrent or lock-free implementations than AVL trees, because their rebalancing needs fewer structural changes per insert.

A common mistake is defaulting to a balanced tree "for safety" when a hash table would do, paying O(log n) for every operation when O(1) average was available and ordering was never actually needed. The opposite mistake is relying on a hash table's average-case guarantee in a context where an adversary controls the keys, for example a public API accepting arbitrary user-supplied strings as hash keys, where the worst case is a real risk rather than a theoretical one.

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:

1. Are all edge weights equal (or is the graph unweighted)? Use BFS: $O(V + E)$, no priority queue needed at all.
2. Do you need distances between every pair of nodes, not just from one source? Use Floyd-Warshall, $O(V^3)$, or repeat Dijkstra from every source if the graph is sparse and there are no negative weights.
3. Otherwise, single-source with weights: are negative edge weights possible? If yes, use Bellman-Ford, $O(V \cdot 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) \log V)$ with a binary heap.
4. 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(\log V)$ 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.

Direct answer

A recursive factorial mirrors the mathematical definition directly (n! = n * (n-1)!) and is easy to read, but every call adds a stack frame that must stay alive until its recursive call returns (so it can perform the pending multiplication), costing $O(n)$ call-stack space. An iterative version computes the same result in a simple loop with $O(1)$ extra space and no risk of hitting a language's recursion-depth limit. Convert to iteration (or, in languages that support it, tail-recursive form with an accumulator) whenever input size could be large or unpredictable enough to threaten stack depth, and keep plain recursion where it makes a naturally tree-shaped or divide-and-conquer problem clearer to read.

Structured elaboration

Recursive (not tail-recursive).

def factorial_recursive(n):
    """Compute n! recursively. Not tail-recursive: the multiplication by n
    happens AFTER the recursive call returns, so a frame must stay on the
    call stack waiting for that multiplication."""
    if n < 0:
        raise ValueError("n must be non-negative")
    if n == 0:
        return 1
    return n * factorial_recursive(n - 1)

Tail-recursive form. A call is "tail recursive" when the recursive call is the very last action taken, with nothing left to do after it returns. factorial_recursive above is not tail recursive: after factorial_recursive(n - 1) returns, the function still has to multiply by n. Rewriting with an accumulator argument that carries the running product forward makes the recursive call itself the last action:

def factorial_tail(n, accumulator=1):
    """Tail-recursive form: the recursive call is the last action, and the
    running product is threaded through as an argument instead of being
    computed after the call returns. (Python does not optimize tail calls,
    so this still uses O(n) stack frames in CPython -- the rewrite only
    pays off in languages/runtimes with tail-call elimination.)"""
    if n < 0:
        raise ValueError("n must be non-negative")
    if n == 0:
        return accumulator
    return factorial_tail(n - 1, accumulator * n)

Iterative form.

def factorial_iterative(n):
    """Compute n! iteratively. O(1) extra space (excluding the result)."""
    if n < 0:
        raise ValueError("n must be non-negative")
    result = 1
    for k in range(2, n + 1):
        result *= k
    return result

Whether the tail-recursive rewrite actually saves stack space depends entirely on the runtime: languages and runtimes that implement tail-call elimination reuse the current frame for the tail call, giving true $O(1)$ space; CPython does not do this, so factorial_tail still consumes one stack frame per call in Python, and the accumulator rewrite is mainly a stepping stone toward the fully iterative version rather than a real fix on its own in this language.

Naive recursive Fibonacci as a cautionary contrast. Recursion's clarity can hide a much worse problem than stack depth: naive recursive Fibonacci recomputes the same subproblems exponentially many times, because fib(n) calls both fib(n-1) and fib(n-2), and those calls each re-derive overlapping smaller values independently instead of sharing them.

call_count = 0

def fib_naive(n):
    global call_count
    call_count += 1
    if n < 2:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)

Worked example

print(factorial_recursive(10), factorial_tail(10), factorial_iterative(10))

for n in (10, 20, 30):
    call_count = 0
    result = fib_naive(n)
    print(f"fib_naive({n}) = {result}, calls = {call_count}")

import sys
print("current recursion limit:", sys.getrecursionlimit())

Output:

3628800 3628800 3628800
fib_naive(10) = 55, calls = 177
fib_naive(20) = 6765, calls = 21891
fib_naive(30) = 832040, calls = 2692537
current recursion limit: 1000

All three factorial implementations agree on 10! = 3628800. The Fibonacci call counts show the exponential blowup directly: going from n=10 to n=20 (10 more) multiplies the call count by roughly 124x, and from n=20 to n=30 (10 more again) by roughly 123x, consistent with call count growing on the order of $O(\varphi^n)$ where $\varphi \approx 1.618$ is the golden ratio (memoizing or converting to an iterative bottom-up loop would fix this in $O(n)$ time, but that is a dynamic-programming technique, not a recursion-vs-iteration one).

Trade-offs & pitfalls

Key points

• Recursion's main cost is call-stack depth, not raw runtime: factorial_recursive and factorial_iterative do the same $O(n)$ multiplications, but only the recursive version risks a stack-depth error for large n.
• Rewriting to tail-recursive form is a code-shape change, not a guaranteed performance fix; check whether your language and runtime actually perform tail-call elimination before relying on it to save stack space.
• Naive recursive Fibonacci is a different failure mode entirely: it is not a stack-depth problem but a wasted-work problem, caused by recomputing identical overlapping subproblems; the fix (memoization or an iterative bottom-up loop) is a dynamic-programming technique, separate from the recursion-vs-iteration question this answer is centered on.

Complexity

• Recursive and iterative factorial: both $O(n)$ time; recursive uses $O(n)$ call-stack space, iterative uses $O(1)$ extra space.
• Naive recursive Fibonacci: $O(\varphi^n)$ time (exponential), $O(n)$ call-stack space (the deepest single call chain).

Edge cases

• Negative input: all three factorial functions raise ValueError explicitly rather than recursing or looping incorrectly.
• n = 0 or n = 1: all three correctly return 1 as the base case.
• Very large n for the recursive forms: Python's default recursion limit (commonly 1000) will raise a RecursionError well before overflowing the actual OS thread stack, since CPython enforces its own configurable limit; the iterative form has no such ceiling beyond available memory and integer size.

Direct answer

A disjoint-set (union-find) structure represents each group as a tree, where every element points to a parent and the root is the group's representative; "same group" is answered by walking both elements up to their roots and comparing, and "merge" is answered by pointing one root at the other. Union by rank keeps those trees shallow in the first place, and path compression flattens a tree every time you walk it, so together the trees stay so flat that both operations run in what is, for any practical input size, effectively constant time.

Structured elaboration

Each element starts as its own group (its own root). Two operations:

• find(x): follow x's parent pointers up to the root of its tree; that root identifies the group.
• union(a, b): find both roots; if they differ, attach one root under the other, merging the two trees into one.

What union by rank contributes on its own: always attach the shorter tree under the taller one's root (tracked by a rank estimate, not the exact height). This alone caps every tree's height at $O(\log n)$, because a tree can only grow taller by merging with another tree of at least equal height, which at minimum doubles its size, so height can double only $\log n$ times. Without path compression, find on such a tree costs $O(\log n)$.

What path compression contributes on its own: every time find(x) walks up to the root, repoint every node on that path directly to the root. This flattens the tree along exactly the paths that get queried. Used alone (without union by rank), the classical result (Tarjan and van Leeuwen) is that a sequence of operations still costs only $O(\log n)$ amortized per operation, because repeated queries on the same region keep flattening it further.

Combined: the two heuristics interact so that the amortized cost per operation in a sequence of $m$ operations on $n$ elements is:

where $\alpha(n)$ is the inverse Ackermann function: it grows so slowly that $\alpha(n) \le 4$ for any $n$ up to sizes far beyond anything a real system would hold, so the bound is, for practical purposes, constant time per operation. This tighter bound (Tarjan's result) is strictly better than either heuristic's individual $O(\log n)$ bound, which is why interviewers ask for both.

Worked example

class DisjointSet:
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x: int) -> int:
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # path compression
        return self.parent[x]

    def union(self, a: int, b: int) -> bool:
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra              # union by rank
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        return True


ds = DisjointSet(6)  # elements 0..5
for a, b in [(0, 1), (1, 2), (3, 4)]:
    ds.union(a, b)
print([ds.find(x) for x in range(6)])
print(ds.find(2) == ds.find(0))
print(ds.find(3) == ds.find(5))
ds.union(2, 3)
print(ds.find(5) == ds.find(0))
print(ds.find(4) == ds.find(0))

Running this prints:

[0, 0, 0, 3, 3, 5]
True
False
False
True

After the first three unions, elements 0, 1, 2 share root 0 and elements 3, 4 share root 3 (5 stands alone), matching the printed parent list. After union(2, 3), groups {0,1,2} and {3,4} merge, so 0 and 4 report the same root while 5 remains separate.

Trade-offs & pitfalls

A disjoint-set structure only answers connectivity, not path reconstruction: it cannot tell you the sequence of edges between two elements the way a breadth-first search (BFS, a graph traversal that explores nodes level by level) tree can, so if a caller needs the actual path, this is the wrong structure. It also has no built-in support for splitting a group back apart (undoing a union); if you need rollback, either use union by rank without path compression (so you can reverse exactly the pointer changes you made) or keep an explicit undo log of the parent and rank values you overwrote. Real systems reach for union-find well beyond one domain: cycle detection while building an undirected graph (an edge closes a cycle exactly when its two endpoints already share a root), counting connected components (the number of distinct roots after all unions), Kruskal's minimum-spanning-tree algorithm, and dynamic connectivity checks in build or dependency graphs, wherever "are these already linked" needs to be asked repeatedly as links are added.

Edge cases

• Out-of-range index: find and union do not validate their input; calling either with an index outside [0, n) indexes past the end of self.parent/self.rank and raises an IndexError rather than failing gracefully.
• Self-union (union(a, a)): find(a) == find(a) always holds, so ra == rb is true and union returns False immediately with no parent-pointer changes; unioning an element with itself is always a safe no-op.
• n=0: DisjointSet(0) builds empty parent/rank lists, so any subsequent find or union call has no valid index to operate on and raises an IndexError, the same as any other out-of-range call.

Direct answer

An array gives $O(1)$ index-based random access and is cache-friendly, because its elements sit in one contiguous block of memory that the CPU can pull into cache together. A singly linked list gives $O(1)$ insertion or deletion once you already hold a reference to the splice point, at the cost of $O(n)$ traversal to reach any given position and extra per-node memory overhead. For a workload that is mostly random reads, pick an array (or dynamic array); for a workload that is mostly insertions and deletions in the middle where you already hold the relevant node reference, a linked list wins.

Structured elaboration

The contiguous-versus-non-contiguous memory allocation framing is exactly this same dimension stated differently: contiguous storage is what gives arrays both their cache locality and their index arithmetic; non-contiguous, per-node allocation is what gives linked lists their cheap local splicing at the cost of locality. In a garbage-collected (GC) language, this also affects collector pressure: many small linked-list node objects mean more individual objects for the garbage collector to track and scan, compared to one contiguous array allocation holding the same data.

Worked example

Consider inserting a new element in the middle of a ten-item collection, repeatedly, as items are typed into an editable list. With an array, each insertion must shift every element after the insertion point one slot over, an $O(n)$ cost per insertion regardless of whether you know exactly where to insert. With a singly linked list, if the editing position is tracked by an existing reference to the node just before it (as a cursor would be in a text-editing context), each insertion is a pure $O(1)$ relink; but if you only know the position as an index and must first walk from the head to reach it, the linked list gains nothing over the array for that access, since both now cost $O(n)$ overall. This is why the deciding factor is not "array versus linked list" in the abstract, but whether the workload naturally hands you a reference to the splice point or only an index.

Trade-offs & pitfalls

Assuming "$O(1)$ insertion" for a linked list means fast in absolute terms is a common mistake: reaching the splice point is usually the dominant cost unless a reference to it is already in hand from a prior traversal or an auxiliary index. Ignoring the per-element memory overhead ratio is another: a linked list of single integers can use several times the memory of the equivalent array, because the pointer overhead per node is fixed regardless of how small the stored value is. Modern hybrid structures such as a deque (double-ended queue) or a rope address parts of this trade-off by chunking data into contiguous blocks rather than choosing purely one extreme or the other.