In-Memory Databases And Query Engines

What's being tested

These prompts test translating SQL-like operations into efficient in-memory algorithms: data modeling, indexing, query execution (projection/filter/sort), and complexity reasoning. Interviewers probe choices of data structure (storage layout, indexes), algorithmic cost, and simple API/edge-case handling under memory constraints.

Patterns & templates

• std::unordered_map / hash table for point lookups — O(1) average, O(n) worst; good for exact-key get/put workloads.

• Sorted array or std::map (tree) for range queries — O(log n + k) to locate start, then sequential scan for k results.

• Columnar projection: read only needed columns to reduce memory bandwidth and cache misses; ideal when few columns are selected.

• Predicate pushdown: apply filters early to shrink working set before expensive operations like sort or join.

• Bitmap / bitset indexes for low-cardinality filters — fast boolean intersection, memory-efficient for millions of rows.

• Secondary index tradeoff: faster reads vs extra write + memory; build only on frequently filtered columns.

• Eviction/LRU for bounded-memory tests — maintain a recency queue and reclaim full rows or columns as configured.

• Stable sort / tie-breaker: use std::stable_sort when deterministic ordering (multi-key) matters; sorting costs O(n log n).

Common pitfalls

Pitfall: Counting only average-case hash complexity — interviewers will ask about worst-case and adversarial input; mention fallback (tree/hash with rehashing).

Pitfall: Ignoring memory for indexes — adding multiple secondary indexes can double/triple memory; quantify approximate per-row overhead.

Pitfall: Designing only for single-threaded access — at least mention concurrency/atomicity and simple locks or copy-on-write for reads.

The practice cards below cover the canonical variants — solve all of them and time yourself.