Algorithm Design Under Constraints Questions

Solving problems when strict constraints are present such as time limits, space limits, forbidden operations, or resource restrictions. Candidates should demonstrate understanding of trade offs, selecting appropriate algorithms or heuristics given constraints, reasoning about complexity and feasibility, and communicating why one approach is preferable under the given limitations.

HardTechnical

71 practiced

Scenario-based (hard): Design an active learning pipeline under a strict labeling budget of 1,000 labels for a multiclass classification task. Specify acquisition functions (uncertainty, diversity, expected model change), batching strategy, stopping criteria, and how to include weak labels or human-in-the-loop verification to maximize final model performance. Describe evaluation experiments you would run to tune the acquisition strategy before spending the full budget.

Sample Answer

**Situation & goals (1,000 labels):**Prioritize maximizing final multiclass accuracy / calibrated confidence under strict budget. Use a mixed acquisition strategy combining uncertainty, diversity, and expected model change (EMC); incorporate weak labels and human verification to stretch labels.

**Acquisition strategy**- Stage 0 (seed 200): stratified random seed to cover classes.- Iterative rounds (batch size 50–100): hybrid scoring - Uncertainty (0.5): class probability margin or entropy for exploitation. - Diversity (0.3): embedding-based k‑center or clustering with farthest-first to avoid redundancy. - Expected model change (0.2): approximate influence using gradient-norm on logits (cheap proxy for EMC).- Score = w1*Unc + w2*Div + w3*EMC; tune w via short sims.

**Batching**- Mini-batches 50–100 with per-class caps to avoid collapse.- Within batch, reserve 20% for low-confidence but high-diversity pool for human verification.

**Stopping criteria**- Primary: label budget exhausted.- Early stop: validation performance plateau for 3 rounds (delta < 0.25% accuracy) or confidence calibration no longer improving.

**Weak labels & human-in-loop**- Use weak sources (heuristics, weak models) to pseudo-label high-confidence examples; mark as lower-trust and use label smoothing / sample weighting.- Human verification: prioritize uncertain examples and samples where weak label conflicts with model prediction; have verification cascade: quick binary checks first, escalate ambiguous to experts.- Maintain provenance and use SSL (consistency regularization) with weak labels to propagate signal.

**Evaluation experiments before full budget**- Offline simulation using an held-out labeled pool: run budgeted simulations (e.g., 200, 400, 600 labels) to compare pure uncertainty, uncertainty+diversity, and uncertainty+EMC hybrids; measure final accuracy, F1, calibration, label efficiency.- Ablation on batch size and weightings w1,w2,w3.- Test weak-label policies: fraction to pseudo-label, weighting strategies, and verification cascade latency vs. gain.- Sensitivity to class imbalance: stratified runs.Use results to pick weights, batch size, verification thresholds before committing full 1,000 labels.

MediumTechnical

91 practiced

Theoretical: Explain gradient checkpointing (activation checkpointing). For a neural network with L layers, derive how checkpointing reduces peak activation memory and quantify the additional computation overhead in terms of recomputed layers. Discuss practical considerations when applying checkpointing to transformers or long RNNs on limited-memory GPUs.

Sample Answer

**Brief explanation / derivation**

- Baseline: storing all forward activations for backprop uses O(L * A) activation memory (A = per-layer activation size).- Checkpointing: split L layers into m segments of size s = L / m. Only keep activations at segment boundaries (checkpoints). During backward, recompute activations inside a segment from the last checkpoint.

Key formulas:

text

Peak activation memory ≈ O(m * C + s * A) ≈ O(s * A)

(usually C ≪ A so dominant term is s * A — activation memory proportional to segment size)

Choose s = sqrt(L) to balance memory vs recomputation:

text

s = sqrt(L)
Peak memory ≈ O(A * sqrt(L))
Recomputation per backward ≈ O(L) original forward + O(L) extra ≈ O(2 * L) ops → overhead ≈ O(sqrt(L)) in terms of recomputed layers per checkpointed segment

Plain-English: with the sqrt(L) split you reduce peak activation from proportional to L to proportional to sqrt(L), at the cost of recomputing ~sqrt(L) layers per segment (overall roughly doubling forward work for optimal split).

**Why it works**- You trade extra compute (rematerialize activations) for much lower memory by only storing a subset of activations and recomputing others on demand during backward.

