Meta Machine Learning Engineer (Staff Level) Interview Preparation Guide

Model calibration measures how well predicted probabilities match observed frequencies: a perfectly calibrated classifier that outputs 0.8 should be correct ≈80% of the time.

Evaluate:

• Reliability diagram (calibration curve): bin predicted probabilities (e.g., 10 bins), plot mean predicted vs empirical accuracy per bin — deviations show miscalibration (over/under-confidence).
• Expected Calibration Error (ECE): weighted average |accuracy_bin − confidence_bin| across bins; low ECE → better calibration. Report Brier score as complementary.

Correct (post-training techniques):

• Temperature scaling: simple parametric rescaling for neural nets; learn single scalar T on a held-out calibration set to minimize NLL. Preserves rank ordering and AUC.
• Platt scaling: logistic regression on model logits/probabilities (two parameters), good for SVMs or small models.
• Isotonic regression: non-parametric monotonic mapping for more flexible corrections (needs more data, risk of overfitting).

Operational implications:

• Always fit calibration on a held-out validation/calibration set representative of production data. Calibration changes predicted probabilities but not class ordering; downstream decision thresholds, SLAs, and business rules depending on raw scores must be reviewed.
• Latency/throughput: temperature or Platt scaling is cheap at inference; isotonic lookup is slightly heavier but acceptable. Log and version calibrator with model versioning for audits and reproducibility.

Monitor calibration drift:

• Continuously compute ECE/Brier and per-bin reliability on recent production samples (store true labels when available). Alert when ECE crosses threshold or curves shift.
• Run periodic recalibration (daily/weekly) or triggered retrain when drift detected. Use anchor sampling to ensure calibration set represents current distribution.
• Instrument upstream changes (feature drift, label distribution shift) since they often cause miscalibration.

Summary: evaluate with reliability diagrams and ECE, correct with temperature/Platt/isotonic using a held-out calibration set, consider downstream impacts, and monitor calibration drift with automated metrics and retraining/recalibration triggers.

BERTScore and MoverScore use contextual embeddings to measure semantic similarity beyond surface n-gram overlap.

How they’re computed

• BERTScore: obtain token embeddings for reference and candidate from a pretrained transformer (e.g., BERT). Compute pairwise cosine similarities. For each reference token, take maximum similarity to any candidate token (recall); for each candidate token, take max similarity to any reference token (precision). Aggregate (usually F1 = 2PR/(P+R)). Optionally weight tokens by IDF.
• MoverScore: uses contextual embeddings + Earth Mover’s Distance (Wasserstein distance). Treat tokens as weighted “mass” (often weighted by IDF); compute minimal cost to transport candidate token mass to reference token mass, cost = 1 - cosine(similarity). Lower cost = better; invert/normalize to a score.

Worked example (BERTScore max-matching, illustrative cosine values). Reference: "A cat was sitting" (tokens A, cat, was, sitting). Candidate: "The cat sat" (tokens The, cat, sat). Suppose the embedding model gives these pairwise cosine similarities: sim(A,The)=0.75, sim(A,cat)=0.20, sim(A,sat)=0.15; sim(cat,The)=0.20, sim(cat,cat)=0.98, sim(cat,sat)=0.30; sim(was,The)=0.25, sim(was,cat)=0.15, sim(was,sat)=0.55; sim(sitting,The)=0.10, sim(sitting,cat)=0.25, sim(sitting,sat)=0.71. Recall takes, for each REFERENCE token, its max similarity to any candidate token: A→0.75 (The), cat→0.98 (cat), was→0.55 (sat), sitting→0.71 (sat); recall = (0.75+0.98+0.55+0.71)/4 = 0.7475. Precision takes, for each CANDIDATE token, its max similarity to any reference token: The→0.75 (A), cat→0.98 (cat), sat→0.71 (sitting); precision = (0.75+0.98+0.71)/3 = 0.8133. F1 = 2PR/(P+R) = 2(0.8133)(0.7475)/(0.8133+0.7475) ≈ 0.779. Notice "sat" matches best to "sitting" (0.71) even though they share no characters, which is exactly the semantic-similarity behavior n-gram overlap metrics like BLEU would miss entirely.

Strengths

• Capture paraphrase/semantic equivalence, synonyms, and contextual nuance missed by BLEU/ROUGE.
• Token-level matching allows partial credit; IDF weighting emphasizes content words.
• Robust across domains with quality embeddings.

