Time and Space Complexity Analysis Questions

Direct answer: An LRU (least-recently-used) cache combines a hash map (for O(1) key lookup) with a doubly linked list (for O(1) reordering and eviction) - a hash map alone can't track recency order in O(1), and a linked list alone can't look up a key in O(1); the combination gives each structure the job it's good at.

Structured elaboration

• A hash map alone gives O(1) get/put by key, but has no notion of "which key was used least recently" without an O(n) scan - you'd need to store and update timestamps, then scan all entries to find the minimum, which is O(n) per eviction.
• A doubly linked list alone naturally tracks recency (move a node to the front on every access, evict from the back), but finding a node by KEY to move it requires an O(n) linear search through the list.
• Combined: the hash map stores key -> node pointers into the linked list. get(key): hash-map lookup finds the node in O(1), then the node is unlinked and relinked at the front of the list in O(1) (doubly-linked, so both neighbors are known without a search). put(key, value): same O(1) lookup-and-move if the key exists, or O(1) insertion at the front plus (if over capacity) O(1) removal of the tail node, whose key is then also removed from the hash map.
• The critical design detail: the hash map's VALUE isn't the cached value directly - it's a pointer/reference to the linked-list NODE, so that once you've found the node via the hash map, you can splice it within the list in O(1) without any further lookup.

Worked example

Trace put(1,'a'), put(2,'b'), get(1), put(3,'c') on a capacity-2 cache:

1. put(1,'a'): list = [1] (front=back=1), map = {1: node1}.
2. put(2,'b'): list = [2,1] (2 is now most-recent, at front), map = {1: node1, 2: node2}.
3. get(1): hash lookup finds node1 in O(1); since node1 is not already at the front, unlink it and relink at front: list = [1,2]. Returns 'a'.
4. put(3,'c'): over capacity (2 items already), so first evict the tail (2, the least-recently-used): remove node2 from the list AND delete key 2 from the map. Then insert 3 at the front: list = [3,1], map = {1: node1, 3: node3}.

Key 2 was correctly evicted because it was least-recently used relative to the get(1) access that promoted 1 - both the eviction (tail removal) and the promotion (move-to-front) happen in O(1) because the linked list's structure means every splice only touches a constant number of neighboring pointers.

Trade-offs & pitfalls

• If you used a SINGLY linked list instead of doubly linked, moving an arbitrary node to the front would require knowing its predecessor to unlink it - which means an O(n) search, defeating the purpose. The "doubly" part is not incidental; it's what makes O(1) splicing possible.
• Many candidates correctly identify "hash map + linked list" but then can't explain WHY neither alone suffices - be ready to name the specific operation (find-by-key for the list, recency-tracking for the map) that the other structure covers.
• This same hash-map-plus-doubly-linked-list pattern generalizes to any "O(1) lookup plus O(1) reordering" requirement, not just LRU - it's worth recognizing as a reusable pattern (e.g. LFU (least-frequently-used) caches use a similar idea with an extra layer for frequency buckets).

Direct answer: Beam search's naive complexity is O(L x B x V) - for each of L generation steps, you consider expanding each of the B current beam candidates by every one of V vocabulary tokens, then keep only the top B resulting sequences. The V factor (vocabulary size, often tens of thousands to hundreds of thousands for modern language models) usually dominates in practice, making vocabulary-side pruning the highest-leverage optimization.

Structured elaboration

• At each of L steps: each of the B beam candidates can be extended by any of V possible next tokens, giving $B \times V$ candidate continuations to score - scoring each candidate typically costs O(1) given the model's per-token output distribution is already computed, but SELECTING the top B from $B \times V$ candidates (if done via a full sort) costs $O(BV \log(BV))$, or $O(BV \log B)$ with a more efficient top-B selection (e.g. a bounded heap) - either way, dominated by the $BV$ term for realistic B and V.
• Total across L steps: $O(L \times B \times V)$ (ignoring the smaller log factor from top-B selection, or including it as $O(L \times BV \log B)$ for a more precise accounting).
• Pruning strategies: top-k restricts each step's candidate continuations to only the k highest-probability next tokens per beam (rather than all V), reducing the per-step candidate pool to $B \times k$ instead of $B \times V$ - a direct reduction proportional to $k/V$, often a massive factor for large vocabularies. Score-threshold pruning discards candidates whose cumulative score falls below some margin relative to the current best candidate, adaptively narrowing the search without a fixed k.

