某大厂面试题

[crossoverJie]

题目：

一个“.”代表一个任意字母。

注意事项：可以假设所有的单词只包含小写字母“a-z”

样例：

 addWord(“bad”);
 addWord(“dad”);
 addWord(“mad”);
 search(“pad”);  // return false;
 search(“bad”);  // return true;
 search(“.ad”); // return true;
 search(“b..”); // return true;

如果有并发的情况下，addWord() 怎么处理？

[CyC2018]

无并发的情况

public class Solution {

    private Trie trie = new Trie();

    public void addWord(String s) {
        trie.insert(s);
    }

    public boolean search(String s) {
        return trie.search(s);
    }

    private class Trie {

        private class Node {
            Node[] childs = new Node[26];
            boolean isLeaf;
        }

        private Node root = new Node();

        void insert(String word) {
            insert(word, root);
        }

        private void insert(String word, Node node) {
            if (node == null) return;
            if (word.length() == 0) {
                node.isLeaf = true;
                return;
            }
            int index = indexForChar(word.charAt(0));
            if (node.childs[index] == null) {
                node.childs[index] = new Node();
            }
            insert(word.substring(1), node.childs[index]);
        }

        boolean search(String word) {
            return search(word, root);
        }

        private boolean search(String word, Node node) {
            if (node == null) return false;
            if (word.length() == 0) return node.isLeaf;
            char c = word.charAt(0);
            String next = word.substring(1);
            if (c == '.') {
                for (Node child : node.childs) {
                    if (search(next, child)) return true;
                }
                return false;
            } else {
                int index = indexForChar(c);
                return search(next, node.childs[index]);
            }
        }

        private int indexForChar(char c) {
            return c - 'a';
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.addWord("bad");
        solution.addWord("dad");
        solution.addWord("mad");
        System.out.println(solution.search("pad"));
        System.out.println(solution.search("bad"));
        System.out.println(solution.search(".ad"));
        System.out.println(solution.search("..d"));
    }
}

[CyC2018]

要支持高并发的话，只要锁住要修改的节点即可。

        void insert(String word) {
            insert(word, root);
        }

        private void insert(String word, Node node) {
            if (node == null) return;
            if (word.length() == 0) {
                synchronized (node) {
                    node.isLeaf = true;
                }
                return;
            }
            int index = indexForChar(word.charAt(0));
            if (node.childs[index] == null) {
                synchronized (node) {
                    node.childs[index] = new Node();
                }
            }
            insert(word.substring(1), node.childs[index]);
        }

[crossoverJie]

public class Search {

    private static Map<String,String> ALL_MAP = new ConcurrentHashMap<>(50000) ;


    /**
     * 换成 ascii码 更省事
     */
    private static final char[] dictionary = {'a','b','c','d','m','p'} ;

    public static void main(String[] args) throws InterruptedException {


        Thread t1 = new Thread(new Runnable() {
            @Override
            public void run() {
                for (int i = 0; i < 10000; i++) {
                    addWord(i + "ad");
                }
            }
        });
        Thread t2 = new Thread(new Runnable() {
            @Override
            public void run() {
                for (int i = 0; i < 10000; i++) {
                    addWord(i + "bd");
                }
            }
        });
        Thread t3 = new Thread(new Runnable() {
            @Override
            public void run() {
                for (int i = 0; i < 10000; i++) {
                    addWord(i + "cd");
                }
            }
        });
        Thread t4 = new Thread(new Runnable() {
            @Override
            public void run() {
                for (int i = 0; i < 10000; i++) {
                    addWord(i + "dd");
                }
            }
        });
        Thread t5 = new Thread(new Runnable() {
            @Override
            public void run() {
                for (int i = 0; i < 10000; i++) {
                    addWord(i + "ed");
                }
            }
        });

        t1.start();
        t2.start();
        t3.start();
        t4.start();
        t5.start();
        t1.join();
        t2.join();
        t3.join();
        t4.join();
        t5.join();
        System.out.println(ALL_MAP.size());
        Assert.assertEquals(50000,ALL_MAP.size());
 
        addWord("bad");
        addWord("dad");
        addWord("mad");
        boolean pad = search("pad");
        System.out.println(pad);
        Assert.assertFalse(pad);

        boolean bad = search("bad");
        System.out.println(bad);
        Assert.assertTrue(bad);


        boolean ad = search(".ad");
        System.out.println(ad);
        Assert.assertTrue(ad);


        boolean bsearch = search("b..");
        System.out.println(bsearch);
        Assert.assertTrue(bsearch);

        boolean asearch = search(".a.");
        System.out.println(asearch);


        boolean search = search(".af");
        System.out.println(search);


        boolean search1 = search(null);
        System.out.println(search1);

    }

    public static boolean search(String keyWord){
        boolean result = false ;
        if (null ==  keyWord || keyWord.trim().equals("")){
            return result ;
        }

        //做一次完整匹配
        String whole = ALL_MAP.get(keyWord) ;
        if (whole != null){
            return true ;
        }

        char[] wordChars = keyWord.toCharArray() ;

        for (int i = 0; i < wordChars.length; i++) {
            char wordChar = wordChars[i] ;

            if (46 != (int)wordChar){
                continue ;
            }

            for (char dic : dictionary) {
                wordChars[i] = dic ;
                boolean search = search(String.valueOf(wordChars));

                if (search){
                    return search ;
                }

                String value = ALL_MAP.get(String.valueOf(wordChars));
                if (value != null){
                    return true ;
                }
            }

        }


        return result ;
    }


    public static void addWord(String word){
        ALL_MAP.put(word,word) ;
    }
}