Design a File-Name Prefix Lookup System (Autocomplete)

Requirements: Given a list of file names, design a data structure/store such that you can (1) look up whether a file exists, and (2) given a prefix, return all files that start with that prefix (e.g. prefix "delivery" -> "delivery", "delivery hut", ...).

Design: Multiple valid approaches were expected:

• Hashing: a hash set gives O(1) existence checks, but prefix search needs an auxiliary sorted index since a hash set alone can't do range/prefix queries efficiently.
• Trees (sorted structure): store file names in sorted order (e.g. a balanced BST or sorted array) so a prefix range can be located via binary search.
• Trie (prefix tree): each node represents one character; existence check and prefix enumeration are both efficient (O(L) to locate the prefix node, O(k) to enumerate k matches) -- the most natural fit for prefix queries.

Discussion extended to suffix tries for suffix-based lookups (e.g. by file extension), though not covered in depth due to time constraints.