Algorithmic Problem-Solving and Data Structure Selection Questions

Direct answer

At millions of players with frequent score changes, you need one structure
that keeps players ordered by score (for "top K") and lets you locate any
one player's position in that order quickly (for "this player's rank").
A balanced ordered structure, a self-balancing binary search tree (BST) or
skip list augmented with subtree/level sizes, answers both queries in
$O(\log n)$ and keeps them $O(\log n)$ after every update. A plain max-heap
paired with a hashmap gives fast top-K but cannot answer "what is this
player's rank" without effectively rebuilding the ordering information the
heap does not maintain, so at scale the rank-of-player requirement is really
what decides the structure, not the update or top-K requirement alone.

Structured elaboration

Access pattern 1: top K. A max-heap answers "give me the current
maximum" in $O(1)$ and "give me the top K" in $O(K \log n)$ by popping K
times (or non-destructively in $O(K)$ if paired with a sorted auxiliary
structure). A rank-augmented balanced BST answers top K in
$O(K + \log n)$: descend to the maximum in $O(\log n)$, then walk K steps
in sorted order.

Access pattern 2: rank of a specific player. This is where the two
choices diverge sharply. A rank-augmented balanced BST, where every node
additionally stores the size of its subtree, answers "how many players
have a score greater than or equal to this player's score" in $O(\log n)$:
descend toward the player's node, and at each step where you branch toward
the smaller-score side, add the size of the larger-score subtree you did not
descend into. A plain heap stores no such ordering information between
siblings, so answering "what is player X's rank" requires either an
$O(n)$ scan, or maintaining a second, separate rank-capable structure
alongside the heap, at which point you have effectively built the augmented
BST's capability anyway, just split across two data structures instead of
one.

Update cost. Both approaches update a single player's score in
$O(\log n)$: a balanced BST re-inserts (remove old score, insert new
score, both $O(\log n)$); a heap paired with a hashmap can decrease/increase
a key via the hashmap's stored heap-index and a sift-up/sift-down, also
$O(\log n)$, provided the heap implementation supports arbitrary-key
updates (a plain textbook binary heap does not expose this directly and
needs an index-tracking layer bolted on).

