V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
zzzrf
V2EX  ›  Java

微软面试题:实现 Trie(前缀树),枯燥至极(滑稽)

  •  
  •   zzzrf · 108 天前 · 863 次点击
    这是一个创建于 108 天前的主题,其中的信息可能已经有所发展或是发生改变。

    实现一个 Trie,包含 insert, search, 和 startsWith 这三个方法。

    在线做题地址

    样例 1:

    输入: 
      insert("lintcode")
      search("lint")
      startsWith("lint")
    输出: 
      false
      true
    

    样例 2:

    输入:
      insert("lintcode")
      search("code")
      startsWith("lint")
      startsWith("linterror")
      insert("linterror")
      search("lintcode”)
      startsWith("linterror")
    输出: 
      false
      true
      false
      true
      true
    

    题解

    Trie(前缀树) 的模板应用.

    维基百科: https://zh.wikipedia.org/zh-hans/Trie

    // Version 1: Array of TrieNodeclass TrieNode {
        private TrieNode[] children;
        public boolean hasWord;
        
        public TrieNode() {
            children = new TrieNode[26];
            hasWord = false;
        }
        
        public void insert(String word, int index) {
            if (index == word.length()) {
                this.hasWord = true;
                return;
            }
            
            int pos = word.charAt(index) - 'a';
            if (children[pos] == null) {
                children[pos] = new TrieNode();
            }
            children[pos].insert(word, index + 1);
        }
        
        public TrieNode find(String word, int index) {
            if (index == word.length()) {
                return this;
            }
            
            int pos = word.charAt(index) - 'a';
            if (children[pos] == null) {
                return null;
            }
            return children[pos].find(word, index + 1);
        }
    }
    public class Trie {
        private TrieNode root;
    
        public Trie() {
            root = new TrieNode();
        }
    
        // Inserts a word into the trie.
        public void insert(String word) {
            root.insert(word, 0);
        }
    
        // Returns if the word is in the trie.
        public boolean search(String word) {
            TrieNode node = root.find(word, 0);
            return (node != null && node.hasWord);
        }
    
        // Returns if there is any word in the trie
        // that starts with the given prefix.
        public boolean startsWith(String prefix) {
            TrieNode node = root.find(prefix, 0);
            return node != null;
        }
    }
    
    // Version 2: HashMap Version, this version will be TLE when you submit on LintCodeclass TrieNode {
        // Initialize your data structure here.
        char c;
        HashMap<Character, TrieNode> children = new HashMap<Character, TrieNode>();
        boolean hasWord;
        
        public TrieNode(){
            
        }
        
        public TrieNode(char c){
            this.c = c;
        }
    }
    public class Trie {
        private TrieNode root;
    
        public Trie() {
            root = new TrieNode();
        }
    
        // Inserts a word into the trie.
        public void insert(String word) {
            TrieNode cur = root;
            HashMap<Character, TrieNode> curChildren = root.children;
            char[] wordArray = word.toCharArray();
            for(int i = 0; i < wordArray.length; i++){
                char wc = wordArray[i];
                if(curChildren.containsKey(wc)){
                    cur = curChildren.get(wc);
                } else {
                    TrieNode newNode = new TrieNode(wc);
                    curChildren.put(wc, newNode);
                    cur = newNode;
                }
                curChildren = cur.children;
                if(i == wordArray.length - 1){
                    cur.hasWord= true;
                }
            }
        }
    
        // Returns if the word is in the trie.
        public boolean search(String word) {
            if(searchWordNodePos(word) == null){
                return false;
            } else if(searchWordNodePos(word).hasWord) 
              return true;
              else return false;
        }
    
        // Returns if there is any word in the trie
        // that starts with the given prefix.
        public boolean startsWith(String prefix) {
            if(searchWordNodePos(prefix) == null){
                return false;
            } else return true;
        }
        
        public TrieNode searchWordNodePos(String s){
            HashMap<Character, TrieNode> children = root.children;
            TrieNode cur = null;
            char[] sArray = s.toCharArray();
            for(int i = 0; i < sArray.length; i++){
                char c = sArray[i];
                if(children.containsKey(c)){
                    cur = children.get(c);
                    children = cur.children;
                } else{
                    return null;
                }
            }
            return cur;
        }
    }
    
    7 条回复    2020-11-18 09:42:57 +08:00
    learningman
        1
    learningman   108 天前
    会了,那微软要我吗
    xcai007
        2
    xcai007   108 天前
    枯燥至极!
    goodboy95
        3
    goodboy95   108 天前
    我:学会了,马上去和微软对线!

    几天后,微软某办公室:
    我:你好,我是过来面试的。
    面试官:好的,你看看你能不能写出个在大量字符串中进行快速前缀匹配的方法,语言随意。
    我:( 10 分钟之后)写完了。
    面试官:不错不错,那么问一下,如果不限定从前缀匹配字符串,而是可以从中间匹配,比如"cd"能匹配"abcde",那应该怎么办?
    我:( WTF ??)额……嗯……那个啥……后缀树?
    面试官:好的,那么你能实现一下后缀树吗?
    我:(忍着蛋疼写了个把一堆 trie 树粘在一起的玩意)
    面试官:嗯……行吧。那么把刚刚的问题倒过来,如果现在给你一个字符串库,再给你一个长字符串,要求你快速找出长字符串包含字符串库的哪些元素,应该怎么办?
    我:( wocao ???!!!)额,我记得好像可以用 AC 自动机……吧……(草草草,AC 自动机代码咋写来着?以前没写过啊)
    面试官:很好,由于时间关系就不用你写出代码了。
    我:(呼,幸好逃过一劫)
    面试官:那么,最后再问个问题。刚刚说的字符串库当中,如果有部分字符串是带有通配符的,例如["i*o", "o?o", "r?a*m", "ft?"],然后给定一个普通的长字符串,例如"microsoft",这样我们认为"i*o"和"o?o"包含在"microsoft"里面,而"r?a*m"和"ft?"不包含。那么,如何才能快速找出长字符串里面包含字符串库的哪些元素呢?
    我:(两眼一黑,倒在地上)
    noreplay
        4
    noreplay   107 天前 via Android
    @goodboy95 我就不一样了。我会因为年龄大了 /第一学历不好 /没有低头捡垃圾等原因没去对线😎😎
    goodboy95
        5
    goodboy95   107 天前
    @noreplay 说起面试这玩意,我就想起来那些随时可能出现的变态笔试题。以前老以为变态笔试题只有大公司会出,像我在的小公司只会搞基础题。后来批卷子的时候,发现了一份卷子的编程题是二维动态规划+矩阵快速幂,我当场就傻了。
    noreplay
        6
    noreplay   107 天前 via Android
    @goodboy95 招算法的吗?如果只是软件岗,我觉得自己好菜好菜啊
    goodboy95
        7
    goodboy95   107 天前
    @noreplay 就是 web 开发,到现在我都不知道是哪个牛逼的二货把那道题放进去的,反正带这道题的卷子,别说矩阵快速幂了,连二维动态规划我都没见谁做出来(虽然我不看答案也解不出来……)
    关于   ·   帮助文档   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   3069 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 29ms · UTC 10:59 · PVG 18:59 · LAX 02:59 · JFK 05:59
    ♥ Do have faith in what you're doing.