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.

EasyTechnical

88 practiced

You have a continuous stream of billions of user events per day but budget allows keeping only 1% of raw events. Design a summarization pipeline that supports anomaly detection and heavy-hitter identification under the 1% storage constraint. Discuss algorithms (count-min sketch, bloom filters, reservoir sampling, t-digest), error characteristics, and how you'd evaluate the system for precision/recall under memory limits.

Sample Answer

Approach: build a multi-stage, space-budgeted summarization pipeline that keeps (a) a 1% reservoir of raw events for ground-truth/labeling, and (b) compact sketches for streaming analytics (heavy-hitters, quantiles, anomaly signals). Use time-windowed summaries (e.g., 1m/5m/1h) to detect temporal anomalies.

Pipeline components:- Ingest + sampling: reservoir sampling stratified by key (user, region, event-type) to ensure the 1% retained raw events are representative across important strata. Keep metadata (timestamp, key, features).- Heavy-hitter detector: Count–Min Sketch (CMS) per time window (or hierarchical CMS by key prefix). Use width w and depth d so error ≤ εN with probability 1−δ (w = e/ε, d = ln(1/δ)). CMS is O(1) update, small memory, overestimates counts.- Cardinality/membership: Bloom filters for approximate set membership (e.g., new user flags) with chosen false-positive rate.- Quantiles/latency distributions: t-digest per window to estimate percentiles (P50/P95/P99) with bounded error and mergeability.- Anomaly scoring: combine signals — sudden count increases from CMS, new patterns via bloom-set growth, and quantile jumps from t-digest. Use the 1% reservoir to compute true metrics for supervised anomaly model / calibrate thresholds.

Error characteristics & trade-offs:- Reservoir sampling: unbiased sample but high variance for rare subgroups; stratification reduces variance for keys of interest.- CMS: never underestimates, overestimation ∼ additive εN. Collisions hurt low-frequency items less predictably — choose ε small enough for desired precision on threshold.- Bloom filter: false positives controlled by bit array size k; no false negatives.- t-digest: excellent for extremes with limited memory, but accuracy decreases with extremely heavy tails; choose compression parameter.

Evaluation strategy under memory limits:- Offline replay + synthetic injection: replay historical stream at scale, inject labeled anomalies (spikes, drops, slowdowns) and measure detection.- Metrics: precision/recall for heavy-hitter detection (top-k); true/false positive rates for anomaly alerts; error in percentile estimates (absolute error or KL divergence).- Budget experiments: sweep memory allocations (CMS w/d, bloom size, t-digest compression, reservoir fraction) and plot Precision@k vs memory; choose operating point maximizing recall subject to acceptable false-positive rate.- Use reservoir as ground truth: compute exact counts/percentiles on the sampled raw set and correct for sampling when possible (e.g., Horvitz–Thompson estimators) to estimate true metrics and calibrate sketch thresholds.

Example knobs:- If top-100 must be ≥90% precision, tune CMS ε to make additive error < count_threshold; increase reservoir stratification for low-frequency but important keys.

This design balances rigorous probabilistic summaries with a small retained raw set for calibration, enabling reliable heavy-hitter and anomaly detection under a strict 1% storage constraint.

MediumSystem Design

67 practiced

Design a training pipeline when network bandwidth between datacenters is limited (e.g., 10 Gbps) and cross-data-center synchronization must be minimized. Data is partitioned by region but you need a global model. Discuss architecture choices (federated learning, parameter server with periodic aggregation, asynchronous SGD, gradient compression/sparsification), trade-offs in accuracy and freshness, and a deployment plan to meet a fixed cost budget.

Sample Answer

Requirements & constraints:- Regional data partitions; need a single global model.- Inter-datacenter bandwidth limited (~10 Gbps) and costly => minimize cross-DC sync.- Budget cap on cross-region transfers and compute.