**Practical considerations (Transformers / long RNNs on limited GPUs)**

- Transformers: checkpoint whole transformer blocks (e.g., every block or every k blocks). Attention stores O(seq_len^2) scratch; checkpointing reduces cross-layer activation memory but not per-layer attention scratch—combine with gradient accumulation, mixed precision, or blockwise attention (sparse/local) to fit long sequences.- RNNs: time dimension matters—checkpoint across timesteps (rematerialize subsequences) or use reversible RNNs to avoid storing hidden states. For very long sequences, combine checkpointing with truncated BPTT.- Overhead & throughput: recomputation increases latency and GPU utilization; measure wall-clock trade-offs. Use framework primitives (PyTorch torch.utils.checkpoint, DeepSpeed activation checkpointing) to avoid manual errors.- Mixed strategies: mixed-precision, activation compression, checkpointing + pipeline/model parallelism for best trade-offs.- Debugging & determinism: ensure recomputation is deterministic (no dropout randomness unless seeded consistently).

Takeaway: activation checkpointing reduces peak activation memory from O(L) to O(sqrt(L)) with roughly O(sqrt(L)) recomputation per segment (practically ~2x compute for the optimal split); combine with other memory techniques for transformers and long RNNs on memory-constrained GPUs.

EasyTechnical

134 practiced

In the context of constraint-based ML systems, explain Big-O, Big-Theta, and Big-Omega notation and why worst-case complexity matters when designing components under strict latency SLOs. Provide a short numeric comparison (estimates) between an O(n) algorithm and an O(n log n) algorithm for n = 1,000,000 and discuss the practical implications for an inference pipeline with limited CPU resources.

EasyTechnical

117 practiced

Explain gradient accumulation and how it enables effectively larger batch sizes when GPU memory is constrained. Provide the mathematical equivalence of gradient accumulation to a larger batch SGD step, and discuss trade-offs in training stability, wall-clock time, and learning rate scaling when using accumulation vs performing true large-batch training.

Sample Answer

**Definition & intuition**

Gradient accumulation batches multiple forward/backward passes with smaller micro-batches, summing (or averaging) their gradients before updating weights. This simulates a larger effective batch without storing all samples' activations at once, reducing peak GPU memory.

**Mathematical equivalence**

If you accumulate gradients over N micro-batches of size m (effective batch = B = N·m), and each micro-batch t yields gradient g_t = ∇L_t(θ), then the accumulated gradient G is:

text

G = 1 / N · sum_{t=1..N} g_t

A single SGD step with learning rate η using true batch B is:

text

θ_{new} = θ - η · (1 / N) · sum_{t=1..N} g_t

With accumulation you perform N backward passes, then:

text

θ_{new} = θ - η · G

Hence accumulation is mathematically identical to one SGD step on batch B (assuming gradients are averaged and no per-example operations like BatchNorm running stats differ).

**Trade-offs**

