Choosing a Data Structure for a Library Search Feature
A school library has 24,000 catalogue records. Each record has a title, author, ISBN and up to 6 subject tags. Students search by exact ISBN, by partial title, and by subject tag. The current system loads all records into a list and scans linearly for every search; a title search takes about 1.8 seconds, which students find too slow. The library wants results under 300 ms. Two students propose: (A) keep the list but sort it once by title and use binary search for all three search types; (B) build a hash map keyed by ISBN, a sorted array of titles for binary search, and an inverted index from tag to record ids.
1. Assess proposal A and proposal B against each of the three search types. Which should be chosen and why?
Read the worked answer
Proposal A: sorting by title makes exact-title and prefix searches fast (binary search, O(log n)), but partial title (substring anywhere) still needs a scan unless the query is a prefix, and ISBN and tag searches gain nothing from title order. So A fixes at most one of three needs.
Proposal B: hash map gives O(1) exact ISBN lookup; sorted titles give O(log n) for prefix and exact title; the inverted index gives O(1)-ish tag lookup returning only matching ids. Substring-anywhere title search still needs a scan or a suffix structure, but with 24,000 records a single scan is fast enough if done in memory on ids only. B is the right choice because it matches each access pattern to a structure. The team should measure the substring case separately.
2. The inverted index must be rebuilt when a record's tags change. Explain the cost and one way to keep it correct without full rebuilds.
Read the worked answer
A full rebuild costs O(total tag entries), which is at most 24,000 x 6 = 144,000 entries; that is cheap once but wasteful on every edit. Incremental update: when a record's tags change, remove its id from the old tag lists and add it to the new ones. This is O(old tags + new tags), i.e. at most 12 operations per edit.
Correctness risk: stale ids if a removal is missed. Mitigate by storing the record's current tag set and diffing, or by validating ids on read (check the record still has that tag). The library should log tag edits and run a periodic consistency check rather than rebuilding on every save.
3. A student suggests caching every search result forever to make repeat searches instant. Give one benefit and two risks, and state a policy.
Read the worked answer
Benefit: repeat popular searches (e.g. the same class assignment) return instantly and reduce load.
Risks: (1) Stale results after catalogue edits, so a student sees a book that was removed or misses a new one; (2) unbounded memory growth from caching every distinct query, including one-off long-tail searches, which wastes memory for little gain.
Policy: cache only the top N frequent queries (e.g. 500) with a short time-to-live (e.g. 5 minutes), invalidate a cached entry when a matching record changes, and never cache per-student data. This keeps the benefit and bounds staleness and memory.