Assess the ability to analyze, compare, and optimize algorithmic solutions with respect to time and space resources. Candidates should be fluent in Big O notation and able to identify dominant operations, reason about worst case, average case, and amortized complexity, and calculate precise time and space bounds for algorithms and data structure operations. The topic includes recognizing complexity classes such as constant time, logarithmic time, linear time, linearithmic time, quadratic time, and exponential time, and understanding when constant factors and lower order terms affect practical performance. Candidates should know and apply common algorithmic patterns and techniques, including two pointers, sliding window, divide and conquer, recursion, binary search, dynamic programming, greedy strategies, and common graph algorithms, and demonstrate how to transform brute force approaches into efficient implementations. Coverage also includes trade offs between time and space and when to trade memory for speed, amortized analysis, optimization tactics such as memoization, caching, pruning, iterative versus recursive approaches, and data layout considerations. Candidates must be able to reason about correctness, invariants, and edge cases, identify performance bottlenecks, and explain practical implications such as cache behavior and memory access patterns. For senior roles, be prepared to justify precise complexity claims and discuss optimization choices in system level and constrained environment contexts.
HardTechnical
73 practiced
Explain the Greenwald-Khanna (GK) algorithm for epsilon-approximate quantile summaries on streams. Provide the space complexity in terms of 1/epsilon and the amortized update time per item. Discuss how GK compares to t-digest and simple sampling for different error/space regimes in production telemetry.
Sample Answer
Greenwald–Khanna (GK) builds a deterministic epsilon-approximate quantile summary for a stream: it maintains an ordered list of tuples (v, g, Δ) where v is a value, g is the minimum rank gap since the previous tuple, and Δ is the allowable slack. Invariant: for any tuple i, the true rank r(v_i) lies in [∑_{j≤i} g_j, ∑_{j≤i} g_j + Δ_i]. On insert you create a new tuple with g=1 and Δ = floor(2εN)−1 (depending on implementation) and periodically compress adjacent tuples when g_i + g_{i+1} + Δ_{i+1} ≤ floor(2εN) to keep slack bounded. Queries return a value whose rank differs from the true rank by at most εN.Space complexity: O((1/ε) log(εN)) worst-case, often summarized as O(1/ε) for fixed-stream growth; more precisely GK stores O((1/ε) log N) tuples in adversarial analysis but practical implementations often observe O(1/ε). Amortized update time: O(1) amortized per item (amortized cost of occasional compressions), worst-case O(1/ε) for a single compress step.Comparison for production telemetry:- GK (deterministic): guarantees rank error ≤ εN; good when strict worst‑case guarantees are required (auditing, SLOs). Memory predictable for moderate ε; heavier bookkeeping than sampling.- t-digest (probabilistic, clustering-based): excels at accurate extreme quantiles (tails) with small memory and fast updates; no strict deterministic rank guarantees but empirically compact and very practical for latency distributions. Prefer t-digest when tail accuracy and low memory are priorities.- Simple reservoir sampling / uniform sampling: trivial, tiny memory, O(1) updates; rank error scales ~O(1/√k) where k is sample size, so to get small ε need large k. Good for rough estimates or very high throughput when you accept probabilistic error.Guidance by regime:- Very tight deterministic ε (small ε): use GK or more advanced deterministic sketches (cost ~1/ε).- Tail‑sensitive with small memory: use t-digest.- Very high throughput + coarse accuracy: use sampling.Trade-offs: GK gives provable worst-case guarantees but more state and complexity; t-digest gives excellent empirical tail behavior and compactness; sampling is simplest but requires larger memory for tight bounds. Choose based on required error type (rank vs value/tail), memory budget, and determinism.
MediumTechnical
81 practiced
Given two sorted arrays of size n each, design an algorithm to find the median of the combined 2n elements in O(log n) time. Describe the divide-and-conquer approach, outline pseudocode, and explain correctness and edge cases when arrays have unequal sizes.
Sample Answer
Approach (divide-and-conquer / binary search):Find the median by recursively discarding halves that cannot contain the combined median. At each step compare medians of A and B:- If median(A) == median(B): return it.- If median(A) < median(B): discard left half of A and right half of B.- Else discard right half of A and left half of B.Each recursion reduces problem size by ~half → O(log n).Pseudocode (arrays A, B of equal length n):
python
def median_of_two(A, B):
# assume len(A) == len(B) and >0
if len(A) == 1:
return (A[0] + B[0]) / 2
if len(A) == 2:
return (max(A[0], B[0]) + min(A[1], B[1])) / 2
m = len(A)//2
medA = A[m] if len(A)%2==1 else (A[m-1]+A[m])/2
medB = B[m] if len(B)%2==1 else (B[m-1]+B[m])/2
if medA == medB:
return medA
elif medA < medB:
# discard A[0..m] and B[m..end] appropriately
return median_of_two(A[m if len(A)%2==1 else m-1 :], B[: m+1 if len(B)%2==1 else m+1])
else:
return median_of_two(A[: m+1 if len(A)%2==1 else m+1], B[m if len(B)%2==1 else m-1 :])
Correctness:At each step we remove symmetric portions whose elements are guaranteed to be all smaller (or larger) than the combined median by comparing medians. This preserves the median of the union. Base cases handle tiny arrays exactly.Unequal sizes:When sizes differ (m ≤ n without loss), run binary search on the smaller array to find a partition i in A and j in B such that:- i + j = (m+n+1)//2- A[i-1] ≤ B[j] and B[j-1] ≤ A[i]Then median is max(A[i-1],B[j-1]) (or average with min(A[i],B[j]) if total even).This is the standard O(log min(m,n)) algorithm and handles edge indices carefully.Complexity: O(log n) for equal-size; O(log min(m,n)) for unequal. Edge cases: empty array, duplicate values, even/odd total lengths—handle via base cases and careful partition index bounds.
EasyTechnical
77 practiced
Define vectorization in the context of NumPy and pandas. Compare the complexity and practical performance of a vectorized sum over a large column vs a Python loop summing each row. Provide tips for when vectorization increases memory usage and how to handle memory-pressure (chunking, in-place ops).
Sample Answer
Vectorization (NumPy/pandas): executing operations over whole arrays/columns using optimized C/Fortran loops instead of Python-level element-by-element loops. Vectorized ops delegate heavy work to compiled code, minimize Python overhead, and can use SIMD/BLAS.Complexity and practical performance:- Algorithmic complexity: both a Python loop and a vectorized sum are O(n).- Practical performance: vectorized sum (np.sum, Series.sum) is orders of magnitude faster because the per-element Python-call overhead is removed and CPU cache/SIMD are leveraged. Example:
python
import numpy as np
a = np.random.rand(10_000_000)
# Vectorized
s_vect = a.sum()
# Python loop (much slower)
s_loop = 0.0
for x in a:
s_loop += x
Key points:- Time: vectorized ~O(n) with tiny constant; Python loop ~O(n) with large per-iteration overhead.- Memory: np.sum can stream/reduce without large extra buffers, but many vectorized expressions allocate temporaries (e.g., a + b creates new array).When vectorization increases memory usage and how to handle memory pressure:- Causes: building intermediate arrays, converting dtypes, or materializing large DataFrame slices.- Strategies: - Chunking: process data in chunks (pandas.read_csv(..., chunksize=...), or iterate over array slices) and accumulate results. - In-place / out parameter: use NumPy ufuncs with out= to avoid temporaries (np.add(a, b, out=a) or np.add.reduce). - Reduce memory footprint: use appropriate dtypes (float32 vs float64), categorical for strings. - Memory-mapped arrays: np.memmap for arrays larger than RAM. - Streaming reductions: apply sum per chunk and combine partial sums. - Use libraries: numexpr for fused computations, Dask for out-of-core vectorized operations.Chunking example (pandas):
python
total = 0.0
for chunk in pd.read_csv('big.csv', usecols=['col'], chunksize=1_000_000):
total += chunk['col'].sum()
Profiling tips: timeit, %prun, memory_profiler, and monitor allocations (tracemalloc) to find temporary creation hotspots. Use vectorization for speed, but when memory is tight, prefer chunked or out-of-core patterns.
HardTechnical
87 practiced
You need to accelerate distributed training on GPUs with 16GB memory per device. Propose algorithmic optimizations (model sharding, gradient checkpointing, mixed precision, operator fusion) and quantify memory vs compute trade-offs. Explain how to reason about memory access patterns and PCIe/NVLink communication bottlenecks when designing the pipeline.
Sample Answer
Approach summary: combine model sharding (tensor + pipeline parallelism), gradient checkpointing, mixed precision, and operator fusion to fit large models into 16GB GPUs while minimizing performance loss. Quantify trade-offs and reason about memory/communication.Algorithmic optimizations and trade-offs:- Model sharding (tensor/model-parallel): split large layers across GPUs so per-GPU parameter memory drops ~1/P where P is shards. Communication overhead: all-reduce for optimizer states or halo exchanges for tensor ops. Trade-off: compute parallelism reduced by syncs; effective throughput ≈ compute / (1 + comm_latency * frequency).- Pipeline parallelism: partition layers into stages to keep GPUs busy. Introduces micro-batch bubble overhead ≈ (num_stages-1)/num_microbatches; amortize by increasing micro-batches.- Gradient checkpointing: store only a subset of activations; recompute during backward. Memory saved ≈ activations_saved, cost = extra forward compute ≈ +30–70% time depending on checkpoint granularity. Good when activation memory >> parameter memory.- Mixed precision (FP16/AMP): halves parameter and activation memory; reduces compute time on Tensor Cores. Must maintain loss scaling and FP32 master weights for stability; memory of optimizer states still matters—use FP16 optimizer states or 8-bit optimizers for extra savings.- Operator fusion: combine adjacent kernels to reduce intermediate activation storage and kernel launch overhead; reduces memory traffic and latency, improves arithmetic intensity.Quantified example (rough):- Baseline: 16GB holds model with 10B params? Not possible. With P=8 tensor shards + FP16, parameter memory per GPU ≈ (10B * 2 bytes)/8 ≈ 2.5 GB; optimizer (FP32 master) adds ≈ 10B*4/8 = 5 GB unless using FP16 optimizer—use LAMB/Adam8bit to cut further.- Activations: without checkpointing may be 6–8 GB; with checkpointing (save 1/4) reduce to ~1.5–2 GB at cost +40% compute.Memory access & communication reasoning:- Memory-bound vs compute-bound: measure roofline — if arithmetic intensity low, optimize to increase reuse (fusion, tiling). Reduce DRAM traffic: keep hot tensors in GPU SRAM (L2/cache), avoid spilling to host.- PCIe/NVLink bottlenecks: NVLink bandwidth ~N×PCIe; topology matters. Design sharding to localize heavy transfers to NVLink-connected peers; reduce all-reduce frequency (use gradient accumulation, overlap comm with compute). Overlap: schedule non-blocking NCCL ops and reorder work so communication of layer l happens during compute of layer l-1.- Prefer collective ops with hierarchical aggregation: intra-node NVLink reductions then inter-node PCIe/Infiniband to minimize cross-node traffic.- Profiling: use nsight/torch.profiler to find hotspots (kernel time vs memcpy). Optimize by increasing batch size until GPU memory or interconnect saturates; if PCIe saturates, reduce cross-device syncs, increase computation per communication via larger micro-batches or fewer synchronization points.Design checklist:- Use FP16 with AMP + loss scaling.- Shard parameters and optimizer (ZeRO stage 2/3) to reduce optimizer state memory.- Apply activation checkpointing selectively on largest layers.- Fuse kernels and tune einsum/blocking for tensor cores.- Overlap NCCL comm with compute; exploit NVLink topology and hierarchical collectives.- Monitor trade-offs empirically: measure steps/sec vs GPU memory usage and network utilization; aim for sweet spot where memory fits with ≤30–50% compute overhead from recompute/comm.
EasyTechnical
89 practiced
Describe amortized time complexity for append operations on a dynamic array (e.g., Python list or C++ vector). Explain why append is amortized O(1) when capacity doubles upon resize. Give the sequence of costs as elements are appended and show intuitively how the average cost per append remains constant.
Sample Answer
Amortized time complexity measures the average cost per operation over a sequence, smoothing occasional expensive operations. For a dynamic array that doubles capacity on resize (e.g., Python list/C++ vector), individual appends are usually O(1) but sometimes O(n) when resizing+copying is needed. Doubling makes the average cost constant.Concrete sequence:- Start capacity 1: append costs: 1 (insert)- 2nd append triggers resize: cost = 1 (insert) + 1 (copy old) = 2- 3rd append: cost 1- 4th append triggers resize: cost = 1 + 2 (copy 2 elements) = 3- 5–8th appends: cost 1 each; 9th triggers resize copying 4 elements, etc.Total-cost argument (intuition):If we perform n appends starting from empty with doubling, each element is copied at most O(log n) times? Better: every time an element is copied, it’s because of a resize that at least doubles capacity, so the total number of element-copies over n appends is ≤ n (each new element causes at most one future copy per doubling sequence, summing to < 2n). Counting the O(1) insert work for each append plus all copies gives total O(n). Therefore average cost per append = O(n)/n = O(1).Bottom line: although some appends are expensive, resizing strategy that doubles capacity bounds the total extra work across n operations, so append is amortized O(1).
Unlock Full Question Bank
Get access to hundreds of Algorithm Analysis and Optimization interview questions and detailed answers.
