HardTries

Autocomplete System

Implement autocomplete

Solution Approach

Track frequency of sentences. For each input, find top 3 matches by frequency and lexicographic order.

Implementation

class AutocompleteSystem:
    def __init__(self, sentences, times):
        self.trie = {}
        self.current = ""
        self.freq = {}
        
        for s, t in zip(sentences, times):
            self.freq[s] = t
    
    def input(self, c):
        if c == "#":
            self.freq[self.current] = self.freq.get(self.current, 0) + 1
            self.current = ""
            return []
        
        self.current += c
        res = sorted([s for s in self.freq if s.startswith(self.current)], 
                     key=lambda x: (-self.freq[x], x))
        return res[:3]

Complexity Analysis

Time Complexity

O(n*log n)

Space Complexity

O(n)

Complexity

Time:O(n*log n)

Space:O(n)

Asked at

GoogleAmazon