Worked example

For L=50 (output length), B=4 (beam width), V=50,000 (a realistic vocabulary size): naive per-step candidate count is $4 \times 50{,}000 = 200{,}000$, across 50 steps giving 10,000,000 total candidate evaluations. Restricting to the top k=100 next-tokens per beam (top-k pruning) before beam-scoring reduces per-step candidates to $4 \times 100 = 400$ - a 500x reduction (200,000/400), and across 50 steps, 20,000 total candidate evaluations instead of 10 million - a dramatic, directly quantifiable win from vocabulary-side pruning specifically, which is why it's the standard first optimization applied in practice, ahead of any beam-width reduction.

Trade-offs & pitfalls

• Increasing beam width B improves output quality (explores more candidate sequences) but increases cost linearly in B - and past a certain point, wider beams give DIMINISHING quality returns (a well-documented empirical phenomenon in sequence generation, sometimes even producing worse outputs past some beam width due to length-normalization or search-error interactions) - "wider is always better" is a common but incorrect assumption.
• Vocabulary-side pruning (top-k or nucleus/top-p sampling-style restriction) is usually the highest-leverage lever since V is typically much larger than B - always check whether the vocabulary term, not the beam-width term, is the actual bottleneck before optimizing beam width.
• Batched scoring (computing model outputs for the whole current beam set in one batched forward pass rather than B separate passes) is a real-world engineering optimization that doesn't change the O(L x B x V) asymptotic bound but substantially improves wall-clock throughput on parallel hardware - worth naming as complementary to the algorithmic pruning strategies.

Direct answer: CSR (compressed sparse row) stores non-zero values grouped by row, giving efficient row-slicing and fast sparse matrix-vector multiply when iterating row-by-row; CSC (compressed sparse column) stores the same data grouped by column, giving efficient column-slicing and is often preferred for certain factorization algorithms and column-oriented access patterns. Both give O(nnz) storage (nnz = number of non-zero entries) versus O(rows x cols) for a dense representation, and O(nnz) time for a full matrix-vector multiply - but the ROW vs COLUMN orientation determines which specific access patterns are cheap versus expensive.

Structured elaboration

• CSR: three arrays - values (non-zero entries, row-major order), col_indices (column index of each value), row_ptr (index into values where each row starts). Getting all of row $i$'s non-zero entries is O(1) to locate the start via row_ptr[i], then O(entries in that row) to read them - efficient row slicing. Sparse matrix-vector multiply ($Ax$) naturally iterates row-by-row (each output element is a dot product of one row with $x$), making CSR the natural format for this operation.
• CSC: the transposed structure - values, row_indices, col_ptr - efficient column slicing, and naturally suited to operations that iterate column-by-column, such as computing $A^Tx$ efficiently, or certain sparse factorization algorithms (like some sparse LU decomposition variants) that process columns sequentially.
• Sparse-sparse multiply: multiplying two sparse matrices efficiently often benefits from having one operand in CSR and the other in CSC (or requires an explicit format conversion), since the natural access pattern for the product touches ROWS of one matrix against COLUMNS of the other - this is a case where format MISMATCH between the two operands' natural orientation actually matters practically, not just as a minor implementation detail.
• Row/column slicing: CSR gives O(1)-to-locate, O(row size)-to-read row slices but O(nnz) (a full scan) for a column slice (no direct index into which entries belong to a given column without scanning); CSC is the exact mirror image.

Worked example

