Data Structure Selection and Trade Offs Questions

Skill in selecting appropriate data structures and algorithmic approaches for practical problems and performance constraints. Candidates should demonstrate how to choose between arrays lists maps sets trees heaps and specialized structures based on access patterns memory and CPU requirements and concurrency considerations. Coverage includes case based selection for domain specific systems such as games inventory or spatial indexing where structures like quadtrees or spatial hashing are appropriate, and language specific considerations such as value versus reference types or object pooling. Emphasis is on explaining rationale trade offs and expected performance implications in concrete scenarios.

EasyTechnical

79 practiced

Implement conceptually (no full code required) how you would use a heap (priority queue) to maintain the top-k tokens by logit score during beam search in a language model. Explain time and memory complexity per step and why a heap is appropriate versus sorting the entire vocabulary each step.

Sample Answer

Approach: iterate over the vocabulary logits for each beam candidate and maintain a min-heap (size k) of (logit, token_id). The heap keeps the current top-k largest logits; use a min-heap so the smallest of the top-k is at the root and can be popped when a new larger logit arrives.

python

import heapq

def topk_from_logits(logits, k):
    # logits: iterable of (token_id, logit_score) for one beam
    heap = []  # min-heap of (score, token)
    for token_id, score in logits:
        if len(heap) < k:
            heapq.heappush(heap, (score, token_id))
        else:
            # if current score is larger than smallest in heap, replace
            if score > heap[0][0]:
                heapq.heapreplace(heap, (score, token_id))
    # result: largest k in ascending order; reverse if needed
    return sorted(heap, reverse=True)

Key points:- Per beam step you scan V logits and do O(1) average work per token plus occasional heap ops.- Time per beam: O(V log k). For B beams: O(B V log k) to produce next-beam candidates.- Memory: O(k) per beam (plus negligible heap overhead); if you combine beams, O(B k).- Compared to sorting V items (O(V log V)), using a heap is far cheaper when k << V.- Heaps avoid allocating/processing full sorted arrays each step; good for large vocabularies.- Alternatives: selection algorithm (nth_element) with O(V) average, or optimized GPU topk kernels. Edge cases: ties, numerical stability (apply softmax temperature/logit masking before selection), and batching across beams for GPU efficiency.

MediumTechnical

80 practiced

Compare CSR (Compressed Sparse Row) and COO (Coordinate) formats for representing sparse input matrices fed into GPU-accelerated models. Discuss conversion cost, memory layout benefits when transferring to GPU, batching trade-offs, and which formats deep learning libraries (PyTorch/TensorFlow) prefer for sparse ops.

Sample Answer

Overview: COO (Coordinate) stores sparse matrices as triplets (row, col, value). CSR (Compressed Sparse Row) stores values and column indices per row with a row-pointer array. Both are useful on GPU but differ in conversion cost, memory layout, batching behavior, and library support.

Conversion cost:- COO -> CSR: O(nnz) linear-time pass to sort/group by row (if not already row-ordered) and build row_ptr. Cheap for static matrices but costs extra CPU work and memory if done per-batch.- CSR -> COO: O(nnz) to expand row pointers into row indices; also linear but can be memory-heavy if you materialize row array.- On-the-fly conversions on CPU before each GPU transfer add latency; prefer converting once offline or in preprocessing pipeline.

Memory layout & GPU transfer:- CSR is compact for row-oriented access: contiguous value and col arrays with a small row_ptr; good for SpMV/row-wise kernels and coalesced GPU reads when processing rows or batched rows.- COO stores three equal-length arrays; simpler and amenable to parallel scatter/gather kernels but less cache-friendly for row operations.- Transfer cost dominated by nnz; contiguous arrays (both formats) copy efficiently. CSR’s smaller metadata (row_ptr length = rows+1) can reduce transfer and memory footprint when nnz ≪ rows*cols.

Batching trade-offs:- Batching many small sparse examples: COO is easier to assemble by concatenating triplets with offset adjustments; CSR batching requires merging row_ptrs or storing per-example row_ptrs (more complex).- For mini-batches treated as a single large sparse tensor (e.g., block-CSR by stacking with offsets), CSR often yields better performance for row-based kernels.- Dynamic per-step sparsity (changing sparsity pattern) favors COO for quick assembly; stable sparsity favors CSR for repeated kernels.

