Instacart·Software Engineer·Technical Phone Screen
- Design a data structure with an add(name) method and a find(prefix, suffix) method that returns all stored file names matching both a given prefix and suffix, in lexicographic order. Discuss time and space complexity and compare approaches like dual tries, suffix automata, and inverted indexes. Assume up to 100,000 insertions and frequent queries.
“I went straight for the two-trie approach: one trie for prefixes, one for reversed strings to handle suffixes, then intersect the result sets.”