Algorithmic Problem-Solving and Data Structure Selection Questions

Direct answer

Reach for a hash map whenever you need the fastest average lookup, insert, and delete and do not care about the order keys come out in. Reach for an ordered structure (a balanced binary search tree, BST for short, meaning a tree kept balanced so its height stays logarithmic; or a skip list, a linked structure with multiple randomly-built "express lane" levels that gives logarithmic search without needing tree rebalancing) whenever you need range queries, sorted iteration, or predecessor/successor lookups, since a hash map fundamentally cannot answer those without scanning every entry.

Structured elaboration

Concrete case where a hash map wins: an in-memory cache keyed by an exact request signature, for example caching a computed response by its full input hash, where every lookup is "does this exact key exist" and there is no notion of "keys near this one" that would ever be queried. The $O(1)$ average lookup directly minimizes latency, and there is nothing to give up, since ordering was never needed.

Concrete case where giving up hash-map speed pays off: a scheduler that needs "the next event after this timestamp." That is a successor query, unsupported by a hash map without scanning every key, but native to an ordered structure in $O(\log n)$. Trading average-case $O(1)$ for guaranteed $O(\log n)$ is a clear win here because the operation the hash map cannot do at all is the operation the system needs on every scheduling step.

Trade-offs & pitfalls

A hash map's worst-case degrades to $O(n)$ under pathological collisions, though modern implementations mitigate this with randomized hash seeding; an ordered structure's $O(\log n)$ is a hard guarantee regardless of key distribution, which matters if an adversary can influence which keys get inserted (for example, in a public-facing API). A common mistake is reaching for an ordered structure "just in case sorted output is needed later," which pays the $O(\log n)$ tax on every single operation for a benefit that may never be used; the right trigger is a concrete, recurring range or predecessor/successor query in the actual access pattern, not a hypothetical one. It is also common to forget that some hash map implementations preserve insertion order as an incidental property (not a sorted, comparison-based order), which is a much weaker guarantee than a true ordered structure's ability to iterate or range-query by key value.

Direct answer

Doubling the bucket array whenever the load factor (occupied slots divided by
total capacity) exceeds 0.75 gives O(1) amortized cost per insert: the
occasional expensive rehash (copying every element into a bigger array) is
paid for by all the cheap inserts since the last resize, and because capacity
doubles, resizes become exponentially rarer as the table grows. Adding a
symmetric shrink-on-deletion policy is only safe if the shrink threshold is
set well below the grow threshold; using the same threshold for both directions
lets an adversarial (or just unlucky) sequence of alternating inserts and
deletes near the boundary trigger a full resize on every single operation,
destroying the amortized guarantee entirely.

Structured elaboration

Amortized cost of grow-only doubling (aggregate method). Suppose the
table starts at capacity $c_0$ and doubles ($c_k = 2^k c_0$) each time
size exceeds $\theta \cdot \text{capacity}$ for threshold $\theta = 0.75$.
At the moment of the $k$-th resize, the table holds roughly
$\theta \cdot c_{k-1}$ live elements, and a resize rehashes (copies) all of
them into the new array:

Summing the rehash cost across all resizes up to the point where the table
has grown to serve $n$ elements is a geometric series:

So total rehashing work across all resizes is $O(n)$, not $O(n \log n)$
or worse, because a geometric series is dominated by its last term. Adding
the $O(1)$ cost of each of the $n$ individual inserts:

Why shrinking naively breaks this. The argument above works because
resize events become rarer as capacity grows (each one "pays off" a
geometrically larger batch of prior inserts). If shrinking uses the same
threshold as growing, a table can cross the grow threshold, resize, and then
land at a load factor that is already below that same threshold, so the very
next deletion immediately triggers a shrink back down, and the next insertion
after that immediately triggers a grow again. There is no batch of cheap
operations paying for each resize anymore, every operation near that boundary
pays for a full resize.

