Frontend School

Top K Frequent Search Suggestions

DSA
medium

Top K Frequent Search Suggestions

Medium
Trie
String
Sorting
Data Structures

Overview

Airbnb's search experience is paramount for connecting guests with unique stays and experiences. When users begin typing into the search bar, providing relevant and popular suggestions can significantly enhance usability and reduce friction. This problem asks you to implement a system that, given a list of historical search queries and a user's current input prefix, efficiently returns the top k most frequent full queries that start with that prefix.

What you need to do / Task

Implement the getTopKFrequentSuggestions function that performs the following:

  1. Process Queries: Given an initial list of historical queries, calculate the frequency of each unique query.
  2. Build Data Structure: Construct an appropriate data structure (e.g., a Trie) to store these queries, allowing for efficient prefix-based searching.
  3. Find Matches: Given a prefix string, traverse your data structure to identify all full queries that begin with this prefix.
  4. Rank and Select: From the identified matching queries, return the k most frequent ones. If there are fewer than k matching queries, return all of them.
  5. Sort Results: The suggestions must be sorted primarily by frequency in descending order. If two suggestions have the same frequency, they should be sorted alphabetically in ascending order.

Input & output

queries: An array of strings representing historical search queries. Each string is a valid query. k: An integer representing the maximum number of suggestions to return. prefix: A string representing the user's current input.

Return: An array of strings, representing the top k most frequent suggestions, sorted as specified.

Clarifications

  • Queries consist only of lowercase English letters ('a'-'z').
  • The frequency of a query is its total count in the input queries array.
  • If k is 0, an empty array should be returned.
  • If no queries match the given prefix, an empty array should be returned.

Examples

1

Example 1

Input:

queries = ["apple", "app", "apple", "apricot", "banana"], k = 2, prefix = "ap"

Output:

["apple","app"]

Note:

Queries and their frequencies: "apple": 2, "app": 1, "apricot": 1, "banana": 1. Matching queries for prefix "ap" are "apple" (2), "app" (1), "apricot" (1). Sorted by frequency (desc) then alphabetically (asc): [("apple", 2), ("app", 1), ("apricot", 1)]. Top 2 are "apple", "app".

2

Example 2

Input:

queries = ["flight", "fly", "fluffy", "flower"], k = 3, prefix = "flo"

Output:

["flower"]

Note:

Queries and their frequencies: all are 1. Only "flower" matches prefix "flo". Since k=3 and only one match, we return all matches.

3

Example 3

Input:

queries = ["apple", "banana", "apricot", "grape", "avocado"], k = 2, prefix = "a"

Output:

["apple","apricot"]

Note:

Queries and their frequencies: "apple":1, "banana":1, "apricot":1, "grape":1, "avocado":1. Matching queries for prefix "a" are "apple" (1), "apricot" (1), "avocado" (1), "banana" (1). Sorted alphabetically among those with same frequency: "apple", "apricot", "avocado", "banana". Top 2 are "apple", "apricot".

Constraints

Constraints & assumptions

  • 1 <= queries.length <= 10^4
  • 1 <= queries[i].length <= 100
  • queries[i] consists of lowercase English letters ('a'-'z').
  • 0 <= k <= queries.length
  • 1 <= prefix.length <= 100
  • prefix consists of lowercase English letters ('a'-'z').
  • The total number of characters across all unique queries will not exceed 10^5.

Out of scope

  • Handling non-alphabetic characters, digits, or case sensitivity in queries.
  • Ranking suggestions based on factors other than frequency (e.g., location, recency, user history).

What interviewers evaluate

  • Trie Implementation: Correct and efficient construction of the Trie data structure.
  • Prefix Search Logic: Efficient traversal and retrieval of all matching queries under a given prefix.
  • Frequency and Sorting: Accurate calculation of frequencies and correct application of sorting rules (frequency descending, alphabetical ascending).
  • Code Quality: Overall code structure, readability, and robust handling of edge cases.

Loading editor...