Meta Machine Learning Engineer Interview Preparation Guide (Junior Level)

Direct answer

Assume $y = X\beta + \varepsilon$ with $\varepsilon \sim N(0, \sigma^2 I)$: maximizing the Gaussian likelihood over $\beta$ is algebraically identical to minimizing the squared-error loss, so the OLS estimator is the maximum-likelihood estimator under this noise model, not merely similar to it. Adding an L2 penalty is the same derivation with one extra ingredient, a Gaussian prior on the weights, $\beta \sim N(0, \tau^2 I)$; maximizing the resulting posterior (MAP) instead of the plain likelihood produces exactly the ridge regression estimator, with the regularization strength $\lambda = \sigma^2/\tau^2$ falling directly out of the ratio between the noise variance and the prior variance.

Structured elaboration

Setup and likelihood. With $X$ an $n\times p$ design matrix and $\varepsilon \sim N(0,\sigma^2 I)$ i.i.d., $y \mid X, \beta \sim N(X\beta, \sigma^2 I)$, so the likelihood is

MLE derivation. The log-likelihood is $\ell(\beta) = -\frac{n}{2}\log(2\pi\sigma^2) - \frac{1}{2\sigma^2}\lVert y - X\beta \rVert^2$. Since $\sigma^2$ doesn't depend on $\beta$, maximizing $\ell(\beta)$ over $\beta$ is exactly equivalent to minimizing $\lVert y - X\beta \rVert^2$, the OLS objective, term for term, with no approximation involved. Setting the gradient to zero,

and, when $X^\top X$ is invertible, $\hat\beta_{\text{MLE}} = (X^\top X)^{-1} X^\top y$, which is precisely the OLS closed-form solution. This isn't a coincidence or an analogy, the two derivations are the same optimization problem viewed from two different starting points (minimize squared error vs. maximize Gaussian likelihood), and they land on the identical estimator because the assumed noise model is exactly what makes squared-error loss the correct one to minimize.

Adding the L2 penalty as a MAP estimate. Place a Gaussian prior on the weights, $\beta \sim N(0, \tau^2 I)$, representing a belief that weights are probably small unless the data strongly indicates otherwise. By Bayes' rule the posterior is proportional to likelihood times prior, so the log-posterior (dropping additive constants that don't depend on $\beta$) is

Maximizing this (equivalently, minimizing its negative) and setting the gradient to zero,

so defining $\lambda = \sigma^2/\tau^2$ gives exactly the ridge regression estimator $\hat\beta_{\text{ridge}} = (X^\top X + \lambda I)^{-1} X^\top y$. The interpretation falls directly out of the algebra: a tighter prior (small $\tau^2$, strong belief that weights should be small) corresponds to a larger $\lambda$ (more shrinkage), and a diffuse, uninformative prior ($\tau^2 \to \infty$) corresponds to $\lambda \to 0$, recovering plain OLS exactly.

Worked example

import numpy as np
from scipy.optimize import minimize

np.random.seed(78)
n, p = 60, 4
X = np.random.randn(n, p)
beta_true = np.array([1.0, -2.0, 0.5, 0.0])
sigma = 1.0
y = X @ beta_true + np.random.randn(n) * sigma

# --- MLE / OLS ---
beta_mle_closed = np.linalg.solve(X.T @ X, X.T @ y)

def neg_loglik(beta):
    return 0.5 * np.sum((y - X @ beta) ** 2) / sigma**2

beta_mle_numeric = minimize(neg_loglik, np.zeros(p), method='BFGS').x

# --- ridge / MAP, prior variance tau^2 = 2.0, so lambda = sigma^2/tau^2 = 0.5 ---
tau2 = 2.0
lam = sigma**2 / tau2
beta_ridge_closed = np.linalg.solve(X.T @ X + lam * np.eye(p), X.T @ y)

def neg_log_posterior(beta):
    return 0.5*np.sum((y-X@beta)**2)/sigma**2 + 0.5*np.sum(beta**2)/tau2

beta_map_numeric = minimize(neg_log_posterior, np.zeros(p), method='BFGS').x

Running this (verified): beta_mle_closed = [0.99960, -2.00892, 0.57924, -0.25262], and beta_mle_numeric (a from-scratch numerical maximization of the Gaussian likelihood, using no closed form at all) matches it to within $1.9\times10^{-8}$, floating-point-precision agreement, confirming the MLE-equals-OLS claim reproduces numerically, not just algebraically.

For the ridge/MAP side, $\lambda = \sigma^2/\tau^2 = 1.0/2.0 = 0.5$: beta_ridge_closed = [0.98253, -1.98270, 0.57721, -0.24889], and beta_map_numeric (direct maximization of the log-posterior) matches it to within $1.5\times10^{-8}$. Cross-checked independently against sklearn.linear_model.Ridge(alpha=0.5, fit_intercept=False).fit(X, y).coef_: matches the closed form to within $9\times10^{-16}$ (floating-point round-off, effectively exact).

As expected, ridge pulls every coefficient slightly toward zero relative to OLS (each shrunk by a small, consistent amount, e.g. the first coefficient moves from $0.9996$ to $0.9825$), which is exactly the Gaussian-prior story: the MAP estimate is a compromise between the data's preferred value (the MLE) and the prior's preferred value (zero), weighted by how much you trust each.

Trade-offs & pitfalls

• This equivalence is specific to Gaussian noise and a Gaussian prior; a different noise assumption (e.g. Laplace-distributed errors) makes the MLE match a different loss (absolute error, not squared error), and a Laplace prior on the weights instead of Gaussian gives you Lasso's L1 penalty as the MAP estimate instead of ridge, the same derivation pattern generalizes, but the specific loss/penalty pair does not.
• $\lambda = \sigma^2/\tau^2$ is a clean interpretation but assumes you actually know or can estimate both variances; in practice $\lambda$ is almost always chosen by cross-validation directly, this derivation explains why the penalty has the shrinkage effect it does, it isn't usually how $\lambda$ gets picked operationally.
• A MAP estimate is a single point (the posterior mode), not the full posterior distribution; if you need calibrated uncertainty over $\beta$ itself, you need the full Bayesian posterior (which, conveniently, is also Gaussian in this conjugate case), not just its mode.
• Don't overstate the "prior" framing to a skeptical audience as though ridge regression requires believing in Bayesian priors to use; the algebra is identical either way, the Bayesian derivation is an interpretation of why the L2 penalty behaves the way it does, not a precondition for the method's validity.

The idea in plain words

"Probability proportional to weight" means that if the weights are 3, 1, 4, 1, 5 (total 14), item e is picked with probability 5/14. A direct way to pick: draw a random whole number r from 0 to total - 1, lay the items out on a number line with item i owning a stretch of weight[i] consecutive positions, and return the item whose stretch contains r. The whole problem is finding that item fast while weights keep changing.

A binary sum tree does both parts in O(log n). Put the weights in the leaves of a binary tree (leaves are nodes with no children), and let every internal node store the sum of its two children. The root then holds the total. To find the owner of position r, start at the root and ask "is r inside the left child's stretch?": if r < left sum, go left; otherwise subtract the left sum from r and go right. One decision per level, so the walk takes as many steps as the tree has levels. To change a weight, add the difference to the leaf and to each of its ancestors, again one step per level. Heights and depths here count edges (empty tree -1, single node 0), so a tree with 8 leaves has height 3.

Weights here are non-negative integers, which makes the arithmetic exact; for decimal weights, scale them to integers first. Each update adds a difference to the ancestors, and with floating-point numbers the rounding can leave a tiny nonzero residue in a node whose true weight is 0, so a descent can then return a zero-weight item.

Brute force and the alternatives

