Machine Learning Algorithms and Theory Questions

Core supervised and unsupervised machine learning algorithms and the theoretical principles that guide their selection and use. Covers linear regression, logistic regression, decision trees, random forests, gradient boosting, support vector machines, k means clustering, hierarchical clustering, principal component analysis, and anomaly detection. Topics include model selection, bias variance trade off, regularization, overfitting and underfitting, ensemble methods and why they reduce variance, computational complexity and scaling considerations, interpretability versus predictive power, common hyperparameters and tuning strategies, and practical guidance on when each algorithm is appropriate given data size, feature types, noise, and explainability requirements.

MediumTechnical

25 practiced

Implement functions in Python to compute ROC and Precision–Recall (PR) curves from `y_true` and `y_scores` without using sklearn. Return arrays of thresholds and corresponding (TPR, FPR) for ROC and (precision, recall) for PR, and compute AUCs. Discuss how ties in scores affect both curves and numerical stability considerations.

Sample Answer

Approach:Sort examples by descending score, then sweep thresholds to compute cumulative TP/FP to produce TPR/FPR for ROC and precision/recall for PR. Use unique score breakpoints (including +inf and -inf) as thresholds. Compute AUC with trapezoidal rule. Handle ties by grouping equal scores — sweeping group-wise avoids unstable tiny steps. Use float64 and add eps where needed to avoid division by zero.

python

import numpy as np

def _prepare(y_true, y_scores):
    y_true = np.asarray(y_true, dtype=np.int32)
    y_scores = np.asarray(y_scores, dtype=float)
    if y_true.shape[0] != y_scores.shape[0]:
        raise ValueError("y_true and y_scores must have same length")
    # sort by score desc
    desc = np.argsort(-y_scores, kind="mergesort")  # stable sort preserves order within ties
    return y_true[desc], y_scores[desc]

def roc_pr_from_scores(y_true, y_scores):
    y_t, s = _prepare(y_true, y_scores)
    P = y_t.sum()
    N = y_t.size - P
    # unique score groups (preserve order)
    uniq_vals, start_idx = np.unique(s, return_index=True)
    # indices where score changes in descending order: start_idx are first occurrences in sorted desc order
    # We'll iterate over groups by their start positions
    thresholds = []
    tpr = []
    fpr = []
    precision = []
    recall = []

    tp = 0
    fp = 0
    idx = 0
    total = y_t.size

    # Add a threshold above max to get (0,0) start
    thresholds.append(np.inf)
    tpr.append(0.0)
    fpr.append(0.0)
    precision.append(1.0)   # by convention, precision=1 at zero positives predicted
    recall.append(0.0)

    # iterate groups of same score
    # find boundaries: for each unique starting index, group until next start or end
    starts = list(start_idx) + [total]
    for i in range(len(starts)-1):
        sidx = starts[i]
        eidx = starts[i+1]
        # count positives and negatives in this tied block
        block = y_t[sidx:eidx]
        tp += block.sum()
        fp += (block.size - block.sum())
        # threshold is current score value
        thresholds.append(s[sidx])
        rec = tp / P if P > 0 else 0.0
        fpr_val = fp / N if N > 0 else 0.0
        prec = tp / (tp + fp) if (tp + fp) > 0 else 1.0
        tpr.append(rec)
        fpr.append(fpr_val)
        precision.append(prec)
        recall.append(rec)

    # convert to arrays
    thresholds = np.array(thresholds)
    tpr = np.array(tpr)
    fpr = np.array(fpr)
    precision = np.array(precision)
    recall = np.array(recall)

    # compute AUCs via trapezoidal rule
    # ROC AUC integrate TPR vs FPR; ensure monotonic increasing FPR
    roc_auc = np.trapz(tpr, fpr)
    # PR AUC integrate precision vs recall: ensure recall is increasing
    pr_auc = np.trapz(precision[::-1], recall[::-1])  # integrate along increasing recall

    return {
        "thresholds": thresholds,
        "roc": {"fpr": fpr, "tpr": tpr, "auc": roc_auc},
        "pr": {"precision": precision, "recall": recall, "auc": pr_auc}
    }