The standard fix: hysteresis. Use two different thresholds with a gap
between them, for example grow at load factor 0.75 but only shrink once load
factor drops below roughly 0.25. This guarantees that after any resize
(grow or shrink), the table must absorb a substantial number of operations
purely from the size change alone before it can cross the other threshold and
trigger another resize, restoring the same "geometric batches pay for
resizes" argument that made grow-only doubling amortized O(1).

Worked example

Simulating exact resize behavior with pinned parameters (capacity starts at
4, size starts at 3, doubling on grow, halving on shrink) demonstrates both
failure and fix:

def simulate_thrashing(n_ops, threshold=0.75):
    capacity, size, total_work, resizes = 4, 3, 0, 0
    for i in range(n_ops):
        if i % 2 == 0:
            size += 1; total_work += 1
            if size / capacity > threshold:
                capacity *= 2; total_work += size; resizes += 1
        else:
            size -= 1; total_work += 1
            if capacity > 4 and size / capacity < threshold:
                capacity //= 2; total_work += size; resizes += 1
    return total_work, resizes

def simulate_with_hysteresis(n_ops, grow_threshold=0.75, shrink_threshold=0.25):
    capacity, size, total_work, resizes = 4, 3, 0, 0
    for i in range(n_ops):
        if i % 2 == 0:
            size += 1; total_work += 1
            if size / capacity > grow_threshold:
                capacity *= 2; total_work += size; resizes += 1
        else:
            size -= 1; total_work += 1
            if capacity > 4 and size / capacity < shrink_threshold:
                capacity //= 2; total_work += size; resizes += 1
    return total_work, resizes

work_t, resizes_t = simulate_thrashing(2000)
work_h, resizes_h = simulate_with_hysteresis(2000)
print("same-threshold:", work_t, resizes_t, work_t / 2000)
print("hysteresis gap:", work_h, resizes_h, work_h / 2000)

Output (verified by running this exact code):

same-threshold: 9000 2000 4.5
hysteresis gap: 2004 1 1.002

With a single shared threshold, all 2000 alternating operations trigger a
resize (2000 resizes for 2000 operations, amortized 4.5 units of work per
operation for this small table); with a 0.75/0.25 hysteresis gap, only 1
resize happens across all 2000 operations, and amortized cost settles at
almost exactly 1.0, the O(1) result the design is supposed to guarantee. The
gap between grow and shrink thresholds is what restores amortized O(1) once
deletions are allowed to trigger shrinking.

Trade-offs & pitfalls

• The failure mode above gets worse, not better, at scale: the per-resize
  cost is proportional to the table's current size, so the same
  shared-threshold thrashing pattern on a table with 100,000 capacity and
  75,000 elements turns every operation into a resize costing roughly 75,000
  units of work, an amortized cost of $O(n)$ per operation instead of
  $O(1)$, which is the whole point of the doubling scheme defeated.
• Hysteresis is not free: keeping the shrink threshold well below the grow
  threshold means the table tolerates more "wasted" empty capacity before
  shrinking (at a 0.25 shrink threshold, the table can be using as little as
  a quarter of its capacity before it shrinks), a deliberate memory-versus-
  resize-frequency trade-off, not a way to avoid the trade-off entirely.
• A related but distinct pitfall is choosing a shrink factor that is too
  aggressive relative to the grow factor (for example, growing by 2x but
  shrinking all the way back to the smallest possible size instead of by a
  matching factor); this can reintroduce the same thrashing risk in a
  different shape if the shrunk table is immediately close to its own grow
  threshold again.

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

Preorder visits node, then left, then right; inorder visits left, then node, then right; postorder visits left, then right, then node; all three are depth-first traversals (DFS), following one branch as deep as possible before backtracking. Level-order (breadth-first search, BFS) instead visits every node one full depth at a time using a queue. To reconstruct a tree from a serialized form, preorder combined with explicit null markers is the natural single-pass choice, because each value tells you exactly where to place it in the recursion without needing a second array to cross-reference.

