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

In Python ML code, compare Python lists (list of tuples/dicts) and numpy.ndarray for storing numeric features and minibatches. Discuss memory layout, value vs reference semantics, performance of vectorized operations versus Python-level loops, impact on transferring data to GPU, and when to convert or keep data in each form during training or inference.

Sample Answer

Brief answer:- Memory layout: numpy.ndarray stores fixed-type, contiguous (C- or Fortran-order) buffers which are compact and cache-friendly. Python lists (of tuples/dicts) are arrays of pointers to heap objects scattered in memory, with large per-item overhead.- Value vs reference semantics: ndarray elements are raw values in a buffer (assignment may copy view vs data), while list elements are references to Python objects (mutating an element mutates the object; copying the list copies refs).- Performance: Vectorized numpy ops operate in C over contiguous memory — orders-of-magnitude faster than Python-level loops over lists. Loops over lists incur Python interpreter overhead and poor cache locality.- GPU transfer: Frameworks (PyTorch/TensorFlow/CuPy) accept contiguous ndarrays or provide zero-copy when possible; lists require building an ndarray (or tensors) first, causing extra allocations and slower transfers.- When to convert/keep: - Keep raw data as lists during data ingestion if records are heterogeneous (dicts), or until heavy preprocessing when flexibility matters. - Convert to ndarray/tensor before minibatching, augmentation, and model input. For training, use contiguous float32 arrays or directly create tensors on the device to minimize copies. - For inference at scale, store compact ndarrays (or serialized tensors) for fast batch transfers to GPU.

Example conversion:

python

import numpy as np, torch
arr = np.array(list_of_feature_tuples, dtype=np.float32)  # one copy, contiguous
tensor = torch.from_numpy(arr)  # shares memory if CPU; .to('cuda') copies to GPU

Edge tips: prefer float32, ensure correct strides (arr.flags['C_CONTIGUOUS']), and avoid lists-of-arrays for hot loops.

MediumTechnical

120 practiced

Compare row-oriented (row-major) vs columnar (column-major like Parquet/Arrow) storage for feature stores and offline training pipelines. Discuss IO patterns, compression benefits, vectorized processing, and how each affects training pipelines that read many features for many examples vs a few features for many examples.

Sample Answer

Requirements and context:- Two common access patterns in offline ML: (A) many features for many examples (full-table scans for model training), (B) few features for many examples (feature selection, lightweight models, or online simulation).- Storage choices: row-oriented (row-major, e.g., typical OLTP/row-based Parquet not optimized) vs columnar (Parquet/Arrow, column-major).

Comparison

1) IO patterns- Row-oriented: best when you read whole rows (many features per example). Sequential reads fetch contiguous rows; fewer seeks when accessing many columns per record.- Columnar: best when you read a subset of columns. Only requested columns are read from disk, reducing IO significantly for “few features” workloads. For “many features” it reads many columns, increasing read overhead and potential random IO across column files/fragments.

2) Compression benefits- Columnar: high compression ratios because values in a column are homogenous and often have low entropy (run-length, dictionary, delta encoding). This reduces IO and storage; decompression is fast and vector-friendly.- Row-oriented: lower compression because rows interleave different types; less benefit from column-wise encodings.

3) Vectorized processing- Columnar: excellent for SIMD/vectorized operations and CPU cache locality—libraries like Arrow expose contiguous memory for fast vector ops, enabling batch transforms, aggregations, and faster feature engineering.- Row-oriented: forces per-row parsing and type handling, worse cache/branch behavior, higher CPU overhead for columnar-style vector ops.

4) Effect on training pipelines- Many features × many examples (full training): Row-oriented can be competitive because you read full rows once; fewer seeks and simpler deserialization. However, columnar still benefits from better compression and parallel column decoding; with efficient IO and column projection disabled, columnar reads can be performant. For very wide feature sets, columnar read cost scales with number of columns and may increase read latency.- Few features × many examples: Columnar wins—reads only needed columns, low IO, high compression, and vectorized preprocessing speeds up data loading and transformation dramatically.