For sparse one-hot categorical features in a logistic-regression training pipeline (each example is a row, with a small number of non-zero features out of a very large feature space, say 100 non-zero out of 1,000,000 possible categories): if training processes examples ROW-BY-ROW (the typical case - one training example at a time, or a mini-batch of rows), CSR is the natural fit, giving O(1)-to-locate-plus-O(100)-to-read per example, versus a dense representation that would need O(1,000,000) per example just to skip over the near-entirely-zero row - a 10,000x difference in touched elements for this specific example (100 non-zeros out of 1,000,000 dimensions), and CSC would require a full O(nnz)-scale scan to gather one row's entries, since row membership isn't directly indexed in a column-oriented format.

Trade-offs & pitfalls

• Choosing the WRONG format for your dominant access pattern (e.g. CSC for a row-iteration-heavy workload) doesn't just lose a minor optimization - it can mean the difference between O(row size) and O(nnz) per access, a potentially enormous gap for large sparse matrices.
• Format CONVERSION (CSR to CSC or vice versa) itself costs O(nnz) time and O(nnz) extra memory (to hold both representations, at least temporarily) - if your pipeline genuinely needs both row and column access patterns at different stages, either maintain both formats (memory cost) or pay the conversion cost at each transition point.
• Neither format supports efficient random INSERTION of new non-zero entries (both require shifting subsequent array segments) - a workload with frequent structural updates (not just value updates to existing non-zero positions) may need a different sparse format (like COO - coordinate format - for construction, then convert to CSR/CSC once the structure is finalized) or a different data structure entirely (like a dictionary-of-keys format during incremental construction).

Direct answer: The roofline model plots achievable performance (FLOPs/second) against a computation's arithmetic intensity (FLOPs performed per byte of memory moved), with a "roof" formed by two ceilings: a flat ceiling at the hardware's peak compute throughput, and a sloped ceiling determined by peak memory bandwidth. A computation is COMPUTE-BOUND if its arithmetic intensity is high enough to sit under the flat compute ceiling; it's MEMORY-BOUND if its arithmetic intensity is low enough that the sloped memory-bandwidth ceiling is the binding constraint.

Structured elaboration

Arithmetic intensity $I = \frac{\text{FLOPs}}{\text{bytes moved}}$. The roofline's two ceilings:

$$\text{Attainable performance} = \min(\text{Peak FLOPs/s},\ I \times \text{Peak Bandwidth})$$

For low $I$ (few FLOPs per byte moved - e.g. simply summing an array, 1 FLOP per 4-8 bytes read), the $I \times \text{Bandwidth}$ term is the binding constraint: you're MEMORY-BOUND, and adding more compute capability (a faster chip) won't help until you either increase $I$ (do more work per byte moved, e.g. via tiling/blocking to increase reuse) or increase available bandwidth. For high $I$ (many FLOPs per byte - e.g. a well-tiled matrix multiply, which reuses each loaded value many times), you eventually hit the flat compute ceiling: you're COMPUTE-BOUND, and only a faster compute unit (or lower-precision arithmetic, or fewer redundant FLOPs) helps.

Worked example

The question gives: matrix multiply requires $2n^3$ FLOPs and moves $O(n^2)$ elements of size 4 bytes (assume single-precision floats, and that with sufficient blocking each of the $n^2$ elements per matrix is read from main memory only once, a best-case bandwidth assumption). Arithmetic intensity:

$$I = \frac{2n^3 \text{ FLOPs}}{3 \times n^2 \times 4 \text{ bytes}} = \frac{2n^3}{12n^2} = \frac{n}{6} \text{ FLOPs/byte}$$

