Design Search Autocomplete System - Practice Coding Problems

Design Search Autocomplete System - Problem

String Depth-First Search Design Trie Sorting Heap (Priority Queue) Data Stream Hard

Design a search autocomplete system for a search engine. Users may input a sentence (at least one word and end with a special character '#'). You are given a string array sentences and an integer array times both of length n where sentences[i] is a previously typed sentence and times[i] is the corresponding number of times the sentence was typed.

For each input character except '#', return the top 3 historical hot sentences that have the same prefix as the part of the sentence already typed. Here are the specific rules:

The hot degree for a sentence is defined as the number of times a user typed the exactly same sentence before.
The returned top 3 hot sentences should be sorted by hot degree (The first is the hottest one).
If several sentences have the same hot degree, use ASCII-code order (smaller one appears first).
If less than 3 hot sentences exist, return as many as you can.
When the input is a special character '#', it means the sentence ends, and in this case, you need to return an empty list.

Implement the AutocompleteSystem class:

AutocompleteSystem(String[] sentences, int[] times) Initializes the object with the sentences and times arrays.
List<String> input(char c) This indicates that the user typed the character c. Returns an empty array [] if c == '#' and stores the inputted sentence in the system. Returns the top 3 historical hot sentences that have the same prefix as the part of the sentence already typed.

Input & Output

Example 1 — Basic Autocomplete

$ Input: sentences = ["i love you", "island", "iroman", "i love leetcode"], times = [5,3,2,2], operations = ["i", "#"]

› Output: [["i love you","island","i love leetcode"], []]

💡 Note: When user types 'i', system returns top 3 sentences starting with 'i' sorted by frequency: 'i love you'(5) > 'island'(3) > 'i love leetcode'(2). When '#' is typed, sentence ends and empty list is returned.

Example 2 — Progressive Typing

$ Input: sentences = ["i love you", "island", "iroman"], times = [5,3,2], operations = ["i", " ", "a", "#"]

› Output: [["i love you","island","iroman"], ["i love you"], [], []]

💡 Note: Type 'i': all 3 sentences match. Type ' ': only 'i love you' matches. Type 'a': no sentence starts with 'i a'. Type '#': end sentence, return empty.

Example 3 — New Sentence Added

$ Input: sentences = ["i love you", "island"], times = [5,3], operations = ["i", "s", "#", "i", "s"]

› Output: [["i love you","island"], [], [], ["i love you","island","is"], []]

💡 Note: First query 'i' shows existing sentences. After typing 'is#', new sentence 'is' is added with frequency 1. Next 'i' query now includes the new sentence 'is' as 3rd result.

Constraints

1 ≤ sentences.length ≤ 100
1 ≤ sentences[i].length ≤ 100
sentences[i] consists of lowercase English letters and spaces.
1 ≤ times[i] ≤ 50
At most 5000 calls will be made to input.

Visualization

Tap to expand

Understanding the Visualization

Input Data

Historical sentences with their frequencies

Build System

Organize sentences for efficient prefix-based retrieval

Query Process

Return top 3 hot sentences matching current prefix

Key Takeaway

🎯 Key Insight: Trie structure with pre-sorted top-k sentences at each node enables efficient autocomplete

Asked in

G Google 15 a Amazon 12 f Facebook 8 M Microsoft 6

The key insight is using a Trie (prefix tree) to efficiently organize sentences by their prefixes. Each Trie node maintains the top 3 sentences for that prefix, pre-sorted by frequency and lexicographically. Best approach is Trie with efficient search: Time: O(p + k log k), Space: O(ALPHABET_SIZE × N × M)

Common Approaches

Approach	Time	Space	Notes
✓ Trie with Efficient Search	O(p + k log k)	O(ALPHABET_SIZE × N × M)	Use a Trie (prefix tree) to organize sentences by prefix for faster lookups
Brute Force Linear Search	O(n × m × k)	O(n × m)	For each character input, search all sentences linearly to find matching prefixes

Trie with Efficient Search — Algorithm Steps

Build Trie with sentences and frequencies
For each character, traverse to the next Trie node
At each node, maintain sorted list of top sentences
Return top 3 sentences from current node
Handle '#' by adding new sentence to Trie

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Trie

Organize sentences by prefix in tree structure

Navigate

For each character, move to next Trie node

Retrieve

Get pre-sorted top 3 sentences from current node

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_CHILDREN 256
#define MAX_SENTENCES 3

typedef struct SentenceFreq {
    char sentence[200];
    int freq;
} SentenceFreq;

typedef struct TrieNode {
    struct TrieNode* children[MAX_CHILDREN];
    SentenceFreq sentences[MAX_SENTENCES];
    int sentenceCount;
} TrieNode;

typedef struct {
    TrieNode* root;
    TrieNode* currentNode;
    char currentInput[200];
} AutocompleteSystem;

TrieNode* createTrieNode() {
    TrieNode* node = (TrieNode*)malloc(sizeof(TrieNode));
    for (int i = 0; i < MAX_CHILDREN; i++) {
        node->children[i] = NULL;
    }
    node->sentenceCount = 0;
    return node;
}

AutocompleteSystem* createSystem(char sentences[][200], int* times, int n) {
    AutocompleteSystem* system = (AutocompleteSystem*)malloc(sizeof(AutocompleteSystem));
    system->root = createTrieNode();
    system->currentNode = system->root;
    strcpy(system->currentInput, "");
    
    // Add initial sentences to trie
    // Implementation details omitted for brevity
    
    return system;
}

char** input(AutocompleteSystem* system, char c, int* returnSize) {
    if (c == '#') {
        strcpy(system->currentInput, "");
        system->currentNode = system->root;
        *returnSize = 0;
        return NULL;
    }
    
    int len = strlen(system->currentInput);
    system->currentInput[len] = c;
    system->currentInput[len + 1] = '\0';
    
    if (system->currentNode->children[(unsigned char)c] != NULL) {
        system->currentNode = system->currentNode->children[(unsigned char)c];
        char** result = (char**)malloc(system->currentNode->sentenceCount * sizeof(char*));
        for (int i = 0; i < system->currentNode->sentenceCount; i++) {
            result[i] = (char*)malloc(200 * sizeof(char));
            strcpy(result[i], system->currentNode->sentences[i].sentence);
        }
        *returnSize = system->currentNode->sentenceCount;
        return result;
    } else {
        system->currentNode->children[(unsigned char)c] = createTrieNode();
        system->currentNode = system->currentNode->children[(unsigned char)c];
        *returnSize = 0;
        return NULL;
    }
}

int main() {
    // Input parsing and solution call
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(p + k log k)

p is prefix length to traverse, k log k to sort sentences at each node

⚡ Linearithmic

Space Complexity

O(ALPHABET_SIZE × N × M)

Trie nodes store references to all sentences with that prefix

✓ Linear Space

89.0K Views

High Frequency

~35 min Avg. Time

1.9K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Trie with Efficient Search — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler