Design Search Autocomplete System

hard trie design

Problem

Implement input(c) — c is a char or '#' to commit. Return up to 3 matching past sentences ranked by frequency then lexicographically.

Inputinit [['i love you',5]] then input 'i', ' ', 'l'

Output['i love you','...']

Stream chars; '#' ends a sentence and learns it.

input

class AutocompleteSystem:
    def __init__(self, sentences, times):
        self.cnt = {}; self.buf = ''
        for s, t in zip(sentences, times): self.cnt[s] = t
    def input(self, c):
        if c == '#':
            self.cnt[self.buf] = self.cnt.get(self.buf, 0) + 1; self.buf = ''; return []
        self.buf += c
        matches = [(s, n) for s, n in self.cnt.items() if s.startswith(self.buf)]
        matches.sort(key=lambda x: (-x[1], x[0]))
        return [m[0] for m in matches[:3]]

class AutocompleteSystem {
  constructor(sentences, times) {
    this.cnt = new Map(); this.buf = '';
    sentences.forEach((s, i) => this.cnt.set(s, times[i]));
  }
  input(c) {
    if (c === '#') { this.cnt.set(this.buf, (this.cnt.get(this.buf) || 0) + 1); this.buf = ''; return []; }
    this.buf += c;
    return [...this.cnt].filter(([s]) => s.startsWith(this.buf)).sort((a, b) => b[1] - a[1] || a[0].localeCompare(b[0])).slice(0, 3).map(x => x[0]);
  }
}

class AutocompleteSystem {
    Map cnt = new HashMap<>(); String buf = "";
    public AutocompleteSystem(String[] s, int[] t) { for (int i = 0; i < s.length; i++) cnt.put(s[i], t[i]); }
    public List input(char c) {
        if (c == '#') { cnt.merge(buf, 1, Integer::sum); buf = ""; return new ArrayList<>(); }
        buf += c; final String p = buf;
        return cnt.entrySet().stream()
            .filter(e -> e.getKey().startsWith(p))
            .sorted((a, b) -> a.getValue().intValue() != b.getValue().intValue() ? b.getValue() - a.getValue() : a.getKey().compareTo(b.getKey()))
            .limit(3).map(Map.Entry::getKey).collect(Collectors.toList());
    }
}

class AutocompleteSystem {
    unordered_map cnt; string buf;
public:
    AutocompleteSystem(vector& s, vector& t) { for (int i = 0; i < (int)s.size(); i++) cnt[s[i]] = t[i]; }
    vector input(char c) {
        if (c == '#') { cnt[buf]++; buf.clear(); return {}; }
        buf += c;
        vector> v;
        for (auto& [s, n] : cnt) if (s.size() >= buf.size() && s.compare(0, buf.size(), buf) == 0) v.push_back({-n, s});
        sort(v.begin(), v.end());
        vector out;
        for (int i = 0; i < min(3, (int)v.size()); i++) out.push_back(v[i].second);
        return out;
    }
};

Explanation

This solution keeps things simple: a count map cnt from each full sentence to how many times it has been typed, plus a growing buffer buf of the characters seen so far in the current sentence.

Every call to input(c) appends c to buf, then scans the map for sentences that start with the buffer. Those candidates are sorted by count descending, breaking ties alphabetically, and the top three are returned.

The special character # means "the sentence is done." We bump that sentence's count in the map (learning it for the future), clear buf, and return an empty list.

Example: with 'i love you' stored at count 5, typing 'i' then ' ' keeps matching it as the buffer becomes "i ", and it ranks first by frequency. Later typing # would commit whatever sentence was being built.

Because each query re-scans and sorts the matching sentences, the cost is roughly O(N log N) per keystroke for N stored sentences.

Time: O(N log N) per query Space: O(N·L)