Library preferences:- PyTorch: recent sparse support centers on COO-like sparse tensors (torch.sparse_coo_tensor) and newer sparse APIs; however, many optimized ops (torch.sparse.mm) and third-party libraries (cuSPARSE/cuSPARSE Lt) accept CSR for high-performance SpMM/SpMV on GPUs. PyTorch’s sparse backends often convert to CSR or internal formats for kernels.- TensorFlow: tf.sparse.SparseTensor is COO-like (indices, values, dense_shape). TensorFlow ops commonly accept COO-style inputs and convert internally; under the hood, optimized routines (cuSPARSE/cuSPARSE wrappers) may use CSR.- Practical guidance: feed models with the format the framework API expects (COO for TF, COO for PyTorch API), but convert to CSR when you control kernel execution and need faster repeated row-wise ops on GPU. Use library-specific sparse kernels (cuSPARSE/cuSPARSELt or vendor libraries) which often require CSR for best throughput.

Recommendation: Preprocess static sparse inputs into CSR for training/inference performance when using row-oriented kernels or repeated SpMMs. Use COO when building/assembling sparse batches dynamically or when using framework APIs that expect coordinate indices; if latency matters, avoid per-batch conversions by caching converted buffers on GPU.

HardTechnical

62 practiced

For extremely long-context transformers (e.g., up to 1M tokens), propose memory-efficient representations for attention masks and sparse attention patterns. Discuss compressed bitset representations, run-length encoding, block-sparse masks, and GPU constraints such as bank conflicts and shared memory limits. Estimate memory usage and algorithmic complexity of computing attention for your chosen approach.

Sample Answer

Clarify target: 1M tokens, attention must be sparse (full dense O(n^2) impossible). I propose a hybrid block-sparse + compressed-mask representation with GPU-friendly layout.

Design summary- Logical pattern: block-sparse attention with fixed block size B (e.g., 64–256 tokens). Each token attends to a local window W (±w blocks) plus a small set of global tokens and periodic strided blocks. This bounds per-row nonzeros to K ≈ (2w+1)*B + G.- Mask representation: store a block index list per query block (sparse block CSR) plus intra-block bitmaps compressed via run-length encoding (RLE) when blocks are mostly contiguous or via 64-bit bitsets when dense. Use delta-encoded block indices then varint encode for compactness.

Compressed bitset vs RLE tradeoff- Compressed bitset (64-bit words): fast bitwise ops on GPU; store block-level 64-bit masks for B=64. Memory per attended block = 8 bytes.- RLE: good when mask has long contiguous runs across token positions (e.g., long local window). Encoded as (run_length) pairs; saves space for very long contiguous spans but requires decode kernel overhead.

GPU constraints and layout- Tile attention by (query-block, key-block). Load a key-block into shared memory once; iterate over query threads for that query-block to compute matmul on only selected key-blocks.- Shared memory limit: typical 48–96 KB per SM — so pick B s.t. activations (B x head_dim) fit. Example: head_dim=64, float16 => B*64*2 bytes = 8KB for B=128.- Avoid bank conflicts: store per-thread contiguous addresses; transpose tiles to ensure coalesced loads; align bitset masks to 128-bit for warp loads.- Branch/warp divergence: use mask-driven gather kernels with a two-phase approach: (1) expand block indices to a contiguous list of key-block addresses, (2) load blocks and compute attention for all queries in block with masked accumulators to minimize divergent branches.

Memory & compute estimates (example numbers)- n = 1,000,000 tokens, B=128 → num blocks Nb = 7813.- If each query attends K ≈ 5 blocks (local+global/strided), nonzero blocks ≈ Nb*5 ≈ 39k blocks references.- Mask storage using 8-byte bitset per block-ref: 39k * 8 = 312 KB. Block index list: 39k * 4 bytes = 156 KB. Per-layer parameterless mask overhead ≪ model activations.- Runtime activation memory dominated by loading one key-block and one query-block per tile: for head_dim=64,f16, two blocks = 2 * (128*64*2B)=32KB — fits shared memory.

Algorithmic complexity- Time: O(n * K * (B * d_h) / tile_width). Effectively O(n * k_eff * d_h) where k_eff = K*B is average attended keys per query. This is linear in n for fixed K.- Memory: mask meta-data O(Nb * avg_ref) ~ O(n/B * K). Peak runtime memory dominated by activations O(B * d_h).

Edge considerations and alternatives- If attention pattern is long contiguous spans, RLE reduces mask storage further but requires decode kernel — trade latencies.- For dynamic sparsity (learned patterns), maintain CSR-like structures and rebuild periodically; use tensor cores by assembling dense tiles for attended blocks.- For ultra-low memory, hierarchical attention (coarse blocks, then local refinement) reduces k_eff further.