High-level options (trade-offs):- Federated learning (local training, periodic model aggregation): minimal raw-data transfer, privacy-friendly, but aggregation staleness and heterogeneous data cause slower convergence and possible accuracy loss.- Parameter server with periodic aggregation: simpler global state, periodic checkpoints reduce traffic but requires pushing/ pulling parameters; fresher than pure federated if frequency high (costs bandwidth).- Asynchronous SGD: low sync wait (faster), but can diverge under high staleness; suits low-latency intra-DC, risky across DCs.- Gradient compression/sparsification + quantization: reduces bytes for any scheme; introduces approximation error but often negligible with error-feedback.

Recommended architecture:- Hybrid federated-periodic-aggregation approach: 1. Local trainers in each region perform multiple local epochs on regional data. 2. Apply gradient compression (Top-k sparsification with 8-bit quantization and error accumulation) before any cross-DC send. 3. Once per N hours (tunable), regions upload compressed model deltas to a global aggregator (in a chosen home DC or multi-region aggregator with redundancy). 4. Aggregator performs weighted averaging (by data size) and pushes a compact global delta back. Use versioning and lightweight metadata to detect stragglers. 5. Optionally maintain an asynchronous intra-region parameter server for fast local sync.

Why this choice:- Minimizes cross-DC traffic by sending infrequent, compressed deltas.- Weighted averaging handles regional skew.- Local multiple epochs improve sample efficiency, lowering required sync frequency.

Accuracy vs freshness trade-offs:- Increasing local epochs or compression reduces bandwidth but increases staleness and potential accuracy drop.- Tune N (aggregation interval) and compression ratio; run experiments measuring validation loss vs network cost to find knee-point.- Use adaptive strategies: more frequent sync for model cold-start; reduced frequency in steady state.

Deployment plan within fixed budget:1. Baseline: measure model convergence with no compression and daily aggregation → get bandwidth and compute baseline.2. Experimentation: try Top-1/Top-10% sparsification, 8-bit quantization, local epochs = {1,5,10}. Track accuracy delta and bytes transferred.3. Choose config meeting budget with <X% accuracy degradation threshold.4. Rollout phases: - Canary: single region + aggregator, monitoring convergence and latencies. - Gradual regional rollout with telemetry (per-region validation, drift). - Auto-tune: monitor network costs and model drift; adapt aggregation frequency/compression.5. Reliability: use checkpointing, retryable uploads, and secure transfers (TLS). Maintain warm standby aggregator to avoid single-point failure.

Monitoring & metrics:- Per-region training throughput, bytes transferred, model staleness (version lag), validation AUC, global convergence rate, and cost per sync.- Alert on divergence, bandwidth spikes, or exceeding budget.

Extensions:- If stricter privacy needed, add secure aggregation (adds compute overhead) or differential privacy (increases noise).- If budget allows, add CDN-like aggregator hierarchy: aggregate intra-continent then global to further reduce cross-continental traffic.

Summary:Hybrid federated + periodic compressed aggregation balances bandwidth limits and global accuracy. Key levers: local epoch count, aggregation frequency, compression level. Use small-scale experiments to find the cost/accuracy sweet spot, then rollout with monitoring and adaptive tuning.

HardTechnical

78 practiced

You're training a recommendation model with a categorical feature space of 100M unique keys and embedding size 128, which cannot fit in GPU memory. Design and provide pseudo-code for an efficient embedding lookup and training strategy that uses CPU memory with SSD-backed cache and hot-key caching on GPU, and uses sampled softmax or negative sampling during training to limit memory and compute pressure. Discuss trade-offs and consistency issues.

Sample Answer

Approach: Keep the full 100M×128 embedding table in CPU RAM (or memory-mapped SSD if RAM insufficient), use an SSD-backed LRU cache for less-frequent keys, and a GPU hot-key cache for the small set of high-frequency keys per mini-batch. During training, load only required keys for the batch (features + sampled negatives) into GPU, compute forward/backward, and asynchronously write sparse gradients back to CPU table. Use sampled softmax / negative sampling to limit number of negative embeddings needed per batch.