• Linear scan: add weights until the running total passes r. Sampling is O(n), updates are O(1).
• Prefix-sum array (cumulative totals [3, 4, 8, 9, 14]): sampling is O(log n) with a binary search, but changing one weight changes every cumulative value after it, so an update is O(n).
• Heap: a heap keeps the largest (or smallest) item at the top and says nothing about sums of subtrees. It is the wrong tool for "pick in proportion to weight". (Heaps do appear in weighted sampling without replacement from a stream, where each item gets a random key built from its weight and a heap keeps the best k keys. That is a rarely asked extension and a different task from sampling from a changing table.)
• Sum tree or Fenwick tree: O(log n) for both operations.

The layout

The tree lives in a flat list. With size leaves (a power of two), leaf i is at index size + i, and the children of node j are 2j and 2j + 1. The five weights above, padded to 8 leaves, look like this (node numbers are the list indexes):

              1:14
          /          \
       2:9            3:5
      /    \         /    \
    4:4    5:5     6:5    7:0
    / \    / \     / \    / \
   3   1  4   1   5   0  0   0
   a   b  c   d   e

The root holds 14. The list is printed by the program below as [0, 14, 9, 5, 4, 5, 5, 0, 3, 1, 4, 1, 5, 0, 0, 0]; index 0 is unused.

Code

import random


class WeightedSampler:
    """Binary sum tree in an array. Leaf i is at size + i; each internal node holds the sum of
    its two children, so tree[1] is the total weight. Weights are non-negative integers."""

    def __init__(self, capacity=4):
        self.size = 1
        while self.size < capacity:
            self.size *= 2
        self.tree = [0] * (2 * self.size)
        self.items = []

    def add(self, item, weight):
        if len(self.items) == self.size:
            self._grow()
        self.items.append(item)
        self.update(len(self.items) - 1, weight)

    def update(self, index, new_weight):
        if not 0 <= index < len(self.items):
            raise IndexError(index)
        if new_weight < 0:
            raise ValueError("weight must be >= 0")
        node = self.size + index
        delta = new_weight - self.tree[node]
        while node >= 1:                          # add the change to every ancestor
            self.tree[node] += delta
            node //= 2

    def _grow(self):                              # doubles the leaf level and rebuilds sums
        leaves = self.tree[self.size:self.size + len(self.items)]
        self.size *= 2
        self.tree = [0] * (2 * self.size)
        self.tree[self.size:self.size + len(leaves)] = leaves
        for node in range(self.size - 1, 0, -1):
            self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]

    def total(self):
        return self.tree[1]

    def find(self, r, log=None):
        """Index of the leaf that owns position r, for 0 <= r < total."""
        node = 1
        while node < self.size:
            left = self.tree[2 * node]
            if r < left:
                node = 2 * node
                where = "left"
            else:
                r -= left
                node = 2 * node + 1
                where = "right"
            if log is not None:
                log.append(f"  at node {node // 2} (left sum {left}): go {where}, r is now {r}")
        return node - self.size

    def sample(self, n, rng):
        if self.total() == 0:
            raise ValueError("no weight to sample from")
        return [self.items[self.find(rng.randrange(self.total()))] for _ in range(n)]


class Fenwick:
    """Fenwick (binary indexed) tree over the same weights: n + 1 slots instead of 2 * size."""

    def __init__(self, weights):
        self.n = len(weights)
        self.t = [0] * (self.n + 1)
        for i, w in enumerate(weights):
            self.add(i, w)

    def add(self, i, delta):
        i += 1
        while i <= self.n:
            self.t[i] += delta
            i += i & -i

    def find(self, r):
        """Smallest index whose running total exceeds r."""
        pos, step = 0, 1 << self.n.bit_length()
        while step:
            nxt = pos + step
            if nxt <= self.n and self.t[nxt] <= r:
                pos = nxt
                r -= self.t[nxt]
            step >>= 1
        return pos


if __name__ == "__main__":
    s = WeightedSampler()
    for name, w in [("a", 3), ("b", 1), ("c", 4), ("d", 1), ("e", 5)]:
        s.add(name, w)
    print("capacity", s.size, "| tree array:", s.tree)
    print("node 1 = total", s.total(), "| node 2 =", s.tree[2], "(leaves a..d) | node 3 =", s.tree[3], "(leaves e..h)")

    log = []
    idx = s.find(9, log)
    print("find(9):")
    print("\n".join(log))
    print("-> index", idx, "item", s.items[idx])

    # Exact check: over r = 0..total-1 every leaf must own exactly `weight` positions
    def check(sampler):
        owned = [0] * len(sampler.items)
        for r in range(sampler.total()):
            owned[sampler.find(r)] += 1
        assert owned == sampler.tree[sampler.size:sampler.size + len(sampler.items)], owned
        return owned
    print("positions owned per item:", check(s))

    s.update(1, 6)                    # b goes from 1 to 6
    s.update(2, 0)                    # c goes from 4 to 0, so it must never be returned
    s.add("f", 2)
    s.add("g", 0)
    s.add("h", 7)
    s.add("i", 3)                     # the ninth item forces the tree to double
    print("after updates, capacity", s.size, "| owned per item:", check(s))

    fen = Fenwick(s.tree[s.size:s.size + len(s.items)])
    assert all(fen.find(r) == s.find(r) for r in range(s.total()))
    print("Fenwick find agrees with the sum tree on all", s.total(), "positions")

    rng = random.Random(42)
    draws = s.sample(20000, rng)
    counts = {k: draws.count(k) for k in s.items}
    print("20000 draws:", counts)
    print("expected   :", {k: round(20000 * w / s.total()) for k, w in zip(s.items, s.tree[s.size:])})

    # Randomised check against a plain list of weights
    rng = random.Random(9)
    ref, t = [], WeightedSampler(1)
    for step in range(400):
        if not ref or rng.random() < 0.3:
            ref.append(rng.randint(0, 5)); t.add(len(ref) - 1, ref[-1])
        else:
            i = rng.randrange(len(ref)); ref[i] = rng.randint(0, 5); t.update(i, ref[i])
        if sum(ref):
            assert check(t) == ref
    print("random add/update sequence checked against a plain list: 400 steps, final size", len(ref))

    # The two guards: nothing to sample, and a negative weight
    for label, action in [("empty sampler, sample(1)", lambda: WeightedSampler().sample(1, rng)),
                          ("update(0, -1) on the sampler above", lambda: s.update(0, -1))]:
        try:
            action()
        except ValueError as err:
            print(f"{label}: ValueError: {err}")

Output:

capacity 8 | tree array: [0, 14, 9, 5, 4, 5, 5, 0, 3, 1, 4, 1, 5, 0, 0, 0]
node 1 = total 14 | node 2 = 9 (leaves a..d) | node 3 = 5 (leaves e..h)
find(9):
  at node 1 (left sum 9): go right, r is now 0
  at node 3 (left sum 5): go left, r is now 0
  at node 6 (left sum 5): go left, r is now 0
-> index 4 item e
positions owned per item: [3, 1, 4, 1, 5]
after updates, capacity 16 | owned per item: [3, 6, 0, 1, 5, 2, 0, 7, 3]
Fenwick find agrees with the sum tree on all 27 positions
20000 draws: {'a': 2144, 'b': 4418, 'c': 0, 'd': 760, 'e': 3728, 'f': 1477, 'g': 0, 'h': 5284, 'i': 2189}
expected   : {'a': 2222, 'b': 4444, 'c': 0, 'd': 741, 'e': 3704, 'f': 1481, 'g': 0, 'h': 5185, 'i': 2222}
random add/update sequence checked against a plain list: 400 steps, final size 139
empty sampler, sample(1): ValueError: no weight to sample from
update(0, -1) on the sampler above: ValueError: weight must be >= 0

How a sample descends: the trace

find(9) on the tree above (the cumulative totals are 3, 4, 8, 9, 14, so position 9 is the first position owned by e):