Key takeaways- Use block-sparse attention to get O(n) scaling; store block-level masks as compact bitsets (64-bit) for fast GPU ops and RLE when long runs dominate.- Tune B, K, head_dim to fit shared memory and avoid bank conflicts; use tile-based kernels that reuse blocks in shared memory to minimize global bandwidth.

HardSystem Design

83 practiced

Design a vector similarity search system that can serve 100B embeddings and deliver median query latency under 10ms. Explain the data structures (compressed indexes, inverted lists, HNSW overlays), sharding/replication strategy, caching layers, quantization strategy (PQ/OPQ), and hardware considerations (NVMe, GPU, memory) needed to meet latency and storage constraints.

Sample Answer

Requirements & constraints:- Store 100B embeddings (e.g., 768-d float32) and serve median <10ms per query with high recall (top-K).- Budget for commodity servers + NVMe; GPUs allowed for re-ranking.

High-level architecture:- Partition data into N shards (range- or hash-shard by vector id/semantic routing) so each shard holds ~hundreds of millions–low billions of vectors. Frontend load-balances queries to relevant shards; query fans out to a subset then merges results.- Each shard = persistent compressed index on NVMe + in-memory HNSW overlay for routing + small hot-cache in RAM.

Indexing & data structures:1. Coarse quantization + inverted lists (IVF): cluster vectors into M coarse centroids (M tuned per-shard). Inverted lists store PQ-compressed residuals for vectors assigned to centroid.2. Product Quantization (PQ) with OPQ preprocessing: apply OPQ rotation to reduce distortion then PQ (e.g., 16 bytes / vector) for storage/fast distance approximations.3. HNSW overlay: build a lightweight HNSW graph over PQ centroids (or a subset of vectors) to quickly find nearest centroids / candidates. HNSW kept in RAM (graph nodes + short pointers) to guide search; its small memory footprint yields low-latency hop routing.4. Residual / rerank store: keep either higher-precision (e.g., 8–16 bytes) compressed residuals on NVMe and top candidates optionally re-ranked on GPU/CPU using full-precision or 8-bit quantized vectors.

Search flow (latency-optimized):- Query OPQ-rotate -> HNSW to get candidate centroids -> probe K inverted lists (K small) -> compute asymmetric distances against PQ codes in CPU with SIMD (AVX) reading PQ tables from NVMe pages or memory-mapped files -> collect top-N candidates -> optional asynchronous GPU/CPU re-rank on full-precision stored in RAM or NVMe cache -> return top-K.

Quantization strategy:- OPQ + PQ for primary storage: typical configuration 64-subvectors (m) with 8-bit codebooks (8 bytes per vector) or 16 bytes for better accuracy. Use asymmetric distance computation (ADC) to compare query (uncompressed) to PQ codes.- Store small per-vector metadata: id, quality score, shard id. Keep a sparse high-precision store for recently hot or high-recall vectors.

Sharding & replication:- Shard size tuned so HNSW fits in RAM per node (e.g., <64–128GB). Replicate each shard R=2-3 for availability & tail-latency mitigation.- Use consistent hashing / routing service. For multi-tenant/semantic routing, route queries to top relevant shards only to reduce fan-out.

Caching layers:- Node-level in-memory caches: - HNSW graph always resident. - Hot-vector cache: keep top-frequent vectors in float16 or int8 in RAM for immediate re-rank. - Inverted list head pages cached in RAM; rest read from NVMe via PMem/IO priorities.- Global cache: smart LRU LFU in front (Redis or custom) for popular query results.- CPU/GPU async prefetch for NVMe reads to hide IO.

Hardware considerations:- NVMe SSDs with high IOPS and throughput for compressed code reads; use direct IO, large sequential IO, and mmap for low-overhead scanning.- RDMA networking between frontend and shard nodes to reduce RPC latency.- Memory: enough RAM to hold HNSW (graph + PQ codebooks) and inverted-list hot pages; target 128–512GB per node depending on shard size.- CPUs with wide SIMD (AVX-512) to perform fast ADC distance computations on PQ codes.- GPUs: optional for latency-critical re-ranking (batch small candidate sets; use GPU kernels optimized for small-matrix distances). Use small persistent GPU kernels to avoid launch overhead.- Consider NVMe-oF and SmartNICs for offloading network and IO.

