Algorithmic Problem-Solving and Data Structure Selection Questions

Direct answer

Maintain three running numbers per stream, a count n, the running mean, and M2 (the running sum of squared deviations from the mean-so-far), updated with Welford's one-pass recurrence; this is what keeps the variance numerically stable even after an arbitrarily long run, unlike accumulating sum(x) and sum(x*x) separately. Two such accumulators, one built independently on each machine, combine losslessly with Chan et al.'s parallel-merge formula: combine the counts, take the count-weighted mean, and add a correction term to M2 that accounts for how far apart the two machines' means were.

Structured elaboration

Why not just track sum and sum-of-squares

The textbook variance formula $\mathrm{Var}(X) = E[X^2] - (E[X])^2$ looks like a natural one-pass accumulator: keep sum_x and sum_x2, divide at the end. It is numerically unstable whenever the values share a large common offset relative to their spread (subtracting two large, nearly equal numbers loses precision, a catastrophic-cancellation problem), and the loss compounds as the stream grows. Welford's algorithm sidesteps this entirely by never squaring raw values; it only ever tracks deviations from a mean that is itself updated incrementally.

The update rule (Welford's algorithm)

For each new value $x$, with running count $n$, mean $\bar{x}$, and M2:

The sample variance is $M2 / (n - 1)$ (population variance is $M2 / n$).

Merging two accumulators (Chan, Golub, LeVeque)

Given accumulator $a$ (from one machine) and $b$ (from another), with counts $n_a, n_b$, means $\bar{x}_a, \bar{x}_b$, and $M2_a, M2_b$:

The $\delta^2 n_a n_b / n$ term is the "between-group" variance contribution: it accounts for the two machines' local means disagreeing, which the naive M2_a + M2_b alone would miss.

The exponential-moving-average variant, as a simpler special case, and where it stops being the same idea

A fixed-weight exponential moving average, $\bar{x}_t \leftarrow \bar{x}_{t-1} + \alpha (x_t - \bar{x}_{t-1})$, is the same one-pass, constant-memory update shape as Welford's mean term, specialized to a fixed decay rate $\alpha$ instead of the shrinking weight $1/n$. It is the right choice when you want to weight recent values more than old ones (e.g. tracking a metric that drifts over time) rather than a true all-time average. It does not, however, inherit the clean two-way merge above: each machine's exponential moving average encodes an implicit, ongoing recency-weighting of its own history, and there is no single count you can use to combine two such weighted means correctly, unlike Welford's exact, count-weighted merge. Combining two exponential-moving-average accumulators correctly generally requires tracking (or approximating) an effective sample size per side or aligning them by timestamped decay, a materially different problem from the exact merge above.

Worked example

class OnlineStats:
    def __init__(self):
        self.n = 0
        self.mean = 0.0
        self.M2 = 0.0

    def add(self, x):
        x = float(x)
        self.n += 1
        delta = x - self.mean
        self.mean += delta / self.n
        delta2 = x - self.mean
        self.M2 += delta * delta2

    def variance(self, ddof=1):
        if self.n <= ddof:
            return float('nan')
        return self.M2 / (self.n - ddof)

    @staticmethod
    def merge(a, b):
        if a.n == 0:
            return b
        if b.n == 0:
            return a
        out = OnlineStats()
        out.n = a.n + b.n
        delta = b.mean - a.mean
        out.mean = a.mean + delta * b.n / out.n
        out.M2 = a.M2 + b.M2 + delta * delta * a.n * b.n / out.n
        return out


import random
random.seed(7)
data = [random.gauss(10, 3) for _ in range(2000)]

whole = OnlineStats()
for x in data:
    whole.add(x)

mid = 837
left = OnlineStats()
for x in data[:mid]:
    left.add(x)
right = OnlineStats()
for x in data[mid:]:
    right.add(x)
merged = OnlineStats.merge(left, right)

print("one-pass mean:", whole.mean, "one-pass variance:", whole.variance())
print("merged mean:  ", merged.mean, "merged variance:  ", merged.variance())

This prints:

one-pass mean: 10.050413560803356 one-pass variance: 9.234143479024658
merged mean:   10.050413560803364 merged variance:   9.234143479024652

The two rows agree to within floating-point rounding (differences on the order of $10^{-15}$), confirming the merge formula reconstructs the same statistics as processing all 2000 samples in one pass.

Trade-offs & pitfalls

Complexity

add: $O(1)$ time, $O(1)$ space per call. merge: $O(1)$ time and space regardless of how many samples either side has already seen, this is the whole point of carrying only three numbers instead of the raw data.

Edge cases

• n=0: a fresh OnlineStats() has n=0; variance() returns nan since n <= ddof
  (0 <= 1); merge(a, b) treats an n=0 accumulator as the identity element
  (if a.n == 0: return b), so merging with an empty accumulator is a safe no-op that returns
  the other side unchanged.
• n=1: after one add(), n=1, mean=x, M2=0; variance() under the default
  ddof=1 still returns nan (1 <= 1), correctly reflecting that sample variance is
  undefined for a single point; population variance (ddof=0) would return 0.
• Single-element merge: merging an n=1 accumulator into another one needs no special
  case beyond the n=0 guards above; the standard Chan formula folds the single point into
  the aggregate correctly via the delta * delta * a.n * b.n / out.n cross term.
• Sample variance ($n-1$ denominator) is undefined for $n \le 1$; decide up front which convention (sample vs population) the accumulator reports and guard the edge case.
• Welford's method is far better conditioned than naive sum/sum-of-squares, but it is not infinitely immune to floating-point drift over an astronomically long run; if that matters, periodic re-basing (subtracting off a running offset) or higher-precision accumulation are options, at additional cost.
• A tempting shortcut, re-summing the whole stored history whenever precision looks suspect, defeats the entire "too large to store in full" constraint by silently reintroducing $O(n)$ memory or $O(n)$ per-update time.
• Reaching for the exponential-moving-average variant when the task actually needs the true all-time mean and variance (or an exact cross-machine merge) trades away exactness for recency-weighting you did not ask for.

Direct answer

A plain stack already gives $O(1)$ push, pop, and top because those operations only ever touch the top element. The trick for $O(1)$ minimum retrieval is to keep a second, parallel stack that tracks what the minimum would be after each push: whenever you push a value onto the main stack, you also push the smaller of that value and the previous minimum onto the min-stack, so its top is always the correct current minimum, and popping both stacks together keeps them in sync without ever rescanning.

Approach

• Maintain two stacks of equal length at all times: stack holds the real values, min_stack holds, at each position, what the minimum was after that push.
• push(x): append x to stack. Append x to min_stack if min_stack is empty or x is less than or equal to its current top; otherwise append the current top again (repeating the still-current minimum).
• pop(): pop from both stacks together; the value from stack is returned, the value from min_stack is discarded.
• get_min(): return min_stack's top directly.

class MinStack:
    def __init__(self):
        self.stack: list[int] = []
        self.min_stack: list[int] = []

    def push(self, x: int) -> None:
        self.stack.append(x)
        if not self.min_stack or x <= self.min_stack[-1]:
            self.min_stack.append(x)
        else:
            self.min_stack.append(self.min_stack[-1])

    def pop(self) -> int:
        if not self.stack:
            raise IndexError("pop from empty stack")
        self.min_stack.pop()
        return self.stack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def get_min(self) -> int:
        return self.min_stack[-1]


if __name__ == "__main__":
    s = MinStack()
    s.push(5)
    s.push(3)
    s.push(7)
    print(s.get_min())  # 3
    s.pop()
    print(s.get_min())  # 3
    s.pop()
    print(s.get_min())  # 5
    print(s.top())       # 5

Running this prints 3, 3, 5, 5: after pushing 5, 3, 7 the minimum is 3; popping 7 (the top) leaves the minimum still 3; popping 3 next leaves only 5, so both the minimum and the top become 5.

Key points

• Using <= (not strict <) when deciding whether to push a new minimum is what makes duplicate minimum values work correctly: if two entries tie for the minimum and you only recorded the first, popping it would incorrectly raise the recorded minimum before the still-present duplicate is gone.
• An alternative "encoded delta" trick stores a single stack, keeping only a running minimum variable, and pushes a value relative to that minimum instead of the raw value, updating the running minimum on push/pop as needed. It roughly halves auxiliary storage but is more error-prone to implement correctly, especially in fixed-width-integer languages (C++, Java) where the encoded delta itself can overflow if the gap between the pushed value and the previous minimum is large.

Complexity

Time: $O(1)$ for every operation (push, pop, top, get_min). Space: $O(n)$ auxiliary for $n$ elements (two stacks, each up to size $n$; a larger constant factor than a single stack, but still linear).

Edge cases

• pop or top on an empty stack should raise or otherwise signal an error rather than reading past the end.
• Duplicate values at the current minimum: handled correctly only if the min-stack push condition uses <=, not <.
• A single-element stack: get_min() must equal top().

Direct answer

A plain prefix-sum array gives O(1) range-sum queries but forces an O(n)
rebuild whenever a single element changes, since every prefix after it shifts.
The structure that supports both range-sum queries and point updates in
$O(\log n)$ is a Binary Indexed Tree, commonly called a Fenwick tree
(named for its inventor, Peter Fenwick): an implicit tree layered over the
array where each node stores the sum of a specific, power-of-two-sized range,
so that both "add a value at one index" and "sum everything up to an index"
touch only $O(\log n)$ nodes, by walking a path determined by the binary
representation of the index.

Structured elaboration

Why plain prefix sums fail the update requirement. If prefix[i] stores
the sum of all elements before index i, a range query is one subtraction,
$O(1)$, but changing a single array element invalidates every prefix sum
from that index onward, an $O(n)$ fix. The question specifically asks for
both operations in $O(\log n)$, so a data structure is needed where a
single update only touches a bounded, logarithmic set of stored partial sums,
not a full contiguous range of them.

How a Fenwick tree gets both operations to $O(\log n)$. Index the
array 1-based internally. Each position i in the underlying tree array
stores the sum of a range of the original array whose length is the lowest
set bit of i (in binary): position 6 (110) stores a range of length 2
(the lowest set bit of 6 is 2), position 8 (1000) stores a range of length
8, and so on. This gives two walks, both bounded by the number of bits in
n, i.e. $O(\log n)$:

• Point update (add(i, delta)): starting at i, repeatedly jump to
  i += i & (-i) (moving to the next node whose range also covers i),
  adding delta at each stop, until past the end of the array. i & (-i)
  isolates the lowest set bit of i in two's-complement arithmetic, which is
  exactly the jump size that walks you through every ancestor node covering
  this index.
• Prefix-sum query (prefix_sum(i)): starting at i, repeatedly add the
  stored value and jump to i -= i & (-i) (stripping the lowest set bit),
  until reaching 0. Each step consumes one bit of i's binary representation,
  which is why the walk terminates in at most $\log_2 n$ steps.

Both operations only ever visit nodes on a path determined by clearing or
adding the lowest set bit, which is why each is $O(\log n)$ rather than
$O(n)$: a Fenwick tree never needs to touch a whole contiguous range of
stored sums the way a plain prefix array does.

Range sum from two prefix sums. range_sum(l, r) = prefix_sum(r) - prefix_sum(l - 1),
same subtraction trick as a plain prefix array, just built on top of
$O(\log n)$ prefix queries instead of $O(1)$ ones, trading a little query
speed for tractable updates.

Worked example

class FenwickTree:
    def __init__(self, nums):
        self.n = len(nums)
        self.tree = [0] * (self.n + 1)
        for i, x in enumerate(nums):
            self._add(i, x)

    def _add(self, i, delta):
        i += 1  # 1-indexed internally
        while i <= self.n:
            self.tree[i] += delta
            i += i & (-i)

    def update(self, i, new_value):
        current = self.prefix_sum(i) - (self.prefix_sum(i - 1) if i > 0 else 0)
        self._add(i, new_value - current)

    def prefix_sum(self, i):
        i += 1
        total = 0
        while i > 0:
            total += self.tree[i]
            i -= i & (-i)
        return total

    def range_sum(self, left, right):
        if left > right:
            return 0
        left_part = self.prefix_sum(left - 1) if left > 0 else 0
        return self.prefix_sum(right) - left_part

nums = [3, 2, -1, 6, 5, 4, -3, 3, 7, 2]
ft = FenwickTree(nums)
print(ft.range_sum(0, 9))  # sum of all elements
print(ft.range_sum(2, 5))  # -1 + 6 + 5 + 4
ft.update(2, 10)           # nums[2] changes from -1 to 10
print(ft.range_sum(2, 5))  # 10 + 6 + 5 + 4
print(ft.range_sum(0, 9))  # total shifts by the same +11 delta

Output (verified by running this exact code):

28
14
25
39

This was additionally cross-checked with a 200-operation randomized test
(seed 42) comparing every range_sum result against a brute-force
sum(arr[l:r+1]) recomputation after each simulated update, with no
mismatches.

Complexity

Time: $O(\log n)$ for both update and range_sum (each is one or two
prefix-sum walks). Space: $O(n)$ for the tree array, on top of the
original array.

Edge cases

• left > right: return 0 (an empty range).
• left == 0: skip the left-side prefix subtraction rather than querying
  prefix_sum(-1).
• Negative numbers: handled transparently, since the structure only ever adds
  and subtracts, with no assumption of non-negativity.
• Building from an existing array costs $O(n \log n)$ if done by calling
  _add once per element (as in the constructor above); an $O(n)$ direct
  build is possible but adds complexity that is rarely worth it unless n is
  very large and construction is on a hot path.

Trade-offs & pitfalls

• A segment tree solves the same problem with the same $O(\log n)$ bounds
  and is more general (it directly supports range-minimum, range-maximum,
  and other associative combining functions, not just sums), at the cost of
  roughly twice the constant-factor overhead and a slightly more involved
  implementation. The absorbed range-minimum-query framing does not carry
  over to a Fenwick tree as cleanly as range-sum does: a Fenwick tree's
  update walk relies on values being combinable by simple addition and
  subtraction (to compute a delta and apply it), but minimum has no inverse
  operation, so a Fenwick tree only supports range-minimum queries under
  restricted conditions (for example, values that only increase over time,
  never need pinpoint decreases); a general point-update range-minimum
  requirement should reach for a segment tree instead, not force-fit a
  Fenwick tree.
• The absorbed weighted-random-sampling framing fits well: a Fenwick
  tree over cumulative weights supports "pick index i with probability
  proportional to its weight" by drawing a random value in
  $[0, \text{total weight})$ and walking the tree to find the smallest
  prefix sum exceeding it (a "find by cumulative frequency" walk, itself
  $O(\log n)$), while still allowing individual weights to be updated in
  $O(\log n)$, which a plain cumulative array cannot do without an $O(n)$
  rebuild per weight change.
• The absorbed order-statistics augmented binary search tree (a binary
  search tree, or BST, where each node additionally stores the size of its
  subtree) is a related but different composition: it targets rank-based
  queries over a dynamic set of keys (insert, delete, find the k-th
  smallest key), whereas a Fenwick tree here targets sum queries over a
  fixed-size indexed array. Both are "compose a query capability onto a
  balanced or implicit tree structure so both queries and updates stay
  logarithmic," but they solve different query shapes (rank-of-key versus
  sum-over-range) and are not interchangeable implementations of each other.