Trade-offs & recommendations- Use columnar (Parquet/Arrow) as default for offline feature stores and batch training where column projection, compression, and vectorized transforms matter.- For extremely wide models where you always use most features and need row-atomicity (e.g., joins or transactional consistency), consider row layouts or hybrid storage (row bursts, or store feature groups together).- Combine: maintain columnar cold storage for training and a row-oriented store/index for fast per-entity retrieval or debugging. Also use columnar in-memory formats (Arrow) to bridge IO->compute cheaply.

Conclusion- Columnar offers better IO efficiency, compression, and vectorized CPU use for most ML offline workflows—especially when you read subsets of features. Row-oriented can be preferable when you always read full rows or require row-level atomicity. Choose storage aligned to your dominant access pattern and consider hybrid architectures.

HardSystem Design

58 practiced

Design an on-disk inverted index for textual features used in a retrieval/feature extraction pipeline. Describe postings list representation, compression (e.g., delta-encoding, variable-byte, PForDelta), support for prefix queries, merging updates efficiently, and trade-offs between memory-mapped files and explicit IO and caching.

Sample Answer

Requirements:- Support disk-resident inverted index for textual features: fast retrieval of postings (docID, term frequency, positions, feature weights), efficient updates/merges, prefix (prefix/wildcard) queries, low storage and CPU overhead for ML pipelines that extract features at inference/training time.- Scale to billions of docs, low-latency reads (tens-hundreds ms), background updates.

High-level design:- Term dictionary (compact trie or FST) → pointer to postings block(s) on disk.- Postings stored as append-only blocks (segments) to enable cheap writes; background merge compacts segments.

Postings-list representation:- Each posting: docID delta (sorted), optional tf, positions block (delta-encoded positions), optional float weight per doc.- Store in blocks (e.g., 128–1024 postings) with header: baseDocID, block length, compressed payload, skip pointers to next block for faster seeks.

Compression:- Delta-encode integer sequences (docID/pos).- Use Variable-Byte (VByte) for low CPU complexity or Simple-9/VarInt-G8IU when memory-CPU balanced.- For dense long lists, use PForDelta (fast SIMD decompression) — good for long lists at scale.- Hybrid: use PForDelta for blocks > threshold (e.g., >2048 postings), VByte for small blocks. Store per-block codec id in header.

Prefix queries:- Use FST to enumerate terms with prefix; for many matching terms, perform query-time union/merge of postings using heap-merge of compressed blocks or build on-the-fly merged postings using OR/AND algorithms. For heavy prefixes, precompute prefix-aggregate postings or use an n-gram index to limit term explosion.

Merging updates efficiently:- Append-only segments: new docs go to in-memory buffer → flushed as immutable segment. Query engine searches across segments and merges postings at query time.- Background compaction: multi-way merge small segments into larger ones; apply delta decoding+re-encoding to rebuild efficient postings and update term dictionary pointers.- Use tombstones for deletes; periodic compaction purges deleted docs.- Make merges incremental and rate-limited to avoid IO spikes.

Memory-mapped files vs explicit IO & caching:- Memory-mapped (mmap): - Pros: simple API, OS-managed caching, zero-copy reads, good for random reads on large datasets. - Cons: less control over eviction, possible page-fault latency spikes, difficulties with partial writes and segmented updates, platform-specific behavior.- Explicit IO (pread/read + custom caching): - Pros: fine-grained control, can implement async IO, prioritize reads, custom LRU/ARC caches tuned for ML workload, safer for large write/merge patterns. - Cons: more complex code, user-space copying overhead.- Recommendation: use mmap for read-only compacted segments (fast, simple). Use explicit IO for write-heavy or merge operations and for keeping a small hot-postings cache (LRU) in process memory for repeated feature extraction during model serving.

