Algorithmic Problem-Solving and Data Structure Selection Questions

Direct answer

A binary heap is a complete binary tree (every level full except possibly the last, which fills left to right) stored compactly in an array. A min-heap keeps every parent less than or equal to its children, so the root is always the minimum; a max-heap keeps every parent greater than or equal to its children, so the root is always the maximum. Insert and extract-min/max both cost $O(\log n)$ because each only has to fix a single root-to-leaf path, while peek is $O(1)$ since the answer always sits at the root. Reach for a heap over a balanced binary search tree (BST) or a plain hash table specifically when the operation you actually need is "give me the current min or max, repeatedly, while other items keep arriving": a heap does that with a simpler structure and lower constant factors than a full BST, and a hash table can't do it at all without a full scan.

Structured elaboration

Array representation and core operations (0-indexed; for a node at index $i$, its children sit at $2i+1$ and $2i+2$)

• Insert: append the new value at the next free array slot, then "sift up", swapping it with its parent while the heap property is violated. Time $O(\log n)$ (tree height), space $O(1)$ auxiliary.
• Peek: return the root value directly. Time $O(1)$.
• Extract-min/max: read the root, move the last array element into the root position, shrink the array by one, then "sift down" from the root, swapping with the smaller (or larger) child until the heap property holds. Time $O(\log n)$.
• Build-heap (heapify) from an existing array: run sift-down starting from the last non-leaf node back to the root, not one insert at a time. This costs $O(n)$ total, not $O(n \log n)$: most nodes sit near the bottom of the tree and only need a short sift-down, and the sum of sift-down work across all levels is a convergent series bounded by $O(n)$, tighter than treating it as $n$ separate $O(\log n)$ inserts.

Heap versus balanced BST versus hash table

Use a heap when you repeatedly need the current best item and nothing else about ordering; use a BST when you also need range queries, in-order traversal, or predecessor/successor lookups; use a hash table when you only need arbitrary-key existence or lookup and never need the min, max, or any ordering.

Worked example

A concrete use of a min-heap of bounded size $k$ to track the top-$k$ largest values in a stream: push each new value; once the heap holds $k$ items, only replace the root (the current smallest of the kept set) if the new value is larger.

import heapq


def top_k_largest(nums: list[int], k: int) -> list[int]:
    heap: list[int] = []
    for x in nums:
        if len(heap) < k:
            heapq.heappush(heap, x)
        elif x > heap[0]:
            heapq.heapreplace(heap, x)
    return sorted(heap, reverse=True)


if __name__ == "__main__":
    nums = [7, 2, 9, 4, 1, 8, 3, 10, 5, 6]
    print(top_k_largest(nums, 3))

Running this prints [10, 9, 8]: the heap only ever holds the 3 largest values seen so far, each of the other 7 values is checked against the current smallest kept value (the root) in $O(1)$ and, if larger, replaces it in $O(\log k)$, for a total cost of $O(m \log k)$ across $m$ input values.

Trade-offs & pitfalls

• Inserting $n$ elements one at a time into an empty heap costs $O(n \log n)$ total; heapify builds the same final structure in $O(n)$. Both produce a valid heap, only the construction cost differs, and conflating the two is a common mistake.
• A heap does not support efficient arbitrary-key lookup or a "decrease this specific key's priority" operation without extra bookkeeping (an auxiliary map from key to its current array position); this matters for algorithms like Dijkstra's shortest-path algorithm that rely on decrease-key.
• $k$-ary heaps (each node has $k$ children instead of 2) trade a shallower tree, so insert and decrease-key touch fewer levels, for a more expensive sift-down, since each step now compares against $k$ children instead of 2; they help when insert/decrease-key frequency dominates extraction frequency.
• Duplicate keys are allowed by the heap property; the ordering among equal keys is unspecified and shouldn't be relied upon.

Direct answer

Quicksort is in-place with average time $O(n \log n)$ but a worst case of $O(n^2)$ on an unlucky pivot sequence; merge sort and heap sort both guarantee $O(n \log n)$ in every case. Merge sort needs $O(n)$ extra space and is stable; heap sort needs only $O(1)$ extra space but is not stable; quicksort's extra space is $O(\log n)$ for the recursion stack on average, but can grow to $O(n)$ in the worst case. For nearly-sorted data, pick an adaptive sort such as TimSort (the hybrid merge/insertion sort behind Python's and Java's built-in sort); when a guaranteed worst case matters more than average speed, pick heap sort or merge sort, never plain quicksort.

Structured elaboration

Nearly-sorted input

