一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 4693|回复: 44
收起左侧

Google刚面完新鲜出炉Onsite3.9

[复制链接] |试试Instant~ |关注本帖
autumnhu 发表于 2015-3-10 10:45:46 | 显示全部楼层 |阅读模式

2015(1-3月) 码农类 硕士 全职@Google - 网上海投 - Onsite |Other

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
第一轮,面的是白人大叔,一上来就做题,一个matrix,实现两个functions,第一个是设置某个位置的value的function,这个小学生都能做,O(1),第二个是给两个位置坐标,这两个位置坐标形成的长方形的值的和,最暴力的方法O(n^2), 大叔说这个function可以怎么优化,答可以预处理,提前算好某个位置到(0,0)形成的长方形的和,然后这样第二个function就可以O(1)实现。大叔继续follow up,那这样的话每次设置了某个位置的value后都需要update每个包含了这个值的长方形的和,所以第一个function又是O(n^2)了,能不能balance一下,后来给他讲了一种两个functions都是O(n)的方法,大概就是只提前存好一维数组的和,大叔表示满意,然后coding实现
第二轮,面的人是华裔小哥,人很喜感也挺nice,也是一上来做题。题目是给你一个positive的值K,然后按照fraction的值的小到大输出所有n/d, 其中1<=d<=k, 0<=n<=d,还有一个要求输出的fraction不能有duplicate,比如1/2和2/4是duplicate,这种情况只要输出1/2。我用了一个hashtable来处理duplicate的情况, fraction的实际小数的值对应其输出string,比如0.5对应1/2,因为输出要按从小到大顺序,所以还用了个arraylist存实际小数的值,最后对这个List排了下序,然后结合hashtable和list输出最后结果。然后问时间复杂度,follow up,如果规定只想要输出某个数值区间的fraction怎么办,数学的一些东西,算下值范围就好了,还问了这种情况的复杂度。

第三轮,面的人是白人小哥,给一个matrix,里面只有0和1,将每一个由1组成的component的indices存入一个list,然后把所有component的list又加入一个list,用了DFS另加一个visited matrix。完成代码后,小哥问了复杂度等,由于用了stack,所以size很大的时候会overflow,有什么办法优化?答BFS,小哥表示满意,这个没有让写代码。之后见时间够加了一题,给一个数字range的array和另一个range,如{[1, 4], [7, 9], [11, 14]}和[10, 13], 求合并之后的结果,{[1, 4], [7, 14]}, 小哥说只需要讲思路,然后我讲了下大概思路。

第四轮,悲剧的遇到了三哥,题目是surpass count,题目貌似是经典题,但这会lz已经精疲力尽,答得很不好,中间卡了很久,估计这轮悲剧了

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

评分

6

查看全部评分

本帖被以下淘专辑推荐:

tanis 发表于 2015-3-10 22:15:27 | 显示全部楼层
这不是标准的Inversions count么。。
回复 支持 1 反对 1

使用道具 举报

funkboy 发表于 2015-3-11 00:03:01 | 显示全部楼层
分数的那个复杂度可以做到NlogN

例如k=5,可以构造出k-1个sorted arry list

1/2<2/3<3/4<4/5.鏈枃鍘熷垱鑷1point3acres璁哄潧

1/3<2/4<3/5

1/4<2/5
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
1/5.鏈枃鍘熷垱鑷1point3acres璁哄潧

然后直接把这几个sorted array list combine就好了

. more info on 1point3acres.com这样不用可以hashmap记录duplicate和最后再sort
回复 支持 1 反对 0

使用道具 举报

lzd1127 发表于 2015-3-11 11:31:20 | 显示全部楼层
ryuichist 发表于 2015-3-11 10:31. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
感谢分享!

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

感觉一般面试最难的是国人吧。。面试难度就最大
回复 支持 1 反对 0

使用道具 举报

averillzheng 发表于 2015-3-13 01:41:59 | 显示全部楼层
surpass的code。 求大牛点拨
  1. package google;. from: 1point3acres.com/bbs

  2. public class Surpasser {. 1point 3acres 璁哄潧
  3.         public static int surpasser(int[] arr){
  4.                 if(arr.length < 2)        return 0;
  5.                 int[] surp = new int[arr.length];
  6.                 for(int i = 0; i < arr.length; ++i) {        surp[i] = 0;        }
  7.                
  8.                 mergeSortHelper(arr, 0, arr.length, surp);
  9.                
  10.                 int max = surp[0];
  11.                 for(int i = 0; i < arr.length; ++i) {
  12.                         max = Math.max(max, surp[i]);. from: 1point3acres.com/bbs
  13.                 }
  14.                
  15.                 return max;
  16.         }
  17.        
  18.         public static int[][] mergeSortHelper(int[] arr, int st, int en, int[] surp) {               
    . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  19.                 int[][] result = new int[2][en - st];
  20.                 if(en - st == 1) {
  21.                         result[0][0] = surp[st];
  22.                         result[1][0] = arr[st];
  23.                 } else {               
  24.                
  25.                         int mid = st + (en - st) / 2;
    .鐣欏璁哄潧-涓浜-涓夊垎鍦
  26.                
  27.                         int[][] left = mergeSortHelper(arr, st, mid, surp);. 1point3acres.com/bbs
  28.                         int[][] right = mergeSortHelper(arr, mid, en, surp);
  29.                         int i = 0, j  = 0, k = 0;
  30.                
  31.                         while(i < left[0].length && j < right[0].length) {
  32.                                 if(left[1][i] < right[1][j]) {
  33.                                         result[0][k] = left[0][i] + right[0].length - j;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  34.                                         result[1][k] = left[1][i];
  35.                                         ++i;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  36.                                 } else {
  37.                                         result[0][k] = right[0][j];-google 1point3acres
  38.                                         result[1][k] = right[1][j];. From 1point 3acres bbs
  39.                                         ++j;-google 1point3acres
  40.                                 }
  41.                                 ++k;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  42.                         }
  43.                
  44.                         if(i < left[0].length){
  45.                                 result[0][k] = left[0][i];
  46.                                 result[1][k] = left[1][i];
  47.                                 ++i;
  48.                                 ++k;
  49.                         }
  50.                 .鏈枃鍘熷垱鑷1point3acres璁哄潧
  51.                         if(j < right[0].length) {                       
  52.                                 result[0][k] = right[0][j];
  53.                                 result[1][k] = right[1][j];
  54.                                 ++j;
  55.                                 ++k;
  56.                         }
  57.                
  58.                         for(int l = st; l < en; ++l){. 1point3acres.com/bbs
  59.                                 arr[l] = result[1][l - st];
  60.                                 surp[l] = result[0][l - st];.1point3acres缃
  61.                         }
  62.                 }
  63.                 . visit 1point3acres.com for more.
  64.                 return result;
  65.         }
  66.        
  67.         public static void main(String[] args){
  68.                 int[] arr = new int[]{10, 3, 0, 7, 1, -1, 14, 23, 6, 9};
  69.                 System.out.println(surpasser(arr));
  70.         }       
  71. }