Key points:- Time: O(n log n) dominated by sort. Space: O(n).- Ties: grouping equal scores produces a single step per tie block, matching sklearn behavior and avoiding many tiny vertical/horizontal steps. Using stable sort preserves deterministic ordering.- Numerical stability: use float64, handle P=0 or N=0 to avoid division by zero, set precision=1.0 when no predicted positives by convention, and include +inf threshold to represent predicting none positive.- Edge cases: all positives or negatives, duplicated scores, empty input, and very large arrays — use mergesort for stability and vectorized ops for performance.

HardTechnical

29 practiced

Case study: False positive manual-review cost is $50, false negative lost revenue is $200. Design a cost-sensitive ML approach to minimize expected operational cost: define expected cost, propose ways to incorporate costs at training time (reweighting or custom loss), choose operating threshold, and describe an A/B testing plan to validate business impact.

Sample Answer

Situation: We need to minimize operational cost where a false positive (FP) — sending a case to manual review — costs $50, and a false negative (FN) — missing a bad case — costs $200. Design must optimize expected cost end-to-end, from training through deployment and A/B validation.

Expected cost definition- For a binary classifier with threshold t, let P(y=1) be ground truth positive (bad case). Expected cost per decision: ExpectedCost(t) = C_FP * P(pred=1, y=0; t) + C_FN * P(pred=0, y=1; t) = C_FP * FPR(t) * P(y=0) + C_FN * FNR(t) * P(y=1)- We can estimate this from validation set empirical rates.

Incorporate costs at training time- Reweighting samples: assign weight w_pos and w_neg so the training objective emphasizes costly errors. Set ratio w_pos/w_neg ≈ C_FN/C_FP (e.g., 200/50 = 4) to penalize misclassifying positives more heavily.- Custom loss: use weighted cross-entropy or focal loss: Loss = - w_pos * y * log(p) - w_neg * (1-y) * log(1-p) with w_pos = C_FN and w_neg = C_FP (or normalized). For decision-centric optimization, implement a differentiable surrogate of expected cost (cost-weighted proper loss) so gradient aligns with business metric.- Alternative: train a calibrated probability model (e.g., logistic, isotonic calibration) without strong cost bias, then optimize threshold later — often more stable.

Choosing operating threshold- Using validation set, compute predicted probabilities p_i and sweep threshold t to minimize empirical ExpectedCost(t). Pick t* = argmin_t ExpectedCost(t).- Use cost curves, and account for class prior shifts by reweighting validation samples to expected production prevalence.- Add safety margin: if cost asymmetry is high, prefer conservative operating point and simulate worst-case prior shifts.

Evaluation and A/B testing plan- Offline validation: - Cross-validated expected cost, ROC/Precision-Recall, calibration plots. - Bootstrap confidence intervals on ExpectedCost(t*).- A/B test in production: - Split traffic clusters (or users) randomly into control (current policy) and treatment (new model+threshold t*). - Primary metric: per-case operational cost (sum of manual review costs + estimated lost revenue) normalized per unit/time. - Secondary metrics: manual-review volume, FN rate on sampled ground-truth (label sampling), latency, user impact. - Sample size: power the test to detect meaningful cost reduction (e.g., 5% relative) using baseline cost variance; compute N accordingly. - Run minimum duration to cover seasonality and obtain enough labeled outcomes (especially positives). - Safety guardrails: kill-switch if key metrics (e.g., FP rate, customer complaints) exceed thresholds.- Post-test analysis: - Use causal uplift and Bayesian A/B analysis to estimate expected cost savings with credible intervals. - Monitor model drift; recalibrate threshold periodically using recent labeled data.

Operational considerations- Ensure probability calibration before thresholding.- Monitor class prior drift, and recompute t* when prevalence changes.- Maintain explainability for manual reviewers; log decisions and features used for downstream auditing.

This approach directly optimizes expected operational cost by either biasing training (weights/custom loss) or by calibrating probabilities and picking the cost-optimal threshold, then validating impact via a statistically powered A/B test with clear metrics and safety controls.

EasyTechnical

27 practiced

Implement k-means clustering from scratch in Python. Your function should accept X (numpy array), k, max_iters, init='random' or 'kmeans++', random_seed and return centroids, labels, and inertia (sum of squared distances). Handle empty clusters robustly and explain complexity and typical failure modes.

Sample Answer

Approach: implement standard Lloyd's k-means with two init options (random sample or kmeans++), iterate assignment and update, handle empty clusters by re-seeding to the farthest point from its centroid (robust), and compute inertia (sum squared distances).

