一亩三分地论坛

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

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

新鲜出炉的谷歌面经

[复制链接] |试试Instant~ |关注本帖
iverson1122 发表于 2015-8-8 03:18:02 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 硕士 全职@Google - 网上海投 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
新鲜出炉的谷歌面经~~ 考官是三哥,信号也一般,真心听不懂,他有时候问无奈了就在google doc上打字出来,汗…
. from: 1point3acres.com/bbs
一共问了两道题,都算基本的,但是第一次面试太紧张T T. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

1. 给一个binary tree 打印所有的path~~然后问了时间空间复杂度~~就用一般递归做的

2. good number问题。 一个数如果能用(至少两组)两个立方数相加得到那么就是good number。print 小于等于n的所有good number。分析时间复杂度。.鐣欏璁哄潧-涓浜-涓夊垎鍦
   我先把小于n的所有立方数存起来。然后就变成了2 sum问题了。。。

最后,剩一分钟,三哥问我有没有什么问题,我问他一个合格的Googler在你心中应该具备什么标准。。。三哥告诉我:think quickly。。。。呵呵呵~~就这么被讽刺了。。。
估计要跪了。。。.鏈枃鍘熷垱鑷1point3acres璁哄潧
. from: 1point3acres.com/bbs
. 1point 3acres 璁哄潧

补充内容 (2015-8-11 04:19):
沾了地里喜气~~今天受到onsite通知~~顺道问下大家,有木有被recruiter安排coaching phone的经历?是个怎么样的过程??

评分

4

查看全部评分

enirinth 发表于 2015-8-10 01:02:01 | 显示全部楼层
第二题LZ看这样是否正确:
1. 创建数组,存储所有 ≤n 的立方数,value = index^3, 一共m个(m = n^1/3)--> O(m)
2. 在这m个立方数中,找两组和相等的
  2.1 一共会有m^2个可能的和(包括重复).鏈枃鍘熷垱鑷1point3acres璁哄潧
  2.2 sort --> O(m^2logm^2) = O(m^2logm)
  2.3 scan 一遍,找consecutive的、相等的、长度≥2的子数组个数 --> O(m^2)

最后的总复杂度为O(m^2logm) ;带入m = n^(1/3) 得O(n^(2/3)logn)
回复 支持 3 反对 0

使用道具 举报