1. At node 1 the left child (node 2) holds 9. r = 9 is not below 9, so go right and set r = 9 - 9 = 0.
2. At node 3 the left child (node 6) holds 5. r = 0 < 5, so go left.
3. At node 6 the left child (leaf 12) holds 5. r = 0 < 5, so go left. Node 12 is a leaf: index 12 - 8 = 4, which is e.

That is exactly the three lines the program prints, and the result e matches the layout.

Why it is correct, and checked exhaustively. At each node the left child owns the first left sum positions of that node's stretch and the right child owns the rest, so the decision never loses a position. The check function in the program tries every r from 0 to total - 1 and confirms that item i is returned for exactly weight[i] of them. That exact count (not a random test) is shown after the updates too, where a weight of 0 is owned by zero positions and so can never be sampled. The 20,000-draw run is a fixed-seed illustration: its counts land near the expected counts but are not exact, which is normal for random draws.

Add, update, and sample(n)

• update(index, new_weight): compute the difference, then add it to the leaf and to every ancestor up to the root: one step per level.
• add(item, weight): put the item in the next free leaf and call update. When the leaves are all used, the tree doubles its leaf count and rebuilds every internal sum in O(size). Amortized means the cost averaged over a whole run of operations. A rebuild at capacity 8 costs about 16 steps, but it can only happen again after 8 more adds have filled the new space, so the rebuild work per add stays constant on average even though one unlucky add costs O(n). In the program, the ninth add doubles the capacity from 8 to 16.
• sample(n): n independent draws of r, each followed by a descent: O(n log N) for N items. That is sampling with replacement (the same item can appear twice). Sampling without replacement can be done by setting a drawn item's weight to 0 with update, and restoring it afterwards, O(log N) each.

Fenwick tree comparison

A Fenwick tree (binary indexed tree) stores partial sums in one list of N + 1 slots, using the lowest set bit of the index to decide which range each slot covers (worked in the walk-through below). Updates add the difference to O(log N) slots; the sample step finds the smallest index whose running total exceeds r by testing powers of two from large to small. The program builds one from the same weights and shows that its find returns the same index as the sum tree for all 27 positions. Choose the Fenwick tree when memory matters or you only need prefix sums plus sampling: it uses N + 1 slots instead of 2 * size (roughly 2N to 4N). Choose the explicit sum tree when you want to read a node's subtree total directly, such as to descend to a subtree, to split sampling by region, or to teach and debug.

Fenwick walk-through on the five weights

Three ideas make the Fenwick tree work. The lowest set bit of a number is its rightmost 1 in binary, and i & -i isolates it (for 12 = 1100 it is 4). Slot i (counting from 1) stores the sum of the i & -i weights that end at index i, so slot 4 covers four weights, slot 6 covers two, and every odd slot covers just itself. Adding i & -i to i jumps to the next slot whose range contains i, which is how an update reaches every slot that must change. And 1 << n.bit_length() is the smallest power of two above n (8 for n = 5), the largest jump the descent can try.

weights = [3, 1, 4, 1, 5]
n = len(weights)
t = [0] * (n + 1)          # slot i (1-based) holds the sum of the last (i & -i) weights ending at i


def add(i, delta):
    i += 1                 # convert to 1-based
    while i <= n:
        t[i] += delta
        print(f"    slot {i} ({i:03b}) += {delta}  -> {t[i]}")
        i += i & -i        # i & -i is the lowest set bit of i; adding it jumps to the next slot that covers i


for idx, w in enumerate(weights):
    print(f"add weight {w} at index {idx}:")
    add(idx, w)
print("slots 1..5:", t[1:])
for i in range(1, n + 1):
    low = i & -i
    print(f"slot {i} ({i:03b}): lowest set bit {low}, covers weights at indexes {i - low}..{i - 1} = {sum(weights[i - low:i])}")


def find(r):
    pos, step = 0, 1 << n.bit_length()
    print(f"find({r}): start pos=0, step={step}")
    while step:
        nxt = pos + step
        if nxt <= n and t[nxt] <= r:
            print(f"    step {step}: slot {nxt} holds {t[nxt]} <= r={r}, take it, r becomes {r - t[nxt]}")
            pos, r = nxt, r - t[nxt]
        else:
            print(f"    step {step}: slot {nxt} " + ("is past the end" if nxt > n else f"holds {t[nxt]} > r={r}, skip"))
        step >>= 1
    return pos


print("owner of position 9 is index", find(9))

# growing a sum tree from 2 leaves to 4 when a third weight arrives
size, tree = 2, [0, 4, 3, 1]          # leaves are tree[2:4] = [3, 1]; tree[1] = 4 is the total
print("\nbefore grow:", tree)
leaves = tree[size:]
size *= 2
tree = [0] * (2 * size)
tree[size:size + len(leaves)] = leaves  # copy the leaves into the new, wider leaf level
for node in range(size - 1, 0, -1):     # recompute every internal sum bottom-up
    tree[node] = tree[2 * node] + tree[2 * node + 1]
print("after grow: ", tree)
tree[size + 2] = 4                      # now the third weight fits; add it to the leaf (node 6) and its ancestors (nodes 3 and 1)
tree[3] += 4
tree[1] += 4
print("after adding weight 4 at index 2:", tree)

Output:

add weight 3 at index 0:
    slot 1 (001) += 3  -> 3
    slot 2 (010) += 3  -> 3
    slot 4 (100) += 3  -> 3
add weight 1 at index 1:
    slot 2 (010) += 1  -> 4
    slot 4 (100) += 1  -> 4
add weight 4 at index 2:
    slot 3 (011) += 4  -> 4
    slot 4 (100) += 4  -> 8
add weight 1 at index 3:
    slot 4 (100) += 1  -> 9
add weight 5 at index 4:
    slot 5 (101) += 5  -> 5
slots 1..5: [3, 4, 4, 9, 5]
slot 1 (001): lowest set bit 1, covers weights at indexes 0..0 = 3
slot 2 (010): lowest set bit 2, covers weights at indexes 0..1 = 4
slot 3 (011): lowest set bit 1, covers weights at indexes 2..2 = 4
slot 4 (100): lowest set bit 4, covers weights at indexes 0..3 = 9
slot 5 (101): lowest set bit 1, covers weights at indexes 4..4 = 5
find(9): start pos=0, step=8
    step 8: slot 8 is past the end
    step 4: slot 4 holds 9 <= r=9, take it, r becomes 0
    step 2: slot 6 is past the end
    step 1: slot 5 holds 5 > r=0, skip
owner of position 9 is index 4

before grow: [0, 4, 3, 1]
after grow:  [0, 4, 4, 0, 3, 1, 0, 0]
after adding weight 4 at index 2: [0, 8, 4, 4, 3, 1, 4, 0]

Read the trace like this. Adding weight 3 at index 0 touches slots 1, 2 and 4: the three slots whose ranges include index 0. The table shows slot 4 holds 9 = 3 + 1 + 4 + 1, the first four weights. In find(9) the descent tries the largest jump first: slot 8 does not exist, slot 4 holds 9 which is not above r = 9, so the whole block belongs before the answer and r drops to 0. The next jump lands on slot 6, past the end, and slot 5 holds 5, which is above 0, so the walk stops with pos = 4: index 4, item e, the same owner the sum tree found. The last three lines show the sum tree's growth step on a 2-leaf tree: the leaves are copied into a wider leaf level and every internal sum is recomputed bottom-up.

A typical interview needs one of the two trees (the sum tree or the Fenwick tree), the update rule and the descent rule. The alias method and sampling with random keys and a heap are deeper material that a coding round rarely asks for.

Complexity

• update, find: O(log size) each, where the tree has about log2(size) levels (3 for 8 leaves, 4 for 16).
• add: O(log size) plus an O(size) rebuild each time the capacity doubles: amortized O(log size).
• sample(n): O(n log size).
• Space: a list of 2 * size entries, where size is at most about 2N for N items, so about 4N entries at most.

