刚出炉的Google virtual onsite面经

第一题题目应该不会给出start[]和end[]两个序列排序的结果吧？假设乱序的话，不考虑quick select，需要做两次排序，复杂度O(2*nlogn + 2 * logn)。而如果只对start[]排序，然后搞一个set依次模拟扫描一遍的话，需要O(nlogn + 2*n)，其实没差，甚至可能平均意义下更优？而如果题目已经对start[]排好序的话，那直接扫描一遍应该是最好的了。

wingnut 发表于 2020-9-12 11:21
积分没188看不到哇

再加了兩個testcase
        int[][] test1 = {{0,100}, {10,20}, {30,50}};
        int[][] test2 = {{0,5}, {10,20}, {15,18}};
        int[][] test3 = {{0,5}, {0,5}, {0,5}};
        int[][] test4 = {{0,5}, {5,10}, {10,15}};

test1
[0, 1]
[0, 1, 2]
[0, 2]
test2
[0]
[1, 2]
[1, 2]
test3
[0, 1, 2]
[0, 1, 2]
[0, 1, 2]
test4
[0]
[0, 1]
[1, 2]

代碼:

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

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

[/i][/i][/i][/i][/i]

xiaoxiao0801 发表于 2020-9-10 23:57
第一题这个思路对吗？对每个用户，找出他可能rank的范围

假如一共有个M区间，对每 ...

还不错 我想答案意思应该是如此

第一题可以把所有interval重新排列组合一下，让第i个start和第i个end组成新的interval。例如例子里面的[[1,100],[10,20],[30,50]]可以变成[[1,20],[10,50],[30,100]]。然后找到第n-1个interval，判断所有一开始的intervals是否和重构之后的第n-1个interval有overlapping，如果有，就加入result。

其实还有个法子
就是把每个区间当成一个node，如果一个区别的end大于另一个区间的start，就是一条有向的边。
然后就是topological sort了
复杂度比较高，但是比较好想。
还是二分法的路子好。

chengliu22 发表于 2020-9-13 23:55
第一题可以把所有interval重新排列组合一下，让第i个start和第i个end组成新的interval。例如例子里面的[[1, ...

嗯，测试了几种case，感觉这是对的，但不知道思路是怎么想出来的。。。

隐藏部分看不了┭┮﹏┭┮求大米

第一题类似于是尔吴伞？ 最好的开会房间？

xiaoxiao0801 发表于 2020-9-10 23:57
第一题这个思路对吗？对每个用户，找出他可能rank的范围

假如一共有个M区间，对每个区间[x1,x2]，找出所 ...

按照这个思路写了下

1. public class RankSearchUser {
   
2. 
   
3.     public void solution(int[][] intervals) {
   
4.         int[][] tempIntervals = Arrays.copyOf(intervals, intervals.length);
   
5.         Arrays.sort(tempIntervals, (a, b) -> a[1] - b[1]);
   
6.         int[] rankRangeStart = new int[intervals.length];
   
7.         int[] rankRangeEnd = new int[intervals.length];
   
8.         for (int i = 0; i < intervals.length; i++) {
   
9.             int startUpperBound = intervals[i][0];
   
10.             int start = 0;
    
11.             int end = intervals.length - 1;
    
12.             while (start <= end) {
    
13.                 int mid = start + (end - start) / 2;
    
14.                 if (tempIntervals[mid][1] >=  startUpperBound) {
    
15.                     end = mid - 1;
    
16.                 } else {
    
17.                     start = mid + 1;
    
18.                 }
    
19. 
    
20.                 int lastValidIdxForStart = end;
    
21.                 rankRangeStart[i] = lastValidIdxForStart + 2;
    
22.             }
    
23.         }
    
24. 
    
25.         Arrays.sort(tempIntervals, (a, b) -> a[0] - b[0]);
    
26.         for(int i = 0; i < intervals.length; i++) {
    
27.             int endLowerBound = intervals[i][1];
    
28.             int start = 0;
    
29.             int end = intervals.length - 1;
    
30.             while (start <= end) {
    
31.                 int mid = start + (end - start) / 2;
    
32.                 if (tempIntervals[mid][0] <= endLowerBound) {
    
33.                     start = mid + 1;
    
34.                 } else {
    
35.                     end = mid - 1;
    
36.                 }
    
37. 
    
38.                 int firstValidIdx = start;
    
39.                 rankRangeEnd[i] = firstValidIdx;
    
40.             }
    
41.         }
    
42. 
    
43.         for (int i = 1; i <= intervals.length; i++) {
    
44.             String s = "";
    
45.             s += "rank " + i + ":";
    
46.             for (int j = 0; j < intervals.length; j++) {
    
47.                 if (i >= rankRangeStart[j] && i <= rankRangeEnd[j]) {
    
48.                     s += "u" + String.valueOf(j + 1) + ",";
    
49.                 }
    
50.             }
    
51.             System.out.println(s);
    
52.         }
    
53.     }
    
54. 
    
55.     public static void main(String[] args) {
    
56.         RankSearchUser solution = new RankSearchUser();
    
57.         int[][] intervals = new int[][]{{0, 100}, {10, 20}, {30, 50}};
    
58.         solution.solution(intervals);
    
59.     }
    
60. }
    

复制代码

感觉面试的时候真的很难想到加写出来

请问楼主，virtual interview是用 google doc写代码吗还是用支持语法的editor？