enirinth 发表于 2015-8-10 20:58:15 | 显示全部楼层
handsomecool 发表于 2015-8-8 11:39.鐣欏璁哄潧-涓浜-涓夊垎鍦
第二题为啥是2 sum?
首先得到小于n的立方数k个(k

"发现重复出现"的这个是需要时间的,除非你第一个set是个hash table,“发现重复出现”才只要O(1)时间,否则:. From 1point 3acres bbs
1.如果是unordered set, 要花O(set size)的时间
2. ordered set, 要花O(log size)的时间来找,还要额外的linear time去维护order. 鍥磋鎴戜滑@1point 3 acres
所以O(k^2)的复杂度还要乘上“发现重复”的amortized running time (linear)

这个问题和2-sum问题相似点在于:
都是先维护一个表,然后去查找另一个相应的值。

(所以相应的,2-sum如果可以用hashtable,查找另一个值只需要O(1)时间,总共是O(N);
.鏈枃鍘熷垱鑷1point3acres璁哄潧不能用hashtable,查找时间最少只能logn,sort是nlogn,总共是nlogn)

我个人觉得,如果你不能给出合理的hashCode() (which requires 题目给出key的一些特征),面试中最好不用hashtable,所以这个题的复杂度lower bound应该就是O((n^(2/3)logn)了
回复 支持 0 反对 1

使用道具 举报

handsomecool 发表于 2015-8-8 11:39:09 | 显示全部楼层
第二题为啥是2 sum?
首先得到小于n的立方数k个(k<=3√n). from: 1point3acres.com/bbs
然后不是应该双层loop来得出答案么? 时间是O(k^2 )

比如n=200,
那么得出k=5个数: 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
1     2     3      4         5
1     8    27     64      125
然后双重loop得出答案有:
1+8=9
1+27=28
1+64=65
1+125=126.1point3acres缃
8+27=35
8+64=72
。。。
. 1point3acres.com/bbs

补充内容 (2015-8-8 12:14):. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
我开始没明白“至少两组”的意思。 不过算法不用怎么改,双重loop的时候用2个set, 两个数的和扔进第一个set, 发现重复出现的,扔进第二个set. return第二个set.  时间还是O(k^2)=O(n^(2/3))
回复 支持 1 反对 0

使用道具 举报

wb7 发表于 2015-8-8 03:49:48 | 显示全部楼层
看起来lz think的挺quickly啊。。。good luck
回复 支持 反对

使用道具 举报

hulahu 发表于 2015-8-8 04:14:22 | 显示全部楼层
答的挺好的。 加油哦, onsite
回复 支持 反对

使用道具 举报

swing 发表于 2015-8-8 04:41:42 | 显示全部楼层
楼主不错,第一面面google,不错
回复 支持 反对

使用道具 举报

 楼主| iverson1122 发表于 2015-8-8 10:36:34 | 显示全部楼层
wb7 发表于 2015-8-8 03:49
看起来lz think的挺quickly啊。。。good luck

算法思路还算清楚,就是问复杂度有点卡壳,开始还说错了,三哥提醒才改过来
回复 支持 反对

使用道具 举报

 楼主| iverson1122 发表于 2015-8-8 10:36:52 | 显示全部楼层
hulahu 发表于 2015-8-8 04:14
答的挺好的。 加油哦, onsite

谢谢~ 加油~
回复 支持 反对

使用道具 举报

 楼主| iverson1122 发表于 2015-8-8 10:37:39 | 显示全部楼层
swing 发表于 2015-8-8 04:41
楼主不错,第一面面google,不错

又被嘲笑了 谷歌回复的太快了还没做好心理准备~
回复 支持 反对

使用道具 举报

maybeluo 发表于 2015-8-8 11:30:41 | 显示全部楼层
复杂度分别是:1.指数(路径数目),2. O(n)吗?
回复 支持 反对

使用道具 举报

handsomecool 发表于 2015-8-8 11:42:29 | 显示全部楼层
maybeluo 发表于 2015-8-8 11:30
复杂度分别是:1.指数(路径数目),2. O(n)吗?

第一题O(n)就行吧 n=节点数目。 就用普通的dfs+一个vector

补充内容 (2015-8-8 12:28):
sry, 不是O(n), 虽然是dfs过一遍,但每次将路径放进答案的时候要复制路径,所以是nlog(n)
回复 支持 反对

使用道具 举报

 楼主| iverson1122 发表于 2015-8-8 11:50:16 | 显示全部楼层
maybeluo 发表于 2015-8-8 11:30.1point3acres缃
复杂度分别是:1.指数(路径数目),2. O(n)吗?

第一题的时间复杂度我答的是O(nlgn),就是一共lgn层,每层递归的路径是O(n)。空间复杂度答的O(n)
第二题答的是O(n^(4/3)),外层大循环是O(n),里层的存的立方数是O(n^(1/3)),两个相乘。阿三考官嘟囔了半天我也没太听明白他到底什么意思= =
回复 支持 反对

使用道具 举报

 楼主| iverson1122 发表于 2015-8-8 11:51:51 | 显示全部楼层
handsomecool 发表于 2015-8-8 11:39
第二题为啥是2 sum?
首先得到小于n的立方数k个(k

可能表述不清楚,注意括号里写的,是“至少两组”两个立方数相加才算是good number,只有一组不算
回复 支持 反对

使用道具 举报

handsomecool 发表于 2015-8-8 12:16:35 | 显示全部楼层
iverson1122 发表于 2015-8-8 11:51
可能表述不清楚,注意括号里写的,是“至少两组”两个立方数相加才算是good number,只有一组不算
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
原来如此。。但是时间应该是O(n^(2/3))吧,一开始找立方数只要n^(1/3)不是么?
回复 支持 反对

使用道具 举报

 楼主| iverson1122 发表于 2015-8-8 12:22:16 | 显示全部楼层
handsomecool 发表于 2015-8-8 12:16
原来如此。。但是时间应该是O(n^(2/3))吧,一开始找立方数只要n^(1/3)不是么?

找立方数是t^(1/3),然后我对t = 1:n做了个循环,每个数都判断是不是good number,所以就是n^(4/3)了。可能有更简单的做法
回复 支持 反对

使用道具 举报

 楼主| iverson1122 发表于 2015-8-8 13:29:17 | 显示全部楼层
handsomecool 发表于 2015-8-8 11:39
第二题为啥是2 sum?
首先得到小于n的立方数k个(k

补充的部分,判断两数之和在不在第一个set里面,应该是O(k^2)复杂度吧(如果不存成hashTable的话),所以总的复杂度也就还是O(n^(4/3))了…. visit 1point3acres.com for more.

补充内容 (2015-8-8 13:33):
当然算法思路很好也很简洁~~
回复 支持 反对

使用道具 举报

f1371342385 发表于 2015-8-8 14:34:31 | 显示全部楼层
iverson1122 发表于 2015-8-8 13:29
补充的部分,判断两数之和在不在第一个set里面,应该是O(k^2)复杂度吧(如果不存成hashTable的话),所以 ...

也不一定是一个two sum的问题了吧,因为可能会有多个相加,dfs可以吗,dfs所有可能的结果。
回复 支持 反对

使用道具 举报

zxy_snow 发表于 2015-8-9 21:16:19 | 显示全部楼层
第二题没看懂啊,至少两组,两个立方数???
回复 支持 反对

使用道具 举报

 楼主| iverson1122 发表于 2015-8-10 01:15:21 | 显示全部楼层
f1371342385 发表于 2015-8-8 14:34.1point3acres缃
也不一定是一个two sum的问题了吧,因为可能会有多个相加,dfs可以吗,dfs所有可能的结果。

他给的题就限定了是两个立方数的和,不考虑多个的情况
回复 支持 反对

使用道具 举报

 楼主| iverson1122 发表于 2015-8-10 01:17:28 | 显示全部楼层
zxy_snow 发表于 2015-8-9 21:16
第二题没看懂啊,至少两组,两个立方数???

比如一个数n = a^3+b^3 = c^3 + d^3,n就是一个good number。比如9就不是good number,因为只能分解成一组两个立方数之和(1+8)
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 01:13

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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