How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Uber.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Uber during technical interviews.

Implement Store Autocomplete | Uber Coding Question

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.

You are given a list of store names and a search string `s`. Return all store names whose names start with `s`. Matching is case-sensitive. If multiple stores match, return them in the same relative order as they appear in the original list. For this problem, implement the straightforward single-query version. In an interview, you can also discuss trade-offs between a simple linear scan and more advanced data structures for handling many autocomplete queries.

Constraints

0 <= len(stores) <= 100000
0 <= len(s) <= 100
0 <= len(store_name) <= 100 for each store name
Matching is case-sensitive
The output must preserve the original relative order of matching stores

Examples

Input: (["McDonald's", "KFC", "Burger king", "Bites", "Biscuit shop"], "B")

Expected Output: ["Burger king", "Bites", "Biscuit shop"]

Explanation: Only the store names starting with uppercase 'B' match, and they are returned in their original order.

Input: (["McDonald's", "KFC", "Burger king", "Bites", "Biscuit shop"], "Bi")

Expected Output: ["Bites", "Biscuit shop"]

Explanation: Both 'Bites' and 'Biscuit shop' start with 'Bi', while 'Burger king' starts with 'Bu'.

Input: (["Burger king", "bistro", "Bites"], "b")

Expected Output: ["bistro"]

Explanation: Matching is case-sensitive, so lowercase 'b' only matches 'bistro'.

Input: (["KFC", "Bites"], "")

Expected Output: ["KFC", "Bites"]

Explanation: Every string starts with the empty string, so all stores are returned.

Input: ([], "A")

Expected Output: []

Explanation: With no stores in the input list, there are no matches.

Input: (["KFC", "Subway"], "Mc")

Expected Output: []

Explanation: No store name starts with 'Mc', so the result is empty.

Hints

For a single autocomplete query, try scanning the list once and checking whether each store begins with the given prefix.
Be careful not to lose the original order of matching stores by sorting or using an unordered structure.

Quick Overview

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.