• A common implementation bug is mixing up 0-indexed and 1-indexed
  bookkeeping between the public API and the internal tree array; keep the
  1-indexing strictly internal, as done above, so callers never need to
  reason about it.

Direct answer

A lowest common ancestor (LCA) query in a general binary tree can be answered with a single postorder-style depth-first search (DFS, a traversal that explores each branch fully before backtracking) that returns node references bubbling up: if a subtree's search finds both target nodes on different sides, the current node is the LCA; if only one side finds anything, that result is passed further up. When the tree happens to be a binary search tree (BST), searching both subtrees isn't necessary at all: comparing the two target values against the current node's key, and walking down toward whichever side both targets agree on, is enough.

Structured elaboration

Approach: general binary tree

• Recurse into both children. At any node, if the node itself is one of the two targets, or if the node is None, return it directly (a None or a matched target both act as the "nothing more to find below here, here's what was found" signal).
• After the recursive calls return, if both the left and right calls found something non-None, the current node sits between the two targets, so it is the LCA; return it.
• If only one side found something, that result (the target itself, or an LCA found deeper down) is passed up unchanged, since the current node cannot be the answer.

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


def lca_general(root, p, q):
    """Lowest common ancestor in a general binary tree. p and q are TreeNode
    references known to exist in the tree."""
    if root is None or root is p or root is q:
        return root
    left = lca_general(root.left, p, q)
    right = lca_general(root.right, p, q)
    if left and right:
        return root
    return left if left else right

