狗家油管上门面经

reliveinfire 发表于 2018-8-17 13:37
请问LZ

第一道题, 用 dp, knapsack 有可能解吗?

您好！
本帖隐藏的内容需要积分高于 110 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 110 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

第四轮：先建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;
}

sxhexe 发表于 2018-9-16 06:56
union find为什么是O(1)呢？我感觉至少得把所有元素都过一遍吧？

不用啊，你那样就重复查询了。
因为有self.find 里面那一步 for n in path:
时间复杂度 average 是 1
def connect(self, a, b):
        self.father[self.find(a)] = self.find(b)

    """
    @param: a: An integer
    @param: b: An integer
    @return: A boolean
    """
    def query(self, a, b):
        return self.find(a) == self.find(b)
   
    def find(self, node):
        path = []
        while self.father[node] != node:
            path.append(node)
            node = self.father[node]
            
        for n in path:
            self.father[n] = node
            
        return node

您好！
本帖隐藏的内容需要积分高于 120 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 120 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

顺便，楼主的面经很用心，点赞


补充内容 (2018-8-17 11:25):
哦第三轮如果只是找“是不是”一样的话，那岂不是Union find更省事一点？直接遍历所有edge，最后看这俩node的parent一不一样就行

szyyn95 发表于 2018-8-17 11:21
**** 本内容被作者隐藏 ****
顺便，楼主的面经很用心，点赞

Onsite让人手撸KMP这种事，虽然我不信谷歌干不出来，但是怎么听怎么有点过分。。。

canoee 发表于 2018-8-17 11:27
第二轮哪个？第二题我写了题号了呀，第一题的话，真的很简单，你听完题目就会了，说白了就是一个list of  ...

哦哦哦我说的是第二轮的第一题，遥控器那个

还差三分才能看TT

请问 lz是在 Mt View 还是在 San Bruno 面的？

Brandon__00 发表于 2018-8-17 11:42
还差三分才能看TT

现在能看了

szyyn95 发表于 2018-8-17 11:29
Onsite让人手撸KMP这种事，虽然我不信谷歌干不出来，但是怎么听怎么有点过分。。。

有个同学在微软面试直接写出来了kmp，因为那轮是大boss面的，所以后面几轮直接让他纯聊天免了做题