Plain quicksort and plain top-down merge sort are not adaptive: both do the same $O(n \log n)$ work regardless of how ordered the input already is. TimSort is: it scans for existing ascending or descending runs, extends and merges them, and degrades toward close to linear work as the input approaches already-sorted. For nearly-sorted data, reach for TimSort (or, if you must hand-roll something, a natural merge sort) rather than a textbook quicksort or merge sort.

Worst-case guarantees matter more than average speed

Both heap sort and merge sort guarantee $O(n \log n)$ in every case; quicksort does not, no matter how the pivot is chosen, because an adversary (or, unintentionally, already-sorted or already-reverse-sorted input under a naive pivot rule) can always construct a sequence that degrades a fixed pivot strategy to $O(n^2)$. Choose heap sort when the extra $O(n)$ memory merge sort needs is unavailable and stability is not required; choose merge sort when stability is required alongside the worst-case guarantee and the memory budget allows it.

Two side notes worth naming explicitly

• Parallelization on resource-constrained devices: merge sort's divide phase maps cleanly onto independent worker threads or cores (each half sorts independently before a merge step), which is attractive on a multi-core mobile device; the cost is the extra O(n) buffer merge sort needs, which is a real constraint on memory-limited hardware. Quicksort's partitions can also be sorted concurrently, but partition sizes are unpredictable (a skewed pivot gives one thread almost all the work), so load balancing is harder to reason about.
• Cross-language floating-point sort determinism: when the same data is sorted by comparator across different languages or platforms, an unstable sort's tie-breaking for equal keys is unspecified and can differ, and NaN comparisons under IEEE 754 floating point are neither less-than nor greater-than any value, which breaks the total-order assumption most sort implementations rely on. If reproducible ordering across systems matters (for example, deterministic test fixtures or replaying a pipeline), use a stable sort and either exclude or explicitly place NaNs, rather than relying on the default comparator.

Worked example

A concrete way to see the worst case: implement a plain quicksort that always pivots on the last element, and run it on an already-sorted array.

def quicksort_last_pivot_count(a: list[int]) -> int:
    """
    Naive quicksort that always pivots on the last element.
    Returns the number of comparisons performed (element-to-pivot checks).
    """
    comparisons = 0

    def sort(lo: int, hi: int) -> None:
        nonlocal comparisons
        if lo >= hi:
            return
        pivot = a[hi]
        store = lo
        for i in range(lo, hi):
            comparisons += 1
            if a[i] < pivot:
                a[i], a[store] = a[store], a[i]
                store += 1
        a[store], a[hi] = a[hi], a[store]
        sort(lo, store - 1)
        sort(store + 1, hi)

    sort(0, len(a) - 1)
    return comparisons


if __name__ == "__main__":
    for n in [6, 10, 20]:
        already_sorted = list(range(n))
        c = quicksort_last_pivot_count(already_sorted)
        expected = n * (n - 1) // 2
        print(f"n={n}: comparisons={c}, n(n-1)/2={expected}")

Running this prints:

n=6: comparisons=15, n(n-1)/2=15
n=10: comparisons=45, n(n-1)/2=45
n=20: comparisons=190, n(n-1)/2=190

Every partition step on already-sorted input with a last-element pivot puts everything on one side, so the recursion depth is n and the total comparisons are exactly $n(n-1)/2 = \Theta(n^2)$, confirmed by the counts matching the closed-form prediction at every size tested. A randomized or median-of-three pivot choice avoids this specific failure mode but does not eliminate the worst case in general, only make it exponentially unlikely to hit by chance.

Trade-offs & pitfalls

The most common wrong turn is treating quicksort as unconditionally the fastest choice: on already-sorted or reverse-sorted input under a naive pivot rule, it is the slowest of the three by an order of magnitude, as the worked example shows directly. A second common gap is forgetting that merge sort's memory cost is real: at large enough n, the O(n) auxiliary buffer competes with other memory pressure, which is exactly why external (disk-based) sorting is built on multi-way merge rather than quicksort, since merge sort's sequential access pattern suits disk or network I/O far better than quicksort's more random access pattern. A third trap is ignoring stability when it silently matters: if you sort by a secondary key after already sorting by a primary key, only a stable sort preserves the primary ordering among equal secondary keys; using an unstable sort there produces a result that looks correct on small examples but is wrong in general.

Direct answer

Advance one pointer (slow) one step at a time and another (fast) two steps at a time. If the list has no cycle, fast reaches the end first and you can report there is none. If it does have a cycle, fast eventually laps slow and the two meet somewhere inside it. Once they meet, restarting one pointer at the head and advancing both pointers one step at a time makes them meet again exactly at the cycle's start. All of this uses $O(1)$ extra space, no visited set required.