Approach: binary search tree

• In a BST, every node's key already encodes where its descendants live relative to it, so two arbitrary nodes don't require searching both subtrees.
• Starting at the root, compare both target values to the current node's key: if both are smaller, the LCA must be in the left subtree, so move left; if both are larger, move right; if they split (one on each side, or either target equals the current key), the current node is the LCA, since that's the first point where the two search paths diverge.
• This turns an O(n) full-tree traversal into an O(h) walk that only ever moves in one direction, without exploring both children at any step.

def lca_bst(root, p_val, q_val):
    """Lowest common ancestor in a binary search tree, using key comparisons
    instead of exploring both subtrees."""
    node = root
    while node is not None:
        if p_val < node.val and q_val < node.val:
            node = node.left
        elif p_val > node.val and q_val > node.val:
            node = node.right
        else:
            return node  # values split here (or one equals node.val): this is the LCA
    return None

Key points

• The general-tree version explores every node in the worst case, since it has no way to prune a subtree without checking it.
• The BST version needs no recursion into both sides at all; it reuses the same "which direction do both targets agree on" comparison as an ordinary BST search, walking a single path from the root.

Worked example

Building this tree:

        6
      /   \
     2     8
    / \   / \
   0   4 7   9
      / \
     3   5

This tree also happens to satisfy the BST ordering property (every left descendant is smaller, every right descendant larger), so both functions can be run on it and compared directly. lca_general(root, node(2), node(8)) and lca_bst(root, 2, 8) both print 6 (the two nodes sit in different subtrees of the root). lca_general(root, node(2), node(4)) and lca_bst(root, 2, 4) both print 2 (node 2 is an ancestor of node 4). lca_general(root, node(3), node(5)) and lca_bst(root, 3, 5) both print 4 (they are siblings under node 4).