Common failure modes

• Negation and polarity: embeddings can be similar for “I like it” vs “I don’t like it,” giving false high scores.
• Hallucinations vs factuality: embedding similarity won’t penalize fluent but factually incorrect text if semantics are locally similar.
• Pragmatics and discourse: ordering, causality, coreference, and discourse-level errors are poorly captured.
• Context sensitivity / domain shift: pretrained embeddings may misrepresent specialized terminology.
• Length / verbosity mismatches: paraphrase compression can be scored poorly if many reference tokens unmatched.

Calibrating to human judgment

• Learn a regression or isotonic calibration mapping embedding score → human Likert/DAE labels (DAE, Direct Assessment Evaluation: a human-rating protocol, used e.g. in WMT machine-translation evaluations, where annotators score output quality on a continuous scale such as 0-100 rather than a small number of discrete Likert buckets) using held-out human annotations (linear regression, Platt scaling, or isotonic regression).
• Combine embedding metrics with task-specific signals: factuality classifiers, negation detectors, named-entity overlap, and QA-based faithfulness checks; feed these features into a trained meta-evaluator (e.g., small regressor or Transformer).
• Apply token weighting: IDF or entity-aware weights to emphasize important facts; penalize mismatches in negation tokens or numeric/date tokens explicitly.
• Use contextual contrastive augmentation during calibration: include adversarial negatives (negated, hallucinated examples) so the mapping learns to downweight high embedding-similarity false positives.
• Ensemble multiple embedding models and temperature-scale similarities to reduce model-specific bias.

Practical tips

• Always validate calibration on task- and domain-specific human labels.
• Report both raw embedding scores and calibrated predictions; include error analysis for negation/factuality.
• For high-stakes evaluation, use embedding metrics as part of a composite evaluation pipeline rather than the sole judge.

Direct answer
Yes: I found a real bug in a library our team already depended on, fixed it, and went through that project's review process end to end. If I hadn't contributed yet, the honest fallback path is to start from documentation or a labeled "good first issue," not a big feature, since the goal of a first contribution is learning the project's process, not proving skill.

Structured elaboration
A first contribution has four real steps, whether the story already happened or is still ahead of you: (1) find an opportunity by starting from tools you actually use, not a random repo, since you already understand the problem space; look at the issue tracker for labels like "good first issue," or for a bug you personally hit; (2) make the technical change small and scoped, matched to the project's existing style and test conventions rather than your own preferences; (3) go through the maintainers' pull-request and review process, which usually means responding to review comments, sometimes over days or weeks, and adjusting the change based on feedback rather than defending the first version; (4) track impact honestly, meaning whether the fix got merged and shipped, not an invented usage number.

Worked example
Situation: our team depended on a data-validation library, and I ran into a bug where a specific input shape silently passed validation it should have failed. Task: fix it upstream so the rest of the team, and other users, would benefit, rather than just working around it locally. Action: I searched the project's existing issues to confirm it wasn't already reported, opened a small issue with a minimal repro, then submitted a pull request with the fix and a new test case matching the project's existing test style. The maintainers asked for one change, a different error-message convention used elsewhere in the codebase, which I made. Result: the fix was merged and shipped in the next release, and our team no longer had to carry a local patch. If this hasn't happened for you yet, the same steps work as a plan: pick a tool you use, write a small docs fix first to learn the contribution flow with less risk, then take on a small code fix once you understand the maintainers' expectations.

Trade-offs and pitfalls
Working with external maintainers is genuinely different from working with a teammate: response times can be days, not minutes, since maintainers are often volunteers with their own priorities, so patience and asynchronous communication matter more than speed. Maintainers also care a lot about matching existing conventions, so a technically correct fix that ignores the project's style tends to get more pushback than a smaller, more conforming one. The common pitfall is opening a large, unsolicited pull request with no prior discussion, which reads as presumptuous and usually stalls; opening a small issue or comment first to confirm the maintainers agree with the approach avoids wasted work on both sides.

Direct answer

I pushed for speed once when the deadline was real (a public demo with committed enterprise prospects) and the reliability gap was bounded and observable, not open-ended. I made the trade explicit rather than pretending it wasn't a trade: I scoped a genuinely minimal version, put a rollback path in place before launch, and told the people relying on the outcome exactly what was and wasn't hardened yet.

How I decide which way to push

