Algorithmic Problem-Solving and Data Structure Selection Questions

Direct answer

Use binary (fast) exponentiation: repeatedly square the base and, on each bit of n that is set, multiply that squared value into the running result. This computes $x^n$ in O(log|n|) multiplications instead of O(n). A negative exponent is handled by inverting the base once up front (1/x) and treating the exponent as positive from then on.

Structured elaboration

Core idea: writing n in binary decomposes the power into a product of the base raised to each power-of-two position where n has a set bit:
$x^n = \prod_{i \,:\, \text{bit}_i(n)=1} x^{2^i}$
Squaring the base once per bit position produces exactly the $x^{2^i}$ terms needed, in the same single pass that reads the bits of n.

def my_pow(x: float, n: int) -> float:
    """
    Compute x**n via binary (fast) exponentiation in O(log|n|) time, O(1) space.
    Handles negative exponents and the 32-bit min-int edge case (in fixed-width languages).
    """
    if x == 0.0:
        if n > 0:
            return 0.0
        if n == 0:
            return 1.0
        raise ZeroDivisionError("0 cannot be raised to a negative power")

    exponent = n
    base = x
    if exponent < 0:
        base = 1.0 / base
        exponent = -exponent

    result = 1.0
    while exponent:
        if exponent & 1:
            result *= base
        base *= base
        exponent >>= 1
    return result


print(my_pow(2.0, 10))
print(my_pow(2.0, -3))
print(my_pow(3.0, 0))
print(my_pow(-2.0, 5))

Output:

1024.0
0.125
1.0
-32.0

Negative-exponent handling: invert x once, negate n, and reuse the same positive-exponent loop; in Python this negation is always safe since ints are arbitrary precision, but in a fixed-width 32-bit language, the most negative representable exponent must first be widened to a 64-bit type before negating it, since negating it directly overflows.

Worked example

Tracing $x=2, n=10$ (binary 1010) bit by bit:

The two set bits (positions 1 and 3) contribute $x^{2^1} \cdot x^{2^3} = 4 \cdot 256 = 1024 = 2^{10}$, matching the printed result exactly.

Complexity

$O(\log|n|)$ time, $O(1)$ space for the iterative version above (a recursive version instead
uses $O(\log|n|)$ call-stack space).

Edge cases

• n = 0: the while exponent loop never executes (exponent starts at 0), returning
  result = 1.0, matching my_pow(3.0, 0) -> 1.0.
• x = 0, n > 0: explicitly special-cased to return 0.0 before the main loop.
• x = 0, n = 0: explicitly special-cased to return 1.0 by convention.
• x = 0, n < 0: explicitly raises ZeroDivisionError, since 0 to a negative power is
  mathematically undefined; this must be special-cased rather than silently returning infinity
  or crashing with an unclear error.
• Negative base: sign is preserved correctly through repeated squaring and multiplication,
  e.g. my_pow(-2.0, 5) = -32.0.
• Most-negative fixed-width exponent (e.g. INT32_MIN): not an issue for Python's
  arbitrary-precision ints, but in a fixed-width 32-bit language the most negative representable
  exponent must be widened to a 64-bit type before negating it, since negating it directly
  overflows.

Trade-offs & pitfalls

• Floating-point precision: repeated squaring compounds rounding error faster than repeated multiplication in some regimes; for |x| very close to 1 raised to a huge power, or extreme |n| combined with |x| far from 1, relative error can grow. Computing via exp(n * log(x)) is an alternative when raw precision matters more than speed, but that requires x > 0 (log is undefined otherwise) and introduces its own rounding from the exp/log calls.
• Modular exponentiation: if the actual need is $x^n \bmod m$ (as in cryptographic-sized exponents), the accumulation step becomes (result * base) % m at every multiply, keeping every intermediate value bounded to a fixed size instead of letting a plain big-integer power grow unboundedly large.

Direct answer

All three (permutations, subsets, and valid combinations of balanced parentheses) share the same backtracking template: make one choice, recurse into the smaller remaining problem, then undo the choice before trying the next one (a "choose, explore, un-choose" loop). What changes between them is only the branching rule (what counts as a legal next choice at each step) and the pruning rule (what makes a partial choice already invalid, so you can abandon that branch immediately instead of completing it and checking at the end).

Structured elaboration

The shared template. Every backtracking search builds a partial solution incrementally. At each step: try each legal next choice, add it to the partial solution, recurse, then remove it (backtrack) before trying the next choice. Pruning means checking a partial solution's validity before recursing further into it, so invalid branches are cut off early rather than discovered only once fully built.

Permutations (branching rule: any not-yet-used element; no pruning needed since every partial arrangement of distinct elements is inherently valid):

