In-Memory Query Engine: Solution Walkthrough
In-Memory Query Engine is a small service for searching transaction records. You give it a filter, such as "settled payments for acct-1 of at least $25.00", and it returns the matching records, newest first.
The starting code handles a single filter correctly, but breaks as soon as you combine two.
The round has five phases:
- Phase 0: Read the existing code, fill in three blanks in a test, and answer three open questions about ordering and pagination.
- Phase 1: A bug report lists four symptoms. They turn out to be four separate bugs across two small files.
- Phase 2: Add cursor pagination with signed, tamper-proof cursors.
- Phase 3: Add
insertanddeletewhile keeping pages correct as records change underneath them. - Phase 4: Grow the dataset to 200,000 records and make queries fast enough to pass a time limit.
Each phase builds on the previous one, so the decisions you make early on matter.
In Phase 1, fixing the sort gives every record an exact position based on (createdAt, id). That exact position is what makes the Phase 2 cursor correct.
If the Phase 2 cursor is a real keyset cursor (one that remembers the last key returned, not a row count), Phase 3 needs almost no work in query(). Phase 4 then comes down to a binary search over that same key.
A candidate who gets the ordering key right early finds every later phase smaller. One who gets it slightly wrong keeps paying for it.