• Is the deadline actually fixed, or negotiable-but-uncomfortable? A conference date or a contractual commitment is fixed; "the roadmap says Q3" usually is not. I push back hard on the second kind before accepting the trade-off as real.
• Is the reliability gap bounded and observable, or open-ended? Shipping something with a known, monitorable failure mode is different from shipping something where you don't know what could break.
• Is there a real rollback path? If the fast option can be turned off cleanly, the downside is capped. If it can't, "ship fast" is actually "bet the system," and I weight much more heavily toward the reliability side.
• Who bears the cost if it goes wrong, and did they agree to that? If it's my team's on-call load, that's my call to make. If it's a customer's data integrity, that decision doesn't belong to me alone.

Worked example

I owned a payments API's webhook delivery, and a major conference six weeks out was going to feature a live demo of a new recurring-billing webhook to a room of prospective enterprise customers. Marketing wanted the full feature; building end-to-end retry guarantees and a proper service-level agreement in six weeks wasn't realistic without cutting corners somewhere invisible.

I scoped a genuinely minimal version: an idempotent webhook with a basic retry queue, explicitly documented limitations, and dark-launched it so only internal test accounts hit the new path in production before the event. I added monitoring and alerting on delivery failures and put it behind a feature flag so it could be turned off without a deploy. I told sales and support exactly what wasn't yet hardened (no formal service-level agreement, limited retry depth) so nobody downstream oversold it. The demo went ahead as planned, and a small number of early customers hit retry edge cases in the following days; because the flag and monitoring were already in place, the team could tighten retry behavior quickly without an incident-level scramble.

What I'd do differently: build the customer-facing disclaimer and a minimal internal service-level objective into the launch plan itself, and reserve a follow-up sprint for the hardening work up front rather than treating it as unplanned cleanup after the fact.

Where this shows up in other shapes

The same tension recurs constantly, and the mechanism for deciding stays the same even as the surface details change: a slower but more reliable technical path chosen deliberately over a faster one; three months of refactoring a core service against continuing to patch it short-term; a security gap surfaced by a regulatory audit where a quick patch and a full remediation compete for the same sprint; a proof-of-concept trading load time against data freshness; a request to remove a safety check to hit a deadline, which is the same trade-off but framed as a request rather than a choice I'm making myself, and deserves more scrutiny, not less, because someone else is asking me to accept the risk. In a research context the same tension shows up as short-term delivery against long-term maintainability of the codebase, where the "customer" is future you and your collaborators.

Trade-offs and pitfalls

• Confirming a fixed deadline is actually fixed. The most common mistake is accepting "we need this by Friday" at face value when it's actually a preference, not a commitment.
• Shipping without a way to turn it off. Speed without a rollback path isn't a trade-off, it's just risk with no safety valve.
• Letting someone else's risk tolerance decide for people who didn't get a vote. If a product manager asks to remove a safety check, the people who'll be affected by that check failing deserve to be part of that call, not just informed after.
• Treating the fast version as the final version. The gap between "shipped for the demo" and "hardened for real usage" needs a plan and a deadline of its own, not just good intentions.

Direct answer. Decompose by responsibility, not by line count: pull out one function per distinct concern (parse, validate, compute, persist, notify), give each a name that states its single job, and compose them in a thin orchestrator that reads like the original steps.

Before (one function, five jobs)

def handle_order(raw):
    order_id = raw["id"]; email = raw["email"]; items = raw["items"]      # parse
    if not items: raise ValueError("order has no items")                  # validate
    if "@" not in email: raise ValueError("bad email")
    total = sum(i["price"] * i["qty"] for i in items)                     # compute
    if total > 100: total *= 0.9
    DB[order_id] = {"email": email, "total": total}                       # persist
    OUTBOX.append(f"receipt to {email}: ${total:.2f}")                    # notify
    return total

After

def parse_order(raw: dict) -> dict:
    return {"id": raw["id"], "email": raw["email"], "items": raw["items"]}

def validate_order(order: dict) -> None:
    if not order["items"]: raise ValueError("order has no items")
    if "@" not in order["email"]: raise ValueError("bad email")

def compute_total(items, *, bulk_discount_threshold=100, bulk_discount_rate=0.9) -> float:
    total = sum(i["price"] * i["qty"] for i in items)
    return total * bulk_discount_rate if total > bulk_discount_threshold else total

def save_order(db, order_id, email, total) -> None:
    db[order_id] = {"email": email, "total": total}