复制代码
回复 支持 1 反对 0

使用道具 举报

houpy 发表于 2015-3-10 10:59:11 | 显示全部楼层
我觉得3个做得不错,1轮一般,应该可以的,祝楼主好运
回复 支持 反对

使用道具 举报

readman 发表于 2015-3-10 10:59:20 | 显示全部楼层
第三轮的题是啥啊...
回复 支持 反对

使用道具 举报

lzd1127 发表于 2015-3-10 11:25:27 | 显示全部楼层
嗯,祝LZ offer
回复 支持 反对

使用道具 举报

houqingniao 发表于 2015-3-10 12:21:55 | 显示全部楼层
bless 楼主。
第二题啥意思?
回复 支持 反对

使用道具 举报

refurbish 发表于 2015-3-10 16:26:18 | 显示全部楼层
安慰一下lz,第四题surpass count是啥意思,没搜到相关的问题。。。
回复 支持 反对

使用道具 举报

 楼主| autumnhu 发表于 2015-3-10 21:13:44 | 显示全部楼层
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。
回复 支持 反对

使用道具 举报

 楼主| autumnhu 发表于 2015-3-10 21:16:38 | 显示全部楼层
houqingniao 发表于 2015-3-10 12:21
bless 楼主。
第二题啥意思?

给个例子,比如k=4, 应该输出"0/4 1/4 1/3 1/2 2/3 3/4 1/1"
回复 支持 反对

使用道具 举报

averillzheng 发表于 2015-3-10 21:57:13 | 显示全部楼层
surpass count 用merge sort的思想来做。
回复 支持 反对

使用道具 举报

 楼主| autumnhu 发表于 2015-3-10 22:37:56 | 显示全部楼层
tanis 发表于 2015-3-10 22:15.鐣欏璁哄潧-涓浜-涓夊垎鍦
这不是标准的Inversions count么。。
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
是的呀,但是脑子一时短路,然后就悲剧了呀
回复 支持 反对

使用道具 举报

sonicgu 发表于 2015-3-11 07:14:55 | 显示全部楼层
第一题楼主存的是每一行的prefix sum?
回复 支持 反对

使用道具 举报

mmliu 发表于 2015-3-11 09:26:46 | 显示全部楼层
第一题的第二个问没太看懂,给两个坐标,算围成的矩形的面积,不是直接坐标相减,然后长乘以宽就行了么?

楼主可以再细讲下么
回复 支持 反对

使用道具 举报

ryuichist 发表于 2015-3-11 10:31:02 | 显示全部楼层
感谢分享!

恕我孤陋寡闻,我觉得三哥都是很阴险的,要么就是笑面虎,要么就是板着一块脸。我和三哥面试基本上就没成功过。
回复 支持 反对

使用道具 举报

lzd1127 发表于 2015-3-11 11:29:26 | 显示全部楼层
ryuichist 发表于 2015-3-11 10:31
感谢分享!

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

估计你太帅了,面了这么多, 没被三哥挂过。。
回复 支持 反对

使用道具 举报

samantha_kr 发表于 2015-3-11 12:23:55 | 显示全部楼层
lzd1127 发表于 2015-3-11 11:31
感觉一般面试最难的是国人吧。。面试难度就最大

我觉得还是看人,三哥有的是很坑,但是国人真的题超难的,我遇过最难的题是国人出的。。也有同学被国人黑过。。但是也有人被国人照顾,真是难说...
回复 支持 反对

使用道具 举报

kaimiku 发表于 2015-3-11 15:12:57 | 显示全部楼层
第一题貌似出现过很多次了, 最优解法是二维树状数组或者线段树吗?时间复杂度两个function都是O(lognlogn)?
回复 支持 反对

使用道具 举报

hno3 发表于 2015-3-12 04:58:00 | 显示全部楼层
averillzheng 发表于 2015-3-10 21:57. visit 1point3acres.com for more.
surpass count 用merge sort的思想来做。

could you PLS explain the merge part ?  thanks!
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-5 16:43

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表