python

import numpy as np

def kmeans(X, k, max_iters=100, init='random', random_seed=None):
    """
    X: (n_samples, n_features) numpy array
    k: number of clusters
    returns: centroids (k, d), labels (n,), inertia (float)
    """
    rng = np.random.default_rng(random_seed)
    n, d = X.shape

    # init centroids
    if init == 'kmeans++':
        centroids = np.empty((k, d), dtype=X.dtype)
        centroids[0] = X[rng.integers(n)]
        closest_sq = np.sum((X - centroids[0])**2, axis=1)
        for i in range(1, k):
            probs = closest_sq / closest_sq.sum()
            idx = rng.choice(n, p=probs)
            centroids[i] = X[idx]
            dist_sq = np.sum((X - centroids[i])**2, axis=1)
            closest_sq = np.minimum(closest_sq, dist_sq)
    else:
        ids = rng.choice(n, size=k, replace=False)
        centroids = X[ids].copy()

    labels = np.full(n, -1, dtype=int)
    for it in range(max_iters):
        # assignment
        dists = np.linalg.norm(X[:, None, :] - centroids[None, :, :], axis=2)**2  # (n, k)
        new_labels = np.argmin(dists, axis=1)

        # if no change, stop
        if np.array_equal(new_labels, labels):
            labels = new_labels
            break
        labels = new_labels

        # update centroids
        for j in range(k):
            members = X[labels == j]
            if len(members) == 0:
                # handle empty cluster: re-seed to farthest point from its centroid set
                # choose point with max distance to its assigned centroid
                assigned_dists = dists[np.arange(n), labels]
                far_idx = np.argmax(assigned_dists)
                centroids[j] = X[far_idx].copy()
            else:
                centroids[j] = members.mean(axis=0)

    # final inertia
    final_dists = np.sum((X - centroids[labels])**2, axis=1)
    inertia = final_dists.sum()
    return centroids, labels, float(inertia)

Key points:- Complexity: each iteration O(n * k * d) for distance computations; total O(nkd * iters).- Space: O(nk) for distance matrix (can compute chunked to reduce memory).- Empty clusters handled by re-seeding to a furthest point (robust alternative to random).- Failure modes: sensitive to initialization and scales (use kmeans++ and feature scaling), can converge to local minima, struggles with non-spherical clusters or differing densities, and choice of k matters.

MediumTechnical

26 practiced

You have limited compute budget and need to tune XGBoost on 10M rows. Propose a practical hyperparameter tuning strategy that balances search quality and cost, including choices like smaller proxy datasets, early stopping, multi-fidelity optimization (successive halving), and warm-starting.

Sample Answer

Approach summary: use a multi-fidelity, prioritized search that starts on cheap proxies and progressively promotes promising configs to larger budgets, combined with smart search-space design and warm-starting to save compute.

1) Prepare proxies- Create smaller but representative datasets: stratified subsamples (e.g., 1%, 5%, 10% = 100k, 500k, 1M) and a feature/label distribution check. Keep the same preprocessing/feature pipeline so signal is consistent.- Use a validation holdout that mirrors production (time-aware if needed).

2) Prioritize hyperparameters- Fix low-impact params (tree_method if GPU available), tune high-impact ones: learning_rate, n_estimators (as budget parameter), max_depth, min_child_weight, subsample, colsample_bytree, lambda/alpha, scale_pos_weight.- Reparameterize: treat learning_rate+n_estimators jointly; search smaller learning rates with proportionally larger budgets.

3) Multi-fidelity search (Successive Halving / ASHA)- Run an ASHA-like scheduler: many configs at tiny budget (e.g., 100 boosting rounds on 100k rows), promote top X% to medium (500 rounds on 500k), finally evaluate top ones on full 10M with early stopping.- Use early stopping at each fidelity (e.g., 20 rounds patience) to cut runs that plateau.

4) Search algorithm & parallelism- Use random search or Bayesian optimization (BOHB) combined with ASHA for sample-efficiency. Random for initial broad coverage; BO/HPO to refine.- Parallelize workers across CPU/GPU; limit max concurrent full-scale runs.

5) Warm-starting and checkpointing- Warm-start by transferring best hyperparams from small to larger budgets; use xgboost’s incremental training (load model and continue boosting) when increasing rounds/budget to avoid retraining from scratch.- Persist checkpoints and metadata so interrupted runs resume.

