Amazon Data Scientist Interview Preparation Guide - Junior Level (1-2 Years)

1. Clarify goals & constraints

• Confirm SLA targets (latency/throughput/error rates), time horizon for 30% reduction, excluded services, and stakeholder priorities (risk tolerance, features to preserve).

2. Inventory & telemetry

• Catalog pipelines, models, infra (compute type, region, storage, infra-as-code). Pull cost by resource, job, and model using cloud billing + tags + job metadata for last 3–6 months.
• Gather performance metrics: inference latency, batch job runtime, accuracy/ROC, data freshness, error rates.

3. Identify candidate savings (prioritization matrix)

• Rank opportunities by cost impact × low-risk feasibility:
  • Idle/overprovisioned VMs, oversized instances, long-running dev jobs
  • Low-usage or duplicate models, ensembles with marginal gains
  • High-frequency pipelines with redundant feature transforms
  • Expensive feature stores or very high retention storage
• Flag candidates with estimated % cost and expected SLA/accuracy impact.

4. Estimate gains quantitatively

• For each candidate, simulate alternatives: right-size instances using historical CPU/GPU utilization; estimate cost = hours × new price. For model simplification, run A/B on holdout to measure accuracy delta and predicted cost per prediction.
• Produce conservative, likely, and optimistic savings scenarios.

5. Pilot safely (staged experiments)

• Create experiment plan: small percentage traffic (5–10%), clear success criteria (SLA, accuracy delta ≤ threshold), instrumentation, and rollback triggers.
• Use feature flags, canary deployments, autoscaling policies, spot instances with fallback, and separate dev/staging pipelines.
• Run pilots for statistically significant windows (e.g., sample size to detect <0.5% accuracy change at 95% CI).

6. Monitor & validate

• Monitor cost metrics, SLA, business KPIs in real time and aggregated. Use alerts for threshold breaches.
• Validate that observed savings match estimates; capture regressions.

7. Rollout & governance

• Gradual rollout with runbook and rollback plan. Bake changes into CI/CD and IaC.
• Document decisions, update cost allocation tags, set budget alerts, and implement FinOps cadence: weekly reviews for first month, monthly thereafter.

8. Measure and report

• Use baseline vs. post-change comparison (same seasonality window), normalize for data volume and traffic.
• Report: absolute $ saved, % reduction vs baseline, SLA adherence, model performance delta, and confidence intervals.
• Recommend next wave of optimizations and institutionalize monitoring and cost-aware model evaluations in model lifecycle.

This approach balances measurable cost reduction with controlled risk to SLAs using data-driven prioritization, conservative estimates, safe pilots, and continuous monitoring.

Direct answer
Early stopping halts training once a monitored validation metric stops improving for a set number of epochs (the patience), keeping the weights from the best epoch rather than the last one; it acts as a regularizer by preventing the model from continuing to fit training-set-specific noise past the point where that stops helping generalization.