Edge cases and common mistakes

• Total weight 0: there is nothing to sample; the code raises ValueError instead of returning an item (the last lines of the first program's output show it).
• Zero-weight items must never be returned: use r < left (strict) when choosing the left child, which the exhaustive check confirms.
• Updating a leaf without updating its ancestors leaves every sum above it stale, so the descent is steered by old totals.
• Using floating-point weights and random.random() * total: rounding can send the descent into a zero-weight leaf. Scale to integers or add a guard.
• Off-by-one on the position: randrange(total) yields 0 to total - 1; using randint(0, total) can pick a position past the end.
• Negative weights make the stretches meaningless; reject them as update does (also shown in the last output line of the first program).

Follow-ups and how the answer changes

• Weights never change and the number of draws is huge: the alias method (a precomputed table of two-way coin flips; rarely asked in interviews) gives O(1) per draw after an O(n) setup, but any update means rebuilding.
• Sampling without replacement while weights change: the zero-and-restore trick above, in O(log N) per draw.
• Different sample sizes per call and a stream of items: keep the same tree and only grow the leaf level when needed.

Running the code

# Python 3.12, standard library only
python weighted_sampler.py     # the sampler (first program)
python fenwick_walk.py         # the Fenwick walk-through (second program)

The idea

To make amount a with the fewest coins, think about the last coin you hand over. If it has value c, what you handed over before it made exactly a - c, and you want that earlier part to use as few coins as possible. Trying every coin as the last one and taking the best gives a formula that reuses answers for smaller amounts. Greedy (always take the biggest coin that fits) can fail, so this needs dynamic programming (DP): solving small versions first and combining them.

The five things to state

1. What one cell means. fewest[a] is the minimum number of coins that sum to exactly a, or infinity if no combination makes a.
2. The transition. fewest[a] = 1 + min(fewest[a - c]) over every coin c with c <= a. The 1 is the last coin, and fewest[a - c] is the best way to build the rest. Taking the minimum over all choices of the last coin covers every possible solution.
3. Base case and initialisation. fewest[0] = 0 (no coins make zero). Every other cell starts at infinity, meaning "not reachable yet". Infinity plus 1 is still infinity, so a coin that leads to an unreachable remainder can never win a minimum.
4. Fill order. Ascending a, because cell a reads smaller cells a - c.
5. Where the answer is. fewest[amount]. If it is still infinity, return -1.

Why the initial value matters

Starting the unreachable cells at 0 treats "impossible" as "free". The driver runs that bug: for coins [2] and amount 3 it prints 1 instead of -1, because fewest[1] stays 0 and the code believes one coin of 2 reaches 3. Starting at -1 fails the opposite way, because min would pick -1 and then add 1 to get 0. With integer infinity (or amount + 1 as a stand-in for infinity: every real answer uses at most amount coins because each coin is worth at least 1, so amount + 1 can never be a genuine count), unreachable amounts are detected by one comparison at the end.

Brute force first

Plain recursion tries every coin from every remainder. For coins [1, 2, 5] and amount 11 it makes 527 calls. With a cache keyed on the remainder it makes 29 calls, because only the 12 remainders 0 to 11 exist. The table version fills those 12 cells directly.

Recovering the coins

Alongside fewest, keep last_coin[a], the coin that gave the current best for a. It is written exactly when fewest[a] improves. After filling, start at the target amount, append last_coin[a], subtract it and repeat until the amount reaches 0. The walk takes fewest[amount] steps.

The code

import random

INF = float("inf")


def coins_brute(coins, amount):
    calls = [0]
    def go(rest):
        calls[0] += 1
        if rest == 0:
            return 0
        best = INF
        for c in coins:
            if c <= rest:
                best = min(best, 1 + go(rest - c))
        return best
    result = go(amount)
    return (-1 if result == INF else result), calls[0]


def coins_memo(coins, amount):
    memo, calls = {}, [0]
    def go(rest):
        calls[0] += 1
        if rest == 0:
            return 0
        if rest not in memo:
            memo[rest] = min((1 + go(rest - c) for c in coins if c <= rest), default=INF)
        return memo[rest]
    result = go(amount)
    return (-1 if result == INF else result), calls[0]


def coin_change(coins, amount):
    """fewest[a] = fewest coins that sum to exactly a. Returns (count, coins used)."""
    if amount < 0 or any(c <= 0 for c in coins):
        raise ValueError("amount must be >= 0 and coins positive")
    fewest = [INF] * (amount + 1)
    last_coin = [0] * (amount + 1)
    fewest[0] = 0
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and fewest[a - c] + 1 < fewest[a]:
                fewest[a] = fewest[a - c] + 1
                last_coin[a] = c
    if fewest[amount] == INF:
        return -1, []
    used, a = [], amount
    while a > 0:
        used.append(last_coin[a])
        a -= last_coin[a]
    return fewest[amount], used


def coin_change_table(coins, amount):
    fewest = [INF] * (amount + 1)
    fewest[0] = 0
    for a in range(1, amount + 1):
        fewest[a] = min((fewest[a - c] + 1 for c in coins if c <= a), default=INF)
    return fewest


def coin_change_each_coin_once(coins, amount):
    """Same table, but amounts visited high to low: every coin can be used at most once."""
    fewest = [INF] * (amount + 1)
    fewest[0] = 0
    for c in coins:
        for a in range(amount, c - 1, -1):
            fewest[a] = min(fewest[a], fewest[a - c] + 1)
    return -1 if fewest[amount] == INF else fewest[amount]


def coin_change_zero_init(coins, amount):
    fewest = [0] * (amount + 1)               # wrong: 0 means "free", not "unreachable"
    for a in range(1, amount + 1):
        fewest[a] = min((fewest[a - c] + 1 for c in coins if c <= a), default=0)
    return fewest[amount]


coins, amount = [1, 2, 5], 11
print("filled table:", coin_change_table(coins, amount))
print("answer and coins:", coin_change(coins, amount))
print("plain recursion (answer, calls):", coins_brute(coins, amount))
print("memoized (answer, calls):", coins_memo(coins, amount))
print("impossible [2], 3:", coin_change([2], 3), "| amount 0:", coin_change([1, 2], 0))
print("zero-initialised table on [2], 3:", coin_change_zero_init([2], 3), "(should be -1)")
print("each coin once on [1, 2, 5], 11:", coin_change_each_coin_once([1, 2, 5], 11), "(unlimited gives 3)")
print("greedy takes 4+1+1 for [1, 3, 4], 6 (3 coins); DP:", coin_change([1, 3, 4], 6))
try:
    coin_change([0, 2], 4)
except ValueError as e:
    print("bad input:", e)

random.seed(9)
for _ in range(400):
    coins = random.sample(range(1, 10), random.randint(1, 4))
    amount = random.randint(0, 22)
    count, used = coin_change(coins, amount)
    assert count == coins_brute(coins, amount)[0] == coins_memo(coins, amount)[0]
    if count >= 0:
        assert len(used) == count and sum(used) == amount and set(used) <= set(coins)
print("400 random cases match brute force; recovered coins sum to the amount")

Output:

filled table: [0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 2, 3]
answer and coins: (3, [1, 5, 5])
plain recursion (answer, calls): (3, 527)
memoized (answer, calls): (3, 29)
impossible [2], 3: (-1, []) | amount 0: (0, [])
zero-initialised table on [2], 3: 1 (should be -1)
each coin once on [1, 2, 5], 11: -1 (unlimited gives 3)
greedy takes 4+1+1 for [1, 3, 4], 6 (3 coins); DP: (2, [3, 3])
bad input: amount must be >= 0 and coins positive
400 random cases match brute force; recovered coins sum to the amount

Reading the output

• The filled table for [1, 2, 5] is fewest[0..11]: for example fewest[10] = 2 (5 + 5) and fewest[11] = 3. The recovered coins [1, 5, 5] sum to 11 and there are 3 of them, matching the table. Because coins are tried in list order and only a strictly better count replaces a cell, ties keep the first coin that reached the best value.
• [2] with amount 3 returns (-1, []), and amount 0 returns (0, []).
• For [1, 3, 4] and amount 6 greedy would pay 4 + 1 + 1 (3 coins), while the DP finds 3 + 3 (2 coins).
• Direction. The shipped loops visit each amount after all smaller ones, so any coin can be reused. The coin_change_each_coin_once variant puts coins on the outside and walks the amounts downwards, so cell a - c still holds the value from before this coin was considered and the coin is used at most once. On [1, 2, 5] and amount 11 it returns -1, because 1 + 2 + 5 = 8 is the most that three single coins can make. Walking upwards in that layout instead lets a coin be reused. The same upward-versus-downward choice is the whole difference between unbounded problems (each item may be used any number of times) and 0/1 problems (each item is used zero or one times); the section on coin systems prints the rows for both on a small input.
• Non-positive coins and negative amounts raise ValueError (the driver triggers it with a coin of 0).
• The check compares the value with brute force on 400 seeded cases and verifies that the recovered coins sum to the amount, number fewest[amount] and come from the coin list.

Complexity

Here k is the number of denominations. Reconstruction adds O(fewest[amount]) time and needs the last_coin array; the value alone needs only fewest.

Which coin systems greedy handles, and the each-coin-once table

A coin system is canonical when greedy (always take the largest coin that fits) gives the fewest coins for every amount; the DP does not need that property. The program below searches amounts up to 200 for a counterexample on two systems. It then prints the table row after each coin for the each-coin-once layout (outer loop over coins, inner loop over amounts), once with the amounts walked from high to low and once from low to high, on coins [2, 3] and amount 6.

INF = float("inf")


def fewest_table(coins, amount):
    fewest = [INF] * (amount + 1)
    fewest[0] = 0
    for a in range(1, amount + 1):
        fewest[a] = min((fewest[a - c] + 1 for c in coins if c <= a), default=INF)
    return fewest


def greedy_count(coins, amount):
    count = 0
    for c in sorted(coins, reverse=True):
        count += amount // c
        amount %= c
    return count if amount == 0 else INF


def first_greedy_failure(coins, limit):
    table = fewest_table(coins, limit)
    for a in range(1, limit + 1):
        if greedy_count(coins, a) != table[a]:
            return a, greedy_count(coins, a), table[a]
    return None


print("[1, 5, 10, 25] first amount up to 200 where greedy is not optimal:", first_greedy_failure([1, 5, 10, 25], 200))
print("[1, 3, 4] first (amount, greedy coins, optimal coins):", first_greedy_failure([1, 3, 4], 200))


def show(row):
    return "[" + ", ".join("inf" if v == INF else str(v) for v in row) + "]"


def each_coin_rows(coins, amount, descending):
    fewest = [INF] * (amount + 1)
    fewest[0] = 0
    print("  start        ", show(fewest))
    for c in coins:
        for a in (range(amount, c - 1, -1) if descending else range(c, amount + 1)):
            fewest[a] = min(fewest[a], fewest[a - c] + 1)
        print(f"  after coin {c}:", show(fewest))


print("coins [2, 3], amount 6, each coin at most once (amounts high to low):")
each_coin_rows([2, 3], 6, descending=True)
print("same layout with amounts low to high (a coin can be reused):")
each_coin_rows([2, 3], 6, descending=False)

Output:

[1, 5, 10, 25] first amount up to 200 where greedy is not optimal: None
[1, 3, 4] first (amount, greedy coins, optimal coins): (6, 3, 2)
coins [2, 3], amount 6, each coin at most once (amounts high to low):
  start         [0, inf, inf, inf, inf, inf, inf]
  after coin 2: [0, inf, 1, inf, inf, inf, inf]
  after coin 3: [0, inf, 1, 1, inf, 2, inf]
same layout with amounts low to high (a coin can be reused):
  start         [0, inf, inf, inf, inf, inf, inf]
  after coin 2: [0, inf, 1, inf, 2, inf, 3]
  after coin 3: [0, inf, 1, 1, 2, 2, 2]

Read the high-to-low rows: after coin 2 only the amount 2 became reachable (cell 4 stays inf, since a second 2 is not allowed), and after coin 3 the amounts 3 and 5 appear. In the low-to-high rows the same coin 2 fills cells 2, 4 and 6 with 1, 2 and 3 coins because each cell reads the cell just updated with the same coin, which is reuse.

Common mistakes

• Initialising unreachable cells to 0 or -1, shown above.
• Using greedy without proving the coin system is canonical (greedy-optimal for every amount). The search up to 200 in the coin-systems section finds the counterexample for [1, 3, 4], but finding none for [1, 5, 10, 25] is a check on those amounts, not a proof.
• Returning fewest[amount] without mapping infinity to -1.

Running the code

python3.12 coin_change_min.py

Standard library only. Save the first listing as coin_change_min.py and run the command above; it prints exactly the output shown. The listing in the coin-systems section is a separate file, canonical_and_once.py, run the same way, and it prints the second output block.

Situation: At my previous company I owned an ML project to detect fraudulent transactions. After six months we were behind schedule: poor data quality, frequent model regressions in CI, and two failed deployment attempts had stalled momentum and morale.

Task: My goal was to re-engage the team, deliver a reliable MVP quickly, and restore sustainable velocity.

Action:

• Re-frame & reduce scope: I proposed an MVP that focused on a high-precision rule-augmented classifier for the top 3 fraud types (vs. the original 12). This cut feature engineering and labeling needs by ~60%.
• Quick wins: I implemented a lightweight baseline (XGBoost with a small feature set) and ran a 2-week benchmark. Within 5 days we had a model achieving 78% precision on the prioritized fraud types — enough to start a shadow deployment.
• Tactically re-engaged the team:
  • Reorganized work into two-week sprints with clear, small tickets (data cleaning, feature parity, CI fixes).
  • Held 15-minute daily standups and a weekly demo where the engineer who completed a task presented results.
  • Assigned rotating “owner” for production readiness (containerization, monitoring).
• Process fixes: Introduced unit tests for data transforms, CI checks to catch label drift, and a canary shadow deployment pipeline to avoid full rollouts.

Result:

• Within 6 weeks we moved from stalled to shipping a shadow deployment; after A/B testing we reduced false positives by 22% and enabled a phased rollout.
• Team velocity (story points completed/sprint) increased 2x over three sprints; bug reopen rate dropped 60%.
• Morale improved: anonymous pulse surveys showed “confidence in project” rising from 2.8 to 4.1/5, and engineers reported clearer ownership and faster feedback loops.

Learning: Breaking the problem into a narrow, high-impact MVP, showing measurable early wins, and fixing feedback loops (tests + CI + demos) are key to rebuilding momentum on ML projects.

Direct answer

An intermittent, load-correlated inference anomaly you cannot reproduce locally means the bug depends on something your local environment does not have: concurrency, batching, a specific hardware code path, or a state that only exists after real traffic patterns build up. The fix is to stop trying to reproduce it by guessing and instead build the reproduction pipeline itself: capture enough about each failing request to replay it exactly, capture the full environment so "works on my machine" stops being ambiguous, and then drive controlled load against a faithful replica until the failure shows up on demand.

Structured elaboration

Trace-id and payload logging, privacy-preserving. Propagate a unique trace identifier through every hop (ingress, feature lookup, model call, postprocessing) and log it alongside stage-level timing, host identifier, model version, and batch composition (batch size and position within the batch) at each stage. For the request payload itself, do not log raw content by default: log a fixed-length hash or fingerprint of the input, plus lightweight, non-identifying shape metadata (input length, feature-presence flags). Add a narrow, rate-limited full-payload capture (encrypted at rest, short retention, access-controlled) that only activates for a small sample or for requests matching a suspected failure signature, so you have enough real examples to replay without indiscriminately logging every user's raw input.

Environment and dependency capture. Snapshot everything that could plausibly change numeric or control-flow behavior under load: container image digest, language runtime and library versions (exact pins, not just major versions), driver and accelerator versions if applicable, and CPU or accelerator microarchitecture identifiers, since a fleet is rarely as homogeneous as the deployment config implies. Record this snapshot per-host, not once globally, because an intermittent failure correlated with load is a good candidate for "only reproduces on host type B under contention," which a single global snapshot would hide.

Deterministic seeding. Log every random seed involved in the request path: any sampling in preprocessing or postprocessing, and the framework's own random-number-generator state if inference involves any stochastic operation (dropout left on by mistake, temperature-based sampling). Record whether deterministic execution flags are enabled, since many frameworks silently pick faster, non-deterministic kernels by default under load and only guarantee bit-identical results when determinism is explicitly requested.

Traffic-replay strategy. Use the captured trace-ids and payload fingerprints to select candidate failing requests, then replay them in an isolated staging environment built from the exact environment snapshot for the host where the failure occurred. Replay both in isolation (single request, to rule out anything intrinsic to that one input) and at the observed concurrency and batch-composition pattern (to test whether it is a contention or batching artifact). If you cannot replay the literal captured payloads for privacy reasons, replay statistically-similar synthetic payloads generated to match the captured shape metadata, at the same volume and concurrency.

The feature-store variant, and the one extra thing it needs captured. If the hard-to-reproduce failures correlate with upstream feature-store changes rather than with load, the replay strategy above has a hole in it: features are fetched at serve time, so replaying a captured request re-queries the feature store and receives CURRENT values, quietly reproducing a different request than the one that failed. Close it by logging, per request, the feature-store dataset or artifact version and the point-in-time feature VALUES actually returned (hashed or bucketed where the values themselves are sensitive), not just the raw input payload, so a replay can be pinned to the same feature snapshot the failing request saw. With that captured, the suspected correlation becomes testable rather than suggestive: replay the same captured requests twice, holding the model artifact and environment snapshot fixed, once pinned to the pre-change feature-store version and once to the post-change version. If the failure appears only under the post-change version, the feature-store change is causally implicated; if it appears under both, the feature-store change was concurrent rather than causal and the real trigger is elsewhere.

Controlled load and chaos testing. Once single-request replay does not reproduce the failure, escalate to load generation that matches the production traffic shape (arrival rate distribution, batch size distribution, concurrency) against the replica, ramping toward the levels observed around the incident. Layer in targeted chaos: inject resource pressure (CPU contention, memory pressure, forced accelerator throttling), simulate degraded network conditions between services, and vary batch composition deliberately (mixing very different input shapes in one batch, since padding and batching code paths are a common source of load-only bugs). Vary one axis at a time where practical, so a reproduction tells you which axis actually matters.

Using the reproduced artifact to confirm a fix. Once you have a deterministic, scripted reproduction (a specific replay payload set, load profile, and environment snapshot that reliably triggers the failure), that reproduction becomes your regression test. Before shipping a candidate fix: run the reproduction against the unfixed code to confirm it still fails (rules out an already-stale repro), then against the fixed code to confirm it now passes, at the same load level and several times in a row to rule out you having only shifted the failure's probability rather than eliminated it. Add the reproduction as a permanent load or chaos test in the pre-production suite, so a regression is caught automatically next time rather than requiring another multi-day investigation.

Worked example

Suppose the anomaly is a fraction of inference responses under heavy load returning a prediction that looks like it was computed on the wrong batch position, and it never reproduces with a single request sent locally. Trace-id logs show the affected responses cluster at high concurrency and specifically at larger batch sizes (16 or more), never at batch size 1. Replaying single captured payloads in isolation, as expected, does not reproduce it: the bug is contingent on batching. Replaying the same payloads with load generation configured to force batch sizes of 16 and above, at the concurrency observed in the trace logs, does reproduce the wrong-batch-position symptom reliably. That localizes the bug to the batching or unbatching code path (for example, a race in how results are demultiplexed, meaning split back out of the single batched output and matched to the individual requests that made up the batch) rather than anything about a specific input's content, since content-only replay never triggered it and load-shaped replay did every time. The fix (correcting the demultiplexing logic to match results to requests by an explicit index rather than by array position under concurrent access) is then validated by running the same load-shaped replay against the fixed build for several repeated runs at the same batch size and concurrency, confirming zero wrong-position responses across all runs, before it is considered resolved.

Trade-offs and pitfalls

A common wrong turn is treating "cannot reproduce locally" as license to guess at fixes and ship them speculatively. Without a scripted reproduction, you cannot tell a real fix from a change that merely shifted the failure's timing or probability, and load-correlated bugs are exactly the kind that can appear to go away for weeks before recurring under a slightly different traffic pattern.

A second pitfall is over-logging in the name of reproducibility. Full-payload capture at scale is both a privacy liability and an operational cost (storage, and the logging itself can perturb the timing behavior you are trying to observe, sometimes called a probe effect). Keep default logging to hashes, fingerprints, and shape metadata, and reserve full capture for a narrow, rate-limited, access-controlled path triggered only when you have a specific reason to suspect a request.

A third pitfall is chaos-testing without varying one axis at a time. If you inject CPU contention, memory pressure, and an unusual batch composition simultaneously and the failure reproduces, you have not learned which of the three mattered, and the "reproduction" you hand to the team fixing it may not actually reflect the real production trigger, wasting their time chasing the wrong axis.

Direct answer

Two clean variants exist. Variant 1, in-place, O(1) extra space: a single write-pointer pass that swaps every element satisfying the predicate to the front; O(n) time, O(1) extra space, but does NOT preserve relative order within either group. Variant 2, order-preserving: build two lists (matched, unmatched) in a single pass and concatenate them; O(n) time, O(n) extra space, and DOES preserve relative order. In general, O(1) extra space and stability cannot both be had in O(n) time; achieving both simultaneously needs O(n log n) time instead, the same trade-off behind why C++'s std::stable_partition switches to a slower algorithm specifically when it cannot get extra memory.

Structured elaboration

Variant 1 mechanics (swap-based partition). Maintain a write pointer starting at 0. Scan read from 0 to n-1; whenever predicate(arr[read]) holds, swap arr[write] and arr[read], then increment write. After the scan, everything before write satisfies the predicate and everything from write onward does not, but a swap can move an unmatched element out of its original relative position among other unmatched elements (or vice versa for matched elements).

Variant 2 mechanics. A single pass builds two separate lists, matched and unmatched, in original encounter order, then concatenates them. Correctness is immediate: each list is built purely by appends in scan order, and appends never reorder elements relative to each other within their own list.

Can O(1) space and stability be achieved together? Yes, but not in O(n) time. A divide-and-conquer approach recursively stable-partitions each half of the array, then merges the two halves' now-partitioned matched and unmatched runs using an in-place rotation (rotation itself can be done with O(1) extra space via the three-reversals trick, in time proportional to the rotated range). This gives the recurrence T(n) = 2T(n/2) + O(n), which solves to O(n log n) time with O(1) extra space (or O(log n) if counting recursion-stack space). This mirrors exactly what C++'s standard library documents for std::stable_partition: O(n) swaps when extra memory is available for a temporary buffer, up to O(n log n) swaps if allocation fails and it must fall back to in-place. It is a genuine impossibility result at O(n) time: you cannot have in-place (O(1) space), stable, AND O(n) time simultaneously for a general predicate-based partition; you must give up exactly one of the three.

Worked example

def partition_inplace_unstable(arr, predicate):
    '''O(1) extra space, O(n) time. Relative order NOT guaranteed.'''
    write = 0
    for read in range(len(arr)):
        if predicate(arr[read]):
            arr[write], arr[read] = arr[read], arr[write]
            write += 1

def partition_stable(arr, predicate):
    '''O(n) extra space, O(n) time. Preserves relative order in each group.'''
    matched = [x for x in arr if predicate(x)]
    unmatched = [x for x in arr if not predicate(x)]
    return matched + unmatched

data = [1, 4, 2, 7, 3, 8, 5, 9, 6]  # pinned
is_even = lambda x: x % 2 == 0

unstable_copy = data.copy()
partition_inplace_unstable(unstable_copy, is_even)
print("input                    =", data)
print("unstable in-place result =", unstable_copy)

stable_result = partition_stable(data, is_even)
print("stable (extra space)     =", stable_result)

evens_in_order = [x for x in data if is_even(x)]
odds_in_order = [x for x in data if not is_even(x)]
print("stability check (evens):", stable_result[:len(evens_in_order)] == evens_in_order)
print("stability check (odds): ", stable_result[len(evens_in_order):] == odds_in_order)

evens_after_unstable = [x for x in unstable_copy if is_even(x)]
odds_after_unstable = [x for x in unstable_copy if not is_even(x)]
print("unstable evens order matches original order?", evens_after_unstable == evens_in_order)
print("unstable odds order matches original order? ", odds_after_unstable == odds_in_order)

Output:

input                    = [1, 4, 2, 7, 3, 8, 5, 9, 6]
unstable in-place result = [4, 2, 8, 6, 3, 1, 5, 9, 7]
stable (extra space)     = [4, 2, 8, 6, 1, 7, 3, 5, 9]
stability check (evens): True
stability check (odds):  True
unstable evens order matches original order? True
unstable odds order matches original order?  False

The stable variant preserves order for BOTH groups, as guaranteed. The unstable variant's evens [4, 2, 8, 6] happen to keep their original relative order for this particular input, but the odds group does not: it ends as [3, 1, 5, 9, 7] instead of the original relative order [1, 7, 3, 5, 9]. That asymmetry is instructive: instability is not a guarantee that EVERY group gets scrambled, it is the absence of a guarantee that ANY group stays in order, and this input concretely demonstrates the odds group breaking.

Trade-offs and pitfalls

• The three-way trade-off (space, stability, time) is the deep point of this question: claiming the swap-based partition is "basically the same as the stable one, just in place" misses that the relative-order guarantee is genuinely lost, not merely an implementation detail.
• A common bug is forgetting to swap (writing arr[write] = arr[read] instead) in the O(1)-space version, which overwrites and destroys data rather than reordering it; this only works if discarding the unmatched values is acceptable, otherwise a real swap is required.
• The O(n)-space stable variant needs no swapping subtlety at all; that simplicity is itself a valid engineering argument, plenty of real systems accept O(n) extra space for a partition specifically to keep the code obviously correct.
• Do not assume "in-place" always means "faster": the swap-based version is not asymptotically faster than the two-list version, both are O(n) time, it only saves memory, and if that memory saving is not needed, the added subtlety may not be worth it.

Direct answer

Implement the conditional imputation entirely within the training fold's own cross-validation structure, computing whatever label-dependent imputation statistic (say, a per-class median) using only the training portion of each inner split, and test correctness by constructing a synthetic case where the true imputation value is known and confirming the pipeline recovers it without ever peeking at validation labels.

Structured elaboration

import numpy as np
from sklearn.base import BaseEstimator, TransformerMixin

class LabelConditionalImputer(BaseEstimator, TransformerMixin):
    """Imputes a column using the per-class median, but the class-conditional statistic
    is learned ONLY from fit(X, y) -- never recomputed from data passed to transform."""
    def __init__(self, column):
        self.column = column

    def fit(self, X, y):
        y = np.asarray(y)
        self.class_medians_ = {}
        for c in np.unique(y):
            values = X.loc[y == c, self.column].dropna()
            self.class_medians_[c] = values.median() if len(values) else X[self.column].median()
        self.global_median_ = X[self.column].median()
        return self

    def transform(self, X, y=None):
        """y is intentionally NOT used here: at transform time (validation/test/production),
        the true label is exactly what you don't have, so imputation must fall back to a
        label-independent estimate, never the class-conditional one."""
        out = X.copy()
        mask = out[self.column].isna()
        out.loc[mask, self.column] = self.global_median_   # label-agnostic fallback, no leakage
        return out

    def fit_transform_train_only(self, X, y):
        """For TRAINING data specifically, where y is genuinely available, impute using the
        class-conditional median learned in fit -- this is the only place the label-aware
        statistic is allowed to be used for imputation itself."""
        self.fit(X, y)
        out = X.copy()
        y = np.asarray(y)
        for c, med in self.class_medians_.items():
            mask = (y == c) & out[self.column].isna()
            out.loc[mask, self.column] = med
        return out

The key correctness property: transform (used for validation, test, and production) never receives or uses y, so it structurally cannot leak label information, while fit_transform_train_only (used ONLY on the training portion, where labels are genuinely available at training time) is the sole place the class-conditional statistic is actually applied.

Worked example

A synthetic test: construct data where class 0's true median for a column is 10 and class 1's is 50, with some values in each class masked as missing; call fit_transform_train_only on the full synthetic set and confirm the imputed values for class-0 missing rows land at 10 and class-1 missing rows at 50 (recovering the known ground truth exactly); then call transform on a held-out portion with the SAME missingness pattern but WITHOUT passing y, and confirm it falls back to the single global median instead, never the class-specific ones, which is the behavior that prevents leakage.

Trade-offs and pitfalls

This asymmetry (label-aware imputation for training, label-agnostic for everything else) is a genuine trade-off, not a free win: the training data gets a systematically MORE ACCURATE imputation than validation, test, or production data ever will, which is intentional (training benefits from every available signal) but worth being explicit about, since it means the model is trained on slightly cleaner data than it will ever see again, a gap that's fine as long as it's understood, not accidentally forgotten.

Direct answer
Computing a conv layer's output size, parameter count, and multiply-add cost is three separate, mechanical formulas applied to the same input configuration, and getting each one right (especially not confusing FLOPs with MACs) matters more than any conceptual insight here.

Structured elaboration
For input spatial size $H$, padding $p$, kernel size $k$, and stride $s$: $H_{out} = \lfloor(H+2p-k)/s\rfloor+1$ (identical along width if the input is square and symmetric). Parameter count for $C_{in}$ input and $C_{out}$ output channels: $C_{out}\times C_{in}\times k\times k$ weights, plus $C_{out}$ biases if used. Multiply-add operations (MACs) for one forward pass: one MAC per output value per weight, so $H_{out}\times W_{out}\times C_{out}\times(C_{in}\times k\times k)$; FLOPs (counting a multiply AND an add as two separate operations) are conventionally reported as roughly $2\times$ this MAC count.

Worked example
For input spatial size $H=128$, padding $p=1$, kernel $k=3$, stride $s=2$, $C_{in}=64$, $C_{out}=128$: $H_{out} = \lfloor(128+2-3)/2\rfloor+1 = \lfloor63.5\rfloor+1 = 63+1=64$, so the output is $(128, 64, 64)$. Parameters: $128\times64\times3\times3 = 73{,}728$ weights plus $128$ biases, total $73{,}856$. MACs: $64\times64\times128\times(64\times3\times3) = 4{,}096\times128\times576 = 301{,}989{,}888$ (about 302 million); FLOPs (multiplies plus adds counted separately) are roughly double that, about 604 million. All three of these figures were recomputed directly in code and match exactly.

Trade-offs & pitfalls
The most common mistake is conflating MACs and FLOPs when comparing a reported number against a paper or framework profiler; some tools report MACs, others report FLOPs (2x MACs), and comparing numbers from two different conventions without checking which is which produces a spurious 2x discrepancy that looks like a bug but is purely a reporting-convention mismatch. A second common gap is forgetting that disabling the convolution's bias term (common practice when a BatchNorm layer immediately follows, since BatchNorm's own learned shift makes the conv bias redundant) removes exactly $C_{out}$ parameters, a small but real difference worth accounting for when the exact parameter count matters.

