This question evaluates a candidate's ability to design and reason about in-memory data storage, indexing, query planning, and the underlying data structures and algorithms for insert and query operations.
##### Question
Design and implement an in-memory database that supports:
insert(table, record)
query(table, columns_to_project, conditions=[(column, operator, value)], order_by=(columns, ascending))
Extend the design to explain how indexes would be built and used for faster WHERE and ORDER BY queries.
Quick Answer: This question evaluates a candidate's ability to design and reason about in-memory data storage, indexing, query planning, and the underlying data structures and algorithms for insert and query operations.
Design an In-Memory Database: Insert, Query, and Indexing
Design and implement a minimal, single-process, in-memory database intended to be embedded inside a service. The database manages multiple named tables, each with a simple schema, and must support one write operation and one read operation.
query
returns the rows of
table
that satisfy all
conditions
, projected down to
columns_to_project
, optionally sorted by
order_by
.
Data model and assumptions
A
record
is a dictionary keyed by column name.
Each
table has a defined schema
— column names and basic types (
int
/
float
/
string
). You may keep type handling simple.
Conditions
are a list of
(column, operator, value)
tuples, combined with
AND
semantics. Supported operators:
=
,
!=
,
<
,
<=
,
>
,
>=
, and
IN
(the last is optional).
order_by
is
(columns, ascending)
: one or more columns to sort by, plus a boolean
ascending
flag.
Execution is
single-threaded
. You do
not
need to support transactions or persistence.
Constraints & Assumptions
Single process, single thread.
No concurrent readers/writers; no locks, transactions, MVCC, durability, or persistence required (raise them only as extensions).
In-memory only.
The full dataset fits in RAM; assume up to the low millions of rows per table so that an
O(N)
full scan is "noticeable but survivable," and a sub-linear access path is a clear win.
Read-heavy, point-and-range workload.
Treat
query
as the hot path: equality lookups (
=
/
IN
), range scans (
<
,
<=
,
>
,
>=
), and
ORDER BY
are the patterns to optimize.
AND-only conditions.
All conditions in one
query
are combined with
AND
;
OR
, joins, aggregation, and
GROUP BY
are out of scope.
Schema is fixed per table.
Columns and their types are known when the table is created; you may keep type checking lightweight.
Clarifying Questions to Ask
What is the expected
table size
and
read:write ratio
— are we optimizing a write-once/read-many analytics store, or a churn-heavy mutable store?
Do queries need
OR, joins, or aggregation
, or strictly
AND
-combined single-table predicates with projection and sort?
Are
deletes and updates
in scope, or only
insert
+
query
? (This decides whether indexes need maintenance on more than just inserts.)
How should
NULL / missing columns
behave in comparisons and in
ORDER BY
— SQL-style three-valued logic, or something simpler?
For
order_by
, is a
single ascending flag for all columns
acceptable, or do you need per-column sort direction?
Are
multi-column (composite) indexes
expected, or is single-column indexing enough for the first pass?
Part 1 — Core design
Design the in-memory data structures and algorithms that implement insert and query. Explain how records are stored, how a record is addressed once written, how conditions are evaluated under AND semantics, and how projection and ordering are applied.
Part 2 — Implementation sketch
Provide working pseudocode or a compact, idiomatic implementation (e.g. Python / Go / Java) showing the core logic for both operations: schema validation and append on insert; candidate selection, residual filtering, ordering, and projection on query.
Part 3 — Indexing
Extend the design to explain how indexes would be built and used to speed up WHERE (conditions) and ORDER BY queries. Cover all four of the following:
What index types
you would support, and why.
How inserts update indexes
(index maintenance on write).
How the query planner chooses
which index to use for different predicates and orderings.
Complexity trade-offs and edge cases.
What a Strong Answer Covers Premium
Follow-up Questions
Deletes and updates.
How do indexes stay consistent when a row is deleted or an
indexed
column is updated? What exactly breaks if you forget to maintain the index on such a write?
Composite indexes.
How does a multi-column index serve
ORDER BY (a, b)
with no post-sort, and which queries does the leftmost-prefix rule
not
help?
Picking the right access path.
Given
id = 7 AND age >= 0
, which index should drive the scan and why? How would a cost-based planner decide between using an index to avoid the sort vs. filtering with a selective index and sorting the small result?
Scaling out of memory.
What changes if the dataset no longer fits in RAM, or if you need concurrent readers and a single writer, durability, or crash recovery?