Structured elaboration
Which metric to monitor should match what you actually care about: validation loss is the most common and most sensitive choice (it reacts to confidence, not just correctness), but if your real goal is a business metric (say, F1 on a rare positive class, or a calibration measure), monitoring that directly is more honest than optimizing loss and hoping the business metric follows along.
Setting patience is a trade-off: too small and you stop on ordinary epoch-to-epoch noise before genuine improvement has a chance to continue; too large and you waste compute training well past the useful point (though you'll still recover the best weights, so the main cost of large patience is wasted compute, not a worse model). A reasonable starting point is patience in the range of 5-15% of your expected total training epochs, tightened or loosened based on how noisy your validation curve looks in practice.
Across model families: for gradient boosting (XGBoost, LightGBM), early stopping means stopping the addition of new trees once validation performance stops improving, this is a direct, cheap, built-in mechanism. For neural networks, it means stopping the gradient-descent training loop, and typically also requires explicitly tracking and restoring the best-epoch weights, since training doesn't naturally "keep" an earlier checkpoint the way boosting naturally keeps earlier trees.

Worked example
A gradient-boosted model validated every 10 trees with patience=5 (50 trees of no improvement) might stop at tree 240 out of a 1000-tree budget, having found its true optimum around tree 200; refitting for exactly 200-240 trees on the full dataset (including what was held out for early-stopping validation) is the typical production step.

Trade-offs & pitfalls
Setting patience based on epoch COUNT alone ignores that different models take very different numbers of epochs to reach their optimum; it's often more robust to set patience as a fraction of expected total training length, or to look at the actual noise level of your validation curve rather than picking a fixed number out of habit.

Direct answer

For a first applied-ML task like duplicate detection, the smallest vertical slice is a simple similarity-based baseline running end to end, deployed even in a limited form, rather than a sophisticated model built in isolation before anything touches production.

Structured elaboration

1. Data and labeling sources. Look for existing signal first: are there user-reported duplicates, support tickets, or manual moderation logs that already contain implicit labels, before investing in a fresh labeling effort.
2. Baseline model choice. Start with a simple similarity measure (comparing text or key fields directly) rather than a learned embedding model; it's fast to build, easy to reason about, and gives you a real floor to compare anything fancier against later.
3. Evaluation metrics. Precision and recall against whatever labeled examples you have, even if the set is small; being explicit that the evaluation is preliminary given limited data is more honest than presenting early numbers as final.
4. Deployment approach. Even a limited deployment (flagging likely duplicates for human review rather than auto-merging them) gets the system into a real workflow immediately, which teaches you more about real-world edge cases than any amount of additional offline development would.

Worked example

A first version comparing exact or near-exact text matches, deployed as a suggestion to a moderator rather than an automatic action, delivers real value from day one and surfaces the actual hard cases (near-duplicates with meaningful differences, legitimately similar but distinct items) that inform what a more sophisticated learned model should focus on next, rather than guessing at the hard cases in advance.

Trade-offs and pitfalls

The common mistake for someone new to applied ML is spending too much time trying to build a sophisticated model before anything is deployed, missing the chance to learn from real usage early. The other risk is deploying an unreviewed automatic action (auto-merging) before the baseline has proven itself, which can cause real damage if the simple similarity measure has more false positives than expected.

Direct answer

The soft-margin SVM dual is derived by Lagrangianizing the primal (which has a margin objective plus slack penalties), applying stationarity conditions to eliminate the primal variables, and arriving at a quadratic program over dual multipliers $\alpha_i$ bounded between 0 and $C$. The KKT complementary-slackness conditions say a point is a support vector (has $\alpha_i > 0$) exactly when it lies on or inside the margin, and SMO solves the resulting QP efficiently by optimizing just two $\alpha_i$ at a time, the smallest update that can respect the dual's equality constraint.

Structured elaboration

Before the algebra, a quick plain-language on-ramp for the four terms this derivation leans on: a primal problem is the original optimization, here minimizing directly over the actual model parameters $w, b, \xi$ subject to constraints. Its dual is an equivalent reformulation that introduces one multiplier per constraint and optimizes over those multipliers instead, useful whenever the dual is easier to solve or reveals extra structure (here, the kernel trick). The Lagrangian is the tool used to build that dual: it folds every constraint into the objective, each weighted by a non-negative multiplier, so that respecting the constraint and optimizing the objective become one combined problem. Stationarity just means the ordinary first-order condition, setting partial derivatives to zero, applied to the Lagrangian's primal variables to eliminate them. KKT (Karush-Kuhn-Tucker) complementary slackness is the extra condition that shows up specifically because of inequality constraints: at the true optimum, for each constraint, either the constraint is exactly tight or its multiplier is exactly zero, never both loose at once, and that pairing is what lets us classify each point's role below.

Primal. The soft-margin SVM with slack variables $\xi_i \ge 0$:

Lagrangian. Introduce multipliers $\alpha_i \ge 0$ for the margin constraints and $\mu_i \ge 0$ for the slack non-negativity constraints:

Stationarity (deriving the dual). Setting the gradient of $\mathcal{L}$ with respect to each primal variable to zero:

Substituting these back into $\mathcal{L}$ eliminates $w$, $b$, and $\xi$ entirely (the $\xi_i$ terms cancel using $\alpha_i + \mu_i = C$), leaving an objective purely in terms of $\alpha$. The resulting dual, using $\mu_i \ge 0$ together with $\alpha_i + \mu_i = C$ to derive the box constraint $0 \le \alpha_i \le C$:

What KKT complementary slackness says about support vectors. The two complementary-slackness conditions are $\alpha_i\left[y_i(w^\top x_i+b)-1+\xi_i\right]=0$ and $\mu_i \xi_i = (C-\alpha_i)\xi_i = 0$. Reading these together, for each point $i$:

• If $\alpha_i = 0$: the point is not a support vector; it lies strictly outside the margin ($y_i(w^\top x_i+b) > 1$) and contributes nothing to $w$.
• If $0 < \alpha_i < C$: from $(C-\alpha_i)\xi_i=0$ with $\alpha_i \ne C$, this forces $\xi_i=0$, and then the first condition forces $y_i(w^\top x_i+b)=1$ exactly: the point sits exactly on the margin boundary. These are the "free" support vectors, used to solve for $b$.
• If $\alpha_i = C$: the point can have $\xi_i > 0$, meaning it's inside the margin or misclassified; these are the "bound" support vectors.

So the support vectors, points with $\alpha_i > 0$, are exactly the points on or inside the margin; everything strictly outside the margin has $\alpha_i=0$ and is discarded from the decision function, which only needs $w = \sum_i \alpha_i y_i x_i$ (a sum over support vectors only).

Kernel trick. The dual depends on the data only through inner products $x_i^\top x_j$, so replacing this with a kernel $K(x_i, x_j) = \phi(x_i)^\top \phi(x_j)$ lets the model learn a non-linear boundary in the implicit feature space $\phi$ without ever computing $\phi(x)$ explicitly.

How SMO solves the QP efficiently. The dual's equality constraint $\sum_i \alpha_i y_i = 0$ means you can't update a single $\alpha_i$ in isolation while holding the rest fixed, that would generally break the constraint. SMO's insight is that the smallest feasible update touches exactly two multipliers at once: fix all $\alpha_k$ for $k \ne i,j$, and the constraint reduces to a single linear relationship between $\alpha_i$ and $\alpha_j$, which turns their joint subproblem into a 1-D quadratic that has a closed-form solution (clipped to stay inside $[0,C]$ and the linear constraint). Repeating this pairwise update, chosen using the KKT violations to pick which pair to update next, converges to the global optimum since the dual is a convex QP, without ever needing to solve the full $n$-variable QP or store the full $n \times n$ kernel matrix at once.

Worked example

Take a 1-D toy problem with decision function already fit to $f(x) = x$ (so $w=1$, $b=0$, a linear kernel) and four labeled points. The support-vector classification rule from the KKT analysis above is: compute the functional margin $y_i f(x_i)$ for each point, then classify it as non-SV if the margin exceeds 1, a free SV if the margin equals exactly 1, and a bound SV (with slack $\xi_i = 1 - y_if(x_i) > 0$) if the margin is below 1.

Only the middle two points, $x=1$ and $x=-0.5$, have $\alpha_i>0$ and enter the sum $w=\sum_i \alpha_i y_i x_i$; the other two ($x=2$, $x=-2$) are discarded entirely from the decision function even though they were part of the training set, which is the concrete mechanism behind the earlier claim that the SVM decision function only needs the support vectors, not all $n$ training points.

Trade-offs and pitfalls

• The KKT-based support vector characterization is exact only at the true optimum; during SMO iterations before convergence, the current $\alpha_i$ values are provisional and shouldn't be interpreted as final support-vector status.
• A common wrong turn is treating every training point as contributing to the model; in the dual view, only points with $\alpha_i > 0$ matter for prediction, which is both the source of SVM's sparsity in the number of "active" points and a reason predictions can be fast even with a large training set, as long as the support vector count stays small relative to $n$.
• The dual formulation depends on the data only through pairwise inner products or kernel evaluations, which is a feature (enables the kernel trick) but also the source of the $O(n^2)$ memory and $O(n^2)$-to-$O(n^3)$ training cost that makes kernel SVMs impractical on very large $n$; SMO reduces the per-step cost but doesn't change this fundamental scaling with the number of training points.
• Choosing which pair of multipliers to update at each SMO step (via the KKT violation heuristic) is what makes practical implementations fast; a naive fixed or random pairing would converge far more slowly in practice, even though any valid sequence of feasible pairwise updates converges eventually for a convex QP.

Direct answer. Frame it in terms they already care about (report speed, or the cost of the current slow experience), name the concrete cost honestly (the write-latency or storage number, not a vague "some overhead"), and commit to a specific way you'll confirm afterward that it actually delivered the promised benefit.

Structured elaboration. Lead with the business-visible symptom and its fix, not the technical mechanism: "this report currently takes X seconds and blocks people from Y; this change gets it to Z seconds" lands better than opening with index internals. State the cost in the same concrete terms: a specific percentage increase in write latency, or a specific amount of additional storage, rather than a hedge like "a little overhead," since a specific number is both more honest and more persuasive precisely because it shows you've actually measured it rather than guessing. Explain briefly WHY the cost exists (every write now has to update this extra structure too) so the trade-off feels like a reasoned decision rather than a black box. Close with how you'll verify the benefit actually materialized after shipping, a specific metric you'll check and a specific timeframe, so the stakeholder isn't just taking your word for it.

Worked example. "Right now this report takes the better part of a minute to load, and three people have told me they've stopped using it because of that. Adding this index gets it to load near-instantly, based on my testing. The cost is a roughly 10% increase in write latency for this specific table, workload testing suggests that stays well within our current write-latency budget, and I'll check actual production write latency and report load time again a week after we ship, to confirm both numbers hold up outside of my test environment, not just in it."

Trade-offs and pitfalls. Resist the urge to round the cost down or bury it in technical language to make the ask easier to approve; a stakeholder who later discovers an unmentioned cost, even a small one, loses trust in every future recommendation you bring them, which is a much larger cost than the discomfort of stating the trade-off plainly up front.

Direct answer

Implement the group-median fill as a straightforward groupby-and-fillna operation, but be deliberate about two edge cases: rows whose group itself is missing, which should be left untouched rather than guessed at, and groups that have no valid (non-missing) values at all, which fall back to the overall dataset median rather than propagating a missing value forward.

Structured elaboration

import pandas as pd
import numpy as np

def impute_group_median(df, group_col, target_col):
    """Fill missing target_col values with the median computed within each group_col group.
    Rows with a missing group_col are left untouched. Groups with no valid target_col values
    fall back to the global median."""
    out = df.copy()
    global_median = out[target_col].median()
    group_medians = out.groupby(group_col)[target_col].median()   # NaN for groups with no valid values
    group_medians = group_medians.fillna(global_median)

    has_group = out[group_col].notna()
    is_missing_target = out[target_col].isna()
    fill_mask = has_group & is_missing_target

    out.loc[fill_mask, target_col] = out.loc[fill_mask, group_col].map(group_medians)
    return out

df = pd.DataFrame({
    "region": ["west", "west", "east", "east", None, "north"],
    "income": [50000, np.nan, 60000, np.nan, np.nan, np.nan],
})
result = impute_group_median(df, "region", "income")
print(result)

Edge cases and complexity: a row with a missing region (the group column itself) is explicitly excluded from filling via the has_group mask, since there's no group to compute a median FROM for it, imputing it with the global median instead would be a reasonable alternative design choice, but silently leaving it missing (as written) makes the caller decide explicitly rather than the function guessing; a group with EVERY value missing (like "north" in the example, a single row with no other members to compute a median from) has an undefined group median, which fillna(global_median) on the group_medians Series resolves to the dataset-wide fallback rather than leaving it NaN.

Worked example

Running the code above: "west"'s missing income fills with west's own median (50,000, since only one valid value exists in that group); "east"'s missing income fills with east's median (60,000); "north"'s single missing value, with no other north rows to compute from, falls back to the global median across all valid incomes (55,000); the row with a missing region is left with income still NaN, untouched by design.

Trade-offs and pitfalls

Complexity is $O(n)$ for the groupby-and-map operations (dominated by a single pass to compute group medians and a single pass to apply them), scaling well; the real design decision worth flagging explicitly to whoever calls this function is the choice to LEAVE missing-group rows untouched rather than silently falling back to the global median for them too, a defensible but non-obvious choice that should be documented, not left implicit.

Difference 1 — NULL-safe equality (handling NULLs in join keys)
Problem: Some dialects treat NULL != NULL; Postgres has IS NOT DISTINCT FROM, MySQL has the NULL-safe <=> operator, Snowflake/BigQuery lack these exact operators.

Portable pattern (works everywhere): explicit NULL-aware comparison
SELECT t1., t2.
FROM t1
JOIN t2
ON (t1.key = t2.key OR (t1.key IS NULL AND t2.key IS NULL));

Notes per DB:

• Postgres: you can instead write ON t1.key IS NOT DISTINCT FROM t2.key (more concise).
• MySQL: you can use ON t1.key <=> t2.key.
• BigQuery / Snowflake: use the portable OR pattern above (or COALESCE with sentinel only if you can guarantee sentinel not present).

Why: explicit boolean condition is standard SQL and avoids dialect-specific operators.

Difference 2 — LATERAL / APPLY (joining to a subquery or table-valued function per row)
Problem: Postgres uses LATERAL, SQL Server uses CROSS/OUTER APPLY, Snowflake supports LATERAL, BigQuery doesn't have APPLY but supports UNNEST/ARRAY subqueries.

Goal: get most recent order per user (top-1 per user) via per-row subquery.

Portable approach using window functions (recommended when portability matters):
SELECT user_id, order_id, order_ts
FROM (
SELECT u.user_id, o.order_id, o.order_ts,
ROW_NUMBER() OVER (PARTITION BY u.user_id ORDER BY o.order_ts DESC) rn
FROM users u
JOIN orders o ON o.user_id = u.user_id
) t
WHERE rn = 1;

Dialect-specific lateral form (when you need a table function per row and window is not an option):

• Postgres:
  FROM users u
  LEFT JOIN LATERAL (
  SELECT * FROM orders o WHERE o.user_id = u.user_id ORDER BY order_ts DESC LIMIT 1
  ) o ON true;
• SQL Server:
  OUTER APPLY (
  SELECT TOP (1) * FROM orders o WHERE o.user_id = u.user_id ORDER BY order_ts DESC
  ) o
• BigQuery:
  LEFT JOIN (
  SELECT AS STRUCT * FROM UNNEST(
  ARRAY(
  SELECT AS STRUCT o.* FROM orders o WHERE o.user_id = users.user_id ORDER BY order_ts DESC LIMIT 1
  )
  )
  ) o ON TRUE
• Snowflake:
  LEFT JOIN LATERAL (
  SELECT * FROM orders o WHERE o.user_id = users.user_id ORDER BY order_ts DESC LIMIT 1
  ) o ON TRUE;

Recommendation: prefer window-function solution for portability and performance. Use lateral/apply only when invoking table-valued functions or when LIMIT per-group is more natural and your target DB supports it.

Direct answer
A decision genuinely reflects a stated value, rather than merely being compatible with it, when the value actually changed what you chose to do, not just how you described it afterward. The strongest answers make that causal link explicit: what you would have done differently if the value hadn't been a factor.

Structured elaboration

• Situation and task: the decision point, described briefly.
• The counterfactual test: name what the default, easier choice would have been, and what specifically made you choose differently.
• Action: what you actually did, including who you had to convince or coordinate with.
• Result: the outcome, and ideally a signal that the choice was validated rather than merely feeling principled at the time.

Worked example
Faced with a choice between shipping a quick, directionally useful analysis in time for a decision meeting, or spending an additional two weeks on a more rigorous version, the default and professionally "safer" choice would have been to wait for rigor. Choosing to ship the quicker, clearly caveated version instead, because the business decision had a hard deadline and a rigorous-but-late analysis would have been useless, shows a genuine trade-off rather than a reflexive one. The decision was validated when the more rigorous follow-up analysis, completed afterward, confirmed the same direction, meaning the faster call hadn't cost the business a wrong decision.

Trade-offs and pitfalls
A story where the value and the easy choice happen to be the same thing doesn't actually demonstrate anything, since no real trade-off was made; choose a story with genuine tension in it. Naming the value first and building a story to fit it, rather than the reverse, tends to produce something that sounds rationalized rather than genuine; a genuinely reflective answer usually names the counterfactual without being asked. A result stated only as "and it felt right" is weaker than any concrete validation signal, even an imperfect one.

Direct answer

Append is $O(1)$ amortized (amortized meaning the average cost per operation across a whole sequence of operations, not the cost of any single call) because the expensive $O(n)$ resize-and-copy step happens rarely, and its cost can be spread over the many cheap $O(1)$ appends that occur between resizes. Summed over any sequence of $n$ appends, the total work stays proportional to $n$, so the average cost per append is a constant. That guarantee depends specifically on doubling (or any fixed multiplicative growth factor); if capacity instead grew by a fixed additive amount each time, resizes become frequent enough that total copying work grows like $O(n^2)$, which makes the amortized cost per append $O(n)$ instead of $O(1)$.

Structured elaboration

Proof sketch for doubling ($\alpha = 2$)

Start empty and perform $n$ appends. Each append either writes into a free slot (cost 1) or triggers a resize that copies the current $m$ elements before writing. Because capacity doubles, the sizes copied across all resizes form the series $1, 2, 4, 8, \ldots$ up to just under $n$:

$1 + 2 + 4 + \cdots + 2^{k} < 2n$

So total cost across all $n$ appends is at most $n$ (the simple writes) plus $2n$ (the copying), giving:

$\text{amortized cost} \le \frac{n + 2n}{n} = 3 = O(1)$

For a general multiplicative factor $\alpha > 1$, the copied sizes form a geometric series bounded by $\frac{\alpha}{\alpha - 1} \cdot n$, so the amortized constant is roughly $1 + \frac{\alpha}{\alpha-1}$: about 3 for $\alpha=2$, about 4 for $\alpha=1.5$, and growing without bound as $\alpha \to 1^+$.

What breaks with fixed additive growth

If capacity instead grows by a fixed amount $c$ each time (not multiplied), resizes happen roughly every $c$ appends, and the $k$-th resize copies about $kc$ existing elements. Summed over $n/c$ resizes:

$\begin{aligned} \text{total copy cost} &= \sum_{k=1}^{n/c} k c \\ &= c \cdot \frac{(n/c)(n/c + 1)}{2} \\ &\approx \frac{n^2}{2c} \end{aligned}$

Total work across $n$ appends is now $O(n^2)$, so the amortized cost per append is $O(n^2) / n = O(n)$: linear per operation on average, not constant. Additive growth trades away the amortized guarantee entirely; it doesn't just make the constant worse, it changes the complexity class.

Reference point (not a claim about your specific runtime, just why factors below 2 are common): production dynamic-array implementations often deliberately avoid a factor-2 growth to reduce peak wasted memory, accepting a larger amortized constant in exchange (for example, growth factors noticeably below 2 are common in real-world implementations). The trade-off is always time (fewer resizes) versus space (less transient waste).

Worked example

Running the doubling and fixed-increment growth strategies and tracking total bytes copied per element appended (all inputs pinned, no timing claims, just operation counts):

def total_copy_cost_doubling(n: int) -> tuple[int, int]:
    """Simulates n appends into a dynamic array that doubles capacity
    on overflow. Returns (total elements copied across all resizes,
    number of resizes)."""
    cap = 1
    size = 0
    total_copy = 0
    resizes = 0
    for _ in range(n):
        if size == cap:
            total_copy += cap  # copy every existing element
            cap *= 2
            resizes += 1
        size += 1
    return total_copy, resizes


def total_copy_cost_additive(n: int, c: int) -> tuple[int, int]:
    """Same simulation, but capacity grows by a fixed amount c each
    time instead of doubling."""
    cap = 0
    size = 0
    total_copy = 0
    resizes = 0
    for _ in range(n):
        if size == cap:
            total_copy += cap
            cap += c
            resizes += 1
        size += 1
    return total_copy, resizes


if __name__ == "__main__":
    print("doubling: n -> total_copy, copy/n")
    for n in (1_000, 10_000, 100_000, 1_000_000):
        total_copy, _ = total_copy_cost_doubling(n)
        print(n, total_copy, round(total_copy / n, 3))

    print("additive (c=8): n -> total_copy, copy/n")
    for n in (1_000, 2_000, 4_000):
        total_copy, _ = total_copy_cost_additive(n, c=8)
        print(n, total_copy, round(total_copy / n, 3))

Running this prints:

doubling: n -> total_copy, copy/n
1000 1023 1.023
10000 16383 1.638
100000 131071 1.311
1000000 1048575 1.049

additive (c=8): n -> total_copy, copy/n
1000 62000 62.0
2000 249000 124.5
4000 998000 249.5

The doubling column stays in a narrow band (roughly 1 to 1.6) no matter how large $n$ gets, which is the empirical signature of $O(1)$ amortized cost. The additive column roughly doubles every time $n$ doubles, which is the empirical signature of the amortized cost growing linearly with $n$, i.e., $O(n)$ per append on average.

Trade-offs & pitfalls

• A larger growth factor means fewer resizes and a lower amortized constant, but more wasted memory sitting unused right after a resize (up to nearly half the array, for doubling).
• A growth factor close to 1 keeps memory tight but causes frequent resizes and a larger amortized constant; taken to the extreme (fixed additive growth), it loses the $O(1)$ guarantee altogether.
• Amortized $O(1)$ is a statement about the long-run average, not a promise that every individual call is fast: a single append can still legitimately cost $O(n)$ when it happens to trigger the resize. That distinction matters in a hot loop with a strict per-call latency budget, where an occasional $O(n)$ spike may be unacceptable even though the average is fine.
• Shrinking on removal needs the same care: if you shrink back to exactly the current size whenever the array isn't full, an alternating pattern of append-then-remove near that boundary can trigger a resize on almost every operation (grow/shrink thrashing). The standard fix is asymmetric thresholds, for example only shrinking once usage drops to a quarter of capacity, and halving (not shrinking all the way to fit) when it does.

Approach: Binary search over the SMALLER array's partition point (not over the values themselves) to find a split of both arrays such that everything on the left of the combined split is <= everything on the right, and the split sizes are balanced. This gives O(log(min(n, n))) = O(log n) time, dramatically better than the obvious O(n) merge-and-index approach.

def find_median_sorted(a, b):
    if len(a) > len(b):
        a, b = b, a  # ensure a is the shorter array
    n, m = len(a), len(b)
    lo, hi = 0, n
    half = (n + m + 1) // 2
    while lo <= hi:
        i = (lo + hi) // 2       # partition point in a
        j = half - i             # partition point in b
        a_left = a[i - 1] if i > 0 else float('-inf')
        a_right = a[i] if i < n else float('inf')
        b_left = b[j - 1] if j > 0 else float('-inf')
        b_right = b[j] if j < m else float('inf')
        if a_left <= b_right and b_left <= a_right:
            if (n + m) % 2 == 1:
                return max(a_left, b_left)
            return (max(a_left, b_left) + min(a_right, b_right)) / 2
        elif a_left > b_right:
            hi = i - 1
        else:
            lo = i + 1
    raise ValueError("input arrays not sorted")

Key points: A valid partition splits the combined 2n elements into a left half and right half of (near-)equal size, such that every element in the left half is <= every element in the right half. Because both a and b are individually sorted, once you fix a partition index i in a, the corresponding partition index j in b is DETERMINED (j = half - i) - so binary search only needs to search over i, not both indices independently, which is what collapses the search to O(log n).

Complexity: O(log(min(n, m))) time (binary searching over the shorter array), O(1) extra space.

Edge cases: one array empty (partition trivially puts everything from the other array on the appropriate side); arrays of very different lengths (handled by always binary-searching the shorter one, keeping the search space small); combined odd vs even total length (changes whether the median is a single middle value or an average of two).

Worked example / execution verification

tests = [
    ([1, 3], [2], 2.0),
    ([1, 2], [3, 4], 2.5),
    ([0, 0], [0, 0], 0.0),
    ([], [1], 1.0),
    ([1, 3, 5, 7, 9], [2, 4, 6, 8, 10, 12], 6.0),
]
for a, b, expected in tests:
    got = find_median_sorted(a, b)
    print(a, b, "->", got, "expected", expected, "OK" if got == expected else "MISMATCH")

Executed: all five test cases pass, including a hand-checkable case ([1,3,5,7,9] merged with [2,4,6,8,10,12] gives the sorted sequence [1,2,3,4,5,6,7,8,9,10,12]... wait, that's 11 elements from lengths 5+6=11, an odd total, so the median is the 6th element; the combined sorted array is [1,2,3,4,5,6,7,8,9,10,12], whose middle (6th of 11) element is 6 - matching the function's returned 6.0).

Trade-offs & pitfalls

• The naive O(n) merge-and-index approach is simpler to implement correctly and is perfectly fine unless the O(log n) bound is specifically required (this is a classic "know the better bound exists and can derive it" interview question, not necessarily a "always use this in production" recommendation - the O(n) version is more readable and the constant-factor difference rarely matters at realistic array sizes).
• The partition-based binary search is notoriously easy to get subtly wrong (off-by-one on partition boundaries, forgetting the +/-infinity sentinels for out-of-range partitions) - the sentinel values for empty-partition edges are what make the boundary conditions uniform and are worth deriving explicitly rather than memorizing.
• This generalizes to finding the k-th smallest element across two sorted arrays (not just the median) with the same O(log(min(n,m))) technique, adjusting the target partition size from half to the desired k.