Frontend School

Pin Search Autocomplete

DSA
medium

Pin Search Autocomplete

Medium
Trie
String
Prefix Search
Data Structures

Overview

Pinterest users often search for specific pins or boards. To enhance the search experience, an autocomplete feature is crucial. When a user types a few characters, the system should instantly suggest relevant pin titles that match the entered prefix, helping them discover content faster and more accurately. This problem focuses on building the core logic for such a suggestion system.

What you need to do / Task

Implement a function getPinSuggestions that takes a list of existing pin titles and a search prefix as input. Your task is to:

  1. Construct an efficient data structure to store the given pinTitles.
  2. Given a searchPrefix, find all pinTitles from the stored collection that start with this searchPrefix.
  3. Return these matching pinTitles in lexicographical (alphabetical) order.

Input & output

Function Signature: function getPinSuggestions(pinTitles: string[], searchPrefix: string): string[]

  • pinTitles: An array of strings, where each string represents a unique title of a pin available on Pinterest.
  • searchPrefix: A string representing the partial input from a user in the search bar.
  • Returns: An array of strings, containing all pinTitles that begin with the searchPrefix. The returned titles must be sorted lexicographically.

Clarifications

  • Empty pinTitles: If the pinTitles array is empty, or if no titles match the searchPrefix, return an empty array.
  • Empty searchPrefix: If searchPrefix is an empty string, all pinTitles should be returned, sorted lexicographically.
  • Case Sensitivity: All comparisons should be case-sensitive. "apple" and "Apple" are different.
  • Uniqueness: Assume all pinTitles in the input array are unique.

Examples

1

Example 1

Input:

pinTitles = ["Fashion Trends", "Food Recipes", "Fitness Motivation", "Furry Friends", "Travel Destinations"], searchPrefix = "F"

Output:

["Fashion Trends","Fitness Motivation","Food Recipes","Furry Friends"]

Note:

Titles starting with 'F' are "Fashion Trends", "Food Recipes", "Fitness Motivation", "Furry Friends". Sorted alphabetically.

2

Example 2

Input:

pinTitles = ["Cats and Dogs", "Cars and Bikes", "Cooking Ideas", "Creative Crafts"], searchPrefix = "Ca"

Output:

["Cars and Bikes","Cats and Dogs"]

Note:

Titles starting with 'Ca' are "Cats and Dogs", "Cars and Bikes". Sorted alphabetically.

3

Example 3

Input:

pinTitles = ["Summer Vacation", "Winter Wonderland", "Autumn Leaves"], searchPrefix = "Spr"

Output:

[]

Note:

No pin titles start with the prefix 'Spr'.

4

Example 4

Input:

pinTitles = ["Art Projects", "Art History", "Artificial Intelligence"], searchPrefix = ""

Output:

["Art History","Art Projects","Artificial Intelligence"]

Note:

An empty prefix should return all titles, sorted lexicographically.

Constraints

Constraints & assumptions

  • 1 <= pinTitles.length <= 10^4
  • 1 <= pinTitles[i].length <= 100
  • 0 <= searchPrefix.length <= 100
  • All pinTitles and searchPrefix consist of lowercase and uppercase English letters, digits, and spaces.
  • The total number of characters across all pinTitles will not exceed 10^6.
  • The solution should be optimized for both time and space complexity, especially considering repeated calls to getPinSuggestions with different prefixes (though for this problem, we only call it once).

Out of scope

  • Handling non-ASCII characters or special symbols beyond letters, digits, and spaces.
  • Fuzzy matching or typo correction for the search prefix.
  • Ranking or relevance scoring for suggestions; simple prefix matching is sufficient.

What interviewers evaluate

  • Data Structure Choice: Ability to select and implement an appropriate data structure (e.g., Trie) for efficient prefix storage and retrieval.
  • Prefix Search Logic: Accurately traverses the Trie to find all words matching the given searchPrefix.
  • Lexicographical Ordering: Ensures the returned suggestions are sorted alphabetically. This can be achieved either by controlled Trie traversal or a final sort.
  • Edge Case Handling: Correctly handles empty pinTitles, empty searchPrefix, and no matching results.
  • Time Complexity: Achieves optimal time complexity for both Trie construction and search operations (e.g., O(L*N) for build, O(P + M) for search).
  • Space Complexity: Manages space efficiently for the Trie structure.

Loading editor...