一亩三分地论坛

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

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

Google Pittsburgh Onsite 面经

[复制链接] |试试Instant~ |关注本帖
泡妞被妞泡 发表于 2015-5-5 03:29:47 | 显示全部楼层 |阅读模式

2015(4-6月) 码农类 硕士 全职@Google - 网上海投 - Onsite |Otherfresh grad应届毕业生

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

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

x
4.29在匹兹堡办公室面的。.鏈枃鍘熷垱鑷1point3acres璁哄潧

第一轮:给你两个人A和B,自己设计数据结构,判断他们是否有血缘关系。我的答案:一开始看不懂这题,紧张的要死,后来终于想到了,这不是二叉树嘛。设计两个TreeNode(int id, TreeNode left, TreeNode right),left和right是root节点的parents,判断A和B是否包含有id相同的节点。我给了俩个答案,第一个是递归,第二个用HashSet。都问了时间复杂度和空间复杂度。由于HashSet方法要遍历二叉树,我还介绍了下遍历二叉树的三种方法(Recursive, Iterative, Morris Traversal),面试官好像对Morris遍历比较感兴趣,让我简单讲了下。
第二轮:给你一个数组和一个Target值,找出满足这个条件的Triplet的个数:三个数相加小于Target。
我的答案:还是写了两个答案,第一个用Backtracking,第二个用for+双指针从左右往中间扫。没注意到是“小于”,自己一直在算“小于和等于”,最后面试官指出说,好吧,那我们就算“小于和等于的吧”。问了时间复杂度和空间复杂度。


第三轮:设计一个函数,判断某个只包含数字的字符串是不是Ambigram(看链接或自行Google,比如,69,88,609,818等都是Ambigram)。Follow up:给一个整数n,找出所有长为n的Ambigram。
我的答案:前面开胃菜简单,String只能包含0,1,6,8,9,再求出String的Ambigram和原String比较是否相等就行了。Follow up比较鬼精鬼精的,答案用递归做,我先是算出n-1的,面试官说其实你可以先求出n-2的答案,再利用n-2的答案求出n的答案,这题方法比较绝,往n-2的答案里面append两个数字的时候分别各自加在两边就行,没必要往中间插入,因为有很多重复的case,我用文字很难描述。我的Solution就是老老实实的那种方法,面试官一直给我hint,说,你看这里,这样是不是更省时间,我说,我靠,你太叼了。感觉这轮最难。问了时间复杂度和空间复杂度,一开始还答错了,唉。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