def permute(nums):
    """All permutations of distinct integers via backtracking. O(n * n!) time."""
    res = []
    n = len(nums)
    used = [False] * n
    path = []

    def backtrack():
        if len(path) == n:
            res.append(path.copy())
            return
        for i in range(n):
            if used[i]:
                continue
            used[i] = True
            path.append(nums[i])
            backtrack()
            path.pop()
            used[i] = False

    backtrack()
    return res

Subsets (branching rule: include or exclude each element in turn, in index order; no pruning needed since every partial inclusion/exclusion choice is valid):

def subsets(nums):
    """All subsets via backtracking: at each element, branch into
    include/exclude. O(2^n) subsets, O(n) recursion depth."""
    res = []
    path = []
    n = len(nums)

    def backtrack(i):
        if i == n:
            res.append(path.copy())
            return
        backtrack(i + 1)          # exclude nums[i]
        path.append(nums[i])
        backtrack(i + 1)          # include nums[i]
        path.pop()

    backtrack(0)
    return res

Balanced parentheses (branching rule: add ( or add ); pruning rule: never add ) unless fewer closes than opens have been placed, and never add ( once n opens are already placed, since either violation can never be repaired later):

def generate_parentheses(n):
    """
    All valid combinations of n balanced parenthesis pairs. Prunes any
    branch that would produce an invalid prefix.
    """
    res = []

    def backtrack(current, open_count, close_count):
        if len(current) == 2 * n:
            res.append(''.join(current))
            return
        if open_count < n:
            current.append('(')
            backtrack(current, open_count + 1, close_count)
            current.pop()
        if close_count < open_count:   # pruning rule: never let ')' outnumber '('
            current.append(')')
            backtrack(current, open_count, close_count + 1)
            current.pop()

    backtrack([], 0, 0)
    return res

The same family, different pruning rule and branching factor. Several other classic problems are this exact generate-and-prune shape with only the branching and pruning rules swapped:

• k-combinations (choose k elements from n, order irrelevant): branch only on elements after the last one chosen (to avoid generating the same combination in different orders), and prune once fewer than the remaining needed elements are available from the rest of the input.
• Partition into k equal-sum subsets: branch by assigning the next number to one of k running buckets, and prune a branch the moment any bucket's running sum exceeds the target per-bucket sum (target = total sum divided by k); sorting the input largest-first before starting makes this pruning fire earlier, since big numbers overflow a bucket's budget sooner.
• N-Queens: branch on which column to place the next row's queen in, and prune immediately if that placement attacks any already-placed queen (same column, or same diagonal). A common refinement is the minimum-remaining-value (MRV) heuristic from constraint-satisfaction search: instead of always filling rows in a fixed order, place the next queen in whichever row currently has the fewest legal remaining columns, since that row is the most likely to fail fast if the branch is doomed, cutting off bad branches sooner.
• Expensive black-box feature-subset search: choosing which features to include for a model is structurally a subset search, but each branch's "cost" (evaluating a model with that feature subset) is expensive, so pruning matters even more: bound-based pruning (stop exploring a subset once a cheap proxy score shows it cannot beat the current best) plays the same role that the diagonal-attack check plays in N-Queens, just with a learned or estimated bound instead of an exact rule.

Worked example

print(permute([1, 2, 3]))
print(subsets([1, 2, 3]))
print(generate_parentheses(3))

Output:

[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
[[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]
['((()))', '(()())', '(())()', '()(())', '()()()']

permute([1, 2, 3]) produces all 3! = 6 orderings. subsets([1, 2, 3]) produces all 2^3 = 8 subsets (including the empty one). generate_parentheses(3) produces exactly 5 valid strings, matching the third Catalan number (the count of valid balanced-parenthesis arrangements for n pairs grows as the Catalan numbers: 1, 1, 2, 5, 14, ... for n = 0, 1, 2, 3, 4); the pruning rule (never let a close-paren outnumber an open-paren so far) is exactly what keeps every generated string valid, so no post-filtering step is needed.

Trade-offs & pitfalls

Key points

• Permutations and subsets need no mid-search pruning because every partial state is automatically valid; balanced parentheses, N-Queens, and partition-into-k-subsets all need an explicit prune check, and skipping it (checking validity only once a candidate is fully built) still gives correct output but wastes enormous work exploring doomed branches to completion.
• Sorting input before backtracking (largest-first for partition-into-k-subsets, or a fixed variable order for N-Queens with the minimum-remaining-value heuristic) does not change correctness, but it changes how quickly invalid branches get pruned, which can be the difference between a search finishing quickly and one that effectively never terminates for larger n.
• For repeated elements in permutations, sort first and skip choosing the same value at the same recursion depth if the previous identical value at that depth was not used, to avoid generating duplicate permutations.

Complexity

• Permutations: time $O(n \cdot n!)$ (n! permutations, each costing O(n) to copy), space $O(n)$ recursion depth plus $O(n \cdot n!)$ to store all results.
• Subsets: time and space $O(n \cdot 2^n)$ (2^n subsets, each up to length n).
• Balanced parentheses: the valid-string count is the n-th Catalan number, so output size and total work are bounded by that count times $O(n)$ per string; no invalid branch is ever explored to completion because of the pruning rule.

Edge cases

• Empty input (n = 0 for parentheses, or an empty list for permutations/subsets): permutations of an empty list is a single empty permutation; subsets of an empty list is a single empty subset; generate_parentheses(0) returns a single empty string.
• Duplicate values in the input for permutations or subsets: without the sort-and-skip guard, the same output can appear multiple times; decide up front whether duplicates in the output are acceptable.
• Large n for any of these: all of them have output sizes that grow factorially or exponentially, so even a perfectly pruned search becomes impractical well before n reaches the double digits for permutations, or a few dozen for subsets.

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

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

Correctness requires every node's value to respect the bounds imposed by all of its ancestors, not just its immediate parent and immediate children. Carry a (low, high) exclusive range down the recursion, tightening it at each step, and reject any node whose value falls outside its inherited range. This is $O(n)$ time and $O(h)$ space, where h is the tree's height.

Structured elaboration

The naive bug. A common but incorrect check only compares a node to its immediate left and right children:

def is_valid_bst_naive(node):
    if not node:
        return True
    if node.left and node.left.val >= node.val:
        return False
    if node.right and node.right.val <= node.val:
        return False
    return is_valid_bst_naive(node.left) and is_valid_bst_naive(node.right)

Consider the tree below: root 10, left child 5, right child 15, and 15's own children are 6 and 20.

graph TD
  A[10] --> B[5]
  A --> C[15]
  C --> D[6]
  C --> E[20]

Every local comparison passes: 5 < 10, 15 > 10, 6 < 15, 20 > 15. The naive check therefore reports this tree as a valid binary search tree (BST). But it is not: node 6 sits in the right subtree of the root (10), so every value in that subtree, including 6, must be greater than 10. It is not. The naive check has no memory of the root's bound by the time it looks at 6, because it only ever compares a node to its direct children.

The fix. Carry the inherited bounds explicitly, tightening them one level at a time:

def is_valid_bst(root):
    def helper(node, low, high):
        if not node:
            return True
        if not (low < node.val < high):
            return False
        return helper(node.left, low, node.val) and helper(node.right, node.val, high)
    return helper(root, float("-inf"), float("inf"))

An equally correct, structurally different alternative is an iterative inorder traversal that checks the visited sequence comes out strictly increasing; it relies on the fact that inorder traversal of a genuinely valid BST always produces sorted values, so it catches the same violation without ever carrying explicit bounds.

Worked example

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


def is_valid_bst_naive(node):
    if not node:
        return True
    if node.left and node.left.val >= node.val:
        return False
    if node.right and node.right.val <= node.val:
        return False
    return is_valid_bst_naive(node.left) and is_valid_bst_naive(node.right)


def is_valid_bst(root):
    def helper(node, low, high):
        if not node:
            return True
        if not (low < node.val < high):
            return False
        return helper(node.left, low, node.val) and helper(node.right, node.val, high)
    return helper(root, float("-inf"), float("inf"))


if __name__ == "__main__":
    root = TreeNode(10, TreeNode(5), TreeNode(15, TreeNode(6), TreeNode(20)))
    print(is_valid_bst_naive(root), is_valid_bst(root))

Running this prints True False: the naive, buggy check wrongly calls the tree valid, and the bounds-checked version correctly rejects it.

Complexity

Time: $O(n)$, since each node is visited exactly once by the bounds-checking recursion (or the equivalent iterative inorder-traversal alternative).
Space: $O(h)$, where h is the tree's height, from the recursion call stack; this is $O(\log n)$ for a balanced tree and $O(n)$ worst case for a completely skewed one.

Edge cases

• Empty tree (root is None): trivially valid, since the base case of the recursion returns True immediately.
• Single-node tree: trivially valid regardless of its value, since there are no bounds to violate.
• Duplicate values: must be rejected with a strict inequality (low < node.val < high); a BST with <= semantics on one side is a different, looser invariant that must be stated explicitly.

Trade-offs & pitfalls

This naive-check bug is one of the most common mistakes in BST-validation answers precisely because it looks correct on any small, balanced example where an ancestor's bound never actually gets violated by a distant descendant; it takes a specific counter-example like the one above to expose it.