Trade-offs & pitfalls

Complexity

General binary tree: Time $O(n)$, visiting every node once in the worst case, since there's no way to prune a subtree that hasn't been checked. Space $O(h)$ for the recursion stack, where $h$ is the tree's height ($O(\log n)$ balanced, $O(n)$ degenerate).
Binary search tree: Time $O(h)$, a single downward walk with no backtracking. Space $O(1)$ with the iterative version shown, or $O(h)$ if written recursively.

Edge cases

• One of the two targets is an ancestor of the other: both approaches correctly return the ancestor itself as the LCA.
• p and q are the same node: returns that node.
• p or q is not actually present in the tree: both implementations shown assume presence and will return a plausible-looking but wrong answer rather than erroring; a production version should verify both nodes exist first, a separate O(n) or O(h) check, if that guarantee doesn't already hold elsewhere.
• A deeply skewed tree: the general-tree recursive version risks hitting the language's recursion limit; converting to an explicit iterative stack avoids that.

Applying the BST shortcut to a tree that is not actually a BST silently gives a wrong answer with no error, since the comparison-based walk assumes an ordering invariant that a general binary tree doesn't provide; always confirm which structure is actually in hand before choosing the approach. A second common mistake in the general-tree version is comparing node values instead of node identity when duplicate values are possible, which can match the wrong node entirely.

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.