Trade-offs and tuning:- Block size: larger blocks → better compression ratio and fewer seeks; smaller blocks → faster selective access and lower decode cost. Choose 128–512 postings typically.- Codec choice: PForDelta for throughput; VByte for CPU-constrained environments.- Keep per-term statistics (docFreq, collectionFreq) cached in-memory for ranking/feature scaling.- Provide metrics and throttling for merges; expose background compaction controls.

This design balances compression, update agility, and query latency for ML feature extraction pipelines while allowing practical operational controls.

HardSystem Design

79 practiced

Design an ANN retrieval system at billion-scale vectors with limited RAM. Discuss combining product quantization (PQ), inverted file (IVF) indexing, and disk-backed retrieval (SSD) while keeping recall high and latency low. Include strategies for index sharding, caching of centroids/quantized codes, and offline/online re-ranking.

Sample Answer

Requirements & constraints:- Serve nearest-neighbor queries over ~1B vectors, limited RAM (tens of GB), low tail latency (<50–100 ms), high recall (>90% top-k).- Use IVF + Product Quantization (PQ) + SSD-backed storage. Support updates and re-ranking.

High-level architecture:Client → Query Router → Sharded ANN Workers (inference + index) → SSD store (raw/partial vectors & PQ codes) → Re-ranker (online) → Return

Key components:1. IVF + PQ index:- Train coarse quantizer (k-means with Kcentroids ~100K) to build IVF. Each vector assigned to a centroid (inverted list).- Store per-vector PQ codes (e.g., M=8, 8 bytes) and optionally residual PQ for OPQ/ADC for higher accuracy.- Keep coarse centroids (K * D * float) in RAM to perform centroid lookup quickly.

2. Disk-backed storage:- Inverted lists and PQ codebooks stored on SSD in block-aligned files for sequential reads. Use memory-mapped IO (mmap) or async NVMe reads.- Store a compact metadata index (centroid -> file offset, list length) in RAM.

3. Sharding & routing:- Shard index across workers by centroid ranges (round-robin or balanced by list size). Router maps query to top-n nearest centroids and fans out to relevant shards.- Prefer multi-host redundancy for hot centroids.

4. Caching:- Cache coarse centroids and PQ codebooks fully in RAM.- Cache head of inverted lists (top-L PQ codes by recency/frequency) in RAM; use LFU for popular lists.- Query-level cache: result of top-k for repeated queries.- Use compressed in-memory caches (e.g., 4–8 bytes per code) and a small in-memory HNSW/graph for very low-latency hot queries.

5. Retrieval pipeline:- Step 1 (coarse search): compute distances to centroids in RAM and select top-C centroids (e.g., C=64).- Step 2 (PQ distance scan): dispatch reads to shards to load PQ codes for selected lists; compute asymmetric distance (ADC) on-the-fly using precomputed centroid+codebook tables in RAM.- Step 3 (candidate merging): aggregate top-R candidates (R large enough to retain recall, e.g., 1k–10k).- Step 4 (online re-ranking): fetch full vectors for top-B candidates (B=50–200) from SSD or a tiered store (if cold -> SSD; if hot -> RAM) and compute exact distances (or use a small neural reranker). Return final top-k.

6. Offline/online re-ranking:- Offline: periodically run more expensive re-ranking (e.g., with cross-encoder or higher-dim features) to precompute rerank scores for frequently queried keys; store them in cache.- Online: lightweight re-ranker (dot-product or small MLP) that uses full vectors for top-B candidates; optionally asymmetric hashing + residuals for higher fidelity.

7. Accuracy vs latency trade-offs:- Increase C and R to raise recall; increase PQ bytes or use residual PQ for accuracy at cost of I/O and CPU.- Use OPQ to rotate space and improve PQ accuracy without adding bytes.- For strict latency, reduce C and rely on cached heads + aggressive re-ranking.

8. Practical optimizations:- Use vector tiling and SIMD for fast ADC; precompute lookup tables per query for PQ subquantizers.- Read SSD in large sequential blocks and use NVMe queues for parallel IO.- Background compaction: merge small inverted-list files, maintain balanced shard sizes.- Monitoring and adaptive auto-tuning: track recall/latency per centroid and adjust caching, C, R per query distribution.