Direct answer

Make the mismatch visible the moment you see it, whether that is after the upstream team is already running behind or as soon as it surfaces during planning itself, and look first for a way to decouple your own delivery from their exact finish order, such as a stub, an adapter, or a feature flag, so you have room to negotiate re-sequencing or reduced scope instead of just waiting to see if the date slips.

Structured elaboration

Surface the mismatch immediately, not once it is a crisis

Whether you discover it because the other team is visibly behind, or because it becomes obvious during a shared planning session, name it out loud right away: here is what we committed to, here is what we now depend on, here is the gap.

Look for a decoupling option before assuming you have to slip

A mock interface, a stubbed API, or a feature flag lets your work continue against a placeholder while the real dependency finishes in parallel, with a defined swap-in point once it is ready.

Negotiate re-sequencing with a concrete ask, not just a complaint

Pointing out that another team is behind invites defensiveness. Proposing a specific way both teams can still hit their dates if two pieces are resequenced invites problem-solving instead.

Communicate consistently to everyone downstream of the decision

Use the same explanation each time: what changed, what the new plan is, and what happens if it changes again.

Set escalation triggers before you need them

Agree upfront on the specific checkpoint, a date or a milestone, at which, if the upstream work still is not ready, the issue escalates automatically to both leads, rather than waiting for the final deadline to find out.

