Interview prompt
Explain choosing a search or sorting strategy to an engineer who understands the surrounding system but has not used this technique. Walk from its contract to a concrete operation, then discuss where it fails or becomes expensive.
A strong answer
Search and sorting choices depend on what is already known about the data and what operations the product needs. A sorted array supports binary search because its order lets each comparison eliminate half the remaining candidates. An unsorted collection cannot safely use that shortcut.
If a dataset is queried once, sorting solely to run one binary search may cost more than a linear scan. If it will serve thousands of lookups, paying the sort cost once can be worthwhile. Merge sort preserves equal-key order when implemented stably; quicksort often has strong locality but can have quadratic worst-case behavior without safeguards.
A complete answer also calls out the assumptions that control correctness. Sorting is not free metadata: updates can invalidate order, and duplicate handling affects semantics. Binary search also requires a precise boundary convention; off-by-one errors often appear when the target is absent or repeated. For large data, external sorting must account for disk reads and writes.
Close by describing one representative test or measurement. Given repeated lookup, frequent insertion, and duplicate keys, compare a sorted array, balanced search tree, and hash table. Explain which requirement changes your choice.
Follow-up questions
Answer the follow-ups in the frontmatter. Use the linked article for the concept and the trace to make the explanation concrete.