Structured elaboration

Recursive versus iterative cost. A recursive traversal uses the call stack, which costs $O(h)$ space where h is the tree's height ($O(\log n)$ for a balanced tree, $O(n)$ worst case for a completely skewed one). An iterative version with an explicit stack (for the depth-first orders) or queue (for level order) has the same asymptotic space cost, but it avoids the recursion-depth limits some language runtimes impose, which matters for very deep, skewed trees.

Level order grouped by depth. Enqueue the root, then repeatedly record the queue's current size before draining exactly that many nodes: that snapshot is what lets you know where one depth level ends and the next begins, since each drained node's children get enqueued for the following level.

Choosing preorder-with-nulls for reconstruction. Preorder plus null sentinels needs only one traversal: read a value, recursively build its left child from what follows, then its right child, treating a null marker as "no subtree here." Preorder plus inorder (without nulls) also works, but only if all values are unique, and it needs an auxiliary index map over the inorder sequence to avoid an $O(n^2)$ naive search, adding bookkeeping the null-marker approach does not need. Level order with null markers is workable too (BFS serialization), but reconstructing parent-child links across levels needs more bookkeeping than the purely recursive preorder approach.

Related extensions from the same traversal family. A BST iterator (an object that exposes a paused, resumable inorder walk) keeps the explicit stack alive across calls instead of finishing the traversal eagerly, giving amortized (averaged over a sequence of operations) $O(1)$ time per next() call. Finding all node pairs at distance k from a target reuses the same level-by-level machinery as level-order traversal, just starting the breadth-first search from the target node instead of the root. The height-balance check, maximum path sum, and invert-binary-tree problems are all further applications of the postorder shape: each recursive call computes something (a height, a best path so far, a swapped subtree) from its children and returns it up to its parent, rather than printing a value as it visits.

graph TD
  A[3] --> B[9]
  A --> C[20]
  C --> D[15]
  C --> E[7]

Worked example

from collections import deque


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def level_order(root: TreeNode | None) -> list[list[int]]:
    if not root:
        return []
    result = []
    queue = deque([root])
    while queue:
        level_vals = []
        for _ in range(len(queue)):  # freeze this level's size before draining
            node = queue.popleft()
            level_vals.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level_vals)
    return result


if __name__ == "__main__":
    root = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
    print(level_order(root))

Running this on the tree pictured above prints [[3], [9, 20], [15, 7]].

Complexity

Time: $O(n)$ for all four traversals (preorder, inorder, postorder, and level-order), since each one visits every node exactly once and does $O(1)$ work per visit.
Space: $O(h)$ for the three depth-first traversals, from the recursion call stack (or an explicit stack for an iterative version), where h is the tree's height, as already noted above. The level-order queue never holds more nodes than one full level of the tree, which is at most $O(n)$ in the worst case (a wide, shallow tree).

Edge cases

• Empty tree (root is None): level_order already returns [] via its explicit check; the depth-first traversals equally return immediately for a None node.
• Single-node tree: all four traversals visit just that one node and produce a single-element result.
• A skewed (essentially linear) tree: recursive depth-first traversals can hit a language's default recursion-depth limit (for example, Python's default is around 1000 frames), which is a concrete argument for the iterative forms in production code.

Trade-offs & pitfalls

The most common bug in the level-order implementation is not snapshotting len(queue) before the inner loop starts; without that snapshot, nodes from the next level get enqueued and then immediately drained in the same pass, smearing two levels together.

Direct answer

On a sorted array, start one pointer at the beginning and one at the end, and move them toward each other based on how the current pair's sum compares to the target: this finds the pair in one linear pass using O(1) extra space, no hash map required. Sorted order is exactly what makes the hash map unnecessary, since it tells you in which direction to move without needing to remember every value you have already seen. The same converging-pointer idea, applied to two arrays instead of one target sum, gives you their intersection: advance whichever array currently has the smaller value.