Performance tuning & trade-offs:- Aim for PQ code size ~8–16 bytes to fit storage while keeping ADC compute under ~1–3ms per shard.- Minimize fan-out: route to <10 shards per query to bound latency; increase replication to parallelize.- HNSW parameter (M, efConstruction, efSearch) chosen to balance memory vs candidate quality.- Use asynchronous re-rank: return fast approximate results within 10ms; if higher precision needed, provide progressive refinement.

Failure & consistency:- Serve from replicas for availability; rebuild shards offline with streaming updates. Use append-only NVMe layout + bloom filters for existence checks.

Estimate:- If each vector = 16 bytes (PQ) => 100B * 16B = 1.6PB raw; with metadata and overhead ~2PB. Spread across ~100–500 shard nodes with multi-TB NVMe each. With optimized ADC + in-memory HNSW and limited fan-out, median latency <10ms is achievable.

This design balances storage (PQ/OPQ), fast candidate routing (HNSW), and IO-efficient inverted list access on NVMe, with CPU/GPU re-ranking and caching to meet latency and scale.

MediumTechnical

115 practiced

You need to keep frequency estimates of tokens from a massive corpus to identify stopwords and rare tokens. Compare Count-Min Sketch, HashMap, and exact frequency approaches. Discuss memory and update time trade-offs, error bounds, effects on vocabulary selection for an NLP model, and how to choose sketch parameters for needed accuracy.

Sample Answer

Situation: You need scalable token frequency estimates from a massive corpus to pick stopwords and prune vocabulary for an NLP model. Below is a practical comparison and guidance.

Comparison (Count‑Min Sketch vs HashMap vs exact):- Exact (HashMap with counters) - Memory: O(V) where V = distinct tokens. High for web-scale corpora. - Update time: amortized O(1) per token. - Error: none (exact counts). - When to use: small-to-medium corpora, offline passes, or when exact top-k / rare-token decisions are critical.- Count‑Min Sketch (CMS) - Memory: O(w·d) where w = width, d = depth. Much smaller than O(V) for large V. - Update time: O(d) per token (a few hash computations and increments). - Error: non-negative overestimation. With parameters w = ceil(e/ε) and d = ceil(ln(1/δ)), each estimate f̂ satisfies f ≤ f̂ ≤ f + ε·N with probability ≥ 1−δ (N = total tokens). - Pros: mergeable, streaming, predictable memory/error trade-off. - Cons: collisions bias rare-token estimates upward; can't decrement reliably unless using conservative updates or signed sketches.- HyperLogLog note: HLL estimates distinct token count, not per-token frequencies — useful to size hashmaps or sketches but not to replace frequency counts.

Effects on vocabulary selection:- Stopwords (very high frequency): CMS reliably identifies heavy hitters because overestimation is small relative to large counts; choose thresholds >> ε·N.- Rare tokens pruning: CMS overestimation can falsely promote rare tokens above a low threshold. If you prune tokens with frequency ≤ T, ensure ε·N << T or complement CMS with a second exact pass for candidates near threshold.- Zipfian distributions: tail is long; memory savings from CMS are large, but rare-token errors concentrate in the tail.

Choosing CMS parameters for needed accuracy:- Decide acceptable absolute error E_abs or relative to threshold T. Because error bound is ε·N, set ε = E_abs / N. Then w = ceil(e/ε).- Set δ small (e.g., 0.01) so d = ceil(ln(1/δ)) ~ 5.- Example: corpus N = 10^9 tokens, want absolute error ≤ 10^3 (so rare threshold T=10^4 safe): ε = 1e3 / 1e9 = 1e-6, w ≈ e/1e-6 ≈ 2.72e6, with d=5 → memory ~13.6M counters (feasible with 4–8 byte counters).- Use conservative update (only increment the minimum counter) to reduce overestimation at cost of slightly more work.

Practical recommendations:- If you can afford a pass and memory for a hashmap for candidate tokens up to a cutoff (e.g., tokens seen > K), combine approaches: first CMS streaming to find heavy hitters and estimate vocabulary size, then materialize exact counts for tokens with CMS estimate > K (reduce memory).- For stopword removal choose high thresholds where CMS error is negligible; for rare-token pruning either use smaller ε or validate borderline tokens with an exact pass.- Monitor collision effects: validate a sample of CMS estimates against exact counts to tune parameters.

This balances memory, update speed, and the tolerable estimation error for downstream NLP decisions.

Unlock Full Question Bank

Get access to hundreds of Data Structure Selection and Trade Offs interview questions and detailed answers.

Join thousands of developers preparing for their dream job.