Google Onsite面经

还是挺难的

mchzh 发表于 2017-2-21 14:09
还是挺难的

晕晕乎乎写了一个复杂的，希望能看到更简洁的

1.     public int linkedComponentListNode(Set<ListNode> set) {
   
2.         Map<ListNode, ListNode> head2tail = new HashMap<>();
   
3.         Map<ListNode, ListNode> tail2head = new HashMap<>();
   
4.         Map<ListNode, ListNode> next2tail = new HashMap<>();
   
5. 
   
6.         Iterator<ListNode> itr = set.iterator();
   
7.         while (itr.hasNext()) {
   
8.             ListNode head = itr.next();
   
9.             ListNode tail = head;
   
10.             while (tail.next != null && set.contains(tail)) {
    
11.                 tail = tail.next;
    
12.                 set.remove(tail);
    
13.             }
    
14. 
    
15.             boolean isHeadConnected = head2tail.containsKey(tail.next);
    
16.             boolean isTailConnected = next2tail.containsKey(head);
    
17.             if (isHeadConnected || isTailConnected) {
    
18.                 if (isHeadConnected) {
    
19.                     //extend head
    
20.                     ListNode oldtail = head2tail.remove(tail.next);
    
21.                     head2tail.put(head, oldtail);
    
22.                     tail2head.put(oldtail, head);
    
23.                 }
    
24.                 if (isTailConnected) {
    
25.                     //extend tail
    
26.                     ListNode prevTail = next2tail.get(head);
    
27.                     ListNode oldHead = tail2head.get(prevTail);
    
28.                     head2tail.put(oldHead, tail);
    
29.                     tail2head.remove(prevTail);
    
30.                     tail2head.put(tail, oldHead);
    
31.                     if (tail.next != null) {
    
32.                         next2tail.put(tail.next, tail);
    
33.                     }
    
34.                 }
    
35.             } else {
    
36.                 head2tail.put(head, tail);
    
37.                 tail2head.put(tail, head);
    
38.                 if (tail.next != null) {
    
39.                     next2tail.put(tail.next, tail);
    
40.                 }
    
41.             }
    
42.         }
    
43. 
    
44.         return head2tail.size();
    
45.     }

复制代码

麻烦问下，第二题无论是不是doubly linked list 用UnionFind不能做么？把每个节点和它的next节点union起来？

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

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

Zhenying 发表于 2017-2-22 13:35
我觉得可以。写了个singly linked list的。不知道有没有问题。

而且这样貌似不需要doubly linked list?

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

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

问下第二题什么是hidden linked list, 是不是就是说有一堆double linked list, 然后给出其中一些node, 然后计算connected components?

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

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

Zhenying 发表于 2017-2-20 16:56
对对对，忘了算这部分了。
我在想可不可以先按email的个数从大到小排个序，然后建一个email到user的mapp ...

为啥要排序？

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

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