Frontend School

Autocomplete Suggestions for Restaurant Search

DSA
easy

Autocomplete Suggestions for Restaurant Search

Easy
Trie
String
Data Structures

Overview

Zomato's success heavily relies on its intuitive user experience, especially in search. When a user starts typing a restaurant name, providing instant, accurate autocomplete suggestions significantly enhances usability. This problem challenges you to implement a core component of such a system using a Trie data structure, enabling efficient prefix-based searches for restaurant names.

What you need to do / Task

Your task is to implement the RestaurantSearchTrie class, which supports the following operations:

  1. constructor(): Initializes the Trie data structure.
  2. insert(word: string): Inserts a word (restaurant name) into the Trie.
  3. search(word: string): Returns true if the word is in the Trie, and false otherwise.
  4. startsWith(prefix: string): Returns true if there is any word in the Trie that starts with the given prefix, and false otherwise.

Input & output

  • insert(word: string): Takes a string word representing a restaurant name. This method does not return anything.
  • search(word: string): Takes a string word. Returns a boolean.
  • startsWith(prefix: string): Takes a string prefix. Returns a boolean.

Clarifications

  • All word and prefix inputs will consist of lowercase English letters (a-z).
  • The Trie should handle duplicate insertions gracefully (i.e., inserting an existing word again should not change the search or startsWith behavior).
  • An empty string word or prefix is not expected as input.

Examples

1

Example 1

Input:

operations = ["RestaurantSearchTrie", "insert", "insert", "search", "search", "startsWith", "startsWith", "insert", "startsWith"], params = [[], ["pizza"], ["pizzeria"], ["pizza"], ["pizzaria"], ["piz"], ["burg"], ["burger"], ["burg"]]

Output:

[null, null, null, true, false, true, false, null, true]

Note:

  1. RestaurantSearchTrie(): Initializes an empty Trie.
  2. insert("pizza"): Adds "pizza" to the Trie.
  3. insert("pizzeria"): Adds "pizzeria" to the Trie.
  4. search("pizza"): Returns true as "pizza" exists.
  5. search("pizzaria"): Returns false as "pizzaria" does not exist.
  6. startsWith("piz"): Returns true as both "pizza" and "pizzeria" start with "piz".
  7. startsWith("burg"): Returns false as no word currently starts with "burg".
  8. insert("burger"): Adds "burger" to the Trie.
  9. startsWith("burg"): Returns true as "burger" now exists and starts with "burg".
2

Example 2

Input:

operations = ["RestaurantSearchTrie", "insert", "search", "startsWith"], params = [[], ["food"], ["food"], ["fo"]]

Output:

[null, null, true, true]

Note:

  1. RestaurantSearchTrie(): Initializes.
  2. insert("food"): Adds "food".
  3. search("food"): Returns true.
  4. startsWith("fo"): Returns true.

Constraints

Constraints & assumptions

  • The total number of insert operations will not exceed 3000.
  • The total number of search and startsWith operations will not exceed 10^4.
  • The length of any word or prefix will be between 1 and 20 characters.
  • The Trie will only store lowercase English letters.
  • Time complexity for insert, search, and startsWith should be optimal (proportional to the length of the input string).
  • Space complexity should be proportional to the total number of characters across all unique words inserted.

Out of scope

  • Handling uppercase letters, numbers, or special characters in restaurant names.
  • Deleting words from the Trie.
  • Returning actual suggestion lists (just boolean checks for existence/prefix match).

What interviewers evaluate

  • Correctness of Trie implementation for insert, search, and startsWith.
  • Efficiency of the chosen data structure and algorithms (time and space complexity).
  • Code clarity, organization, and adherence to best practices.
  • Ability to reason about the problem and articulate the solution.

Loading editor...