Design Search Autocomplete System

Prerequisite: Trie data structure

In this approach, we will use a Trie. Trie is an efficient data retrieval data structure mostly used for string manipulations. It provides a way to store strings efficiently and also to search for them in a lot lesser time complexity. We will store the top 3 hot sentences directly on each node. When we get the input character, we will simply read off the answer from the node. Whenever we add a sentence at each node of the corresponding trie, we will update that node’s info appropriately if its top three answer changes. We will use a list to store our answers, which will keep track of only the top three hot sentences.

Each Trie Node will have four fields:

1. TrieNode[] children: Denoting next layers.
2. String s: Any sentence.
3. int times: Hot degree of this sentence ‘S’.
4. List<TrieNode> hot: To store the top 3 hot sentences at this node.

Comparing two Trie Nodes:

A Trie Node ‘A’ is hotter than Trie Node ‘B’ if A.TIMES is greater than B.TIMES. If A.TIMES is equal to B.TIMES, then ‘A’ is hotter than ‘B’ if A.S is lexicographically smaller than B.S. Otherwise, ‘B’ is hotter and will be placed ahead of ‘A’.
 

How to get the top 3 hot sentences for any testing sentence?

Suppose if the testing sentence is “abc” and there exits a Trie Node ‘T’, where T.s = “abc” then the top 3 hot sentences for this query will be the sentences stored in T.hot.

Algorithm :

Function AUTOCOMPLETESYSTEM(‘SENTENCES’, ‘TIMES’);

• Initialize a TrieNode ‘ROOT’ and ‘CUR’.
• Initialize a StringBuilder ‘SB’.
• Iterate ‘I’ in ‘TIMES.LENGTH’:
  • Add ‘SENTENCES’[‘i’] and ‘TIMES’[‘I’] in the Trie.
     

Function INPUT(‘C’);

• Initialize a list ‘RESULT’.
• If ‘C’ is ‘#’:
  • Add ‘SB’ to Trie.
  • Re-initialize ‘SB’.
  • Set ‘CUR’ as ‘ROOT’.
  • Return ‘RESULT’.
• Append ‘C’ to ‘SB’.
• If ‘CUR’ is not null, set ‘CUR’ as ‘CUR.CHILDREN’[‘C’].
• If ‘CUR’ is null, return ‘RESULT’.
• Iterate ‘NODE’ in ‘CUR.HOT’:
  • Add ‘NODE.S’ to ‘RESULT’.
• Return ‘RESULT’.

Maintain a class TrieNode:

• Initialize a TrieNode array ‘CHILDREN’ of size 128, a string ‘S’ as null, an integer ‘TIMES’ as 0, and an empty TrieNode list ‘HOT’.
• Inside class TrieNode, maintain a function ‘UPDATE’(TrieNode ‘NODE’):
  • Add ‘NODE’ to ‘HOT’ of this TrieNode.
  • Sort ‘HOT’.
  • If ‘HOT’ contains more than three TrieNodes, remove the extra ones and just keep the top 3.
     

Maintain a function ADD(‘SENTENCE’, ‘T’):

• Set ‘TEMP’ as ‘ROOT’.
• Initialize a list ‘VISITED’.
• Iterate ‘C’ in ‘SENTENCE’:
  • Set ‘TEMP’ as ‘TEMP.CHILDREN’[‘C]’.
  • Add ‘TEMP’ to ‘VISITED’,
• Set ‘TEMP.S’ as ‘SENTENCE’.
• Add ‘T’ to ‘TEMP.TIMES’.
• Iterate ‘NODE’ in ‘VISITED’:
  • Call ‘NODE.UPDATE’(‘TEMP’).

O(N * L + C), where 'N' is the number of sentences, ‘L’ is the length of the longest sentence, and ‘C’ is the number of characters in the testing sentence.

The time for building Trie is O(N * L), and the time for answering queries is O(C). Hence, the total time complexity is O(N * K).

O(N * L), where 'N' is the number of sentences and ‘L’ is the length of the longest sentence.
 

We may have to store ‘N’ sentences of length ‘L’ in Trie. Hence, the total space complexity is O(N * L).