一亩三分地论坛

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

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

热乎的Google MTV onsite面经

[复制链接] |试试Instant~ |关注本帖
mwsak47 发表于 2016-4-1 06:23:39 | 显示全部楼层 |阅读模式

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

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

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

x
第一轮:
年轻三哥。.鏈枃鍘熷垱鑷1point3acres璁哄潧
1. 给一堆votes(candidate, timestamp),问当前时刻T得票最高的人是谁。Follow up问得票最高的前K个人。
2. 问一个字符串的任意permutation是不是回文,leetcode 266。

第二轮:
年长三哥。
1. 数学题,不写代码。给5个在网格上的点(x,y坐标都是整数),求证5个点两两连线的中点必有一个在网格上(x,y坐标都是整数)。
2. 给一个整数N,将集合S={1,2,3,...,N}分两个子集S1和S2,问使sum(S1) == sum(S2)的划分方法有多少个。类似subset,leetcode 90。


午饭

第三轮:
发型诡异的日本大叔。
Trapping Rain Water, leetcode 42。这轮代码写得有点儿懵逼。

第四轮:
貌似是中国小哥,带白人小哥shadow。
1. 给一个整数数组a,函数f(i)返回除a外所有整数的乘积,求所有的f(i)。Follow up问不许用除法怎么做。
2. 平面上一堆点,找两个点使由这两个点确定的直线平分剩余所有点。只说了下思路,并没有写代码。. more info on 1point3acres.com
我的思路是先找到最下面的点P,然后根据其余点与P的连线和P所在水平线的夹角找中位点。又说了可能有共线的情况,小哥说不用考虑共线。不知道思路对不对。


总之是面完了。希望4月8号之前给结果,不然要被迫从了Amazon了。
顺便求问如何跟Amazon要deadline的extension。
. From 1point 3acres bbs

补充内容 (2016-4-5 02:28):
第二轮第二题应该是leetcode 78,没有重复元素。. more info on 1point3acres.com

补充内容 (2016-4-9 22:47):
昨天接到电话,挂了。。。

评分

3

查看全部评分

本帖被以下淘专辑推荐:

  • · Google|主题: 54, 订阅: 45
zatarratw 发表于 2016-4-5 10:46:23 | 显示全部楼层
比如說,這個是n = 7的dp table,因為要partition成兩組一樣和的set,所以只要算到summation(n)的一半就好了。然後因為兩兩一組,所以最後的值要除以2。

dp-table

dp-table

. 1point 3acres 璁哄潧
. 鍥磋鎴戜滑@1point 3 acres
回复 支持 3 反对 0

使用道具 举报

 楼主| mwsak47 发表于 2016-4-1 12:45:07 | 显示全部楼层
zatarratw 发表于 2016-4-1 11:22
我被他掛得很慘,根本沒時間閒聊,依稀記得他上嘴唇的鬍子挺厚的是吧?

应该是他,中等身高,挺瘦的。
回复 支持 0 反对 1

使用道具 举报

 楼主| mwsak47 发表于 2016-4-1 14:22:19 | 显示全部楼层
夜辉冥 发表于 2016-4-1 13:41
那个数学题你是肿么证明的? 可以给他举例说最坏情况吗? 还说说要严格的数学证明?

反证法。设两个点为(x1,y1)和(x2,y2)。只有x1和x2奇偶性相同且y1和y2奇偶性想同时,这两点连线的中点才会on grid。所以点一共有(奇,奇)(奇,偶)(偶,奇)(偶,偶)四种情况。而一共有五个点。所以必然会有两个点的x和y的奇偶性都相同,这样必有连线中点on grid。
回复 支持 1 反对 0

使用道具 举报

newbiee 发表于 2016-4-1 07:05:33 | 显示全部楼层
希望也能见到这些题,难度感觉稍有降低
回复 支持 反对

使用道具 举报

mrhohn 发表于 2016-4-1 07:20:43 | 显示全部楼层
也是这周面完,同问怎么跟亚麻要extension…G家hr说下周一才能拿齐feedback
回复 支持 反对

使用道具 举报

tcomein2009 发表于 2016-4-1 07:44:33 | 显示全部楼层
感谢楼主分享

给一个整数N,将集合S={1,2,3,...,N}分两个子集S1和S2,问使sum(S1) == sum(S2)的划分方法有多少个。类似subset

这题大家还有别的思路吗?
回复 支持 反对

使用道具 举报

zatarratw 发表于 2016-4-1 09:05:01 | 显示全部楼层
感覺你第二面遇到的三哥應該跟我第一面是同一個,題目都一模一樣!不知道他這次有沒有邊嗑花生米邊面你 XD