- Training stability: Large effective batches reduce gradient noise which can harm generalization; accumulation reproduces this effect. However, BatchNorm/statistics across micro-batches can differ — prefer SyncBatchNorm or use GroupNorm/LayerNorm.- Wall-clock time: More forward/backward passes increase compute-to-IO and may add overhead (optimizer step less frequent). You save memory, but total time can be higher than true large-batch if micro-batch size prevents kernel fusion or efficient GPU utilization.- Learning rate scaling: Same LR rules apply (linear scaling rule η' ≈ η·N sometimes), but tuning is still required. Warmup and smaller base LR often help; optimizer state (momentum) must be handled correctly (accumulate gradients and apply momentum once per effective step).

**Practical tips**

- Average gradients, not sum, to keep LR semantics.- Use accumulated-gradients-compatible optimizers (handle momentum correctly).- Monitor BatchNorm behavior or switch to statless norms.

EasyTechnical

76 practiced

Technical-coding (Python): You are not allowed to use external ML libraries. Implement a memory-efficient linear regression trainer using stochastic gradient descent that works when the dataset is streamed from disk (i.e., cannot fit in memory). The trainer should read data in minibatches, support L2 regularization, and log validation loss after each epoch. Include comments about how to handle streaming I/O and checkpointing in low-disk environments.

Sample Answer

**Approach (brief)** Use minibatch SGD reading lines from disk via a streaming generator. Maintain weight vector in memory (O(d)). Compute L2 regularized gradients, update with learning rate schedule, and evaluate validation loss by streaming validation file after each epoch. Support checkpointing via atomic overwrite and keep only latest checkpoint.

**Code (Python)**

python

import math, os, tempfile

def stream_csv(path):
    with open(path, 'r') as f:
        for line in f:
            parts = line.strip().split(',')
            if not parts or parts==['']: 
                continue
            # last column is target
            *xs, y = parts
            yield [float(v) for v in xs], float(y)

def dot(a, b):
    return sum(x*y for x,y in zip(a,b))

def sgd_train(train_path, val_path, d, epochs=5, batch_size=32, lr=0.01, l2=0.0, checkpoint_path=None):
    # initialize zero weights + bias as last element
    w = [0.0]*(d+1)  # w[:d], w[d] is bias
    step = 0

    def save_checkpoint(w):
        if not checkpoint_path: return
        # atomic write to avoid partial files
        dirn = os.path.dirname(checkpoint_path) or '.'
        fd, tmp = tempfile.mkstemp(dir=dirn)
        with os.fdopen(fd,'w') as f:
            f.write(','.join(map(str,w)))
        os.replace(tmp, checkpoint_path)  # atomic
        # keep only latest checkpoint to save disk

    def load_checkpoint():
        if not checkpoint_path or not os.path.exists(checkpoint_path): return None
        with open(checkpoint_path) as f:
            return [float(x) for x in f.read().strip().split(',')]

    # optional resume
    ck = load_checkpoint()
    if ck: w = ck

    for epoch in range(epochs):
        batch_X, batch_y = [], []
        for x, y in stream_csv(train_path):
            if len(x) != d:
                raise ValueError("feature dimension mismatch")
            batch_X.append(x)
            batch_y.append(y)
            if len(batch_X) >= batch_size:
                # compute gradient for minibatch
                grad = [0.0]*(d+1)
                for xi, yi in zip(batch_X, batch_y):
                    pred = dot(xi, w[:d]) + w[d]
                    err = pred - yi
                    for j in range(d):
                        grad[j] += err * xi[j]
                    grad[d] += err  # bias gradient
                # average and add L2 (not on bias)
                scale = 1.0/len(batch_X)
                for j in range(d):
                    g = grad[j]*scale + l2 * w[j]
                    w[j] -= lr * g
                w[d] -= lr * (grad[d]*scale)
                step += 1
                batch_X, batch_y = [], []
        # end of epoch: optional final partial batch
        if batch_X:
            grad = [0.0]*(d+1)
            for xi, yi in zip(batch_X, batch_y):
                pred = dot(xi, w[:d]) + w[d]
                err = pred - yi
                for j in range(d):
                    grad[j] += err * xi[j]
                grad[d] += err
            scale = 1.0/len(batch_X)
            for j in range(d):
                g = grad[j]*scale + l2 * w[j]
                w[j] -= lr * g
            w[d] -= lr * (grad[d]*scale)

        # validation loss (streamed)
        n=0; loss=0.0
        for x,y in stream_csv(val_path):
            pred = dot(x, w[:d]) + w[d]
            loss += 0.5 * (pred - y)**2
            n += 1
        val_loss = loss / max(1,n)
        print(f"Epoch {epoch+1}/{epochs} val_loss={val_loss:.6f}")
        save_checkpoint(w)
    return w

**Key concepts & reasoning**- Streaming: generator yields one example at a time; memory = O(d + batch_size). - L2: added to feature gradients (not bias) to penalize magnitude. - Validation: streamed separately to avoid loading into memory. - Checkpointing: atomic replace and keep single file to minimize disk.

**Complexity**- Per epoch time: O(N*d). Memory: O(d + batch_size*d).

**Practical notes**- For shuffled training when data is too large: buffer-based shuffle (read B examples into memory, shuffle, emit) or reservoir sampling for randomness. - In low-disk environments: compress checkpoints, upload to remote (S3) then delete local, and retain only latest checkpoint file. Use atomic writes to avoid corruption.

Unlock Full Question Bank

Get access to hundreds of Algorithm Design Under Constraints interview questions and detailed answers.

Join thousands of developers preparing for their dream job.