Design Search Autocomplete System

Design Search Autocomplete System is a Hard Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Design Patterns pattern, in the Design (General/Specific) subpattern.

Problem statement

You are given a list of historical sentences sentences and an integer array times, where sentences[i] is a previously typed sentence and times[i] is the number of times it has been typed. Implement the AutocompleteSystem class:

- AutocompleteSystem(String[] sentences, int[] times) initializes the system with the given sentences and their corresponding frequencies. - The method List input(char c) is called whenever the user types a character c: - If c is not the character '#', append c to the current input prefix and return the top 3 historical sentences that have the current prefix. The returned sentences should be sorted by: 1. Highest frequency of occurrence. 2. If frequencies are equal, lexicographically smaller sentence first. - If c is the character '#', the current input prefix is considered a completed sentence. Add it to the historical records (or increment its frequency if it already exists), reset the current prefix to empty, and return an empty list.

You should design the system to efficiently support up to 5000 calls to input.

Constraints: - n == sentences.length == times.length - 1 <= n <= 100 - 1 <= sentences[i].length <= 100 - 1 <= times[i] <= 50 - Each sentence consists of lowercase letters and spaces. - The input character c is a lowercase letter, a space ' ', or '#'. - The total number of characters input via input will not exceed 200.

Return the list of top 3 matching sentences for each call to input (except when c == '#', in which case return an empty list).

Topics and companies

Topics: String, Depth-First Search, Design, Trie, Sorting, Heap (Priority Queue), Data Stream.

Reported in interviews at Microsoft, Amazon, Lyft, Google.

How to practise Design Search Autocomplete System on Thita.ai

Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(L + S log S) per input, where L is the length of the current input, and S is the number of sentences with the current prefix. For each input character, we traverse the Trie (O(L)), and to get top 3, we collect all matching sentences (O(S)), then sort them (O(S log S)). time and O(N * M), where N is the number of unique sentences and M is the average length of a sentence. Each sentence is stored in the Trie, and the frequency map stores all sentences. space.

Open Design Search Autocomplete System in the code editor, or read the Design Search Autocomplete System editorial for a worked solution with its approach and complexity analysis.

Where Design Search Autocomplete System sits in the DSA pattern sheet

Problems related to Design Search Autocomplete System

Other problems that use the same Design (General/Specific) and Design Patterns techniques:

Preparing this workspace.