第四轮:这个面试官是学长,明显水过。
问了“Word Break”,Word Break我说时间复杂度和n^2,学长说不对,求HashCode这里也要花时间,所以应该是n^3。还问我求HashCode有没有比较省时间的方法,我说自己设计个求HashCode的方法,加上新字符的时候,加上这个字符的HashCode就行了,学长说没问题了。. 1point 3acres 璁哄潧
“石子合并(http://blog.csdn.net/acdreamers/article/details/18039073)”,一开始问了随机合并任意两堆用什么算法,我说这题我会,用贪心算法,然后就问了时间复杂度和空间复杂度,最后得出结论是用Heap最省时间。然后问了合并相邻两堆(看那链接里的文章),写了方程式,他还问我你知道平行四边形法则吗?我说知道,可以把石子归并时间复杂度简化到n^2,然后就没问了。
最后学长说,看来你LeetCode刷的不错,好,这轮面试没问题,接下来我考道你不会的意思意思一下:给一个二维整形数组array,在里面圈一个长方形,求出长方形内所有整数的和。我一开始说,这题我没见过,用线段树做吗,他说不用那么麻烦,然后我就给了个一般的解,另建立一个二位数组sum,sum(m, n)位置表示的是array(0, 0)到array(m, n)之间所有整数的和,再求出给定矩形内的和就行饿了等等。

总结:感觉这次面试题目比较简单,除了第三轮优化的过程比较绝,每个Solution都会问到详细的时间复杂度和空间复杂度,我以前没注意到这点,时间复杂度和空间复杂度有的还答错了。
另外,学长说,我这两年面试都是用这些题,看来我得换换题目了,如果每个面试官都和他这样的话,那面经真的有用。

还在等Google的消息。. 1point 3acres 璁哄潧

评分

2

查看全部评分

本帖被以下淘专辑推荐:

wangxinlei 发表于 2015-5-6 06:11:52 | 显示全部楼层
问了“Word Break”,Word Break我说时间复杂度和n^2,学长说不对,求HashCode这里也要花时间,所以应该是n^3.
求问楼主word break什么时候求hash code? dictionary 不是以hashtable形式给出的么?那lookup不是O(1)么?
回复 支持 反对

使用道具 举报

wangxinlei 发表于 2015-5-6 06:25:56 | 显示全部楼层
第一题的血缘关系指的是什么?父子母子这种,还是兄弟?还是表兄弟,爷爷孙子这种都算?
回复 支持 反对

使用道具 举报

hami33 发表于 2015-5-6 13:25:33 | 显示全部楼层
感觉楼主答的很好呀,应该没问题!
回复 支持 反对

使用道具 举报

 楼主| 泡妞被妞泡 发表于 2015-5-7 07:43:41 | 显示全部楼层
wangxinlei 发表于 2015-5-6 06:11
.鐣欏璁哄潧-涓浜-涓夊垎鍦问了“Word Break”,Word Break我说时间复杂度和n^2,学长说不对,求HashCode这里也要花时间,所以应该是n ...

他说JAVA里面计算每个String的HashCode也加算个O(n)时间(String.HashCode()),我也没争论。
回复 支持 反对

使用道具 举报

 楼主| 泡妞被妞泡 发表于 2015-5-7 07:44:07 | 显示全部楼层
wangxinlei 发表于 2015-5-6 06:25
第一题的血缘关系指的是什么?父子母子这种,还是兄弟?还是表兄弟,爷爷孙子这种都算?

都算,只要两个人的祖先有共同的人,他俩就是亲属。
回复 支持 反对

使用道具 举报

wangxinlei 发表于 2015-5-7 08:14:15 | 显示全部楼层
泡妞被妞泡 发表于 2015-5-7 07:44
都算,只要两个人的祖先有共同的人,他俩就是亲属。

哦。。那有说一对夫妻只有一个孩子么?不然感觉应该是个图而不是树啊。。。做法是不是对A开始把每个ancestor放进hashtable,然后对B开始遇到的每个ancestor都check一下这个table?
回复 支持 反对

使用道具 举报

mymiracle 发表于 2015-5-7 08:51:59 | 显示全部楼层
wangxinlei 发表于 2015-5-7 08:14
哦。。那有说一对夫妻只有一个孩子么?不然感觉应该是个图而不是树啊。。。做法是不是对A开始把每个ances ...

乱伦才会出图...如果每个节点不保存parent指针,你这个办法是不是先得遍历找到A的,然后遍历找到B,再做比较?
回复 支持 反对

使用道具 举报

wangxinlei 发表于 2015-5-7 09:08:46 | 显示全部楼层
mymiracle 发表于 2015-5-7 08:51
乱伦才会出图...如果每个节点不保存parent指针,你这个办法是不是先得遍历找到A的,然后遍历找到B,再做 ...

哦。。。我懂了,我一开始想的是如果是亲兄弟的话就有同样的父母,所以会出现两个点的child是一样的情况,所以是图。但是这题貌似每次只管一个node就行,所以看child1时候就把C1当做root,而C1下面肯定是二叉树,遍历树就可以了。
回复 支持 反对

使用道具 举报

aiwojiujiu 发表于 2016-2-10 10:18:29 | 显示全部楼层
楼主肯定offer 妥妥的了  请问楼主dp的平行四边形法则优化 哪里学的? 有没有链接。。。
回复 支持 反对

使用道具 举报

 楼主| 泡妞被妞泡 发表于 2016-4-12 10:53:17 | 显示全部楼层
aiwojiujiu 发表于 2016-2-10 10:18
楼主肯定offer 妥妥的了  请问楼主dp的平行四边形法则优化 哪里学的? 有没有链接。。。
.鏈枃鍘熷垱鑷1point3acres璁哄潧
哈哈,并没有,一年后Google HR告诉我,其实我当时面试已经过了,但是没有找到合适的Team,就把我拒了,现在联系我重新面试。
回复 支持 反对

使用道具 举报

rasperrypie 发表于 2016-8-20 08:09:03 | 显示全部楼层
泡妞被妞泡 发表于 2015-5-7 07:43
他说JAVA里面计算每个String的HashCode也加算个O(n)时间(String.HashCode()),我也没争论。

复杂度应该是指数或者factorial的吧?每个string的位置都有N个单词的可能。所以O(N^length of string)
回复 支持 反对

使用道具 举报

liurudahai 发表于 2016-10-6 00:07:34 | 显示全部楼层
第一题感觉不太对啊,每对夫妇只有一个孩子吗?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 07:00

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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