一亩三分地论坛

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

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

谷歌2015二月中旬onsite

[复制链接] |试试Instant~ |关注本帖
sodasun 发表于 2015-3-15 13:05:04 | 显示全部楼层 |阅读模式

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

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

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

x
二月中旬去google montain view onsite了 一共四轮. 鍥磋鎴戜滑@1point 3 acres

第一轮:印度男 人挺好的 问的majority number(leetcode) 之后把输入从一个数组改为一个stream再做。
. 1point3acres.com/bbs
第二轮:白人男 删除树中的重复子树,发现重复子树就把这个指针指到之前有这棵树的位置(当时我也不知道怎么做也不太懂题目) 暴力做了。。。

第三轮:华裔女,图中有没有环。。。我没写过图的算法,bfs,dfs都只写出一半反正怎么弄都不全对。

第四轮:白人男 年纪比较大 找一个数组中的popular value,就是返回一个已经排序好的数组中超过四分之一的数,刚开始我以为跟第一轮差不多,后来想不一样,反正扫一遍肯定能做,他问我有没有巧妙一点的方法。我用两个指针的方法做的,他好像也没说什么

面完后收到拒信,让我加面一轮看能不能去那个engineering recidency program。 有米有同学了解这个项目?有米有参加过的来说说,看了大家都是在面试这个项目。。。

评分

4

查看全部评分

本帖被以下淘专辑推荐:

wny 发表于 2015-3-15 13:16:24 | 显示全部楼层
楼主面完多久收到据信的。。。?
回复 支持 反对

使用道具 举报

 楼主| sodasun 发表于 2015-3-15 13:19:02 | 显示全部楼层
wny 发表于 2015-3-15 13:16
楼主面完多久收到据信的。。。?

两三周了才收到 催了半天
回复 支持 反对

使用道具 举报

cow12331 发表于 2015-3-15 23:13:25 | 显示全部楼层
周五电面被问了第4轮那题,他不说要求,搞到最后hashmap做的显然不是满意答案
回复 支持 反对

使用道具 举报

clfhaha1234 发表于 2015-3-15 23:25:00 | 显示全部楼层
第四轮个人O(LogN)答案:

既然有一个数超过了1/4,也就是说,我们从取第一个数字,然后每隔N*1/4-1的间隔取数字。总共会取到4个数,那么这4个数其中之一,一定就是答案。所以只用检查着4个数就好了。

头尾那2个比较好判断,中间那两个需要用二分判。
回复 支持 反对

使用道具 举报

refurbish 发表于 2015-3-15 23:47:17 | 显示全部楼层
第二轮的暴力解法是O(n^3),一个优化做法是O(n^2),需要从底向上来搞. Waral 鍗氬鏈夋洿澶氭枃绔,
第三轮应该用bfs,扫一遍遇到见过的就是有环了
第四轮可以用merge sort的思想O(nlogn). From 1point 3acres bbs


补充内容 (2015-3-15 23:55):
感觉第三轮国人女应该是在放水了
回复 支持 反对

使用道具 举报

sonicgu 发表于 2015-3-16 00:07:12 | 显示全部楼层
refurbish 发表于 2015-3-15 23:47
第二轮的暴力解法是O(n^3),一个优化做法是O(n^2),需要从底向上来搞
第三轮应该用bfs,扫一遍遇到见过的 ...

如果是无向图,碰到见过的就是环,但是有向图就不一定了,这个题不能说简单
回复 支持 反对

使用道具 举报

sonicgu 发表于 2015-3-16 00:14:40 | 显示全部楼层
祝lz后面面试好运
回复 支持 反对

使用道具 举报

cow12331 发表于 2015-3-16 00:25:17 | 显示全部楼层
其实第四轮是个细节题,比如没有popular num的时候怎么返回,百分之25怎么处理, 我面的时候说的sorted array,其实一个count记录当前统计数就可以了,但是那人没说要求。前面有人说跳数的方法是不行的比如12222就不能通过。
回复 支持 反对

使用道具 举报

refurbish 发表于 2015-3-16 01:01:10 | 显示全部楼层
sonicgu 发表于 2015-3-16 00:07. Waral 鍗氬鏈夋洿澶氭枃绔,
如果是无向图,碰到见过的就是环,但是有向图就不一定了,这个题不能说简单

恩忘了有向图了,有向图直接拓扑排序,更简单
回复 支持 反对

使用道具 举报

 楼主| sodasun 发表于 2015-3-16 04:13:47 来自手机 | 显示全部楼层
clfhaha1234 发表于 2015-3-15 23:25
第四轮个人O(LogN)答案:

既然有一个数超过了1/4,也就是说,我们从取第一个数字,然后每隔N*1/4-1的 ...

