Problem Analysis & Optimization Questions
Core technical skills covering problem analysis, algorithmic thinking, and performance optimization. Includes evaluating time and space complexity, selecting appropriate data structures, designing efficient algorithms, and considering trade-offs to optimize software systems.
HardTechnical
49 practiced
You must run k-means clustering on 1M points in 100D. Propose algorithmic and implementation optimizations: k-means++ initialization, mini-batch k-means, Elkan's triangle inequality pruning, vectorized distance computation, and parallelization. Provide complexity estimates and explain which optimizations you would prioritize for speed and memory efficiency.
Sample Answer
Situation: We need to cluster 1M points in 100D — scale is large in n and moderate in d — so both CPU time and memory matter.Approach summary and practical pipeline:- Use scalable init: k-means++ is high-quality but O(nk) and costly; prefer k-means|| (a scalable, parallel approximation of k-means++) to get good seeds in O(n log n) work with few passes.- Use mini-batch k-means for training to reduce passes over data: sample batches b (e.g., 1k–10k) and perform many cheap updates; this gives near-competitive quality with much lower time.- Use vectorized distance computation leveraging BLAS / SIMD: compute squared Euclidean distances with (||x||^2 + ||c||^2 - 2 x·c) to reuse norms and do matrix multiply X·C^T for a batch.- Parallelization: data-parallel minibatches across CPU cores or GPUs. For distributed data, use Spark/MapReduce with local partial centroid sums + global reduction. Use asynchronous updates carefully for large clusters.- Elkan’s triangle-inequality pruning: very effective when k is small and clusters well-separated — reduces distance evals from O(nk) to much less. It has O(nk) memory for bounds; use only if k is modest (<~500) and you can afford extra memory for bounds.- Memory/IO: stream data in chunks, keep centroids in RAM (k×d floats). For 1M×100 at float32 that's ~400MB for data if loaded — better to stream or use mmap. Mini-batches avoid full dataset in memory.Complexity estimates:- Standard Lloyd: per iteration O(n k d) time, O(k d) memory.- k-means++ init: O(n k d) (one pass per center) — replace with k-means|| to make init ~O(n d log k) with parallel sampling.- Mini-batch: per batch O(b k d) per update; total runtime ≈ (#batches × b × k × d). Often converges in many fewer full-epoch equivalents.- Elkan pruning: amortized distance evals << n k; extra memory O(n k) for bounds (can be reduced with lazy updates).Which optimizations to prioritize:1. k-means|| initialization (speed + quality) — cheap to parallelize; prevents slow convergence.2. Mini-batch k-means with vectorized batch distance via GEMM (X_batch · C^T) using BLAS or GPU — biggest win for time and memory (streaming).3. Parallelize across cores/GPUs or distributed workers for batches; keep centroid reduce step synchronized.4. Use Elkan pruning only if k is small and clusters separable — otherwise overhead and memory not worth it.5. Further micro-optimizations: use float32, precompute norms, batch size tuning, early stopping by centroid movement threshold.Concrete numbers example (k=1k, b=5k):- Per batch BLAS cost: multiply 5k×100 by 100×1k => ~5e8 multiply-adds per batch; on GPU this is fast; on CPU use optimized MKL.- Memory: centroids 1k×100×4B ≈ 0.4MB; bounds for Elkan (if used) ~1M×1k floats (impractical) so don't use for large k.Trade-offs: mini-batch sacrifices some clustering quality for massive speed; k-means|| + fewer full Lloyd iterations recovers quality. Elkan gives fewer distance ops but large memory; useful only for small k. Vectorization + parallelism are universally high priority.
EasyTechnical
62 practiced
Implement reservoir sampling (Algorithm R) in Python to uniformly sample k items from a stream of unknown and potentially massive length that cannot fit in memory. The function should accept items one-by-one via an iterator, maintain only O(k) memory, and return a uniform sample at the end. Explain correctness and analyze time & space complexity.
Sample Answer
To sample k items uniformly from a stream of unknown length, use Reservoir Sampling (Algorithm R): keep the first k items in a reservoir, then for the i-th incoming item (i starting at k+1), with probability k/i replace a random item in the reservoir.Why correct (sketch): By induction, after processing i items, each item seen so far has probability k/i of being in the reservoir. Base: first k items have prob 1 = k/k. Step: for i+1, an existing item stays with prob (k/i) * (1 - 1/(i+1)) + replaced appropriately, yielding k/(i+1); new item chosen with prob k/(i+1). Thus uniform.Complexity:- Time: O(n) one pass, O(1) amortized per item.- Space: O(k) for the reservoir.Edge cases: k <= 0 returns empty; if stream has fewer than k items, returns all items. Use a good RNG for reproducibility (seed random).
python
import random
from typing import Iterable, List, TypeVar
T = TypeVar("T")
def reservoir_sample(stream: Iterable[T], k: int) -> List[T]:
"""
Reservoir sampling: returns k items uniformly sampled from stream.
Memory: O(k). Single pass.
"""
if k <= 0:
return []
reservoir: List[T] = []
for i, item in enumerate(stream, start=1):
if i <= k:
reservoir.append(item)
else:
# with probability k/i, replace a random index in reservoir
j = random.randrange(i)
if j < k:
reservoir[j] = item
return reservoirMediumTechnical
64 practiced
Training time grows superlinearly as dataset size increases. Describe a practical, step-by-step profiling plan to identify whether the bottleneck is disk/network IO, CPU preprocessing, GPU utilization, or synchronization across workers. Name specific tools and metrics you'd use and propose optimizations for each root cause.
Sample Answer
Step-by-step profiling plan to localize the bottleneck, with tools/metrics and fixes.1) Reproduce & isolate- Run training with (a) synthetic data that bypasses IO/preprocessing and (b) real data but no augmentation. Compare step/sec and epoch time growth. If synthetic matches real → IO/CPU likely; if synthetic is faster → IO/CPU likely; if both slow and GPU low → sync/comm issue.2) Measure host I/O & network- Tools/metrics: iostat/dstat/atop (throughput MB/s, IOPS, avg wait/await), iotop (per-process IO), iftop/ss (network bandwidth), cloud console network metrics, iostat -x for queue depth/latency.- Quick test: cp/read benchmark of dataset directory, or use dd to test raw disk.- Optimizations: convert to efficient formats (TFRecord/LMDB/Parquet), shard dataset, use local SSDs or instance-local disks, increase parallel reads, enable filesystem caching, pre-copy to local disk, use a distributed filesystem tuned for reads (e.g., AWS S3 with cached layer, or HDFS), increase read buffer, use HTTP range requests or transfer via high-bandwidth NICs.3) Measure CPU preprocessing- Tools/metrics: top/htop (per-core%), pidstat (per-thread), perf or perf top (hotspots), py-spy/pyinstrument/cProfile (Python-level hotspots), flamegraphs, torch.utils.bottleneck, Intel VTune.- Metrics: CPU utilization, per-core imbalance, sys vs user time, context switches, Python GIL wait, latency of transform functions.- Quick tests: disable augmentation, reduce num_workers, or run transforms in a separate script to measure time.- Optimizations: move heavy ops to compiled libraries (OpenCV, NumPy), vectorize ops, batch augmentations, use NVIDIA DALI or TF data pipeline, increase num_workers (or reduce if oversubscription), use multiprocessing with pinned memory, precompute augmentations, cache preprocessed shards, use asynchronous prefetch/prefetch_factor.4) Measure GPU utilization and transfer overhead- Tools/metrics: nvidia-smi (util %, memory, GPU %), nvtop, NVIDIA Nsight Systems / cupti (SM utilization, memory throughput, kernel times), torch.cuda.profiler / TensorBoard profiler (time spent in kernels vs memcpy), PCIe throughput tools.- Metrics: GPU utilization %, SM occupancy, kernel vs memcpy times, H2D/D2H transfer time, active vs idle GPU time, batch processing time.- Quick tests: increase batch size or run forward-only loops; measure step time without data transfer (data preloaded to GPU).- Optimizations: increase batch size, use mixed precision (AMP), use pinned (page-locked) host memory, overlap data transfers with compute (async Dataloader + streams), fuse kernels, reduce PCIe transfers (keep data on GPU), use NVLink nodes or faster interconnects, optimize model (pruning/quantization) to reduce kernel time.5) Detect synchronization / distributed communication- Tools/metrics: nvprof/Nsight to see NCCL/allreduce timelines, torch.distributed autograd profiler, netstat/ifstat for inter-node traffic, collect logs of barrier/wait times, TensorBoard profiler per step traces.- Metrics: time spent in collective operations, imbalance across workers, communication-to-compute ratio, idle time waiting at all-reduce.- Quick tests: run single-node single-GPU; run multi-node with reduced world_size; run with GLOO vs NCCL; profile with NCCL_DEBUG=INFO to inspect timelines.- Optimizations: increase per-GPU batch size to improve compute/comm ratio, gradient accumulation to reduce sync frequency, use fused all-reduce (NCCL), enable mixed-precision to reduce payload, overlap gradient communication with backward compute (torch.distributed.optim hooks), use hierarchical/compression techniques (gradient quantization, sparsification), ensure even data sharding to avoid stragglers, tune backend (NCCL_SOCKET_IFNAME, NCCL_DEBUG, NCCL_IB_HCA), upgrade network (10→25→100GbE, RDMA).6) Systematic experiments & metrics to collect- For each change collect: step time, host CPU%, disk MB/s, GPU util%, GPU kernel vs memcpy times, network MB/s, per-epoch wall time, queue sizes in DataLoader.- Use an end-to-end profiler (Nsight Systems, TensorBoard Profiler) to get combined timeline traces.General tips- Start with synthetic-data baseline to separate model vs data pipeline.- Profile at multiple dataset sizes to confirm superlinearity source (e.g., small, medium, large).- Prefer concrete optimizations: caching, format conversion, DALI, pinned memory, mixed precision, gradient accumulation, and network/SSD upgrades.- Automate profiling as CI to catch regressions as dataset scales.
EasyTechnical
54 practiced
Compare quicksort, merge sort, and heap sort: state average and worst-case time complexities, additional space requirements, stability, and which algorithm is preferable for ML preprocessing tasks (e.g., external sorting of large logs, stable sort for time-series joins). Describe external-memory sorting considerations and I/O bottlenecks.
Sample Answer
Quicksort, Merge sort, Heap sort — quick comparison:- Time complexity: - Quicksort: average O(n log n), worst O(n^2) (rare; avoidable with random pivots). - Merge sort: average and worst O(n log n). - Heap sort: average and worst O(n log n).- Additional space: - Quicksort: O(log n) stack (in-place partitioning); worst O(n) for bad implementations. - Merge sort: O(n) auxiliary (top-down); can be O(1) for some in-place variants but complex. - Heap sort: O(1) extra.- Stability: - Quicksort: unstable (unless modified). - Merge sort: stable (standard implementation). - Heap sort: unstable.- Which to prefer for ML preprocessing: - External sorting of large logs: use external merge sort (multi-way merge). Merge sort’s streaming, stable nature and predictable I/O make it ideal for datasets larger than RAM. - Stable sort for time-series joins: use stable merge sort so equal-key ordering (timestamps) is preserved.- External-memory considerations & I/O bottlenecks: - Minimize passes over data: use large runs (generate sorted chunks that fit memory), then multi-way merge to reduce disk seeks. - Use sequential I/O, not random access; prefer SSDs or parallel disks to reduce latency. - Tune buffer sizes and number of merge streams to balance memory vs. number of I/O streams. - I/O, not CPU, is usually the bottleneck: profile read/write throughput, compress data on disk to reduce I/O, and overlap I/O with CPU (asynchronous reads, pipelining).Overall: for ML pipelines handling big data and requiring stability, external merge sort is the practical choice. Quicksort is great in-memory when speed matters and instability is acceptable; heap sort is useful when constant extra space is critical.
MediumTechnical
60 practiced
Design and provide Python pseudocode for an efficient minibatch generator for image training that supports on-the-fly augmentation, shuffling, deterministic reproducibility across epochs, multi-worker prefetching, and bounded memory usage. Discuss trade-offs between threads vs processes, serialization overhead, file formats (JPEG vs TFRecord), and how to debug such a pipeline when it becomes the training bottleneck.
Sample Answer
Approach: create a deterministic, shuffling minibatch generator that reads image paths and labels, uses a seeded RNG per-epoch for reproducible shuffle/augment, applies on-the-fly augmentations, prefetches with a bounded queue, and supports parallel workers (processes preferred for CPU-bound ops). Use producer-consumer: worker pool loads + decodes + augments and pushes tensors into a fixed-size multiprocessing.Queue; consumer yields minibatches to trainer.Key points:- Deterministic reproducibility: seed per-epoch + fixed worker ids; avoid global RNG state in workers.- Bounded memory: out_queue maxsize limits prefetch memory.- Processes vs threads: use processes for CPU-heavy decoding/augmentation to avoid GIL; threads may suffice for I/O-bound reads and lower serialization cost.- Serialization overhead: mp.Queue requires pickling tensors — minimize by sending raw bytes or using shared memory (multiprocessing.shared_memory or framework-specific shared tensors) to reduce copy cost.- File formats: JPEG/PNG cheap storage; decoding CPU cost. TFRecord/LMDB or WebDataset (tar) bundles reduce filesystem overhead and enable faster sequential reads; trade-off: TFRecord requires one-time conversion, less random-access convenience.- Debugging pipeline bottlenecks: - Measure per-stage latency (read, decode, augment, transfer) with timers. - Monitor GPU utilization; if GPU starved, pipeline is bottleneck. - Reduce augmentations or add more workers; try synthetic data to confirm I/O vs compute. - Use tools: iostat, dstat, perf, nvtop; sample profiling logs. - Check queue fill levels to detect producer/consumer imbalance.- Alternatives: framework data APIs (tf.data, PyTorch DataLoader with IterableDataset + num_workers) provide many optimizations and shared-memory transfer.Trade-offs summary:- More workers -> higher throughput but more memory/CPU and contention.- Processes -> avoids GIL, higher IPC cost; threads -> lower IPC but limited by GIL for Python CPU ops.- Packed formats (TFRecord/LMDB/WebDataset) -> faster reads, sequential I/O, but extra conversion step and less ad-hoc inspectability.Edge cases:- Last partial batch handling, shuffling with distributed training (use per-replica shard + different epoch seeds), worker crashes (heartbeat + restart).
python
# python pseudocode (framework-agnostic)
import random, multiprocessing as mp
from queue import Empty
def worker_loop(task_queue, out_queue, seed_base, worker_id, stop_event):
rng = random.Random(seed_base + worker_id)
while not stop_event.is_set():
try:
idx = task_queue.get(timeout=1)
except Empty:
continue
if idx is None:
break
path, label = idx
# read & decode (prefer fast libs e.g., Pillow, libjpeg-turbo)
img = read_image(path) # decode JPEG/PNG or TFRecord parse
img = augment(img, rng) # deterministic per-worker RNG
tensor = to_tensor(img)
out_queue.put((tensor, label))
class MinibatchGenerator:
def __init__(self, index_list, batch_size, num_workers=4, prefetch=32, seed=0):
self.index_list = index_list
self.batch_size = batch_size
self.seed = seed
self.num_workers = num_workers
self.prefetch = prefetch
def __iter__(self):
# deterministic shuffle
rng = random.Random(self.seed + epoch) # increment epoch externally
perm = list(self.index_list)
rng.shuffle(perm)
# spawn workers and queues
task_q = mp.Queue()
out_q = mp.Queue(maxsize=self.prefetch)
stop = mp.Event()
workers = [mp.Process(target=worker_loop, args=(task_q, out_q, self.seed, i, stop))
for i in range(self.num_workers)]
for w in workers: w.start()
for item in perm:
task_q.put(item)
for _ in workers: task_q.put(None) # sentinel to stop
# consume and yield batches
batch_imgs, batch_labels = [], []
received = 0
total = len(perm)
while received < total:
t, l = out_q.get()
batch_imgs.append(t); batch_labels.append(l)
received += 1
if len(batch_imgs) == self.batch_size:
yield stack(batch_imgs), stack(batch_labels)
batch_imgs, batch_labels = [], []
# cleanup
stop.set()
for w in workers: w.join()Unlock Full Question Bank
Get access to hundreds of Problem Analysis & Optimization interview questions and detailed answers.
Sign in to ContinueJoin thousands of developers preparing for their dream job.