Structured elaboration

Why meeting implies a cycle, and why no meeting implies no cycle. With no cycle, fast strictly gains ground toward a null terminator every step and reaches it in at most n/2 steps; it can never occupy the same node as slow without a cycle to loop back through. Once both pointers are inside a cycle, fast closes the gap to slow by exactly one node per step, because fast gains two steps of distance while slow gains one, a net closing rate of one per step. Since the gap can never exceed the cycle's length, they are guaranteed to meet within one full lap of the cycle.

Why the meeting point locates the cycle's start. Let a be the distance from the head to the cycle's start, c be the cycle's length, and b be the distance from the cycle's start to the meeting point, with $0 \le b < c$. By the time they meet, slow has traveled a + b steps and fast has traveled exactly twice that, but fast has also gone around the cycle some whole number of extra laps $n \ge 1$:

So a and (c - b) differ by a whole number of cycle lengths, meaning a pointer walking one step at a time from the head, and a pointer walking one step at a time from the meeting point, land on the same node after exactly a steps: the cycle's start.

Related applications of the same fast/slow pattern. Removing the n-th node from the end of a list uses the same shape without any cycle involved: advance one pointer n steps first, then move both pointers together; when the front pointer reaches the end, the trailing pointer sits exactly at the node to remove. Finding a duplicate number hidden in an array reframes the array itself as an implicit linked list, where the value stored at each index tells you which index to visit next; a repeated value forces two different positions to point at the same next index, creating a cycle in that implicit list, which Floyd's tortoise-and-hare detects exactly the way it detects a cycle here.

Worked example

class Node:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next


