The Library Search That Takes Four Seconds
The school library catalogue is a single SQLite table of 12,400 rows: id, title, author, isbn, shelf. The librarian, Ms Nolan, searches by title fragment several times an hour and wants results "as she types". The current page runs SELECT *, pulls every row into Python, lowercases each title and does a substring test. A search for "hist" takes 4.2 seconds on the library PC. About 40 records change each day - new arrivals, withdrawals, corrections. A student proposes sorting the titles once and using binary search; a second proposes a Python dictionary keyed by exact title; a third says "just add an index". The table is stored in insertion order and titles keep their original capitalisation. There are 3 duplicate titles and 11 records with no title at all. Ms Nolan insists the search must still find "A Short History of Europe" when she types hist.
1. Evaluate the binary-search proposal against the current linear scan, using the numbers given. Be explicit about what binary search can and cannot find.
Read the worked answer
Binary search on a sorted list takes about log2(12,400) ≈ 14 comparisons instead of up to 12,400 - roughly 900 times fewer. That is real, but three things undercut the proposal here.
(a) It answers a different question. Binary search needs a total order that matches the query. Sorted by title, it finds "History of Ireland" from the prefix hist. It cannot find a fragment in the middle of a word or phrase, so "A Short History of Europe" - which the librarian explicitly requires - is missed. The proposed fix silently changes behaviour, and a search that returns fewer results is a worse outcome than one that is slow.
(b) Maintaining the sort has its own cost. Forty edits a day times a full re-sort is 12,400 × 13.6 ≈ 170,000 comparisons per rebuild, which is more work than one scan per search. Inserting in order into a Python list is O(n) per insert (about 6,200 shifts on average) - fine at this size, but it only works if every write path maintains the invariant. One forgotten path and binary search returns confidently wrong answers, which is far worse than slow.
(c) It does not touch the bottleneck. The 4.2 seconds is dominated by pulling 12,400 rows through the DB driver and lowercasing 12,400 strings on every request. Twelve thousand in-memory substring tests take single-digit milliseconds. The algorithm is not what is slow.
2. Recommend what the team should actually build. Justify it against both alternatives: the sorted list plus binary search, and the dictionary keyed by title.
Read the worked answer
Recommendation: keep a normalised in-memory index, rebuilt only when the catalogue changes.
On startup, read the table once and build a list of (normalised_title, id) pairs, where normalised means lowercased and whitespace-collapsed. A search then scans that list for a substring - no I/O, no per-request lowercasing. At 12,400 entries the memory cost is roughly 12,400 × 60 bytes ≈ 1 MB, which is nothing, and a scan is microseconds. Rebuild the index when a write happens: 40 rebuilds a day is trivial. This preserves substring matching, which is the requirement, and removes the actual cost.
Against sorted list + binary search: it is faster per comparison but cannot answer a mid-string substring query, and it makes every write path responsible for an invariant. The failure mode is wrong results, not slow results.
Against the dictionary: a dict gives O(1) lookup but only for exact, normalised keys. hist is not a key. It also collapses duplicates unless the values are lists, and the 11 untitled records need a deliberate policy (exclude them from the title index, keep them searchable by author). A dict is the right structure for "look up this ISBN", not for "find titles containing this text".
If the catalogue ever outgrows memory or the search needs ranking, SQLite's FTS5 virtual table gives the same substring/word behaviour with an on-disk index - and note that a plain B-tree index on title only accelerates LIKE 'hist%' prefix queries, not LIKE '%hist%'.
3. The librarian types quickly, so every keystroke currently fires a request. Explain what difference that makes to your solution and what else you would change for a catalogue of two million rows.
Read the worked answer
Debounce first. Typing "history" fires seven requests, six of which are thrown away. Even with an instant index, that is seven times the work and seven chances to interleave a slow response with a fast one, so a stale result can overwrite a fresh one (a race the team should fix by tagging each response with its query and discarding mismatches). Waiting 150–250 ms after the last keystroke, plus cancelling in-flight requests, cuts the load by an order of magnitude and changes nothing the librarian notices. Debouncing is worth doing before the index, because it is five lines and it helps on the slowest machine in the room.
At two million rows, the in-memory index stops being free. Two million × ~60 bytes is over 100 MB per process, plus rebuild time on every write; that is no longer a sensible thing to hold in a request-handling web app. The design changes in three ways:
- Move matching into the database with an FTS5 index and only return the top 50 rows. Ranked results and limits replace full materialisation.
- Keep the debounce and add a minimum query length (two characters), because short prefixes match almost everything.
- Reconsider the requirement: at that size a prefix/word index is the only thing that scales, so the librarian's substring requirement needs renegotiating rather than engineering around.