Structured elaboration

Two-sum on a sorted array: maintain the invariant that every valid pair still under consideration lies between left and right. If arr[left] + arr[right] == target, you are done. If the sum is too small, arr[left] cannot be part of any valid pair with anything to its left (everything to the left is even smaller, making the sum only smaller), so advance left. If the sum is too large, by the same logic on the other side, retreat right. Because the array is sorted, this monotonic narrowing never skips over a valid pair: if one exists, it is found.

Why sorted order removes the need for a hash map: an unsorted two-sum needs a hash map to remember "have I seen the complement of this value yet," since there is no way to know which direction to search without that memory. Sorted order replaces that memory with structure: the comparison arr[left] + arr[right] versus target alone tells you which pointer must move, with no need to have seen anything before.

Adapting to intersect two sorted arrays: instead of pointers converging toward each other, they move in the same direction, each independently, starting both at index 0. Compare the current elements of each array: if equal, that value is in the intersection, and advance both; if array a's current element is smaller, it cannot match anything later in b (which is only larger from here), so advance a; otherwise advance b. This is the same "sorted order tells you which pointer to move, so no hash map is needed" idea, just applied across two sequences instead of within one.

Worked example

Two-sum, sorted array:

def two_sum_sorted(arr: list[int], target: int) -> tuple[int, int]:
    left, right = 0, len(arr) - 1
    while left < right:
        s = arr[left] + arr[right]
        if s == target:
            return left, right
        if s < target:
            left += 1
        else:
            right -= 1
    return -1, -1

arr = [2, 7, 11, 15]
print(two_sum_sorted(arr, 18))

Running this prints:

(1, 2)

arr[1] + arr[2] = 7 + 11 = 18.

Sorted-array intersection:

def intersect_sorted(a: list[int], b: list[int]) -> list[int]:
    i, j = 0, 0
    result = []
    while i < len(a) and j < len(b):
        if a[i] == b[j]:
            result.append(a[i])
            i += 1
            j += 1
        elif a[i] < b[j]:
            i += 1
        else:
            j += 1
    return result

a = [1, 2, 2, 3, 5, 8]
b = [2, 2, 3, 6, 8, 9]
print(intersect_sorted(a, b))

Running this prints:

[2, 2, 3, 8]

Key points

• Both algorithms use the same underlying idea: sorted order lets a single comparison decide which pointer must move, replacing the memory a hash map would otherwise need to provide.
• The intersection version keeps every duplicate (two 2s appear in both inputs, so two 2s appear in the output); deduplicating the result, if needed, is a separate, trivial step.

Complexity

for the sorted two-sum (n is the array length), and

for the intersection of arrays of length n and m, since each pointer advances at most once per element and never backtracks.

Edge cases

• Empty or single-element array: two_sum_sorted correctly returns (-1, -1) since the while left < right loop never runs.
• No valid pair exists: the loop exits naturally when left meets right, returning (-1, -1).
• Negative numbers: handled correctly, since the comparison s < target / s > target does not depend on sign.
• One array is empty in the intersection case: the while loop's length check exits immediately, correctly returning an empty result.

Trade-offs & pitfalls

Reaching for a hash map here works too (build a set of one array's values in $O(n)$ time and $O(n)$ space, then scan the other), and is actually necessary if the input is not sorted and sorting it first is not acceptable (for example, if the original order must be preserved in the output); but given already-sorted input, that hash map is pure overhead, since the sort order already encodes everything the hash map would tell you. A common mistake is trying to adapt the sum-target converging-pointer pattern directly to intersection by starting the second pointer at the end instead of at the start: intersection is fundamentally a same-direction scan (both arrays are being consumed left to right looking for equal elements), not a converging one (which relies on one array's values increasing while the other's decrease, a relationship two independent sorted arrays don't have with each other).