Autocomplete System Implementation

Autocomplete systems are a ubiquitous feature in modern applications, providing users with suggestions as they type. This challenge asks you to implement a basic autocomplete system in JavaScript, focusing on efficient prefix matching and ranked suggestions. This is a valuable exercise in data structures, algorithms, and string manipulation.

Problem Description

You are tasked with building an autocomplete system that suggests words based on a given prefix. The system should maintain a dictionary of valid words and, upon receiving a prefix, return a list of words from the dictionary that start with that prefix, sorted by their frequency of appearance in the dictionary (most frequent first). If multiple words have the same frequency, they should be sorted alphabetically.

Key Requirements:

• addWord(word): Adds a word to the dictionary and updates its frequency.
• getSuggestions(prefix): Given a prefix, returns a list of suggested words from the dictionary that start with the prefix, sorted by frequency (descending) and then alphabetically (ascending).
• Dictionary: The system should use an efficient data structure to store the dictionary and allow for fast prefix lookups. A Trie is a suitable choice, but other approaches are acceptable if they meet the performance constraints.
• Frequency Tracking: The system must accurately track the frequency of each word in the dictionary.

Expected Behavior:

The getSuggestions method should return an empty array if no words in the dictionary start with the given prefix. The suggestions should be returned as an array of strings.

Edge Cases to Consider:

• Empty prefix: Should return suggestions for words starting with an empty string (i.e., all words in the dictionary, sorted by frequency and then alphabetically).
• Empty dictionary: Should return an empty array for any prefix.
• Case sensitivity: The system should be case-sensitive (e.g., "apple" and "Apple" are considered different words).
• Prefix not found: Should return an empty array if no words start with the given prefix.
• Duplicate words: Adding the same word multiple times should update its frequency correctly.

Examples

Example 1:

Input:
addWord("apple");
addWord("application");
addWord("banana");
addWord("apple");
addWord("app");

getSuggestions("app")

Output:
["apple", "application", "app"]

Explanation: "apple" and "application" both start with "app". "apple" appears twice, "application" once, and "app" once. Therefore, the order is "apple", "application", "app".

Example 2:

Input:
addWord("cat");
addWord("car");
addWord("can");
addWord("dog");

getSuggestions("ca")

Output:
["cat", "car", "can"]

Explanation: "cat", "car", and "can" all start with "ca". They all appear once, so they are sorted alphabetically.

Example 3: (Edge Case - Empty Prefix)

Input:
addWord("apple");
addWord("banana");
addWord("cherry");

getSuggestions("")

Output:
["banana", "apple", "cherry"]

Explanation: An empty prefix means we want all words, sorted by frequency (all are 1) and then alphabetically.

Constraints

• The dictionary will contain words consisting of lowercase English letters.
• The maximum length of a word in the dictionary is 20 characters.
• The maximum number of words in the dictionary is 1000.
• The maximum length of the prefix is 10 characters.
• The addWord operation should take O(m) time, where m is the length of the word.
• The getSuggestions operation should take O(n log n) time, where n is the number of suggestions returned (due to sorting). Prefix lookup should be efficient (ideally O(k) where k is the length of the prefix).

Notes

• Consider using a Trie data structure for efficient prefix matching.
• You can use JavaScript's built-in sort method for sorting the suggestions, but be mindful of the sorting criteria (frequency descending, then alphabetically ascending).
• Think about how to efficiently store and update word frequencies.
• Focus on code clarity and maintainability. Good variable names and comments are appreciated.
• Testing is crucial. Write thorough test cases to cover various scenarios, including edge cases.