google两轮电面

今天面的第二轮，还不有关系结果。直接上题。

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

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

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

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

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

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

我的思路。

1. class Endpoint{
   
2.     int time;
   
3.     boolean isend;
   
4.     List<Integer> range;
   
5.     public Endpoint(int time, List<Integer> range){
   
6.         this.time = time;
   
7.         isend = false;
   
8.         this.range = range;
   
9.     }
   
10. }
    
11. class Solution{
    
12.     public List<Integer> findMeetingTime(List<List<Integer>> list1, List<List<Integer>> list2, int T){
    
13.         List<Integer> res = new ArrayList<>();
    
14.         List<Endpoint> list = new ArrayList<>();
    
15.         for(List<Integer> ele : list1){
    
16.             Endpoint ep1 = new Endpoint(ele.get(0),ele);
    
17.             Endpoint ep2 = new Endpoint(ele.get(1),ele);
    
18.             ep2.isend = true;
    
19.             list.add(ep1);
    
20.             list.add(ep2);
    
21.         }
    
22.         for(List<Integer> ele : list2){
    
23.             Endpoint ep1 = new Endpoint(ele.get(0),ele);
    
24.             Endpoint ep2 = new Endpoint(ele.get(1),ele);
    
25.             ep2.isend = true;
    
26.             list.add(ep1);
    
27.             list.add(ep2);
    
28.         }
    
29.         Collections.sort(list, (a, b)->(a.time - b.time));
    
30.         int pool = 0;
    
31.         Endpoint prev = null;
    
32.         for(Endpoint cur : list){
    
33.             if(!cur.isend) pool++;
    
34.             else{
    
35.                 pool--;
    
36.             }
    
37.             if(pool == 2 ){
    
38.                 int start = Math.max(prev.range.get(0), cur.range.get(0));
    
39.                 int end = Math.min(prev.range.get(1), cur.range.get(1));
    
40.                 if(end - start >= T){
    
41.                     res.add(start);
    
42.                     res.add(end);
    
43.                     return res;
    
44.                 }
    
45.             }
    
46.             prev = cur;
    
47.         }
    
48.         return res;
    
49.     }
    
50. // follow up K 人：
    
51. K 个人-> pool size == k
    
52. int i = 0;
    
53. while(i < list.size()){
    
54.     int pool = 0;
    
55.     int endmin = Integer.MAX_VALUE;
    
56.     for(int j = 0; j < k; j++){
    
57.         if(!list.get(j).isend) pool++;
    
58.         else{
    
59.             endmin = Math.min(endmin, list.get(j).time);
    
60.             pool--;
    
61.         }
    
62.         if(pool == k){
    
63.             res.add(list.get(j).time);
    
64.             res.add(endmin);
    
65.             return res;
    
66.         }
    
67.     }
    
68. }   
    
69.    public static void main(String[] args){
    
70.         Solution test = new Solution();
    
71.         List<List<Integer>> l1 = new ArrayList<>();
    
72.         List<Integer> range = new ArrayList<>();
    
73.         range.add(1);range.add(3); l1.add(range);
    
74.         range = new ArrayList<>(); range.add(6); range.add(9);l1.add(range);
    
75.         range = new ArrayList<>(); range.add(12); range.add(15);l1.add(range);
    
76.         List<List<Integer>> l2 = new ArrayList<>();
    
77.         range = new ArrayList<>();
    
78.         range.add(4);range.add(5); l2.add(range);
    
79.         range = new ArrayList<>(); range.add(7);range.add(10); l2.add(range);
    
80.         range = new ArrayList<>(); range.add(11);range.add(16); l2.add(range);
    
81.         List<Integer> res = test.findMeetingTime(l1, l2, 2);
    
82.         System.out.println(res.get(0) + " " + res.get(1));
    
83. 
    
84.     }
    
85. }
    

复制代码

请问楼主第二问的follow up是用什么方法写的？我现在想到用divide and conquer的方法写，貌似用的空间有点大，需要用k 个 heap存potential candidates

请问第一题除了头节点，尾节点和链表里没有这个节点之外，还有什么corner case吗

Lcq3527 发表于 2018-11-9 13:30
请问楼主第二问的follow up是用什么方法写的？我现在想到用divide and conquer的方法写，貌似用的空间有点 ...

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

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

飞人殿下 发表于 2018-11-9 14:19
请问第一题除了头节点，尾节点和链表里没有这个节点之外，还有什么corner case吗

应该就这几个，我当时没睡醒，一个都没考虑

楼主能给点思路吗第二题，感觉一开始是merge intervals不过是取交集。。。

我觉得第二题可以用mergeinterval的思路吧 一个map, <开始的时间，1>, <结束的时间,-1>
然后开始扫这个map，如果累计到了k，说明k个人都有时间了，当不再等于k的时候，少了多少就是多少个人走了，记录这个时间，就是k个人开会的时间

kzhu 发表于 2018-11-9 14:56
**** 本内容被作者隐藏 ****

我差不多是这么说的，面试小哥没反对