Google 店面 一轮 过了

店面一轮，题目是给一个double linked list，给一个subset of nodes in this

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

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

p）

解法在回答里面，求加米，没权限看不了面经很难过

就是hash table的题吧。遍历一个节点的时候把他前后节点的计数+1，遍历之后的节点时如果有对应的key已经在表中，我们减去对应的value。

public int numberOfGroup(Set<DLinkedNode> set){
        Map<DLinkedNode, Integer> map = new HashMap<>();
       
        int count = 0;
        for(DLinkedNode node : set){
            count++;
            
            int sameGroup= map.getOrDefault(node, 0);
            count -= sameGroup;
            
            if(node.pre!=null)
                map.put(node.pre, map.getOrDefault(node.pre, 0)+1);
            if(node.post!=null)
                map.put(node.post, map.getOrDefault(node.post, 0)+1);
        }
       
        return count;
    }

为何要额外set 直接随便选一个然后在linkedlist里左右延伸 边延伸边删除set里元素 直到两头都不在set里 然后重复操作直到set为空

没给head 那就这样，不知道这个list里面有没有环

public int groupList(Set<Node> set) {
                Set<Node> visited = new HashSet<>();
                int res = 0;
                for (Node i : set) {
                        if (visited.contains(i)) continue;
                        res ++;
                        visited.add(i);
                        left(i,visited,set);
                        right(i,visited,set);
                }
                return res;
        }
        private void left(Node temp, Set<Node> visited , Set<Node> set) {
                if (temp == null || temp.left == null) return;
                if (!set.contains(temp.left) || visited.contains(temp.left)) {
                        return;
                       
                }else {
                        visited.add(temp.left);
                        left(temp.left , visited , set);
                }
                return;
        }

解法一
union-find, google很喜欢union find和分组的题啊，要求良好基本功才能在20分钟写出来，然而我没有

解法二：
思路来源于2 sum，merge interval， k-empty slot(oa 题)
用两个set保存所有group的左右边界(exclusive)节点
比如 group{2}, left存1，right存3。
等到遍历到3，存在于right中，删除掉3，把3.next（4）放入right，count 不变
同理对于left。
当一个节点同时，在left和right中，说明可以concatenate两个group，group count--，update left and right
不在left，right就新开一个group，add its prev and next separately to left and right.
O(n) time and space

zyy_123 发表于 2018-3-14 15:11
为何要额外set 直接随便选一个然后在linkedlist里左右延伸 边延伸边删除set里元素 直到两头都不在set里 然 ...

我想了一种方法，但是没解决set里面iteration的问题，会报错，但原理应该是对的；不知道有没有办法解决

public int groupList(ListNode head , Set<Node> set) {
        int origin = count(head);//count the num of nodes
        int res = 0;
        for (Node cur : set) {
                res ++;
                if (set.contains(cur.left)) {
                        left(cur , set);
                }
                if (set.contains(cur.right)) {
                        right(cur , set);
                }
                set.remove(cur);
        }
        return origin - res;
}
private void left(Node temp, Set<Node> s) {
        if (temp == null) return;
        if (s.contains(temp.left)) {
                left(temp.left,s);
                s.remove(temp.left);
        }
        return;
}

你的做法对于offline可以，但我写的能online，这是我想的唯一优势。

zyy_123 发表于 2018-3-14 15:11
为何要额外set 直接随便选一个然后在linkedlist里左右延伸 边延伸边删除set里元素 直到两头都不在set里 然 ...

Online优势

yzkst06100 发表于 2018-3-14 23:22
我想了一种方法，但是没解决set里面iteration的问题，会报错，但原理应该是对的；不知道有没有办法解决
...

没给head 忘了说
再有要同时考虑left right都包含cur，否则left right更新错误

这个题目没太看懂。。。就lz举的这个例子来说，构成哪几个group呢？求解答一下

double linked list: 1，2，3，4，5
subset : {1,2,5}
{1,2,5}能构成2个group（相连为一个group）; 1,2 一个，5一个