6) Practical settings & monitoring- Use a conservative initial learning_rate (0.05-0.1) with early stopping; constrain max_depth (4-10) and subsample/colsample to reduce overfitting and cost.- Measure cost per epoch and set budget caps (e.g., max X hours). Track validation metric, training time, and resource utilization; abort or reduce fidelity if cost overruns.

Expected benefits & trade-offs- Big compute savings by discarding bad configs early and only evaluating few on full data.- Risk: proxy mismatch — mitigate by ensuring representative sampling and final validation on full data.- Final step: fine-tune small number (2–5) best configs on full dataset with longer early stopping to pick winner.

HardTechnical

21 practiced

Implement PCA using SVD in Python without calling sklearn.decomposition.PCA. Write `pca_svd(X, n_components=None)` that centers X, computes SVD, returns principal components, transformed data (scores), and explained variance ratio. Handle both cases when n_features > n_samples and vice versa efficiently.

Sample Answer

Approach: center X, then compute SVD efficiently. If n_samples >= n_features, do economy SVD on X_centered (U, S, Vt) and take Vt as components. If n_samples < n_features, compute eigen-decomposition (or SVD) of the smaller n x n matrix X X^T to get U and singular values, then recover components = (X_centered.T @ U) / S. Return components (principal axes), transformed data (scores = X_centered @ components.T), and explained variance ratio.

python

import numpy as np

def pca_svd(X, n_components=None, eps=1e-12):
    """
    PCA via SVD without sklearn.
    Returns: components (k, p), scores (n, k), explained_variance_ratio (k,)
    """
    X = np.asarray(X, dtype=float)
    n, p = X.shape
    # center
    mean = X.mean(axis=0)
    Xc = X - mean

    # max components
    max_k = min(n, p)
    if n_components is None:
        k = max_k
    else:
        k = min(int(n_components), max_k)

    if n >= p:
        # compute compact SVD on Xc: U (n x p), S (p,), Vt (p x p) with full_matrices=False
        U, S, Vt = np.linalg.svd(Xc, full_matrices=False)
        components = Vt[:k, :]                     # principal axes (k, p)
        scores = Xc @ components.T                 # (n, k)
    else:
        # n < p: compute SVD on X X^T (n x n) to get U and S, then recover V
        # Note: Xc @ Xc.T = U (n x n) * S^2 * U.T
        M = Xc @ Xc.T
        # eigen-decomp of M (symmetric) is cheaper: returns eigenvalues descending
        eigvals, U = np.linalg.eigh(M)
        # eigh returns ascending eigenvalues -> reverse
        eigvals = eigvals[::-1]
        U = U[:, ::-1]
        # numerical stability: singular values
        S_all = np.sqrt(np.clip(eigvals, 0, None))
        # keep top k where singular values > eps
        S = S_all[:k]
        U = U[:, :k]                               # (n, k)
        # components V = Xc.T @ U / S
        components = (Xc.T @ U) / (S.reshape(1, -1))  # (p, k) then transpose
        components = components.T                    # (k, p)
        scores = U * S.reshape(1, -1)                # (n, k)

    # explained variance: sigma^2 / (n - 1)
    # singular values S (length k). If we computed full S earlier, ensure using the right S
    # recompute singular values for consistency:
    # For n>=p branch S already available; for other branch S set above
    if n >= p:
        var_explained = (S[:k] ** 2) / (n - 1)
    else:
        var_explained = (S ** 2) / (n - 1)

    total_var = np.sum(np.var(Xc, axis=0, ddof=1))
    # handle degenerate total_var
    if total_var <= 0:
        explained_variance_ratio = np.zeros_like(var_explained)
    else:
        explained_variance_ratio = var_explained / total_var

    return components, scores, explained_variance_ratio

Key points:- components shape (k, n_features): each row is a principal axis.- scores = projection of centered data onto components.- Time complexity: O(min(n,p)^2 * max(n,p)). Using n x n eig when n << p reduces cost.- Edge cases: constant features (zero variance), n_components > min(n,p), numerical tiny singular values—handled via clipping and eps.- Alternative: randomized SVD for very large matrices (faster approximate PCA).

Unlock Full Question Bank

Get access to hundreds of Machine Learning Algorithms and Theory interview questions and detailed answers.

Join thousands of developers preparing for their dream job.