def detect_cycle_start(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            ptr = head
            while ptr is not slow:
                ptr = ptr.next
                slow = slow.next
            return ptr
    return None


if __name__ == "__main__":
    nodes = [Node(i) for i in range(5)]  # values 0,1,2,3,4
    for i in range(4):
        nodes[i].next = nodes[i + 1]
    nodes[4].next = nodes[2]  # cycle back into node with value 2
    start = detect_cycle_start(nodes[0])
    print(start.val)

Running this prints 2. In the derivation's terms: a = 2 (two steps from the head, value 0, to the cycle's start, value 2), c = 3 (the cycle 2 to 3 to 4 back to 2 has three edges), and the two pointers first meet at the node with value 3, so b = 1 (one step from the cycle's start to that meeting point). Checking the identity: c - b = 3 - 1 = 2, which equals a, confirming the derivation against this concrete run.

Complexity

Time: $O(n)$. The pointers meet within one full lap of the cycle once both are inside it, and finding the cycle's start afterward takes at most another full lap; both phases are bounded by a constant multiple of the list's length n.
Space: $O(1)$, since only the slow and fast pointers (and later ptr) are held, with no visited set.

Edge cases

• Empty list (head is None): fast is None immediately, so the loop never runs and the function correctly returns no cycle.
• Single node with no self-link: fast.next is None on the first check, so the loop exits immediately with no cycle detected.
• Single node that cycles to itself: slow and fast both land back on that same node on the first iteration, correctly reporting it as the cycle's start.

Trade-offs & pitfalls

A common bug is comparing pointer values instead of pointer identity; when list values can repeat, slow.val == fast.val can be true without slow and fast being the same node, so the check must be slow is fast.

Direct answer

Build the index on a trie (a prefix tree: a tree where each edge is labeled with one character, so the path from the root spells out a prefix), with each trie node caching its own top-K most relevant completions. A query walks the trie one character per typed key, in time proportional only to the prefix length, and returns the cached list directly, so latency stays flat regardless of corpus size. Writes update the cached top-K along the path of the changed term, keeping the structure current without a full rebuild.

Structured elaboration

Requirements: sub-100ms perceived latency as the user types (query cost should not grow with corpus size), support for millions of terms, and near-real-time updates as term popularity changes.

Index structure: a trie node stores:

• children: map from next character to child node.
• top_k: the K highest-scoring completions reachable through this node, kept sorted.

Query(prefix): walk the trie by prefix, one node per character; if the walk falls off (no child for the next character), there are no completions. Otherwise return the node's cached top_k directly.

Update(term, score): walk the trie again along the term's characters, and at every node visited (including the root), remove any stale entry for this term from that node's top_k, then insert the new (score, term) pair in sorted position and trim back to K entries. This means an update only touches the nodes on the path of that one term, not the whole trie.

flowchart LR
    Client[Typing client] --> API[Autocomplete API]
    API --> Cache[Hot-prefix cache]
    API --> Trie["In-memory trie (top-k per node)"]
    Ingest[New-term ingestion] --> Trie
    Trie --> Store[("Persistent store")]
    Trie --> ShardA["Shard: prefixes a-m"]
    Trie --> ShardB["Shard: prefixes n-z"]

Scaling for a corpus that does not fit on one machine: shard the trie by prefix range (as sketched above), route each query to the owning shard, and put a small cache in front for the hottest prefixes so most keystrokes never reach the trie at all. Keep a compressed variant (a radix tree, also called a compact or Patricia trie, which merges any chain of single-child nodes into one edge) when memory, not latency, is the binding constraint, such as on a memory-limited mobile client.

Worked example

from bisect import insort


class _TrieNode:
    __slots__ = ("children", "top_k")

    def __init__(self):
        self.children: dict[str, "_TrieNode"] = {}
        self.top_k: list[tuple[int, str]] = []  # sorted, (-frequency, term)


class Autocomplete:
    def __init__(self, k: int = 3):
        self.root = _TrieNode()
        self.k = k
        self.freq: dict[str, int] = {}

    def _refresh_node_topk(self, node, term, freq):
        node.top_k = [e for e in node.top_k if e[1] != term]
        insort(node.top_k, (-freq, term))
        if len(node.top_k) > self.k:
            node.top_k.pop()

    def add_term(self, term: str, count: int = 1) -> None:
        new_freq = self.freq.get(term, 0) + count
        self.freq[term] = new_freq
        node = self.root
        self._refresh_node_topk(node, term, new_freq)
        for ch in term:
            node = node.children.setdefault(ch, _TrieNode())
            self._refresh_node_topk(node, term, new_freq)

    def suggest(self, prefix: str) -> list[str]:
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return []
            node = node.children[ch]
        return [term for _, term in node.top_k]


ac = Autocomplete(k=2)
for term, count in [("cat", 5), ("car", 9), ("cart", 2), ("care", 7)]:
    ac.add_term(term, count)
print(ac.suggest("ca"))
print(ac.suggest("car"))
print(ac.suggest("cax"))

Running this prints:

['car', 'care']
['car', 'care']
[]

("care" also starts with "car", so it correctly competes for that node's top-2 alongside "cart".)

Complexity

suggest(prefix): $O(L + K)$ time, where $L$ is the length of the typed prefix and $K$ is the number of cached suggestions returned; each of the $L$ characters costs one $O(1)$ dict lookup on children, and reading off the cached top_k costs $O(K)$. This is independent of corpus size, which is exactly why latency stays flat as the corpus grows.

add_term(term): $O(L \cdot K)$ time, since every one of the $L$ nodes visited along the term's path re-sorts its top_k list in $O(K)$ (_refresh_node_topk does a linear filter plus an insort).

Space: $O(C + N \cdot K)$, where $C$ is the total number of characters across all inserted terms (the trie's own node/edge count) and $N$ is the number of trie nodes; caching the top-$K$ list at every node adds $O(N \cdot K)$ on top of the base trie.

Edge cases

• Empty prefix "": the walk touches zero characters and suggest returns the root's own cached top_k, i.e. the corpus-wide top-K.
• Prefix with no matching terms: the walk falls off the trie (a character missing from children) and returns [] immediately, as shown for "cax" above.
• k=0 (Autocomplete(k=0)): every node's top_k is trimmed to length 0, so suggest always returns [].
• Re-adding the same term: _refresh_node_topk strips any existing entry for that term before inserting the refreshed one, so a term is never double-counted in a node's top_k.

Trade-offs & pitfalls

Caching top-K at every node is a memory-for-latency trade: memory grows with number of nodes * K, which can be heavy at corpus scale, so production systems often store only IDs plus a pointer into a central score table at each node, and recompute on demand for cold prefixes instead of eagerly maintaining every node's cache. A common mistake is treating this as a purely single-term prefix problem when the real ask is different: for scanning a stream of text against many keywords at once (for example, flagging keywords across a log stream), the right structure is Aho-Corasick, a trie augmented with failure links for simultaneous multi-pattern matching, not repeated prefix lookups. Likewise, finding words embedded in a 2D grid (the Word Search II style problem) combines this same trie with backtracking search over the board, which is a different traversal shape from a typed-prefix query even though it reuses the trie. Finally, remember that update cost is proportional to term length times K (each node touched does an O(K) resort), so very high write rates may call for batching updates or an approximate top-K structure (a lossy counter) rather than an exact resort on every single write.

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.