一亩三分地论坛

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

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

Google Pittsburgh Onsite 面经

[复制链接] |试试Instant~ |关注本帖
fordreamzju 发表于 2015-9-4 08:09:44 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 硕士 全职@Google - 内推 - Onsite |Otherfresh grad应届毕业生

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

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

x
今天去Google Pittsburgh Onsite,貌似CMU的学生都是直接拿Pittsburgh的Onsite不用电面。一进门先看到两个同班同学,都是来onsite的,真是醉了。
一共四轮,每轮45分钟,中午吃饭。过程很简单,每一轮都是随便聊聊天然后直接上白板写题。所有的面试官都是白人,交流非常通畅。
第一轮 three sum的变种,给一个array,找出所有 three tuple 组合的数量, 使得三个数加起来小于等于某个target。我用了two pointer. n^2复杂度做完。由于我们并不用返回所有的tuple,只要数量,所以又用了binary Search优化。. visit 1point3acres.com for more.
第二轮自己implement 一个stack类,实现pop,push , isEmpty这三个函数。这题之前见过所以直接上手就写出了O(1)时间的实现。之后面试官又问我,如果你有同样的testcase,但是每次跑出来的结果都不一样,可能是什么原因?我说第一可能这个程序和time stamp有关,他说还有呢?我说第二可能有random number。他说还有呢?我说第三可能是hashMap iterator每次返回值不同,他说还有呢?这时我快要崩溃了,想了半天想起上个学期Distributed System每次跑实验总是跑出不同的结果,所以我说可能和network也有关吧。他终于满意了,不再问“还有呢”了。。。第三轮是一个简单的字符串加密。比如有Key={A,B,C} 先把他们转化为数字,对应0,1,2,然后对于一个字符串“BLUE”,每个字母移动相应的位数,B移动0位还是B,L移动1位变成M这样。但是注意要考虑很多coner case,面试官一开始并没有把所有规则说完,就等着你问他。比如大小写,比如字母超过Z以后怎么办,有标点符号怎么办,字符串比Key的长度长等等。把这些情况都处理清楚,这题还是很简单的。之后又问了一个更简单的two pointer问题,我只说了思路他就表示可以了。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
第四轮是实现有权重的随机数,比如A的权重是5,B的权重是3,C的权重是2,那我们要有0.5的概率产生随机数A,0.3的概率产生随机数B,0.2的概率产生随机数C。权重不一定是整数可以是小数。这个题关键是首先判断随机数所处的区间,再看如何把区间映射到一个值。我用了hashMap+array才把时间降到O(n),然后又用了Binary Search优化。一天写两个Binary Search,写得晕晕乎乎。。。。不知道对不对。
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
-google 1point3acres
总之感觉Google Pittsburgh还是挺简单的。除了算法题也不问其他问题了。祝找工的小伙伴们Good Luck!. visit 1point3acres.com for more.

评分

5

查看全部评分

本帖被以下淘专辑推荐:

wenqiang88 发表于 2015-9-4 09:00:22 | 显示全部楼层
请问LZ第一轮的three sum为什么返回数量就可以用binary search优化?
回复 支持 反对

使用道具 举报

宝贝忆彼岸 发表于 2015-9-4 09:04:16 | 显示全部楼层
谢楼主分享,请问楼主第一题的3sum怎么用binary search优化?是可以assume这个array里不含重复的数字么?
回复 支持 反对

使用道具 举报

hulahu 发表于 2015-9-4 09:25:21 | 显示全部楼层
楼主, 最后权重那道能不能说下? 祝您拿到big offer
回复 支持 反对

使用道具 举报

 楼主| fordreamzju 发表于 2015-9-4 09:50:25 | 显示全部楼层
宝贝忆彼岸 发表于 2015-9-4 09:04
谢楼主分享,请问楼主第一题的3sum怎么用binary search优化?是可以assume这个array里不含重复的数字么?

因为是要找小于等于的 所以当你固定两个pointer 就可以用binary search找到第三个pointer的位置。应该是assume没有重复的。你只要找到不满足条件的最小pointer位置就可以了
回复 支持 反对

使用道具 举报

 楼主| fordreamzju 发表于 2015-9-4 09:58:12 | 显示全部楼层
hulahu 发表于 2015-9-4 09:25
楼主, 最后权重那道能不能说下? 祝您拿到big offer

比如我们认为在[0,0.5]返回A,[0.5,0.8]返回B,[0.8,1.0]返回C。先构造一个Array:{0.5,0.8,1.0},再记录一个map{0.5:A,0.8:B,1.0:C}。任意产生一个0到1的随机数,找到这个随机数所在的区间的上限(可以用Binary search找),再返回map里对应的值就可以了。
回复 支持 反对

使用道具 举报