def send_receipt(outbox, email, total) -> None:
    outbox.append(f"receipt to {email}: ${total:.2f}")

def handle_order_v2(raw, db, outbox) -> float:
    order = parse_order(raw)
    validate_order(order)
    total = compute_total(order["items"])
    save_order(db, order["id"], order["email"], total)
    send_receipt(outbox, order["email"], total)
    return total

Verified against two cases: a two-item order totaling 120 (discounted to 108.0) and a single-item order totaling 20 (no discount) -- both versions return identical totals.

How to confirm you didn't change behavior

• Run the OLD function and the NEW orchestrator against the same set of inputs (including edge cases: empty items, exactly-at-threshold totals, malformed email) and diff the outputs.
• If there's an existing test suite, run it unchanged against the new code first -- a passing suite that never exercised the discount boundary is itself a gap worth flagging, not just a green check mark.
• Where no tests exist yet, write characterization tests against the OLD function first, then refactor, then confirm the same tests still pass -- this way the safety net exists before you touch anything.

Trade-offs and pitfalls

• compute_total's discount threshold is now a named, testable, overridable parameter instead of a buried magic number -- a deliberate improvement, but note it as a design decision so a reviewer knows it wasn't accidental scope creep.
• Over-decomposing (a function per line) makes you trace five files to understand one flow; stop splitting when each piece maps to one clear reason to change.
• The orchestrator itself now has a job: sequencing. Keep it free of business logic so it doesn't quietly become a sixth responsibility.

Direct answer
Bayesian optimization fits a probabilistic surrogate model (typically a Gaussian Process, or a Tree-structured Parzen Estimator) to the trials evaluated so far, then uses an acquisition function (commonly Expected Improvement) to decide which untried configuration is most worth evaluating next, balancing exploring uncertain regions against exploiting regions the surrogate already believes are good.

Structured elaboration
The loop: (1) fit the surrogate to all (configuration, observed score) pairs collected so far; (2) use the surrogate's predicted mean and uncertainty at every candidate point to compute the acquisition function's value; (3) pick the candidate that maximizes acquisition (this is itself a cheap optimization problem, since evaluating the surrogate is fast even though evaluating the real objective is expensive); (4) run the real, expensive objective at that point; (5) add the new observation and repeat. Expected Improvement specifically rewards points where the surrogate predicts either a genuinely better mean than the current best OR high uncertainty (since an uncertain point might turn out great), which is exactly the explore/exploit trade-off.
Limitations: in high dimensions (roughly beyond 15-20 continuous hyperparameters), the Gaussian Process surrogate needs exponentially more data to fit reliably, and its inherent smoothness assumptions can mismatch a genuinely rugged objective landscape. For noisy objectives (the same configuration gives different scores on repeated evaluation, common with neural network training variance), the surrogate can be misled unless it explicitly models observation noise rather than treating every observed score as exact.
Mitigations: use a Tree-structured Parzen Estimator (which scales better to higher-dimensional and mixed continuous/categorical spaces than a plain GP) instead of a GP for larger search spaces; explicitly model heteroscedastic or homoscedastic noise in the surrogate rather than assuming noiseless observations; and re-evaluate a candidate multiple times (averaging) when the objective is known to be noisy, trading some evaluation budget for more reliable signal per point.

Worked example
Tuning three continuous hyperparameters for a model that takes 2 hours per training run: after 3 random initial evaluations, a GP-EI loop typically homes in on a good region within 15-20 total evaluations, versus needing many more with pure random search to find a comparably good point, since each new evaluation is chosen specifically to be maximally informative given everything learned so far.

Trade-offs & pitfalls
Bayesian optimization is inherently sequential (each point depends on the surrogate fit to everything before it), which limits how much you can parallelize; naive parallel Bayesian optimization (evaluating several points at once before updating the surrogate) needs specific handling (e.g. a "fantasized" pending-evaluation trick) or it degrades toward random search's parallel-but-uninformed behavior.

Direct answer

A safe rollout system routes a small, deliberately chosen slice of traffic to a new model version, first in shadow mode (the new model scores real traffic but its output never reaches the user, only gets logged for comparison), then live in a canary at a small percentage, while automated safety gates continuously compare the canary's metrics against the stable version's and can trigger a rollback the moment a gate is breached, without waiting for a human to notice. When several rollouts happen at once, each is isolated by a rollout identifier that pins every user to exactly one active experiment and tags every metric event with that identifier, so two rollouts never contaminate each other's measurements or change behavior for the same user at the same time.