我跟你做的类似吧 但是我做的时候当发现第0个和第n/4-1不等的时候 我是直接在0到n/4-1之间去寻找n/4-1的那个数 因为这之间只有这个数还可能成为popular value
回复 支持 反对

使用道具 举报

 楼主| sodasun 发表于 2015-3-16 04:15:08 来自手机 | 显示全部楼层
refurbish 发表于 2015-3-15 23:47
第二轮的暴力解法是O(n^3),一个优化做法是O(n^2),需要从底向上来搞
第三轮应该用bfs,扫一遍遇到见过的 ...

我觉得她没想放水 应该是写出来以后后面还有大招等我。。。可我连小boss都没打过就没见着大boss。。。
回复 支持 反对

使用道具 举报

 楼主| sodasun 发表于 2015-3-16 04:16:03 来自手机 | 显示全部楼层
cow12331 发表于 2015-3-16 00:25
其实第四轮是个细节题,比如没有popular num的时候怎么返回,百分之25怎么处理, 我面的时候说的sorted arr ...

你说的对 就是细节题 被问到没有这个value怎么返回了
回复 支持 反对

使用道具 举报

 楼主| sodasun 发表于 2015-3-16 04:17:17 来自手机 | 显示全部楼层
sonicgu 发表于 2015-3-16 00:14
祝lz后面面试好运

谢谢你啦^_^
回复 支持 反对

使用道具 举报

amy1991 发表于 2015-3-16 06:13:55 | 显示全部楼层
clfhaha1234 发表于 2015-3-15 23:25
第四轮个人O(LogN)答案:. more info on 1point3acres.com
. more info on 1point3acres.com
既然有一个数超过了1/4,也就是说,我们从取第一个数字,然后每隔N*1/4-1的 ...

没有看懂 举个例子来说 如果一个长度为11的数组
出现次数应该为3次

1 2 3 4 5 6 7 8 9 10 11. Waral 鍗氬鏈夋洿澶氭枃绔,

那么超过1/4的数字 一定存在于加粗的这三个数字 并不需要检查4个。
但是剩下来的排除过程 其实还是相当于遍历O(n) 并没有更快呀

或者我有什么地方没有看懂。 求解惑。
回复 支持 反对

使用道具 举报

Justice 发表于 2015-3-16 07:13:36 | 显示全部楼层
Round 4:
另 数组为 A,有N个元素
(1)先考虑A[N/2],用二分查找找出有几个,如果超过N/4个,返回,退出。少于N/4个时,另最小坐标为S,最大为B。考虑[0,S-1]和[B+1,N-1]。区间大小 <= N/2
(2)考虑[0 - S-1],用二分查找 A[S/2], 如果还是不超过N/4个,设最小坐标为S1,B1。直接判断区间[0,S1-1],[B1+1,S-1].区间大小 <= N/2
(3)考虑[B+1,N-1],跟(2)一样。
时间复杂度:(lg(N)). 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

补充内容 (2015-3-16 07:14):
(2)区间大小写错了。区间大小 <= N/4
回复 支持 反对

使用道具 举报

timtam85 发表于 2015-3-16 10:04:29 | 显示全部楼层
refurbish 发表于 2015-3-15 23:47
第二轮的暴力解法是O(n^3),一个优化做法是O(n^2),需要从底向上来搞. from: 1point3acres.com/bbs
第三轮应该用bfs,扫一遍遇到见过的 ...

能具体说一下第二轮的优化做法么?还有暴力解法不是O(n^2)么,在每一个node判断它的左右子树是否相同,不同就继续往下判断。
回复 支持 反对

使用道具 举报

 楼主| sodasun 发表于 2015-3-16 10:41:29 来自手机 | 显示全部楼层
timtam85 发表于 2015-3-16 10:04. 1point 3acres 璁哄潧
能具体说一下第二轮的优化做法么?还有暴力解法不是O(n^2)么,在每一个node判断它的左右子树是否相同, ...

不能只判断每个点的左子树和右子树 我做的是每个点和其他所有点判断是不是相同的树
回复 支持 反对

使用道具 举报

shinichish 发表于 2015-3-26 11:06:21 | 显示全部楼层
sodasun 发表于 2015-3-15 18:41
不能只判断每个点的左子树和右子树 我做的是每个点和其他所有点判断是不是相同的树

楼主,被engineering recidency program录取了?拿到offer了?
回复 支持 反对

使用道具 举报

shinichish 发表于 2015-3-26 11:15:50 | 显示全部楼层
Justice 发表于 2015-3-15 15:13
Round 4:
另 数组为 A,有N个元素. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
(1)先考虑A[N/2],用二分查找找出有几个,如果超过N/4个,返回,退出 ...

说白了,就是binary search,是不是?但是,复杂度为什么是logn?T(n) = 2T(T/n) + O(logn),不是吗
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 06:13

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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