A real-world instance of the same trade-off: production leaderboards
(for example, Redis's sorted set) are implemented as exactly this kind of
augmented ordered structure, most commonly a skip list (a probabilistic,
linked-list-based structure with multiple "levels" that let a search skip
over many elements at once) paired with a hashmap from member to score, which
is precisely "balanced ordered structure for rank and range, hashmap for O(1)
point lookup of a player's current score," the two pieces used together
rather than as alternatives.

Recommendation. For a leaderboard with millions of players that must
answer both queries frequently, use the balanced ordered structure (skip
list or an augmented balanced BST) as the source of truth for ordering, plus
a hashmap from player id to score for O(1) "what is player X's current
score" lookups; this covers both access patterns at $O(\log n)$ without
needing a second ordering structure bolted onto a heap. A heap-only design
is the right choice only when the product genuinely never needs
rank-of-player, just periodic top-K snapshots (for example, a "top 10 today"
banner with no per-player rank display).

Worked example

A compact way to demonstrate the rank-of-player query concretely: represent
scores with a Fenwick tree (a Binary Indexed Tree, the same cumulative-count
structure used for range-sum queries) over a coordinate-compressed set of
score values, counting how many players currently hold each score, so
"rank of player X" becomes "how many players have score greater than or
equal to X's score," a suffix-count query.

import bisect

class RankLeaderboard:
    def __init__(self, score_universe):
        self.sorted_scores = sorted(set(score_universe))
        self.S = len(self.sorted_scores)
        self.bit = [0] * (self.S + 1)
        self.player_score = {}

    def _bucket(self, score):
        return bisect.bisect_left(self.sorted_scores, score) + 1

    def _add(self, i, delta):
        while i <= self.S:
            self.bit[i] += delta
            i += i & (-i)

    def _prefix(self, i):
        total = 0
        while i > 0:
            total += self.bit[i]
            i -= i & (-i)
        return total

    def set_score(self, player, score):
        if player in self.player_score:
            self._add(self._bucket(self.player_score[player]), -1)
        self._add(self._bucket(score), 1)
        self.player_score[player] = score

    def rank_of(self, player):
        bucket = self._bucket(self.player_score[player])
        return self._prefix(self.S) - self._prefix(bucket - 1)

board = RankLeaderboard(range(0, 101))
scores = {"alice": 90, "bob": 75, "carol": 90, "dave": 60, "eve": 100}
for p, s in scores.items():
    board.set_score(p, s)
for p in scores:
    print(p, board.rank_of(p))
board.set_score("dave", 95)
print("dave new rank:", board.rank_of("dave"))

Output (verified by running this exact code):

alice 3
bob 4
carol 3
dave 5
eve 1
dave new rank: 2

alice and carol tie at rank 3 (three players, eve, alice, carol,
have a score of 90 or above); after dave jumps to 95, only eve (100) and
dave (95) score 95 or above, so dave's rank becomes 2. Both results were
cross-checked against a brute-force sum(1 for s in scores.values() if s >= my_score)
recomputation with no mismatches.

Trade-offs & pitfalls

• The Fenwick-tree version above assumes a bounded, known (or periodically
  refreshed) universe of possible score values to bucket into; a truly
  unbounded, continuously-varying score range needs an augmented balanced
  BST or skip list instead, since those do not require pre-declaring the
  value universe.
• A common wrong turn is reaching for "just a heap" because top-K sounds
  heap-shaped, without checking whether the product also needs
  rank-of-player; that second requirement is usually what should decide the
  structure, since retrofitting rank support onto a heap-based design later
  is close to a rewrite.
• The same rank-plus-priority composition appears in a CI (continuous
  integration) test-scheduler: add, cancel, and promote a queued test
  along with "get the current top-K highest-priority tests," which is the
  identical requirement (ordered structure for priority/rank, hashmap for
  O(1) lookup of a specific test's current state) applied to test scheduling
  instead of player scores.
• At true internet scale, sharding by score range (so each shard owns a
  contiguous score band) reduces write contention, but complicates
  "global" top-K and rank queries, which now need to merge results across
  shards; this is a genuine added cost of horizontal scaling that a
  single-machine design does not have to pay.

Complexity

The table above already gives the general balanced-BST-vs-heap comparison. For the
RankLeaderboard Fenwick-tree worked example specifically, with $S$ the size of the
(coordinate-compressed) score universe and $P$ the number of distinct players tracked:
set_score: $O(\log S)$, two Fenwick point-updates (_add); rank_of: $O(\log S)$,
two Fenwick prefix-sum queries (_prefix); space: $O(S + P)$, the bit array is sized to
the score universe and player_score holds one entry per player.

Edge cases

• Player never scored: rank_of(player) looks up self.player_score[player] directly
  and raises a KeyError if set_score was never called for that player.
• Score above the declared universe: _bucket returns self.S + 1 for a score above every
  value in sorted_scores; _add(self.S + 1, delta)'s while i <= self.S condition is false
  on the first check, so the update is silently a no-op, meaning out-of-universe high scores
  are dropped rather than rejected with an error.
• Tied scores: players sharing a score land in the same bucket and are counted together in
  the suffix sum, so ties correctly share the same rank number, as shown for alice and
  carol both ranking 3rd in the worked example.
• Empty leaderboard: with no set_score calls made yet, rank_of on any player raises a
  KeyError immediately, since player_score is still empty.

Direct answer

Before writing any code, look for two structural signals: does the problem have overlapping subproblems and optimal substructure (an optimal solution is built from optimal solutions to smaller versions of itself)? If yes, it is a dynamic programming (DP) problem, not a greedy one. Within DP, whether you reach for memoization (caching recursive-call results, computed top-down) or tabulation (filling a table iteratively, bottom-up) is a secondary implementation choice, not a correctness question: both compute the same recurrence.

Structured elaboration

Signal 1: does a locally optimal choice guarantee a globally optimal one? Greedy algorithms make one irrevocable choice at each step and never reconsider it. That is only correct when the problem has the "greedy-choice property": committing to the best-looking option right now cannot make the final answer worse. You test this by trying to construct a counterexample where the locally-best choice forecloses a better global outcome (an exchange argument): if you can build one, greedy is wrong and you need DP; if every attempt to build a counterexample fails and you can sketch why (an exchange argument that any optimal solution can be rearranged to match the greedy choice without loss), greedy is likely correct.

Signal 2: overlapping subproblems and optimal substructure. If solving the problem for a larger input naturally requires solving the same smaller subproblem many times (for example, "the best way to reach state k" depends on "the best way to reach state k-1", but state k-1 also gets asked about from other paths), you have overlapping subproblems. If, in addition, an optimal solution to the whole problem is composed of optimal solutions to its subproblems (no locally-suboptimal subproblem answer can still lead to a globally optimal whole), you have optimal substructure. Both together mean DP applies: cache each subproblem's answer once, reuse it everywhere it recurs.

Signal 3: what does the recurrence look like? Write the recurrence in terms of "the answer for state X depends on the answer for smaller states Y, Z, ...", before touching code. If you can write this recurrence but it does not have an ordering where "smaller" always resolves before "larger" (a genuine dependency cycle), you likely need a different technique entirely (graph shortest-path with cycles, for instance).

Once you know it's DP: memoization vs tabulation. These are the same recurrence expressed two ways, not two different algorithms:

Worked example

Take "minimum coins to make amount 6 from denominations {1, 3, 4}" (the coin change problem). The recurrence is: minCoins(a) = 1 + min(minCoins(a - c) for c in coins if c <= a), with minCoins(0) = 0. Overlapping subproblems are visible immediately: computing minCoins(6) needs minCoins(5), minCoins(3), minCoins(2); computing minCoins(5) also needs minCoins(2). minCoins(2) gets requested from two different callers, so caching it once and reusing it is exactly what turns an exponential naive recursion into a linear-in-target one. That overlap is the tell that this is DP, not greedy: a greedy "always take the largest coin" would take 4 then 1 then 1 (3 coins), while the true optimum is 3 + 3 (2 coins), because taking the largest coin first forecloses the better pairing, a real exchange-argument counterexample, confirming greedy is unsafe here and DP (with either memoization or tabulation) is required.

Trade-offs & pitfalls

Key points

• The most common mistake is reaching for greedy because a locally-best choice feels right; the discipline is to actively try to break it with a counterexample before trusting it, not to trust it by default.
• A DP recurrence existing does not by itself tell you whether to memoize or tabulate; that choice depends on whether the reachable state space is sparse (favors memoization) or dense with a clean iteration order (favors tabulation), and on language-specific recursion-depth limits.
• Some problems only look like DP: if there is no genuine overlap (each subproblem is only ever needed once), plain recursion or divide-and-conquer is simpler and DP's caching buys you nothing.

Complexity

• These are meta-level signals, not a specific algorithm, so there is no single complexity here; once you commit to DP, complexity is (number of distinct states) times (work per state), whether computed top-down with a cache or bottom-up with a table.

Edge cases

• A problem with optimal substructure but no overlapping subproblems (each subproblem solved once) does not need DP's memoization; plain recursion or divide-and-conquer suffices and adding a cache only adds overhead.
• A problem where you cannot write a clean dependency order for tabulation (irregular, data-dependent state transitions) may force memoization even in a dense-looking state space, since an explicit iteration order is hard to construct correctly.

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 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 TrieNode holds a dictionary of child nodes keyed by character, plus an is_word flag.
• insert(word): walk from the root, creating a child node for each character not already present, then mark the final node's is_word as 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's is_word is 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_word is 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_word at 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(\text{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("") and startsWith("") 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_word just 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.

Direct answer

A sorting algorithm is stable if it preserves the relative order of elements
that compare equal on the sort key. If two records tie on the key you sorted
by, a stable algorithm guarantees the one that came first in the input still
comes first in the output. This matters for multi-key sorts: if you sort by a
secondary key after already sorting by a primary one, stability is what lets
the primary ordering survive as a tiebreaker inside each secondary-key group.
Merge sort and Python's Timsort (the algorithm behind sorted() and list.sort())
are stable; classic in-place selection sort and a typical quicksort are not.

Structured elaboration

Why stability matters for multi-key sorts. The standard trick for sorting
by (primary key, secondary key) without writing a composite comparator is:
sort once by the primary key, then sort the result by the secondary key. This
only produces the correct combined order if the second sort is stable: a
stable sort only reorders elements that actually differ on the secondary key,
so within any group of equal secondary-key values, the primary-key order from
step one is left untouched. An unstable sort makes no such promise: it may
reorder equal-secondary-key elements arbitrarily while grouping them, silently
destroying the primary ordering you already paid to establish.

A stable sort: merge sort, and Timsort (the hybrid merge/insertion sort
used by Python and Java's Collections.sort for objects). Both work by
merging or shifting elements without ever swapping two elements past an equal
one, so ties keep their input order.

An unstable sort: classic in-place selection sort (repeatedly swap the
current position with the position of the next-smallest remaining element).
The swap step moves elements across long distances in the array, including
past other elements with the same key, which is exactly what breaks ties.
Typical in-place quicksort implementations are unstable for the same reason
(the partition step swaps non-adjacent elements).

If you only have an unstable sort available, you can force stability by
attaching the original index to each record and sorting by (key, original_index)
instead of key alone. Ties on key are then broken by index, which exactly
reproduces stable behavior, at the cost of allocating one extra field per record.

Worked example

Take four employee records, already sorted by name (the primary key):

Now sort by department (the secondary key). A stable sort must produce:

Eng: Chen, Ito       (name order preserved)
Sales: Alvarez, Diallo  (name order preserved)

Running this in Python, where sorted() is stable, versus a hand-rolled
unstable selection sort, on the exact same input:

records = [
    {"name": "Alvarez", "dept": "Sales"},
    {"name": "Chen", "dept": "Eng"},
    {"name": "Diallo", "dept": "Sales"},
    {"name": "Ito", "dept": "Eng"},
]

stable_result = sorted(records, key=lambda r: r["dept"])

def unstable_selection_sort_by_dept(items):
    items = list(items)
    n = len(items)
    for i in range(n):
        min_idx = i
        for j in range(i + 1, n):
            if items[j]["dept"] < items[min_idx]["dept"]:
                min_idx = j
        items[i], items[min_idx] = items[min_idx], items[i]
    return items

unstable_result = unstable_selection_sort_by_dept(records)

print([(r["dept"], r["name"]) for r in stable_result])
print([(r["dept"], r["name"]) for r in unstable_result])

Output (verified by running this exact code):

[('Eng', 'Chen'), ('Eng', 'Ito'), ('Sales', 'Alvarez'), ('Sales', 'Diallo')]
[('Eng', 'Chen'), ('Eng', 'Ito'), ('Sales', 'Diallo'), ('Sales', 'Alvarez')]

The Eng group comes out identical either way, but the Sales group is
reversed under the unstable sort: Diallo now precedes Alvarez, even though
Alvarez came first alphabetically. That reversal is the bug: any downstream
code relying on "same department, alphabetical order" is now silently wrong,
and the failure is data-dependent, so it will not show up on every input.

Trade-offs & pitfalls

• Stability is a property of the algorithm's specification, not just a given
  implementation detail: "quicksort" is not stable by definition, but a
  particular library's sort might document stability as a guarantee (check
  the docs rather than assuming from the algorithm's name).
• The index-as-tiebreaker trick works with any comparison sort, stable or not,
  but costs O(n) extra memory for the index field and slightly more comparison
  overhead per element; it is the right choice when the language's built-in
  sort is unstable by contract (e.g. a raw quicksort library call) and you
  cannot swap in a stable one.
• A common wrong turn is assuming "the final order looks right on my test
  data" is proof of stability; instability is a tie-breaking behavior that
  only shows up when there are actual ties, so it hides in datasets with few
  duplicate keys and surfaces later at a different data distribution.
• Do not confuse stability with sort correctness on the primary sort key
  itself: an unstable sort still produces a fully correct order on the key it
  was told to sort by, it only fails to preserve unrelated prior ordering
  among equal elements.