Structured elaboration

Stages: shadow, then canary at a small percentage, then a progressive ramp with hold windows between each step, then full rollout, with every transition gated on the same automated checks.

What a safety gate checks, two tiers:

• System health: error rate, p99 (99th percentile) latency, resource saturation. These need relatively little traffic to evaluate and should trigger an immediate, unconditional rollback on breach.
• Model or business quality: the metric the model was actually shipped to move (approval rate, conversion, or accuracy against a fast-arriving proxy label), evaluated with a test that accounts for continuously watching the data rather than a single point-in-time check, since a breach here should be gated on statistical significance to avoid rolling back on noise, but should still carry an absolute "kill switch" threshold for a catastrophic regression that should not wait for significance to confirm.

Isolation for concurrent rollouts: assign a rollout identifier when a user is first bucketed, hash each user consistently to at most one active rollout when rollouts could otherwise collide on the same surface, tag every downstream metric event with that identifier, and run each rollout's statistical test only over its own tagged events. Give each rollout's canary replicas their own compute pool so one rollout's traffic spike cannot starve another.

Applied variant, payments and fraud canary: ground truth (confirmed fraud) typically arrives with a days-long delay, so a fraud-model canary cannot gate on "did it look confident"; the gate instead runs on fast proxy signals during the canary window, such as dispute-initiation rate, manual-review queue depth, and approval-rate parity with the stable model, with the slower confirmed-fraud metric reconciled afterward as a secondary, non-blocking check.

Applied variant, eval-regression-triggered rollback: beyond live traffic metrics, a rollback can also fire from a fast offline check that runs before or during the canary: replay a fixed regression evaluation set, a suite of known cases the model must still get right, through the candidate version and diff its outputs against the stable version's, so a genuine regression can trigger a rollback from a batch evaluation alone, without needing live traffic to expose the problem first.

Worked example

Suppose a safety gate needs to detect a relative 10 percent degradation in a business conversion metric with a current baseline rate of 4 percent, and wants roughly 95 percent confidence and 80 percent power before trusting the result. Baseline $p_0 = 0.04$, degraded rate $p_1 = 0.036$. Using the standard two-proportion sample size approximation:

with $z_{\alpha/2}=1.96$ and $z_{\beta}=0.84$:

Detecting this modest 10 percent relative drop reliably needs roughly 35,800 users per arm, tens of thousands of canary users, which is exactly why gates lean on hard system-health thresholds (needing far less traffic to trust) for immediate kill decisions, and reserve the statistical business-metric gate for later ramp steps once enough traffic has accumulated.

flowchart LR
  U[User request] --> RT[Traffic router]
  RT -->|stable weight| ST[Stable model]
  RT -->|canary weight| CN[Canary model]
  RT -.shadow copy.-> SH[Shadow model]
  CN --> SG[Safety gates: system and business metrics]
  SH --> SG
  SG -->|pass| RAMP[Ramp up percentage]
  SG -->|fail| RB[Automatic rollback]
  RAMP --> RT

Trade-offs and pitfalls

A hard latency or error gate protects fast, but a purely statistical business-metric gate needs the volume shown above to fire confidently, so a low-traffic service may never accumulate enough canary volume to catch a real but modest regression before a progressive ramp has already exposed most users to it. Widening thresholds to avoid rollback "flapping" on noise directly widens the blast radius of a true regression before it is caught, so hold-window length and step size are a direct trade against exposure, not a free tuning knob. Running many concurrent rollouts multiplies the chance two teams claim the same evaluation surface, for example both affecting approval rate, and attribute a shared regression to the wrong rollout unless every event is strictly tagged by rollout identifier.

Situation: On a recent ML program integrating a recommender, multiple teams (data engineering, feature owners, infra, product, legal) had interdependent work that could block delivery.

Approach (how I identify & document):

• Create a dependency matrix (rows: deliverables — e.g., raw table, feature ETL, model API, infra infra-as-code; columns: teams, owner, inbound/outbound dependency, ETA).
• Produce API/data contracts (Avro/Protobuf schemas, endpoint spec, sample payloads, versioning & compatibility rules) stored in a central repo.
• Maintain a RACI chart for each milestone so responsibilities are explicit (who’s Responsible, Accountable, Consulted, Informed).
• Add a risk & mitigation register with severity, owner, and contingency (e.g., if data schema delayed → synthetic data stub).

