Apple Machine Learning Engineer Interview Preparation Guide - Entry Level

Direct answer

Put every number into a hash set for O(1) average membership checks, then only start counting a run from numbers that are the START of a run, meaning num - 1 is not in the set. From each such start, walk forward while the next consecutive integer is present, tracking the longest run found. This turns an O(n log n) sort-based approach into O(n) average time, because the set lets you test "is this the start of a run" without looking at the rest of the array.

Structured elaboration

Approach

def longest_consecutive(nums):
    num_set = set(nums)
    best = 0
    for n in num_set:
        if (n - 1) not in num_set:
            length = 1
            while (n + length) in num_set:
                length += 1
            best = max(best, length)
    return best

Why this is O(n), not O(n times the average run length)

The inner while loop only ever runs starting from a number that has no predecessor in the set, that is, the FIRST element of some run. Every other number in that run gets skipped by the outer loop's guard (n - 1 not in num_set is false for them), so the inner loop is never re-entered from the middle of a run it has already walked. Summed across the whole execution, every number in the array is visited by the inner loop's forward walk at most once, across the ENTIRE algorithm, not once per outer-loop iteration; that is what keeps the total work at O(n) despite the code superficially looking like a nested loop.

Application: contiguous ID spans in event logs (the question's explicit ask)

If event or record identifiers are integers assigned in increasing order, but the log has gaps (from filtered-out, dropped, or retried events), this exact technique finds the longest unbroken run of the IDs that DID make it into the log, in one O(n) pass over an unsorted set of IDs, without first sorting the whole log.

Worked example

Executed with python3 s74.py, pinned inputs:

input: [100, 4, 200, 1, 3, 2, 101, 102]
longest_consecutive(nums) = 4

The run 1, 2, 3, 4 has length 4; the run 100, 101, 102 has length 3; 4 is the longer of the two, matching the printed result.

event_ids: [7001, 7002, 7004, 7005, 7006, 7010]
longest contiguous ID span length = 3

The span 7004, 7005, 7006 (length 3) is longer than the span 7001, 7002 (length 2), matching the printed result and directly demonstrating the event-log framing the question asks about.

Trade-offs and pitfalls

• The single most common bug is dropping the (n - 1) not in num_set guard and letting the inner loop start from every element; that degrades to O(n^2) in the worst case (for example, one long consecutive run), even though the code still looks like "the hash-set version" at a glance.
• Duplicate values in the input do not affect correctness (the set removes them), but the returned length measures the run over DISTINCT values; if a caller actually needs to count how many raw events fall in the longest span, including duplicates, this exact function does not do that and needs a small extension.
• If the caller needs the actual start and end of the run for reporting (not just its length, which is what the event-log framing implies you would want in practice), track the start value alongside the length whenever a new best is found.

Direct answer

Go to the colleague privately first, before doing anything more public, and frame the concern as a question about the sampling method rather than a conclusion about their competence. Bring the specific evidence, propose a joint, falsifiable check that would settle whether the bias is real, and only then decide together how to handle the already-circulated report.

Structured elaboration

1. Verify before you raise it. Confirm the specific gap yourself (which source, what kind of gap) so you are not escalating a hunch. Raising a vague suspicion is more likely to read as an attack than raising a concrete, checkable one.
2. Private channel first. Do not raise it in the stakeholder meeting or a public thread. The goal at this stage is a shared understanding between the two of you, not a public correction.
3. Lead with evidence, not the conclusion. Ask how the sample was chosen and show what you noticed, rather than opening with "your report is biased." The evidence does the work; you are not the one delivering a verdict.
4. Propose a joint, falsifiable test. Agree in advance on a specific check that would settle the question either way, for example, re-running the analysis with a more complete data source and comparing results. If the two produce materially different conclusions, that is evidence of the bias; if not, the original report holds and nothing was lost.
5. Handle the stakeholder-facing correction together. If the test confirms the bias, present the fix as a normal part of the quality process, credit the colleague's original work, and avoid framing it as catching an error.

Worked example

A colleague circulated a cohort analysis to stakeholders built from a single data source you know has intermittent collection gaps. Rather than flagging it in the stakeholder thread, you ask to talk privately: "I noticed this cohort uses source A, do you know if that source had full coverage this quarter?" You show the specific evidence (gap periods, affected date ranges) and ask how the sample was chosen. Together you agree on the joint test: re-run the same cohort analysis using a second, more complete source and compare the two results. If the numbers move meaningfully, you have confirmed a real bias and both go to stakeholders together with an updated report and a data-quality caveat; if the numbers hold steady, the original report stands and the check cost an afternoon, not a reputation.

Trade-offs & pitfalls

• Raising it directly in the stakeholder meeting "to protect the org from a bad decision" scores a point in the moment but damages the working relationship and makes the colleague defensive on the next collaboration.
• Staying silent because raising it feels confrontational lets a real bias ship into decisions uncorrected, which is a worse outcome for the partnership than a slightly awkward private conversation.
• The senior move here is designing the joint test so the evidence settles the question, rather than relying on how persuasively you phrase the concern. A well-chosen test does the convincing; the conversation itself does not have to.
• A remaining pitfall: proposing a fix without proposing how to verify it worked. A joint investigation that ends without a joint, agreed check on the outcome tends to resurface as the same disagreement later.

Situation: After a recent deployment, our recommendation model started returning unsafe product suggestions for ~2% of users, triggering customer complaints and a rollback. As the senior ML engineer, I led the post-incident RCA and response.

Task: Quickly find root causes, contain user impact, communicate clearly to stakeholders, prioritize mitigations vs long-term fixes, and introduce governance to prevent recurrence while meeting regulatory and policy constraints.

Action:

• Technical RCA (48 hours sprinted):

  • Reproduce failure in a sandbox using the production input distribution and exact model binary/config.
  • Gather telemetry: input feature drift, model confidence, feature importance, data pipeline logs, infra metrics, and A/B test logs.
  • Hypothesis-driven debugging: tested three hypotheses (data schema change, feature transformation bug, stale feature store join). Binary diffing of model artifacts and transformation code pointed to a schema mismatch after a downstream ETL change that shifted a categorical index.
  • Verified root cause by simulating the ETL change and observing identical regressions and high feature-importance shifts.
  • Quantified impact: 2% users, precision drop from 0.86→0.62, increase in support tickets by 4x.

• Communication:

  • Immediate: incident summary, user impact, and mitigation plan to Execs, PM, Legal, Customer Support within 2 hours.
  • Daily updates with technical postmortem draft; held a cross-functional postmortem meeting with engineering, product, ops, and compliance to review evidence and proposed fixes.
  • Final RCA doc: timeline, root cause, replication steps, metrics, and runbook for similar incidents; shared with stakeholders and retained in incident system.

• Prioritization (short vs long term):

  • Short-term (hours–days): Rollback to previous stable model (already done), feature validation gate to block deployments where production feature distributions deviate beyond thresholds, and a hotfix to ETL to backfill corrected categorical mapping for recent data.
  • Long-term (weeks–months): Add schema-contract enforcement between ETL and feature store, automated end-to-end integration tests that run model inference on synthetic and sampled production traffic, and strengthen CI/CD with pre-deployment canarying and shadow traffic testing.

• Governance & compliance:

  • Updated deployment checklist to require signed-off data contracts and automated schema checks; added mandatory shadow runs for models affecting user-facing decisions for at least 48 hours.
  • Introduced an ML-specific change-control ticket that includes privacy, fairness, and regulatory impact assessment fields; Legal and Compliance must sign off for high-risk models.
  • Implemented monitoring SLAs and alerts tied to business metrics and regulatory thresholds; logs and audit trails retained per policy for 2 years to satisfy compliance.
  • Trained teams on new runbooks and governance steps; scheduled quarterly audits and tabletop exercises.

Result: Containment within 6 hours, full rollback restored baseline metrics; hotfix reduced recurrence risk by eliminating the immediate data mismatch. New validation gates and governance reduced deployment-related incidents in the following quarter to zero for similar classes of change. The process improved cross-team trust and created auditable controls that satisfied Compliance and Exec leadership.

This taught me to treat ML incidents as socio-technical problems: rigorous technical debugging, fast transparent communication, clear short/long-term action separation, and embedding governance into the CI/CD pipeline.

Direct answer

Count distinct paths from source to target in a directed acyclic graph (DAG) with top-down dynamic programming: recursively define countPaths(u) as 1 if u == target, otherwise the sum of countPaths(v) over every direct successor v of u, and memoize each node's result the first time it is computed so repeated calls to the same node (reached via different paths through the DAG) are answered in $O(1)$ instead of being recomputed. Because the graph is acyclic, this recursion is guaranteed to terminate, and because it is memoized, each node's true path-count is computed exactly once, giving $O(V+E)$ total time.

Structured elaboration

Why memoization is valid here specifically, and would NOT be valid on a general (possibly cyclic) graph. Memoizing on (node) alone (not (node, path-so-far)) is correct because a DAG has no cycles, so the number of distinct paths from a given node to the target does not depend on how that node was reached, it only depends on the node's own outgoing structure, which never changes across different calls. On a graph WITH cycles, this same memoization would be unsound in general: a node could be part of the current path already (revisited), and blindly reusing a cached "path count from this node" would either double-count paths that loop back through already-visited nodes, or (if a visited-set is added to forbid revisiting) the cached value would depend on WHICH nodes happen to already be visited on the current path, which varies call to call and therefore cannot be safely cached by node identity alone.

Overflow handling for large counts. The number of distinct paths in a DAG can grow exponentially in the number of nodes (a DAG shaped like a complete layered bipartite structure, where every node in layer $i$ connects to every node in layer $i+1$, has a path count that multiplies layer over layer). A 32-bit signed integer overflows past roughly $2.1 \times 10^9$; using a 64-bit integer (long long in C++, which this implementation uses throughout) delays overflow to roughly $9.2 \times 10^{18}$, which is enough headroom for most realistic DAG sizes but is not unconditionally safe for an adversarially constructed DAG with enough layers and branching factor, at which point the correct fix is either an arbitrary-precision integer type or capping/reporting "count exceeds representable range" explicitly rather than silently wrapping around to a negative or incorrect value.

Worked example

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

long long countPaths(unordered_map<int, vector<int>>& graph, int source, int target,
                      unordered_map<int, long long>& memo) {
    if (source == target) return 1;
    auto it = memo.find(source);
    if (it != memo.end()) return it->second;
    long long total = 0;
    for (int next : graph[source]) {
        total += countPaths(graph, next, target, memo);
    }
    memo[source] = total;
    return total;
}

int main() {
    // DAG: 0->1, 0->2, 1->3, 2->3, 1->4, 3->4, 2->4  (diamond plus extra edges)
    unordered_map<int, vector<int>> graph;
    graph[0] = {1, 2};
    graph[1] = {3, 4};
    graph[2] = {3, 4};
    graph[3] = {4};
    graph[4] = {};

    unordered_map<int, long long> memo;
    long long result = countPaths(graph, 0, 4, memo);
    cout << "paths from 0 to 4: " << result << endl;
    return 0;
}

Output:

paths from 0 to 4: 4

Hand-enumerated paths from node 0 to node 4 in this DAG: 0-1-4, 0-1-3-4, 0-2-4, 0-2-3-4, exactly 4 distinct paths, matching the executed program's output. The memoization visibly matters here: node 3's countPaths(3) is computed once (yielding 1, since 3->4 is its only edge) and then reused for BOTH the call arriving via 1->3 and the call arriving via 2->3, rather than being recomputed from scratch each time.

Trade-offs and pitfalls

• Common mistake: forgetting to memoize at all, which still produces the correct COUNT on a DAG (acyclicity guarantees termination either way), but degrades runtime from $O(V+E)$ to potentially exponential, since the same node can be re-explored once for every distinct path reaching it, exactly the redundant work memoization exists to eliminate.
• Common mistake: memoizing on (node) alone for a graph that is NOT guaranteed acyclic. If the input might contain a cycle, this exact technique breaks (infinite recursion with no cycle to bound it, or the visited-set-dependent unsoundness described above); a production function accepting untrusted graph input should validate acyclicity first (for example, via a topological-sort attempt) rather than assume it.
• unordered_map<int, vector<int>> defaults every unlisted node to an empty vector on first access (via operator[]'s side effect of inserting a default entry), which is convenient here for target's empty successor list but is a real footgun in performance-sensitive code, since every lookup on a nonexistent key silently inserts a new empty entry rather than signaling "not found"; a find()-based lookup would avoid this side effect if it mattered for a specific use case.
• long long is not unconditional overflow safety, only a much larger safety margin than int. For a DAG whose true path count could plausibly exceed roughly $9.2 \times 10^{18}$ (an unusually large or densely-layered DAG), the count would still silently overflow into an incorrect value with no runtime error, and a system that must handle such inputs correctly needs either an arbitrary-precision integer library or an explicit overflow check before returning a result.

Direct answer
Plain assignment doesn't copy anything, it just gives a second name to the same object. A shallow copy creates a new outer container but reuses references to the same nested objects inside it, so mutating a nested element through either the original or the shallow copy is visible in both. A deep copy recursively copies every nested object too, giving you a fully independent structure.

Structured elaboration

• Assignment (b = a): a and b are now two names for the exact same object; b is a is True. There is no 'original' versus 'copy', they're the same thing.
• Shallow copy (copy.copy(a), or list(a), or a[:] for a list): creates a genuinely new outer object (b is a is now False), but for every element that is itself a mutable object (a nested list, a dict, a custom object), the copy holds a reference to the SAME nested object, not a copy of it (b[0] is a[0] is True).
• Deep copy (copy.deepcopy(a)): recursively walks the structure and makes a new copy of every nested mutable object too, so nothing is shared (b[0] is a[0] is False).
• The bug shape this causes: code that shallow-copies a nested structure believing it now has an independent snapshot, then mutates the original, and the 'snapshot' silently changes too, because the shallow copy's nested elements were never actually copied.

Worked example

import copy
original = [[1, 2, 3], [4, 5, 6]]
shallow = copy.copy(original)
deep = copy.deepcopy(original)

original[0].append(999)   # mutate a NESTED element of the original

Verified results after that mutation: original == [[1, 2, 3, 999], [4, 5, 6]], shallow == [[1, 2, 3, 999], [4, 5, 6]] (the nested list was shared, so the shallow copy sees the change too), deep == [[1, 2, 3], [4, 5, 6]] (fully independent, unaffected).

A realistic version of this bug: code takes a shallow copy of a dataset as a 'before' snapshot, then runs an in-place normalization pass over the dataset:

def normalize_inplace(rows):
    for row in rows:
        total = sum(row)
        for i in range(len(row)):
            row[i] = row[i] / total if total else 0

After running normalize_inplace on the dataset, the shallow-copied 'snapshot' taken beforehand is bitwise identical to the now-normalized dataset (verified by running it: snapshot == dataset evaluates True after normalization), because normalize_inplace mutates each row list in place, and the shallow copy's rows are the SAME row objects as the original's. The 'backup' was never a backup.

Trade-offs & pitfalls
The fix depends on what you actually need: if you truly need an independent snapshot, use copy.deepcopy (accepting its cost, see the mutability discussion) or rebuild the structure by copying each nested piece explicitly. If deep-copying every row of a large dataset is too expensive, the more scalable fix is usually to stop mutating in place at all, have normalize_inplace return a new structure instead of mutating its argument, which sidesteps the shallow/deep copy question entirely by removing the shared-mutable-state pattern that created the risk.

Approach summary:

• Start from a trained or partially trained float model, fuse Conv+BN(+ReLU) where possible, wrap model with fake-quant stubs, prepare QAT (quantization-aware training) with proper qconfig (per-channel weight quant, activation observers), fine-tune with smaller LR and possibly freeze BN stats to recover accuracy, then convert to a fully quantized model for export.

Code-level recipe (PyTorch >=1.8):

import torch
from torch.quantization import get_default_qat_qconfig, prepare_qat, convert, fuse_modules, QuantStub, DeQuantStub

class QATResNetBlock(torch.nn.Module):
    def __init__(self, block):
        super().__init__()
        self.quant = QuantStub()
        self.dequant = DeQuantStub()
        self.body = block

    def forward(self, x):
        x = self.quant(x)
        x = self.body(x)
        x = self.dequant(x)
        return x

# 1. Fuse modules (example for simple conv-bn-relu)
model = ...  # pretrained float model
fuse_modules(model, [['conv', 'bn', 'relu']], inplace=True)

# 2. Insert Quant/DeQuant stubs at model boundaries
model = QATResNetBlock(model)

# 3. Set QAT qconfig (use per-channel weights)
model.qconfig = get_default_qat_qconfig('fbgemm')  # for x86; use 'qnnpack' on mobile

# 4. Prepare model for QAT (inserts FakeQuant modules)
prepare_qat(model, inplace=True)

# 5. Optionally freeze batchnorm stats before fine-tuning:
def freeze_bn(m):
    if isinstance(m, torch.nn.BatchNorm2d):
        m.eval()               # stop tracking running stats
        m.weight.requires_grad = False
        m.bias.requires_grad = False
model.apply(freeze_bn)

# 6. Fine-tune (small LR, longer)
# After training:
qat_model = convert(model.eval(), inplace=False)  # produces a quantized model

Key concepts / where fake-quant modules live:

• prepare_qat replaces activations/weights observers with FakeQuantize modules that simulate quantization during forward/backward so model learns quantization error.
• FakeQuant modules are inserted on activations and weights according to qconfig; weights use per-channel FakeQuantize (better accuracy), activations usually per-tensor.

BatchNorm handling (folding vs freezing):

• Folding: fuse Conv+BN into Conv before preparing QAT (fuse_modules). That effectively folds BN scale/shift into conv weights - important for quantization stability.
• Freezing: during QAT you usually set BN to eval() so running mean/var are fixed (no batch noise). Also freeze BN affine params to avoid large shifts. Alternative: set momentum=0 (use running stats) or use a small number of epochs with BN tracking before freezing.

Hyperparameter tips to recover accuracy:

• Start QAT from a high-quality pretrained float checkpoint.
• Use lower initial LR (1e-4–5e-5) and smaller LR decay steps; longer fine-tuning (5–30 epochs depending on dataset).
• Reduce weight decay slightly; use AdamW or SGD with momentum.
• Use per-channel weight quantization qconfig and 'fbgemm' for server, 'qnnpack' for mobile.
• Use larger batch size for better BN statistics before freezing; if BN frozen early, ensure running stats were well estimated (run a few epochs of calibration with no weight updates).
• Optionally use knowledge distillation from float teacher during QAT.
• Monitor activation histograms; adjust observer type (moving_average_minmax vs histogram) if saturation occurs.
• Validate with representative data and run a calibration pass before convert if needed.

Practical gotchas:

• Ensure model in training/eval modes appropriately: prepare_qat expects training mode to insert FakeQuant that behave correctly; convert requires eval().
• Some layers (e.g., custom ops) need custom qconfig or manual fake-quant insertion.
• Test the converted quantized model end-to-end (latency and accuracy) and compare per-layer quant params when debugging.

This sequence (fuse -> set qconfig -> prepare_qat -> optional BN freeze -> fine-tune with small LR and per-channel weights -> convert) is the standard, practical path to robust QAT in PyTorch.

Also covers (folded from merged near-duplicates): b666b8ef adds LR/regularization schedule + activation-clipping specifics.

Verification note: Verified via execution end-to-end on a real toy conv-bn-relu model: fuse_modules, QuantStub/DeQuantStub wrapping, prepare_qat, a real forward+backward pass through the fake-quantized model, and convert() to a genuinely quantized model, all completed successfully. NOTE (portability, not a code bug): get_default_qat_qconfig('fbgemm') only works on x86 - on this ARM test machine the only available engine is 'qnnpack' (confirmed via torch.backends.quantized.supported_engines), and running convert() with an 'fbgemm' qconfig on an ARM-only machine fails with RuntimeError: Didn't find engine for operation ... NoQEngine. The code's own comment already says 'use qnnpack on mobile' - worth stating even more explicitly that production code should select the engine from torch.backends.quantized.supported_engines rather than hardcoding one.

Direct answer
With 10,000 labeled examples, limited compute, and a monthly retraining cadence, a compact pretrained CNN backbone (rather than a Vision Transformer) fine-tuned via a cheap, staged strategy is the right choice, since CNNs' stronger built-in inductive bias converges faster with less data, and a lightweight fine-tuning approach keeps each monthly retrain fast and low-risk.

Structured elaboration
Model family: a pretrained CNN (e.g. an EfficientNet-B0/B2 or ResNet50-class backbone) generally outperforms a Vision Transformer at this data scale, since ViTs' weaker built-in locality/translation-equivariance bias means they typically need substantially MORE labeled data (or much heavier pretraining) than a CNN to reach comparable accuracy; 10,000 examples is squarely in the regime where a CNN's stronger prior pays off.
Fine-tuning strategy, staged for monthly retraining specifically: an initial CHEAP stage freezes the backbone entirely and trains only a new classification head, which is fast enough to re-run every month with minimal compute; if validation performance plateaus below what's needed, a SECOND, more expensive stage unfreezes the last few blocks with a discriminatively lower learning rate for those pretrained layers versus the head. For the ONGOING monthly cadence specifically, a lightweight ADAPTER-based approach (inserting small trainable adapter modules into an otherwise-frozen backbone, training only the adapters plus the head) is worth strong consideration, since it keeps each monthly retrain both fast and low-risk of catastrophic forgetting relative to repeatedly fully fine-tuning the whole network from a moving checkpoint.
Deployment: distilling the fine-tuned model into a smaller student (or applying post-training quantization) keeps serving cost and latency controlled independent of how the training-side model evolves month to month.

Worked example
A concrete monthly operational pattern: month 1 does a full staged fine-tune (frozen-backbone head training, then a partial-unfreeze pass) from the pretrained CNN checkpoint; months 2 through 4 WARM-START from the PREVIOUS month's fine-tuned checkpoint and retrain only the head or adapters on the newly accumulated data (cheap, fast); a full partial-unfreeze pass is repeated only quarterly, or immediately if a validation-drift monitor flags a meaningful accuracy or calibration regression between the cheap monthly updates.

Trade-offs & pitfalls
A common mistake is fully re-fine-tuning the entire backbone from scratch (or from the ORIGINAL pretrained checkpoint, discarding prior months' adaptation) every single month regardless of whether the data has actually shifted meaningfully; this wastes compute relative to warm-starting from the previous month's checkpoint, and can even introduce MORE month-to-month instability in production behavior than a lighter, incremental update would. A second common gap is skipping post-deployment monitoring specifically FOR the retraining cadence itself (accuracy, calibration, and data-drift metrics tracked monthly, not just once at initial launch); without this, a silent regression introduced by one month's retrain could persist undetected until the NEXT month's cycle, since nothing else in the pipeline would otherwise catch it between cadence cycles.

Proposal: Architectural changes — implement a lakehouse with curated, privacy-preserving feature stores and nearline materialized views to serve analysts quickly; add event streaming + real-time aggregation layer and self-service sandboxed query endpoints. Process changes — introduce "fast-path" templates for common analyses, standardized measurement libraries, and analyst-run model templates. Governance — strict privacy templates, automated lineage and schema checks, RBAC for sensitive datasets, and a rapid-approval path for low-risk requests. Operationally, enable CI for analytics (tests for data quality and instrumentation) and provide runbooks. Estimate risks: biggest engineering risk is building reliable nearline pipelines without increasing maintenance (risk: data drift/consistency); biggest organizational risk is change resistance and misuse of faster access leading to privacy mistakes. Mitigations: phased rollout with pilots, tight monitoring, enforcement of automated privacy checks, and training. Expected outcome: reduce time-to-insight by caching common aggregates, streamlining request-to-delivery workflows, and empowering PMs with vetted self-serve tools while keeping privacy controls intact.

Approach

Quadratic probing is open addressing (every entry lives directly in one flat array, no linked chains) where a collision at the home slot is resolved by trying home + 1^2, home + 2^2, home + 3^2, ... modulo the table capacity, instead of the fixed stride double hashing would use. The quadratic step spreads consecutive colliding keys apart quickly, which avoids the long runs of adjacent occupied slots that plain linear probing (home + 1, home + 2, ...) produces (a problem known as primary clustering). Deletes cannot just null out a slot, because a later key may have probed past it; a tombstone marker keeps get probing through a deleted slot while letting put reclaim it.

Code (Java)

public class QuadraticProbingMap {
    private static final Object TOMBSTONE = new Object();
    private Object[] keys;
    private Object[] values;
    private int capacity, size, used;

    public QuadraticProbingMap(int capacity) {
        this.capacity = capacity;
        this.keys = new Object[capacity];
        this.values = new Object[capacity];
    }

    private int home(Object key) {
        return (key.hashCode() & 0x7fffffff) % capacity;
    }

    public void put(String key, Integer value) {
        if ((double) (used + 1) / capacity > 0.6) resize();
        int base = home(key), firstTombstone = -1;
        for (int i = 0; i < capacity; i++) {
            int slot = (int) (((long) base + i * i) % capacity);
            if (keys[slot] == null) {
                int target = (firstTombstone != -1) ? firstTombstone : slot;
                if (keys[target] == null) used++;
                keys[target] = key; values[target] = value; size++;
                return;
            } else if (keys[slot] == TOMBSTONE) {
                if (firstTombstone == -1) firstTombstone = slot;
            } else if (keys[slot].equals(key)) {
                values[slot] = value;
                return;
            }
        }
        throw new IllegalStateException("table full, resize invariant violated");
    }

    public Integer get(String key) {
        int base = home(key);
        for (int i = 0; i < capacity; i++) {
            int slot = (int) (((long) base + i * i) % capacity);
            if (keys[slot] == null) return null;
            if (keys[slot] != TOMBSTONE && keys[slot].equals(key)) return (Integer) values[slot];
        }
        return null;
    }

    public boolean remove(String key) {
        int base = home(key);
        for (int i = 0; i < capacity; i++) {
            int slot = (int) (((long) base + i * i) % capacity);
            if (keys[slot] == null) return false;
            if (keys[slot] != TOMBSTONE && keys[slot].equals(key)) {
                keys[slot] = TOMBSTONE; values[slot] = null; size--;
                return true;
            }
        }
        return false;
    }

    private void resize() {
        Object[] oldKeys = keys, oldValues = values;
        capacity = nextPrime(capacity * 2);
        keys = new Object[capacity]; values = new Object[capacity];
        size = 0; used = 0;
        for (int i = 0; i < oldKeys.length; i++) {
            if (oldKeys[i] != null && oldKeys[i] != TOMBSTONE) put((String) oldKeys[i], (Integer) oldValues[i]);
        }
    }

    private static boolean isPrime(int n) {
        if (n < 2) return false;
        for (int i = 2; (long) i * i <= n; i++) if (n % i == 0) return false;
        return true;
    }

    private static int nextPrime(int n) {
        int candidate = Math.max(n, 2);
        while (!isPrime(candidate)) candidate++;
        return candidate;
    }

    public int size() { return size; }
    public int capacity() { return capacity; }

    public static void main(String[] args) {
        QuadraticProbingMap m = new QuadraticProbingMap(11);
        m.put("x", 1); m.put("y", 2); m.put("z", 3);
        System.out.println("get x -> " + m.get("x"));
        System.out.println("get missing -> " + m.get("nope"));
        m.remove("y");
        System.out.println("get y after remove -> " + m.get("y"));
        m.put("w", 4);
        System.out.println("get w -> " + m.get("w"));
        System.out.println("get x still resolves past tombstone -> " + m.get("x"));
        for (int i = 0; i < 25; i++) m.put("k" + i, i * 5);
        System.out.println("size -> " + m.size() + " capacity -> " + m.capacity());
        boolean allCorrect = true;
        for (int i = 0; i < 25; i++) if (!Integer.valueOf(i * 5).equals(m.get("k" + i))) allCorrect = false;
        System.out.println("all 25 post-resize keys correct -> " + allCorrect);
        System.out.println("z survived resize -> " + (m.get("z") == 3));
        System.out.println("y stays deleted after resize -> " + (m.get("y") == null));
    }
}

Output (compiled with javac and executed as shown; starting capacity 11):

get x -> 1
get missing -> null
get y after remove -> null
get w -> 4
get x still resolves past tombstone -> 1
size -> 28 capacity -> 47
all 25 post-resize keys correct -> true
z survived resize -> true
y stays deleted after resize -> true

Key points

• Collision resolution choice: quadratic probing was chosen over linear probing specifically to avoid primary clustering (long runs of adjacent full slots that make every new insertion near that run progressively more expensive), at the cost of a subtler risk covered below. It was chosen over chaining because the goal here is to keep every entry inside one contiguous array, which is more cache-friendly (fewer pointer chases) and avoids per-entry node allocation.
• Tombstones on delete: remove marks the slot with TOMBSTONE rather than null, so get keeps probing past it (confirmed above: x still resolves after y's slot becomes a tombstone), while put is free to reuse that slot for a new key (w reuses y's old slot).
• Resize and rehashing: capacity grows to the next prime at least double the old size once used (live entries plus tombstones) crosses 60% of capacity; every live entry is walked and reinserted, and tombstones are dropped in the process, reclaiming their space.
• Memory implications: open addressing stores keys and values directly in two flat arrays with no per-entry node object and no next-pointer, which is more memory-efficient per live entry than chaining (which pays for a node object per entry) as long as the load factor is kept reasonably low; the cost is that the array itself must always be sized somewhat larger than the live entry count (here, never let past 60% full), whereas chaining can, in principle, run at a load factor above 1.0 with only a linear degradation in bucket length.

Complexity

• Average case, put/get/remove: (O(1)), given a good hash and the load factor kept under the resize threshold.
• Worst case: (O(n)), a table with heavy clustering or many tombstones can force a long probe sequence.
• Resize: (O(n)) when triggered, but (O(1)) amortized per insert, by the same doubling argument as any doubling hash table: total rehashing work across all resizes up to (n) inserts is bounded by a constant multiple of (n).

Edge cases and pitfalls

• The quadratic-probing coverage limitation: for home + i^2 mod capacity with a prime capacity, i and capacity - i produce the same residue, so the probe sequence for i = 0, 1, 2, ... visits only about half of the table's slots before repeating, not all of them. A load factor of 0.6 is inside the danger zone for this: it is possible (though not certain, and it did not occur in the run above) for put to fail to find a free slot even though the table is well under 100% full, because the reachable half happens to be occupied. The safer engineering choice is either to cap the load factor nearer 0.5 for this exact probing formula, or use a probing sequence proven to cover every slot, such as triangular-number probing (i(i+1)/2) on a power-of-two-sized table.
• Deleting then reusing a slot for an unrelated key: must not break lookups for keys whose probe sequence passes through that slot (verified above).
• A key that was never inserted: the probe sequence hits an empty (null) slot and both get and remove correctly report absence.
• A table saturated with tombstones but few live entries: resizing on used, not size, prevents probe sequences from silently degrading even when the map looks small from the outside.

Requirements and constraints:

• Explore combinatorial search over 2^100-ish space using backtracking (prune by score/constraints).
• Must scale horizontally, support preemption/resume, deterministic reproducibility, progressive best-result aggregation, low coordinator bottleneck.

High-level architecture:

• Master (lightweight scheduler + global state), Workers (execute tasks), Distributed storage (object store for checkpoints — e.g., S3 or Ceph), Metadata DB (consistent task registry — e.g., PostgreSQL or etcd), Result store + aggregator service.

Partitioning the search tree:

• Represent search as depth-first backtracking over ordered features [0..99]. Partition by fixed prefix: each task = explore subtree where first k decisions are fixed (k chosen to make subtree approx target work units). Use adaptive splitting: start with k small, measure subtree size/time, then refine split depth.
• Encode a task as (prefix bitmask, next_index, pruning_bounds).

Checkpointing partial states:

• Workers periodically create incremental checkpoints: (prefix, stack of decisions, local heuristics state, RNG seed, best-so-far within subtree). Store as compact binary blobs in object store with unique IDs. Use write-once immutable checkpoint artifacts and metadata in DB referencing them.
• Checkpoint frequency adjustable (time-based or node-count-based) to tradeoff overhead vs. lost work.

Work stealing:

• Workers pull tasks from a distributed ready queue. Idle worker requests task from master; master returns from global queue or issues a “steal token” to a busy worker.
• Busy worker can split its current subtree at a deeper prefix and publish one half as a new task (serialize checkpoint for stolen branch). Use leases to avoid duplicate work; tasks are claimed with lease TTL and re-queued on lease expiry.
• Use decentralized steal paths: if master overloaded, workers can query peer directories stored in etcd.

Deterministic reproducibility:

• Determinism requires: fixed feature ordering, deterministic pruning heuristics, and deterministic RNG seeds per task.
• Derive per-task RNG seed deterministically: global_seed XOR hash(prefix). Save seed in checkpoint. Ensure any nondeterministic operations (multithreading, unordered maps) avoided or deterministic-ordered.
• Version all code/config and include version id in checkpoints; refuse resume if code/config mismatches.

Progressive aggregation of best results:

• Maintain a distributed top-K structure in the metadata DB with atomic updates (compare-and-swap or serializable transactions). Workers push local best candidates periodically; aggregator merges and updates global best-so-far.
• Use pruning bound propagation: when global best improves, master broadcasts bound to workers to enable aggressive pruning.

Fault tolerance and correctness:

• Tasks are idempotent and resume from checkpoints. Use task leases and a retry policy. Garbage collect checkpoints after task completion and after global commit.
• To avoid double-counting results, use unique candidate IDs and idempotent upserts to result store.

Operational considerations:

• Autoscale workers by queue depth and average task time.
• Instrumentation: per-task runtime, nodes processed, prune rates to adapt partition size.
• Example tech stack: Kubernetes for workers, S3/MinIO for checkpoints, PostgreSQL/etcd for metadata, Redis for fast queues, Prometheus/Grafana for metrics.

Trade-offs:

• Larger prefix -> many small tasks (higher overhead) but better load balance. Smaller prefix -> fewer big tasks, simpler but risk stragglers.
• Checkpoint frequency balances restart cost vs. IO overhead.
• Centralized master simplifies coordination but is a single point of failure; can run active-passive with shared metadata.

This design yields scalable, resumable, and reproducible distributed backtracking search with progressive aggregation and robust work stealing.