Google刚面完新鲜出炉Onsite3.9

第一轮，面的是白人大叔，一上来就做题，一个matrix，实现两个functions，第一个是设置某个位置的value的function，这个小学生都能做，O(1)，第二个是给两个位置坐标，这两个位置坐标形成的长方形的值的和，最暴力的方法O(n^2), 大叔说这个function可以怎么优化，答可以预处理，提前算好某个位置到（0，0）形成的长方形的和，然后这样第二个function就可以O(1)实现。大叔继续follow up，那这样的话每次设置了某个位置的value后都需要update每个包含了这个值的长方形的和，所以第一个function又是O

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

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

urpass count，题目貌似是经典题，但这会lz已经精疲力尽，答得很不好，中间卡了很久，估计这轮悲剧了

写出来给自己的job hunting之路攒下RP吧，GG的话就让它随风而去吧，耳边响起let it go。。。

这不是标准的Inversions count么。。

surpass的code。 求大牛点拨

1. package google;
   
2. 
   
3. public class Surpasser {
   
4.         public static int surpasser(int[] arr){
   
5.                 if(arr.length < 2)        return 0;
   
6.                 int[] surp = new int[arr.length];
   
7.                 for(int i = 0; i < arr.length; ++i) {        surp[i] = 0;        }
   
8.                
   
9.                 mergeSortHelper(arr, 0, arr.length, surp);
   
10.                
    
11.                 int max = surp[0];
    
12.                 for(int i = 0; i < arr.length; ++i) {
    
13.                         max = Math.max(max, surp[i]);
    
14.                 }
    
15.                
    
16.                 return max;
    
17.         }
    
18.        
    
19.         public static int[][] mergeSortHelper(int[] arr, int st, int en, int[] surp) {               
    
20.                 int[][] result = new int[2][en - st];
    
21.                 if(en - st == 1) {
    
22.                         result[0][0] = surp[st];
    
23.                         result[1][0] = arr[st];
    
24.                 } else {               
    
25.                
    
26.                         int mid = st + (en - st) / 2;
    
27.                
    
28.                         int[][] left = mergeSortHelper(arr, st, mid, surp);
    
29.                         int[][] right = mergeSortHelper(arr, mid, en, surp);
    
30.                         int i = 0, j  = 0, k = 0;
    
31.                
    
32.                         while(i < left[0].length && j < right[0].length) {
    
33.                                 if(left[1][i] < right[1][j]) {
    
34.                                         result[0][k] = left[0][i] + right[0].length - j;
    
35.                                         result[1][k] = left[1][i];
    
36.                                         ++i;
    
37.                                 } else {
    
38.                                         result[0][k] = right[0][j];
    
39.                                         result[1][k] = right[1][j];
    
40.                                         ++j;
    
41.                                 }
    
42.                                 ++k;
    
43.                         }
    
44.                
    
45.                         if(i < left[0].length){
    
46.                                 result[0][k] = left[0][i];
    
47.                                 result[1][k] = left[1][i];
    
48.                                 ++i;
    
49.                                 ++k;
    
50.                         }
    
51.                
    
52.                         if(j < right[0].length) {                       
    
53.                                 result[0][k] = right[0][j];
    
54.                                 result[1][k] = right[1][j];
    
55.                                 ++j;
    
56.                                 ++k;
    
57.                         }
    
58.                
    
59.                         for(int l = st; l < en; ++l){
    
60.                                 arr[l] = result[1][l - st];
    
61.                                 surp[l] = result[0][l - st];
    
62.                         }
    
63.                 }
    
64.                
    
65.                 return result;
    
66.         }
    
67.        
    
68.         public static void main(String[] args){
    
69.                 int[] arr = new int[]{10, 3, 0, 7, 1, -1, 14, 23, 6, 9};
    
70.                 System.out.println(surpasser(arr));
    
71.         }       
    
72. }
    

复制代码

ryuichist 发表于 2015-3-11 10:31
感谢分享！

恕我孤陋寡闻，我觉得三哥都是很阴险的，要么就是笑面虎，要么就是板着一块脸。我和三哥面试 ...

感觉一般面试最难的是国人吧。。面试难度就最大

我觉得3个做得不错，1轮一般，应该可以的，祝楼主好运

第三轮的题是啥啊...

嗯，祝LZ offer

bless 楼主。
第二题啥意思？

安慰一下lz，第四题surpass count是啥意思，没搜到相关的问题。。。

refurbish 发表于 2015-3-10 16:26
安慰一下lz，第四题surpass count是啥意思，没搜到相关的问题。。。

输入一个数组，返回每个元素的surpasser个数。
数组元素a【i】的surpasser是指元素a[j], j > i， a[j] > a【i】。
比如[10, 3, 7, 1, 23, 14, 6, 9] 这个数组中10的surpasser是23和14，surpasser个数是2。

houqingniao 发表于 2015-3-10 12:21
bless 楼主。
第二题啥意思？

给个例子，比如k=4, 应该输出"0/4 1/4 1/3 1/2 2/3 3/4 1/1"

surpass count 用merge sort的思想来做。