ML Engineer interview prep

Short answer: Big O describes how an algorithm's running time or memory usage grows as the input size n increases, dropping constants and lower-order terms. It's an upper bound on the growth rate.

In detail:

Big O answers the question "what happens when n becomes very large?". We're not interested in the exact number of operations, only the nature of the growth. That's why O(2n + 100) simplifies to O(n), and O(3n² + n) — to O(n²).

The main growth classes (from best to worst):

# O(1) — constant: doesn't depend on n
def first(arr):
    return arr[0] if arr else None

# O(log n) — logarithmic: each step halves the problem (binary search)
def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

# O(n) — linear: a single pass
def total(arr):
    s = 0
    for x in arr:        # n iterations
        s += x
    return s

# O(n log n) — efficient sorts (merge, quick, Timsort)
def sort_it(arr):
    return sorted(arr)

# O(n^2) — quadratic: a nested loop
def has_dup_naive(arr):
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            if arr[i] == arr[j]:
                return True
    return False

# O(2^n) — exponential: naive Fibonacci, enumerating subsets
def fib_naive(n):
    if n < 2:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)

A rough guide to growth at n = 1,000,000: O(1) — 1 operation, O(log n) — ~20, O(n) — a million, O(n log n) — ~20 million, O(n²) — a trillion (already too much), O(2^n) — infeasible even at n = 50.

⚠️ Gotcha: Big O is about asymptotics (behavior at large n), not about actual time. An O(n) algorithm can be slower than an O(n²) one on small data because of large constants. People also confuse: Big O (upper bound), Ω (lower bound), Θ (tight bound); in interviews "O" usually means Θ.

Short answer: Overfitting means the model learned the noise of the training set instead of the pattern: low error on train, high error on new data. You detect it via the train/validation gap and fix it with regularization, a simpler model, early stopping, and more data.

In depth:

1. Detection — compare train vs validation error; learning curves: train error keeps falling while validation error stalls or rises → the model started memorizing noise.
2. Treatment — reduce capacity or add signal, don't just chase the metric.

	Detect	Fix
Metric gap	train ≈ 0, validation clearly worse	regularization (L1/L2), simpler model
Learning curves	curves diverge as training goes on	early stopping
Cross-validation	unstable metrics across folds	more data, augmentation
Model complexity	deep trees, millions of weights	limit depth, prune features

⚠️ Common mistake: saying "cross-validation prevents overfitting." CV only detects it — it gives an honest quality estimate. Prevention comes from regularization, simpler models, and data.

Short answer: Greedily: at each node it scans features and thresholds and picks the split with the largest impurity reduction (Gini or entropy; MSE for regression). With unlimited depth the tree drives leaves to purity — i.e. it memorizes the training set, noise included.

In depth:

1. Split criterion — the gain: impurity(parent) − weighted impurity(children); Gini G = 1 − Σpₖ², entropy −Σpₖ·log pₖ — nearly interchangeable in practice.
2. Greediness — each node is optimized in isolation; the globally optimal tree is NP-hard, so a bad split near the root is never revisited.
3. Why overfitting — the model is piecewise-constant: with unlimited depth every leaf shrinks to a single sample → zero training error, high variance on test.

Constraint	What it does
max_depth	caps the number of levels
min_samples_leaf	stops leaves shrinking to 1 sample
ccp_alpha (pruning)	cuts nodes that don't pay for their complexity
Ensembles	RF/boosting turn the tree's weakness into strength

⚠️ Common mistake: believing the tree finds the globally "best partition" — it's greedy, and that's a fundamental limitation, not an implementation detail.

Short answer: Precision = TP/(TP+FP) — the share of true positives among everything the model flagged as positive. Recall = TP/(TP+FN) — the share of actual positives the model found. Recall is critical where a miss is costly (cancer screening, fraud); precision where a false alarm is costly (spam filters, content takedowns).

In depth:

	Actual: 1	Actual: 0
Predicted: 1	TP	FP
Predicted: 0	FN	TN

1. Precision — read the "predicted: 1" row: how many of the model's alerts are real. The cost-of-false-alarm metric.
2. Recall — read the "actual: 1" column: what fraction of real positives we caught. The cost-of-a-miss metric.
3. Trade-off via the threshold — on a fixed dataset, lowering the threshold cannot decrease recall, but precision can rise or fall depending on the labels of the newly included observations. For scores 0.9 (negative) and 0.8 (positive), lowering the threshold from 0.9 to 0.8 increases precision from 0 to 1/2. Evaluate the actual precision–recall curve instead of assuming monotonic precision.

⚠️ Common mistake: reciting the formulas and stopping. A strong answer starts from "which is more expensive — a miss or a false alarm", and only from that decides which metric leads.

Source: scikit-learn: precision–recall curve.

Short answer: Scaling matters for models that rely on distances, dot products, or gradient descent: kNN, SVM, k-means, PCA, regularized linear models, neural nets. Trees, forests, and boosting don't need it — they are invariant to monotone transforms.

In depth:

Model	Scaling	Why
kNN, k-means, SVM	required	distances: a feature in meters drowns out one in kilometers
PCA	required	variance: components chase the feature with the largest scale
Linear + L1/L2	required	the weight penalty depends on feature scale
Neural nets	needed	gradient descent convergence
Trees / RF / boosting	not needed	threshold splits; value order doesn't change

And the key point: the scaler is part of the model. Fit on train only, transform valid/test — otherwise test statistics leak into training.

⚠️ Common mistake: scaling everything "just in case" before the split — a harmless habit turns into leakage; and conversely, wasting time scaling for XGBoost.