狗家油管上门面经

atlantic7200 发表于 2018-8-20 17:26
@szyyn95, 第四轮, "面试官是不是想问最少用多少个拼出来呢，那就和地里一个店面题很像" 请问你还记得是 ...

自己搜一下，谷歌的店面题，至少有二十条讨论我记得，就是八月份的，那么多积分呢不用白不用

szyyn95 发表于 2018-8-20 21:27
自己搜一下，谷歌的店面题，至少有二十条讨论我记得，就是八月份的，那么多积分呢不用白不用

感谢提示, 是不是这篇, 这篇的楼主最后过了, 貌似这题面试官只要求O(m*n) http://www.1point3acres.com/bbs/thread-437474-1-1. html

补充内容 (2018-8-21 01:11):
http://www.1point3acres.com/bbs/thread-437474-1-1.html

补充内容 (2018-8-21 01:56):
再補充一下, 應該用類似szyyn95提出的這個做法就可以了.
http://www.1point3acres.com/bbs/ ... p;page=3#pid4380320

补充内容 (2018-8-21 06:41):
刚才又想了一下, szyyn95的做法好像也是O(m*n, m = len(A), n = len(B)). pop掉那些已经小于当前index的值+更新queue的worst case还是O(m*n) ; eg: A="CCCCCC"对上B="ABCA", 那对每个'C'都要O(n)的时间去reset

atlantic7200 发表于 2018-8-21 01:04
感谢提示, 是不是这篇, 这篇的楼主最后过了, 貌似这题面试官只要求O(m*n) http://www.1point3acres.com/b ...

我在那个贴子里提到的那个pop list in dict的做法其实是错的，原因在于如果你只检查每个list的最后一个（下一个被pop的val），会遇到一个edge case:假设现在a在dict里的list是[7,3]，现在的index是6，实际上list里的7是可以的，但是由于3并没有被pop掉，导致你误认为需要再来开始一个新的String。

canoee 发表于 2018-8-17 11:59
MTV zszszs

对于选择去 Mt View 还是去 San Bruno 面， 楼主有什么推荐吗？

第四轮：先建Trie，O(M^2)，再循环O(N),总 O(N + M^2).
class TrieNode {
    char lable;
    TrieNode father;
    HashMap<Character, TrieNode> children = new HashMap<>();
    public TrieNode(char c, TrieNode f) {
        label = c;
        father = f;
        if (f != null) {
            f.children.put(c, this);
        }
    }
    public TrieNode() {
        this('#', null);
    }
}

TrieNode buildTrie(String str) {
    TrieNode root = new TrieNode();
    char[] cs = str.toCharArray();
    TrieNode node = root;
    for (int i = 0; i < cs.length; i++) {
        TrieNode n = new TrieNode(cs[i], node);
        node = node.father;
        while (node != null) {
            if (node.children.containsKey(cs[i])) {
                break;
             }
             node.children.put(cs[i], n);
             node = node.parent;
         }
         node = n;
     }
}

TrieNode getNode(TrieNode node, char c) {
    if (node == null) return null;
    return node.get(c);
}

int minCount(String dst, String src) {
    TrieNode root = buildTrie(src);
    int count = 0;
    TrieNode node = root;
    for (i = 0; i < dst.length(); ) {
        TrieNode n = getNode(node, dst.charAt(i));
        if (n == null) {
            if (node == root) {
                return -1;
            }
            count++;
           node = root;
        }
        else {
            node = n;
            i++;
        }
      }
      return count;
}

如果第5轮只需要判断能不能的话，可以O(m),如果要返回循环几次的话暂时只能想到o(mn),
楼主最后过了吗求更新

楼主，吃饭的时候都聊什么话题？