Failure modes & mitigations:- Hot-spot centroids: replicate hot shards and use load-aware routing.- Stale offline reranks: version metadata and fallback to online re-ranker.- Memory pressure: degrade gracefully by serving from SSD-only path with lower C and larger latency SLO.

This design balances RAM constraints by keeping only small critical structures (centroids, codebooks, metadata, hot-cache) in memory, offloading bulk PQ codes and raw vectors to SSD, and combining coarse IVF pruning + efficient ADC + small online re-ranking to maintain high recall with low latency.

MediumTechnical

61 practiced

Discuss tensor memory layouts (row-major vs column-major, contiguous vs strided/noncontiguous) and how they affect batching, transposes, and GPU/kernel performance. Provide guidance on when to enforce contiguity, when to prefer channels-first vs channels-last for conv nets, and how to avoid expensive copies before GPU ops.

Sample Answer

Brief overview:- Row-major (C-contiguous): last index varies fastest (e.g., NumPy/PyTorch default: NHWC? actually PyTorch default tensor.stride uses row-major; common conv layouts vary). Column-major (Fortran): first index varies fastest. Contiguous means memory layout has no gaps; strided/noncontiguous means slices/transposes create strides that skip elements.

How layout affects ops:- Batching: contiguous batch dimension enables fast bulk copies, scatter/gather and batched GEMMs. If batch is noncontiguous, kernels must handle strided access which reduces memory coalescing on GPU.- Transposes: transposing usually produces a view with permuted strides (cheap) but subsequent ops often require contiguous layout; many GPU kernels expect contiguous memory for best bandwidth. For large tensors, forcing contiguous() does an expensive copy.- GPU/kernel perf: contiguous, properly aligned, and dimension-major ordering that matches kernel expectations (e.g., inner dimension contiguous for matrix-multiply) gives maximum memory coalescing and vectorized loads/stores. Strided access leads to cache misses, uncoalesced loads, and lower occupancy.

Guidance:- Enforce contiguity when you will call kernels that assume contiguous inputs (cuBLAS/cuDNN matmul/conv) or when you plan many successive elementwise ops that benefit from contiguous GCC-friendly memory. Use tensor.contiguous() sparingly and batch such conversions to avoid per-call copies.- Channels-first (NCHW): often faster on CUDA/cuDNN historically because kernels expect NCHW and cuDNN is highly optimized; NCHW makes channel and spatial dims contiguous for many implementations. Channels-last (NHWC) can be faster for some architectures (e.g., mixed-precision, TPU, or memory-bound backbones) and enables better SIMD/AVX utilization on CPU and some GPUs with channels-last optimized kernels.- Prefer channels-last if: using frameworks/hardware that provide optimized NHWC kernels (TPU, recent cuDNN versions with channel-last support), large batch sizes, and when memory bandwidth is the bottleneck. Prefer channels-first when using legacy CUDA kernels or when the framework's conv implementation is tuned for NCHW.

How to avoid expensive copies:- Design pipeline to produce tensors in the desired layout (data loader, augmentations, preprocessing should respect target memory layout).- Use in-place ops and avoid unnecessary transpose chains; collapse or reorder ops to postpone transposes until just before a kernel that must have specific order.- Use framework helpers: PyTorch supports memory_format=torch.channels_last to allocate tensors in NHWC and to convert whole models via .to(memory_format=).- When interfacing with libraries (cuDNN/cuBLAS), batch conversions: convert once per batch rather than per sample; reuse preallocated buffers to avoid repeated allocations.- Profile: use nvprof/nsys and framework profilers to find expensive copies and check tensor.is_contiguous() and .stride().

Example practical rule: Keep training loop tensors in the format expected by your dominant compute kernels; if you must transpose for a small number of ops (e.g., visualization), do it on CPU asynchronously or after backward to avoid blocking critical GPU path.

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.