Pseudo-code (Python-like):

python

# Assume: EmbTable is memory-mapped (np.memmap) or in-RAM dict
# GPUCache is a small dict of key->tensor on GPU with LRU eviction
# SSDCache wraps memmap for persistence and faster partial reads
def train_step(batch_keys, model, k_neg=100):
    # 1. Construct sampling set: positives + sampled negatives
    neg_keys = sample_negatives(k_neg, batch_size=len(batch_keys))
    keys_needed = unique(batch_keys + neg_keys)

    # 2. Ensure keys present in GPU cache (async prefetch)
    missing = [k for k in keys_needed if k not in GPUCache]
    for k in missing:
        emb = SSDCache.read_or_load(k)      # fast read from SSD or memmap
        GPUCache.insert(k, emb.cuda())      # may evict LRU -> writeback flag

    # 3. Build embedding matrix for this batch
    emb_matrix = stack([GPUCache[k] for k in keys_needed])

    # 4. Forward + sampled-softmax / negative-sampling
    outputs = model.forward(emb_matrix, ...)
    loss = sampled_softmax_loss(outputs, targets, negatives=neg_keys)

    # 5. Backprop: compute sparse grads for used keys
    loss.backward()
    grads = collect_sparse_grads(keys_needed)

    # 6. Async writeback: update CPU/SSD table, mark dirty for eviction
    for k, g in grads.items():
        GPUCache[k] -= lr * g
        async_write_to_CPU(k, GPUCache[k].cpu())  # batched/aggregated writes

    # 7. Eviction policy persists evicted embeddings to SSD/CPU

Key design points and trade-offs:- CPU/SSD memmap allows storing 100M keys cheaply; SSD adds latency vs RAM but scales cost-effectively.- GPU hot-cache minimizes PCIe transfers for hot keys but cache misses cost IO and latency; prefetching and batching misses reduces overhead.- Sampled softmax / negative sampling reduces number of negatives per batch from 100M to O(100), shrinking memory and compute.- Async gradient writeback and batched updates reduce PCIe/IO pressure but introduce staleness; acceptable with small learning rates or with consistency controls (versioning, locking, or merging updates on CPU).Consistency and correctness issues:- Staleness: GPU may use slightly stale embeddings; mitigate with frequent sync for very hot keys or bounded staleness protocols (e.g., apply delayed gradients with timestamp checks).- Race conditions: concurrent updates from multiple GPUs require atomic updates or parameter server/batched aggregation; use sharded CPU partitioning and per-key locks or lock-free accumulators.- Fault tolerance: persist SSD checkpointing and replay buffered updates on restart.

Complexity:- Per-step IO proportional to unique(keys_needed) misses; design to keep miss rate low (hot-set << GPU cache size).- Negative sampling reduces compute from O(Vocab) to O(k).

MediumTechnical

70 practiced

You are forbidden from using any external pre-trained models or weights and have limited compute and labeled data. Propose a practical training strategy to reach acceptable performance: consider architecture selection, strong data augmentation, synthetic data generation, self-supervised pretraining on unlabeled in-domain data, active learning, and validation methodology given compute limits.

Sample Answer

Situation: Small labeled dataset, no external pretrained weights, limited compute.

Strategy (high-level goals): maximize signal from unlabeled/in-domain data, enlarge effective labeled set cheaply, and use efficient models + careful validation to avoid wasted compute.

Architecture:- Start with a lightweight, well-regularized backbone (e.g., MobileNetV3 / EfficientNet-lite or a small ResNet) to reduce training time and overfitting.- Use depthwise separable convolutions and mixed-precision training.

Self-supervised pretraining:- Pretrain on all available unlabeled in-domain data with contrastive or instance discrimination methods (SimCLR-style with large augmentations) or BYOL/SwaV variants that avoid negative pairs to be compute-friendly.- Use smaller batches with longer augmentations and cosine LR; freeze lower layers initially when fine-tuning.