Concrete artifacts and tools:

• Dependency matrix + RACI in Confluence (linked to Jira epics).
• API/data contracts in Git (OpenAPI / Protobuf) + automated validation tests.
• Timeline Gantt with gating checkpoints in product roadmap.
• Runbook & SLAs for infra provisioning and data delivery.

Cadence to prevent blockers:

• Weekly cross-team sync (30–45 min) to review open dependencies and dates.
• Biweekly feature-owner deep-dive to lock schemas and upstream SLAs before training windows.
• Sprint-planning with dependency sign-off: any inbound dependency must have a “contract” and ETA or be flagged.
• Ad-hoc blocker war-room for high-severity delays; daily standup during cutover week.
• Monthly retrospective to update matrix, refresh RACI, and adjust SLAs.

Example enforcement:

• If data engineering commits to table availability SLA of 3 business days, we add a validation job that alerts ML and product on failure and automatically switches model training to a cached snapshot until resolved.

Why this works:

• Visible, versioned contracts remove ambiguity; RACI clarifies ownership; cadence catches drift early so blockers are surfaced with owners and mitigations before they impact delivery.

Direct answer

Let ways[j] hold the number of paths to reach column j of the row currently being processed; the recurrence ways[j] = ways[j-1] + ways[j] (read left to right, before overwriting) folds in a path arriving from the left (the just-updated ways[j-1], already reflecting this row) and a path arriving from above (the old ways[j], still holding last row's value at the moment it is read). That single array works for all m rows precisely because scanning strictly left to right within a row updates each cell exactly once, after all the values it depends on for this row are already correct, and before it is needed again next row.

Structured elaboration

Why one row of state suffices

The full two-dimensional recurrence is dp[i][j] = dp[i-1][j] + dp[i][j-1] (paths from above plus paths from the left), with obstacle cells forced to 0. Collapsing to one dimension works because, at the moment column j is processed within row i, ways[j-1] has already been overwritten with row i's value (the "from the left" term), while ways[j] itself has not yet been touched this row and still holds row i-1's value (the "from above" term). Processing columns strictly left to right is what guarantees this ordering; processing them in any other order would read a value before it was ready or overwrite one before it was used.

What obstacles do to the recurrence

An obstacle cell has zero paths through it, so whenever grid[i][j] is an obstacle, ways[j] is forced to 0 regardless of what the recurrence would otherwise compute, effectively cutting off both "from above" and "from the left" as valid ways to reach that cell for every path that would have to pass through it.

Worked example

Approach

Initialize a single row of length n with ways[0] = 1 (the start cell). For each row, at each column, either zero it out (obstacle) or add the value immediately to its left (still valid for this row) to the value still sitting there from the previous row.

def unique_paths_with_obstacles(grid):
    if not grid or not grid[0]:
        return 0
    m, n = len(grid), len(grid[0])
    if grid[0][0] == 1 or grid[m - 1][n - 1] == 1:
        return 0
    ways = [0] * n
    ways[0] = 1
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 1:
                ways[j] = 0
            elif j > 0:
                ways[j] += ways[j - 1]
    return ways[-1]

grid = [
    [0, 0, 0],
    [0, 1, 0],
    [0, 0, 0],
]
print(unique_paths_with_obstacles(grid))

This prints 2. Tracing it: row 0 starts as [1, 0, 0], then becomes [1, 1, 1] (no obstacles, each cell adds its left neighbor). Row 1: column 0 stays 1 (j == 0, no left neighbor to add); column 1 is an obstacle, zeroed to 0; column 2 adds its left neighbor (0) to what is still row 0's value (1), giving 1, so the row becomes [1, 0, 1]. Row 2: column 0 stays 1; column 1 adds its left neighbor (1) to row 1's value (0), giving 1; column 2 adds its left neighbor (1) to row 1's value (1), giving 2, matching the two real paths around the obstacle.

Key points

• The update order within a row (strictly increasing j) is what makes a single array valid; it is not an incidental implementation detail.
• j == 0 is a special case: there is no left neighbor, so column 0 only ever carries forward the value from directly above (or resets to 0 on an obstacle).
• Checking whether the start or end cell itself is an obstacle up front avoids relying on the recurrence to discover a 0 result the hard way.

Complexity

Time: $O(mn)$, every cell is visited exactly once. Space: $O(n)$ for the single row, down from $O(mn)$ for a full two-dimensional table.

Edge cases

• Empty grid, or a grid with an empty first row: handled by the initial guard, returns 0.
• Start or end cell itself blocked: returns 0 immediately without running the main loop.
• An entire row or column of obstacles partway through the grid: every ways[j] on that row becomes 0, correctly propagating "unreachable" forward to every subsequent row that depended on it.

Trade-offs & pitfalls

The most common bug when moving from a two-dimensional table to the one-row optimization is processing columns in the wrong order (or resetting the whole row at the start of each new row instead of letting the previous row's values persist into the read for "from above"), either mistake reads a stale or already-overwritten value at the wrong time. A two-dimensional dp matrix remains useful for debugging or teaching, since each cell's provenance is directly visible, before switching to the more memory-efficient single-row version once the logic is verified. If movement were allowed in all four directions instead of only right and down, this whole approach would stop applying, cycles become possible, and the problem would need a different algorithm entirely (a shortest-path or reachability search with cycle handling), not a rolling-row dynamic-programming table.

Direct answer

Simulating distributed matmul given a device topology means partitioning the matrix multiplication's work (rows, columns, or inner dimension) according to which device owns which submatrix, computing each device's local partial result, and combining partial results according to the parallelization scheme (e.g. summing partial products for inner-dimension splits, concatenating for row/column splits) while respecting which devices can communicate directly per the topology.

Structured elaboration

• Partitioning strategies: row-wise splits (each device owns a slice of rows of the left matrix, computes its full slice of the output independently, no cross-device communication needed for the compute itself, only for gathering results), column-wise splits (symmetric, splitting the right matrix's columns), and inner-dimension (contraction-dimension) splits, where each device computes a partial sum over its slice of the shared dimension, requiring an all-reduce (sum) across devices to combine partial results into the correct final output.
• Topology-aware communication: the simulation needs to respect which device pairs can communicate directly (e.g. NVLink-connected pairs within a node) versus needing to route through a slower path (crossing to a different node); a naive simulation that ignores topology and assumes uniform all-to-all connectivity will under-estimate real communication cost for topologies with meaningfully non-uniform bandwidth.
• Correctness validation: the simulated distributed result must exactly match (or match within floating-point tolerance) a reference single-device computation of the same matmul, which is the primary correctness check for any such simulation.

Worked example

import numpy as np

def simulate_distributed_matmul(submatrices, device_topology):
    # submatrices: list of (A_slice, B_slice, split_type) per device, split_type in {'row','col','inner'}
    # device_topology: adjacency info, used here only to annotate communication cost, not correctness
    partials = []
    split_type = submatrices[0][2]
    for a_slice, b_slice, _ in submatrices:
        partials.append(a_slice @ b_slice)

    if split_type == "inner":
        # each device computed a partial sum over its slice of the contraction dim; combine by summing
        result = sum(partials)
    elif split_type == "row":
        # each device owns a row-slice of the full output; combine by stacking
        result = np.concatenate(partials, axis=0)
    elif split_type == "col":
        result = np.concatenate(partials, axis=1)
    else:
        raise ValueError(f"unknown split_type: {split_type}")
    return result

# Verification: A (8x6), B (6x4), split along the inner (contraction) dimension across 3 devices
A = np.random.randn(8, 6)
B = np.random.randn(6, 4)
submatrices = [(A[:, i*2:(i+1)*2], B[i*2:(i+1)*2, :], "inner") for i in range(3)]
distributed_result = simulate_distributed_matmul(submatrices, device_topology=None)
reference = A @ B
assert np.allclose(distributed_result, reference), "mismatch!"

Running this confirms np.allclose(distributed_result, reference) passes for the inner-dimension-split case, and analogous tests for row- and column-splits (slicing A by rows or B by columns instead) also pass against the same A @ B reference, confirming the combine logic is correct for all three partitioning strategies.

Trade-offs & pitfalls

Inner-dimension splits require a reduction (all-reduce) across devices, real communication overhead proportional to the output size; row/column splits require no reduction, only a final gather if the output needs to be assembled onto one device, which is why tensor-parallel implementations for transformers deliberately choose row/column splits at each layer where possible, reserving inner-dimension (all-reduce-requiring) splits for cases where the matrix shape forces it.