Worked example

Base case: discovered after the upstream team is already behind. A team is building a feature on top of a platform capability, and the platform team is now behind schedule on it. Rather than waiting to see if the platform team catches up, the team builds a lightweight adapter against a mocked version of the interface, so its own work continues. They set an explicit go or no-go checkpoint a week before their real deadline: if the real dependency is not ready by then, they ship against the mock with a manual fallback, and swap in the real dependency once it lands.

Planning-time discovery variant. During a multi-team sprint-planning session, it becomes clear in the room that one team's planned start date for a shared integration depends on another team's work, which is not scheduled to finish until after the first team's own committed date, a mismatch nobody had caught before that meeting. The engineer facilitating the session, in this scenario a DevOps engineer coordinating the shared infrastructure both teams touch, flags the conflict on the spot and proposes re-sequencing right there: the first team starts against a stubbed interface while the second team's work continues in parallel, with the real dependency swapped in once ready. Right after the session, the facilitator sends a short written summary to both team leads and stakeholders using a repeatable communication template: what was found, what was agreed, and what happens if either date slips again. The summary also sets an explicit escalation trigger: if the second team's work is not ready by a named checkpoint date, it escalates automatically to both leads instead of surfacing again only at the final deadline.

Trade-offs and pitfalls

Building a decoupling layer, such as an adapter, a mock, or a flag, costs real engineering time that is wasted if the upstream team finishes on schedule after all. It is worth it when the downside of waiting and being wrong is worse than the cost of building it and not needing it, which is usually true for anything on a hard external deadline.