(the factor of 3 accounts for reading matrices A and B and writing/reading the output C, each $n^2$ elements). Take a representative GPU with peak compute of 20 TFLOP/s and peak memory bandwidth of 900 GB/s. The ridge point (where the two ceilings cross) is at $I_{\text{ridge}} = \text{Peak FLOPs} / \text{Peak Bandwidth} = 20 \times 10^{12} / 900 \times 10^9 \approx 22.2$ FLOPs/byte. Setting $I = n/6 = 22.2$ gives $n \approx 133$: for $n$ larger than roughly 133 (with this idealized single-read-per-element assumption), the (well-tiled) matrix multiply is compute-bound; for smaller $n$, it would be memory-bound. This matches real-world experience: large matrix multiplies are compute-bound on modern accelerators (which is exactly why they benefit so much from more raw FLOP throughput, e.g. specialized tensor cores), while operations with inherently low arithmetic intensity (elementwise ops, simple reductions) remain memory-bound regardless of how fast the compute units are.

Trade-offs & pitfalls

• This calculation assumes an IDEALIZED memory-access pattern (each element read exactly once, via good tiling) - a naive, unblocked matrix multiply has much lower EFFECTIVE arithmetic intensity (repeated re-reads of the same data from memory), which is precisely why tiling (the roofline-adjacent technique from the earlier survivor) matters: it doesn't change FLOP count, but it increases effective arithmetic intensity by improving reuse, potentially shifting an operation from memory-bound to compute-bound.
• The roofline model is a useful FIRST-ORDER diagnostic, not a complete performance predictor - it ignores latency effects, cache-hierarchy nuances (L1 vs L2 vs L3 have different bandwidths), and assumes perfect overlap of compute and memory access, none of which hold exactly in practice.
• Different operations on the SAME hardware can sit on very different points of the roofline - profiling a real workload's actual arithmetic intensity (not just assuming from the algorithm's FLOP formula) is the correct way to diagnose whether a specific kernel is compute- or memory-bound before trying to optimize it.

Direct answer: Detecting hot keys (disproportionately accessed shard keys) in a distributed workload trades off between exact counting (accurate but memory-proportional-to-distinct-keys, similar to the exact-vs-approximate top-K trade-off), sampling (cheap and low-overhead, but noisy for keys just above the detection threshold), and heavy-hitter sketch algorithms like Count-Min Sketch (bounded memory regardless of key cardinality, with a tunable but nonzero estimation error).

Structured elaboration

• Exact counting: maintain a per-key access counter (e.g. in a shared hash map or hardware counter array), flag any key exceeding a threshold. Perfectly accurate, but memory scales with the number of DISTINCT keys ever accessed - for a workload with a very large or unbounded key space, this can itself become a scalability problem (ironic, given the goal is detecting a scalability problem).
• Sampling: only track a random subset of requests (e.g. 1-in-1000), extrapolating observed frequencies to estimate full-traffic frequencies. Memory is bounded by how many DISTINCT keys appear in the sample (much smaller than the full key space), and detection latency/overhead is low - but for a threshold near the sampling rate's noise floor, sampling can both miss genuinely hot keys (false negative, if the sample happened to under-represent them) and flag non-hot keys as hot (false positive, from sampling variance) - the accuracy trade is fundamentally statistical, not just "less precise."
• Heavy-hitter sketch (Count-Min Sketch or similar): fixed memory regardless of key cardinality, with a one-sided (always-overestimate) error bound as derived in the companion sketch survivor - directly applicable here, since detecting "this key's estimated frequency exceeds a threshold" is exactly the heavy-hitters use case these structures are designed for.

Trade-offs & pitfalls

• Detection LATENCY matters as much as accuracy for this use case: a hot key causing real-time overload needs fast detection (favoring lightweight sampling or sketch-based approaches that update in O(1) per request) over a batch-computed exact count that might only be available minutes later, by which point the overload has already caused damage.
• The action taken on detecting a hot key (redistributing load, e.g. via additional replication or key-splitting/salting) has its own cost and complexity - detection is only half the problem, and a scheme that detects too aggressively (low threshold, high false-positive rate) can trigger unnecessary, costly rebalancing.
• Combining approaches is common in practice: cheap sampling or sketch-based detection as a fast first-pass alarm, with exact counting reserved for confirming and precisely measuring an already-suspected hot key, rather than running exact counting continuously across the full key space.