Strong data augmentation:- Apply domain-appropriate heavy augmentations (RandAugment, MixUp, CutMix, style augmentations) to increase robustness.- Use test-time augmentation ensembles only if inference budget allows.

Synthetic data generation:- Use lightweight generative approaches: classical transformations, render-based augmentation, or simple GANs/VAEs trained on-domain to produce labelled variants; prioritize rule-based synthetic labeling where possible (e.g., geometric transforms, programmatic labels).

Active learning:- Iteratively label most informative samples (uncertainty sampling + diversity via embeddings) in small batches to get maximal benefit per label.- After each labeling round, fine-tune from the previous checkpoint rather than retraining from scratch.

Compute-aware training & validation:- Use progressive resizing (train on smaller images, then fine-tune at full resolution).- Early stopping based on a hold-out validation set; use cross-validation folds if compute allows but prefer stratified small validation to monitor overfitting.- Track calibration and per-class metrics; use learning rate warmup, weight decay, and label smoothing.

Trade-offs & monitoring:- Prioritize methods that reuse checkpoints (fine-tuning, continual active loops).- Monitor marginal gains per compute/time; stop or switch strategies when returns diminish.

This pipeline optimizes data efficiency and compute while steadily improving performance without external pretrained weights.

EasyTechnical

91 practiced

You must deploy an image classification model to an edge device that has 128MB total RAM, no GPU, and an average inference latency requirement of 50ms. You are not allowed to call cloud inference. Describe an end-to-end plan to fit and ship a model under these constraints: model selection, compression techniques, runtime choices (e.g., TFLite/ONNX), testing on-device, and rollout plan for updates.

Sample Answer

Plan overview: pick a tiny, efficient architecture, compress aggressively with quantization/pruning/distillation, run on a lightweight mobile runtime (TFLite/ONNX), thoroughly test on-device for latency/memory, then roll out staged OTA updates with monitoring and rollback.

Model selection- Start with MobileNetV3 Small or EfficientNet-Lite0 as base (low FLOPs, good accuracy/size tradeoff).- Target model binary + runtime < ~60–80MB to leave room for OS and app (128MB total RAM).

Compression techniques- Quantization: prefer full int8 (weights + activations) via quantization-aware training (QAT) to preserve accuracy.- Pruning: structured pruning to remove channels/filters, followed by fine-tuning.- Knowledge distillation: train a small student model using a larger teacher to regain accuracy after compression.- Weight clustering + gzip packaging for storage size.

Runtime choices- Use TensorFlow Lite with XNNPACK and int8 delegate; if device is MCU-like, use TFLite Micro or CMSIS-NN. Alternatively, ONNX Runtime Mobile with NNAPI delegate if supported.- Convert with TFLite converter: enable QAT results or post-training int8 with a representative dataset for calibration.

On-device testing- Create a representative input dataset; measure: - Peak RAM during model load + inference - End-to-end latency (cold start and steady-state) — aim <50ms median and <75ms p95 - CPU utilization, thermal / power impact- Iterate: if latency >50ms, reduce channels, decrease input resolution (e.g., 224 → 160), or use fewer layers.- Automate tests via CI that runs benchmarks on target hardware (or hardware lab).

Rollout and updates- Staged rollout: internal QA → 1% of devices → 10% → full fleet.- Build OTA package with versioning, signature verification, and atomic swap with rollback.- Telemetry: collect anonymized latency, memory, accuracy drift, and crash reports; include canary monitors.- Fast rollback path if telemetry shows regressions.

Metrics & acceptance- Target: model binary <10MB (int8), peak RAM <100MB, median latency <50ms, accuracy within 1–2% of baseline.- Keep a fallback lightweight heuristic or earlier model for emergency rollbacks.

Tools- TensorFlow Model Optimization Toolkit, TFLite converter, ONNX Runtime, x86 profiling and on-target benchmarks, CI for regression tests.

This plan balances accuracy, memory, and latency while providing safe rollout and observability.

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.