wenqiang88 发表于 2015-9-4 10:18:20 | 显示全部楼层
fordreamzju 发表于 2015-9-4 09:50
因为是要找小于等于的 所以当你固定两个pointer 就可以用binary search找到第三个pointer的位置。应该是a ...

固定第一个pointer后,用两个指针往中间移动也是O(n^2).
为啥Binary Search就一定优化了?每次找要O(log n),虽然每次寻找的总长度会越来越小,但是怎么证明这个过程一定比两个指针的方法要好?
回复 支持 反对

使用道具 举报

Warren 发表于 2015-9-5 22:43:24 | 显示全部楼层
好赞,祝楼主offer多多~
回复 支持 反对

使用道具 举报

swing 发表于 2015-9-5 23:05:20 | 显示全部楼层
楼主,你们是招聘会去的么,还是?
回复 支持 反对

使用道具 举报

 楼主| fordreamzju 发表于 2015-9-6 00:48:25 | 显示全部楼层
swing 发表于 2015-9-5 23:05
楼主,你们是招聘会去的么,还是?

我是内推的。
回复 支持 反对

使用道具 举报

swing 发表于 2015-9-6 03:06:57 | 显示全部楼层

好的,谢谢,祝拿offer哟~
回复 支持 反对

使用道具 举报

wzhwawhxm 发表于 2015-9-6 03:39:53 | 显示全部楼层
楼主,我也对你第一题的那种优化有点困惑,我不认为用binary search是优化,我觉得它的time complexity甚至要大于O(n^2)了
回复 支持 反对

使用道具 举报

fezfeng 发表于 2015-9-6 04:49:48 | 显示全部楼层
wzhwawhxm 发表于 2015-9-6 03:39
楼主,我也对你第一题的那种优化有点困惑,我不认为用binary search是优化,我觉得它的time complexity甚至 ...

我觉得我大概明白楼主的意思,当你确定了左右指针之后,肯定要判断array[left]+array[right]是否小于target,那么假设它们的和大于target,正常的操作是把右指针向左移动一位,直到找到满足条件的右指针。但是,这个过程是线性复杂度,完全可以用二分找到对于右指针来说最小的不满足条件的位置,这样,对于一个左指针,有多少合法的右指针就可求了。同理,当左指针右移时,同样用二分找到最小的不满足条件的左指针位置,这样就可以做到快速地累加合法结果。复杂度是O(nlgn)
回复 支持 反对

使用道具 举报

fezfeng 发表于 2015-9-6 05:00:07 | 显示全部楼层
楼主面得很不错~一定有offer!小问一下第二轮那个小哥追问,有没有可能是想问线程的执行顺序不一样呢?瞎猜的。
回复 支持 反对

使用道具 举报

wzhwawhxm 发表于 2015-9-6 05:36:58 | 显示全部楼层
fezfeng 发表于 2015-9-6 04:49. 鍥磋鎴戜滑@1point 3 acres
我觉得我大概明白楼主的意思,当你确定了左右指针之后,肯定要判断array[left]+array[right]是否小于targ ...

哦,好像是这个意思,厉害。。。这题换我去面就拜拜了。。。我去面就是想到binary search估计也觉得不可行。。。
回复 支持 反对

使用道具 举报

wenqiang88 发表于 2015-9-6 05:46:16 | 显示全部楼层
fezfeng 发表于 2015-9-6 04:49
我觉得我大概明白楼主的意思,当你确定了左右指针之后,肯定要判断array[left]+array[right]是否小于targ ...

但是对于worst case,假设右边指针只需要像左移动一位,但是binary search仍然需要O(log n)才能找到。所以不一定优化了
回复 支持 反对

使用道具 举报

fezfeng 发表于 2015-9-6 06:17:02 | 显示全部楼层
wenqiang88 发表于 2015-9-6 05:46
但是对于worst case,假设右边指针只需要像左移动一位,但是binary search仍然需要O(log n)才能找到。所 ...

哦。。。那个并不是nlogn。。。
回复 支持 反对

使用道具 举报

agneshanlu 发表于 2015-9-6 06:46:17 | 显示全部楼层
fezfeng 发表于 2015-9-6 06:17
哦。。。那个并不是nlogn。。。

请问不是nlogn指的是什么?.1point3acres缃
回复 支持 反对

使用道具 举报

fezfeng 发表于 2015-9-6 09:26:41 | 显示全部楼层
agneshanlu 发表于 2015-9-6 06:46
请问不是nlogn指的是什么?

哦 我之前说楼主的优化想法是nlogn,但是后来想了想,应该不是,二分法的优化可能不见得好于n^2的解法。
回复 支持 反对

使用道具 举报

agneshanlu 发表于 2015-9-7 00:59:40 | 显示全部楼层
fezfeng 发表于 2015-9-6 09:26
哦 我之前说楼主的优化想法是nlogn,但是后来想了想,应该不是,二分法的优化可能不见得好于n^2的解法。

多谢!多谢多谢!
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 04:21

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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