System design question, even can be done with Map Reduce


  • -1

    Implement with Trie + List + Naive Sort, results look ok as the list is not long. If list is long, consider replacing the list with a priority queue would be a better idea.

    I was told that, in real application, the hotlist could be updated everyday, not necessary to be real-time. In that case, we can simply maintain a hash map and construct the Trie structure at night asynchronously. Then push the Trie list to the memory and let the webserver to point to it.

    class AutocompleteSystem {
        Trie trie;
        public AutocompleteSystem(String[] sentences, int[] times) {
            Map<String, Integer> map = new HashMap<>();
            trie = new Trie(map);
            if (sentences == null) return;
            for (int i = 0; i < sentences.length; i++) {
                map.put(sentences[i], times[i]);
            }
            for (String s : sentences) trie.insert(s);
        }
        
        public List<String> input(char c) {
            return trie.search(c);
        }
        
        public static class TrieNode {
            public List<String> prefix;
            public TrieNode[] children;
            public TrieNode() {
                prefix = new ArrayList<>();
                children = new TrieNode[27];
            }
        }
        
        public static class Trie {
            private TrieNode root;
            private TrieNode runner;
            private Map<String, Integer> map;
            private StringBuilder sb;
            private Comparator<String> compare;
            public Trie(Map<String, Integer> map) {
                root = new TrieNode();
                runner = root;
                sb = new StringBuilder();
                this.map = map;
                compare = new Comparator<String>() {
                    @Override
                    public int compare(String s1, String s2) {
                        if (map.get(s1) == map.get(s2)) {
                            return s1.compareTo(s2);
                        } else {
                            return map.get(s2) - map.get(s1);
                        }
                    }
                };
            }
            
            public void insert(String s) {
                char[] chs = s.toCharArray();
                TrieNode node = root;
                for (int i = 0; i < chs.length; i++) {
                    int index = (chs[i] == ' ') ? 26 : chs[i] - 'a';
                    if (node.children[index] == null) {
                        node.children[index] = new TrieNode();
                    }
                    List<String> prefix = node.children[index].prefix;
                    prefix.add(s);
                    node = node.children[index];
                }
            }
            
            public List<String> search(char c) {
                if (c == '#') {
                    runner = root;
                    String word = sb.toString();
                    sb.setLength(0);
                    if (map.containsKey(word)) {
                        map.put(word, 1 + map.get(word));
                    } else {
                        map.put(word, 1);
                        insert(word);
                    }
                    return root.prefix;
                } else {
                    sb.append(c);
                    int index = (c == ' ') ? 26 : c - 'a';
                    if (runner.children[index] == null) {
                        runner.children[index] = new TrieNode();
                    }
                    runner = runner.children[index];
                    Collections.sort(runner.prefix, compare);
                    if (runner.prefix.size() <= 3) {
                        return runner.prefix;
                    }
                    else {
                        List<String> res = new ArrayList<>();
                        for (int i = 0; i < 3; i++) res.add(runner.prefix.get(i));
                        return res;
                    }
                }
            }
            
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.