Design a File-Name Prefix Lookup System

Problem Given a list of file names, design a store that supports two operations: check whether an exact file name exists, and given a prefix, return every file starting with it (prefix "delivery" -> "delivery", "delivery hut", ...).

Requirements

• insert(fileName) and delete(fileName)
• exists(fileName) -> bool — exact-match existence check
• findByPrefix(prefix) -> List<String> — all names starting with the prefix
• Prefix search must not scan the entire file list

Core design Three approaches, each with a different trade-off:

• Hash set: O(1) existence checks and trivial to build, but a hash destroys locality by construction — keys that share a prefix land in unrelated buckets, so prefix search degenerates to a full scan. Usable only with an auxiliary sorted index alongside it.
• Sorted structure (balanced BST or sorted array): names in lexicographic order mean every prefix match occupies one contiguous range. Binary search the lower bound of the prefix, then walk forward while entries still match: O(log n + k). Existence is O(log n). Cheap on memory, and range/ordered iteration comes free.
• Trie (prefix tree): each node is one character; a path from the root spells a prefix. Walk L characters to reach the prefix node (O(L), independent of n), then enumerate the subtree for the k matches: O(L + k). Existence is O(L) with a terminal flag marking a complete name. The natural fit — the structure is the prefix relationship.

Trie construction detail: each node holds a child map (array of 26 for a fixed alphabet, hash map for arbitrary filename characters) plus an isEndOfWord flag, which is what distinguishes the stored name "delivery" from the mere prefix "deliver".

Discussion points

• Trie memory is the real cost: one node per character per unique path, with per-node child-map overhead. A compressed trie (radix tree) collapses single-child chains into one edge, cutting node count dramatically on filenames that share long unique tails.
• Trade-off: sorted array is compact and cache-friendly but O(n) to insert; trie gives O(L) insert and lookup independent of n, at several times the memory.
• Autocomplete usually wants ranked results, not all matches — storing a top-k list per node (or a max-priority value in the subtree) avoids enumerating a huge subtree just to return 10 suggestions.
• Case-insensitive and locale-aware matching: normalize on insert and query, and be explicit that byte-order sorting is not the same as human alphabetical order.
• Suffix-based lookups (find by file extension) are the mirror problem: a prefix trie cannot answer them, but a trie over reversed names, or a suffix trie/array, can.
• Deletion in a trie is fiddly — unset the terminal flag, then prune nodes bottom-up only while they have no children and no terminal flag.
• Concurrency: a shared trie under concurrent insert needs locking or a copy-on-write root swap; the sorted array is trivially safe if rebuilt immutably.