Implement Store Autocomplete
Company: Uber
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given a list of store names, for example:
```text
["McDonald's", "KFC", "Burger king", "Bites", "Biscuit shop"]
```
Implement an `autoComplete(s)` method that returns all store names whose names start with the input string `s`.
Example:
```text
autoComplete("B") -> ["Burger king", "Bites", "Biscuit shop"]
```
Assume matching is case-sensitive unless the interviewer specifies otherwise. If multiple stores match, return them in the same relative order as they appear in the original input list.
Be prepared to clarify requirements and discuss trade-offs for different implementations, such as a simple linear scan versus approaches optimized for many autocomplete queries. Write tests to verify your implementation.
Quick Answer: This question evaluates string matching, prefix search, and data structure selection skills by requiring an autocomplete method that returns entries beginning with a given prefix from a list of store names.