http://www.1point3acres.com/bbs/thread-167364-1-1.html
回复 支持 反对

使用道具 举报

dimi 发表于 2016-4-1 09:46:43 | 显示全部楼层
很详细,题目不简单阿
回复 支持 反对

使用道具 举报

 楼主| mwsak47 发表于 2016-4-1 09:54:42 | 显示全部楼层
zatarratw 发表于 2016-4-1 09:05
感覺你第二面遇到的三哥應該跟我第一面是同一個,題目都一模一樣!不知道他這次有沒有邊嗑花生米邊面你 XD
...

哈哈哈哈哈 并没有 是gmail spam detection组的那个么
回复 支持 反对

使用道具 举报

zatarratw 发表于 2016-4-1 11:22:38 | 显示全部楼层
mwsak47 发表于 2016-4-1 09:54. more info on 1point3acres.com
哈哈哈哈哈 并没有 是gmail spam detection组的那个么

我被他掛得很慘,根本沒時間閒聊,依稀記得他上嘴唇的鬍子挺厚的是吧?
回复 支持 反对

使用道具 举报

dimi 发表于 2016-4-1 11:29:25 | 显示全部楼层
zatarratw 发表于 2016-4-1 11:22
我被他掛得很慘,根本沒時間閒聊,依稀記得他上嘴唇的鬍子挺厚的是吧?

聽說google每個月會退役一批題目,看來這個三哥的題目還在線。
回复 支持 反对

使用道具 举报

夜辉冥 发表于 2016-4-1 13:41:50 | 显示全部楼层
那个数学题你是肿么证明的? 可以给他举例说最坏情况吗? 还说说要严格的数学证明?
回复 支持 反对

使用道具 举报

GUIXIANG 发表于 2016-4-4 23:30:30 | 显示全部楼层
感谢楼主分享,祝楼主早日拿到offer. 弱问第二轮第二题,S1和S2里的元素是必须包括1到N的所有数吗?如果不是,类似leetcode 90题,是不是要先找出所有的subset, 然后在所有的subset里找sum相等的?还有第四轮第一题,为什么要用到除法?遍历数组,元素相乘,碰到index是i就跳过不可以了吗?
回复 支持 反对

使用道具 举报

yucheyang2 发表于 2016-4-4 23:35:05 | 显示全部楼层
和Amazon HR赶紧约一个Offer Call,就明说你有Pending Onsite,一般延长两周没问题的。
回复 支持 反对

使用道具 举报

zatarratw 发表于 2016-4-5 00:13:13 | 显示全部楼层
partition sets那題,應該要用DP解,把問題簡化之後,會變成0/1 knapsack problem
回复 支持 反对

使用道具 举报

 楼主| mwsak47 发表于 2016-4-5 02:27:40 | 显示全部楼层
GUIXIANG 发表于 2016-4-4 23:30
感谢楼主分享,祝楼主早日拿到offer. 弱问第二轮第二题,S1和S2里的元素是必须包括1到N的所有数吗?如果不是, ...
.鐣欏璁哄潧-涓浜-涓夊垎鍦
谢谢。第二轮第二题是要划分从1到N的N个数,所以是没有重复的,所以其实应该是leetcode 78。找到和是总和一半的子集数再除以2就行了。第四轮第一题是要在O(n)的时间内求所有的f(i)。
回复 支持 反对

使用道具 举报

 楼主| mwsak47 发表于 2016-4-5 02:29:43 | 显示全部楼层
yucheyang2 发表于 2016-4-4 23:35
和Amazon HR赶紧约一个Offer Call,就明说你有Pending Onsite,一般延长两周没问题的。

OK,多谢。Amazon效率挺慢的,约到了今天下午,不知道还来不来得及。
回复 支持 反对

使用道具 举报

 楼主| mwsak47 发表于 2016-4-5 02:33:44 | 显示全部楼层
zatarratw 发表于 2016-4-5 00:13
partition sets那題,應該要用DP解,把問題簡化之後,會變成0/1 knapsack problem

不明觉厉啊
回复 支持 反对

使用道具 举报

zatarratw 发表于 2016-4-5 10:08:32 | 显示全部楼层

就是0/1背包問題。你寫個dp的table,其中一軸是n的數字,另外一軸是sum(1 to n) / 2,cell value是count,用手寫一下從1 - 5 or 7左右,應該就會很清楚了。我當初就是卡在再給我五分鐘就可以把這個dp table寫出來,然後這題就可以解出來,但是三哥給我遲到15min....
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 21:18

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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