Store name autocomplete by typed prefix

Implement autocomplete over a list of store names: given the prefix a user has typed so far, return the stores whose names begin with it. The list is loaded once and then queried many times, once per keystroke.

Interface

Unless you agree on a different interface with the interviewer, assume:

• StoreAutocomplete(names: list[str]) — builds whatever index you choose.
• suggest(prefix: str, limit: int = 10) -> list[str] — names that start with prefix, ignoring case, in alphabetical order, at most limit of them. An empty prefix returns [].

Example

ac = StoreAutocomplete(["Starbucks", "Star Market", "Staples", "Subway", "Stop & Shop"])
ac.suggest("sta")        ->  ["Staples", "Star Market", "Starbucks"]
ac.suggest("st", 2)      ->  ["Staples", "Star Market"]
ac.suggest("su")         ->  ["Subway"]
ac.suggest("x")          ->  []

Constraints

• Up to 10^5 names of up to 100 characters; up to 10^5 queries.
• Names may contain spaces, digits and punctuation.

Clarifying questions

• Is matching case-insensitive? Should accents be ignored?
• Only the start of the full name, or the start of any word ("Market" matching "Star Market")?
• How many results, and in what order: alphabetical, by popularity, by distance?
• Can duplicates appear in the list, and should they be returned once?
• Can stores be added or removed after loading?

What a strong answer covers

• A baseline: a linear scan with startswith, and why it is fine for a few thousand names.
• A sorted list with binary search for the first match, then reading forward: O(log n + k).
• A trie keyed on normalized characters, storing at each node the top limit names so a query costs O(len(prefix)).
• The memory cost of each option and when the trie is worth it.
• Tests: empty prefix, no matches, a prefix equal to a full name, case differences.

Follow-ups

• Rank by popularity instead of alphabetically, and keep top results cheap per keystroke.
• Match any word in the name, not only the start.
• Tolerate one typo in the prefix.
• Stores open and close during the day. Support inserts and deletes.