Escalating too early, before giving the upstream team a real chance to communicate a plan, burns trust and can look like an attempt to shift blame preemptively. Escalating too late removes any options besides slipping the date. Pre-agreed, specific escalation triggers tied to a date rather than a feeling are what keep this from being a judgment call made under pressure.

Direct answer. Big-O complexity describes how operation count scales, but wall-clock time also depends on the cost per operation, which memory access patterns change dramatically: an algorithm that touches memory unpredictably (scattered, pointer-chasing access) pays a cache-miss penalty on nearly every access, while one with sequential, predictable access mostly hits cache. With a large enough gap in per-operation cost, an asymptotically "worse" $O(N\log N)$ algorithm can beat an asymptotically "better" $O(N)$ one in practice.

Structured elaboration: building the estimate. Model each algorithm's time as (number of memory accesses per element) times (base op cost plus miss-rate-weighted miss cost):

where $a, b$ are memory accesses per element for each algorithm and $m_a, m_b$ are their respective cache-miss rates.

First, the miss rates the question suggests. Plug in $N = 10^6$, $t_{op} = 5\text{ns}$, $t_{miss} = 100\text{ns}$, $a = 3$, $b = 1$, and the two rates named in the question, 10% for the scattered linear algorithm and 1% for the sequential log-factor one:

At those rates there is no crossover at all: the linear algorithm still wins by about 2.7x. That is the first thing worth saying out loud, because it sets the bar for what "realistic conditions" has to mean. A $\log_2 10^6 \approx 19.93$ factor is a 20x handicap, and a 10% miss rate only triples the linear algorithm's per-access cost (from 5ns to 15ns). Tripling does not cover 20x.

The break-even miss rate. Solve for the $m_a$ at which the two are equal, holding $m_b = 0.01$, $a = 3$, $b = 1$:

So the linear algorithm has to miss cache on roughly 35% or more of its accesses before the log-factor algorithm catches it, given three accesses per element against one. That single number is the actual answer to "under what conditions", and it is far outside the 1%-to-10% band the question offers, which is why the crossover needs a genuinely pathological access pattern rather than a merely mediocre one.

Worked example at a rate that does cross over. Suppose the $O(N)$ algorithm is implemented with pointer-chasing (e.g. a linked structure like a chained hash table with poor locality), needing $a = 3$ memory accesses per element at a high $m_a = 0.95$ miss rate (scattered heap allocations rarely share a cache line, so almost every access is a fresh line):

Meanwhile the $O(N\log N)$ algorithm is a comparison-based sort over a contiguous array (e.g. mergesort), doing $\log_2(10^6) \approx 19.93$ comparisons per element with $b = 1$ access per comparison and a low $m_b = 0.01$ miss rate (sequential scans prefetch well):

Under these assumptions the $O(N\log N)$ algorithm (about 120 ms) beats the $O(N)$ algorithm (about 300 ms) by roughly 2.5x, purely because its per-access cost is so much lower. Note that $m_a = 0.95$ is well past the 0.35 break-even derived above, which is the point: the crossover exists, but it lives in the pathological corner of the parameter space, not in the ordinary one.

Trade-offs & pitfalls: the realistic conditions for this crossover. This happens specifically when the $O(N)$ algorithm's constant factor combines a higher access count per element AND a much higher miss rate than the $O(N\log N)$ alternative, typically because the linear algorithm relies on scattered, pointer-heavy structures (hash tables with chaining, trees with heap-allocated nodes) while the log-factor algorithm operates on contiguous, cache-friendly memory. The crossover shrinks or disappears if the $O(N)$ algorithm is instead implemented cache-consciously (e.g. open-addressing with a compact array, low load factor, few probes), which is exactly why "asymptotically better" implementations still lose to careful engineering of the "asymptotically worse" one only under specific memory-layout conditions, not as a general rule.

Two limits of the model are worth stating when you present it. First, it charges the full $t_{miss}$ for every miss, which overstates the cost of the sequential algorithm: a prefetcher and multiple outstanding misses overlap latency, so a stream of predictable misses costs far less than their sum. That bias makes the model conservative in favour of the linear algorithm, so a crossover the model predicts is more likely to be real than one it rules out. Second, the break-even $m_a \approx 0.35$ moves with $a$ and $b$: at $a = 1$ instead of 3, the required rate exceeds 100% and no crossover is possible at these constants at all, so the access count per element matters as much as the miss rate does.