一亩三分地论坛

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

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

给Google onsite面经添砖加瓦

[复制链接] |试试Instant~ |关注本帖
猫头鹰也是猫 发表于 2016-10-16 11:37:32 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 全职@Google - 猎头 - Onsite |Otherfresh grad应届毕业生

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

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

x
等结果太焦虑发个面经吧。。虽然之前花了基本一周的时间刷近期面经,但除了俩lc原题外一题面经都没考到。的确刷G的面经回报率太低,还不如把刷过的lc多夯实总结更有效。所以接下来的你们就凑活着看吧……

第一轮:超级nice的国人姐姐。因为到的比较早,先去kitchen拿了点零食然后闲聊了半天G家的室内装潢(……)和简历上的经历。题目是给一个positive integer N,求N最少能由几个2^i组成。比如N=1的时候,1=2^0,那么N最少能被1个2^0组成。再比如N=7的时候,7=4+2+1=2^2+2^1+2^0,这个case中N最少被3个2^i组成。然后follow up是,可以同时使用正或负的2^i。同样的例子N=7,在这个情况下,7=8-1=2^3-2^0,这样最少只需要2个2^i就能组成N。

第二轮:台湾葛格,人也挺nice的。没有废话直接上题,就是lc的bomb enemy,不同的是bomb也能放在enemy所在的位置。第二题是给一个iterator: 2,3,1,5,1,8… 要求写一个iterator要能return 3,3,5,8…

第三轮:印度姐,上来直接给了个bomb enemy,我说上轮问过了(敲黑板!同学们如果碰到重复的题一定要提出来,否则HC是能够看到的)然后她换成了LC 298,followup是不用global variable怎么写。第二题是个蜜汁OOD设计,要求巨多。设计一个剧院的订座系统,user一次可以query不多于5个座位,然后这个系统要能return相应数量并尽可能相连的座位。接着用户可以选择订或不订这些位子:订的话这些位子就不available了;没订的话位子就都还available,但要求这位用户下次query还是return这些位子(防止用户不停刷系统以拿到他们想要的位子),除非下次query前这些位子里k个被别人订了,那系统再生成k个available的位子。搞清楚需求就花了半天,最后时间只给了个barely能work的框架,没时间优化。感觉要跪就跪这轮了…

第四轮:白人小哥,看起来就智商很高的那种。题目是给一瓶药,里面100颗完整的药片,每天需要吃半颗。每天吃的方法是随机从瓶子里取一颗药,如果是整颗就吃半颗,剩下半颗扔回瓶子里;如果取出的是半颗,那就直接吃掉。第一小问是simulate这个过程,然后print每天瓶中剩下的整颗和半颗的数量,直到空瓶。第二问是,求整个simulation过程中,瓶中剩下1整颗,0半颗的概率。最后问了running time。

除了印度姐姐全程冷漠脸以外其他面试官都很热情友好,交流得也很顺畅……一天下来感觉面试总体难度还行,并没有某些面经那么难(面之前看别人的面经真是吓得不轻……) 接下来默默等结果吧,也希望大家都能遇到原题,拿到心仪的offer!加油!!

. visit 1point3acres.com for more.

补充内容 (2016-10-18 02:03):-google 1point3acres
哇效率奇高,面完一周就告知我过HC了!希望大家也能早日收到好消息!

评分

6

查看全部评分

本帖被以下淘专辑推荐:

海盗包子 发表于 2016-10-18 09:26:31 | 显示全部楼层
网上看到了一个关于第四轮第二问的解法,http://www.feynmanlectures.info/solutions/half_pills_sol_3.pdf
主要是   leaving the bottle by considering w and h not as integer numbers of pills but as real-valued (mean) quantities of pills
回复 支持 1 反对 0

使用道具 举报

yxyxyx 发表于 2016-10-16 12:44:21 | 显示全部楼层
猫头鹰也是猫 发表于 2016-10-16 00:14
第一问应该没问题,但第二问还不大对,你看7那个例子

第二问做法和leetcode397很像:
对于当前的n如果n%2 == 0那就把n往右进一bit;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
如果n%2 != 0那么分两种情况:
如果n的最后两bit是3,那么就n+1;否则的话(最后两bit是1)那么就n-1;
最后就记录下n+1或n-1的次数就好

比如对于n=7的算法是:
7 (+1)-> 8 -> 4 -> 2 -> 1 (-1) -> 0

两次+1或-1,所以答案是2

7 (最后两bit是1) -> 6

补充内容 (2016-10-16 00:44):
忽视最后一行。。。。
回复 支持 1 反对 0

使用道具 举报

海盗包子 发表于 2016-10-20 04:04:10 | 显示全部楼层
robinbach 发表于 2016-10-19 20:23
第四题1/199 相当于200片药总共100对 吃到最后两片是一对的概率 200选2除以100选1 得1/199 要是这样想不通 ...
. From 1point 3acres bbs
不能这么想吧, 假设剩下1整片和1半片,这样取出一个半片的概率是1/2,
按照你的想法200个半片是等概率的,取出半片的概率是1/3,
所以必须编程simulation...
回复 支持 1 反对 0

使用道具 举报

yxyxyx 发表于 2016-10-16 22:50:55 | 显示全部楼层
wtcupup 发表于 2016-10-16 04:11
给一个iterator: 2,3,1,5,1,8… 要求写一个iterator要能return 3,3,5,8…  . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
why return 3,3,5,8 ?

意思应该是说第一个iterator的含义是2个3,1个5,1个8...
回复 支持 1 反对 0

使用道具 举报

magic95 发表于 2016-10-19 05:52:18 | 显示全部楼层
samuelling 发表于 2016-10-19 04:26
请问楼主,onsite之后recruiter多久会follow up和你说送hc啊,我昨天onsite之后给recruiter写了一封thank y ...

至少要等interviewer把feedback都提交给HR,以及等到下一个HC开会的日子才会送HC. 刚面完不着急啦~
回复 支持 1 反对 0

使用道具 举报

raychien 发表于 2016-10-17 02:16:47 | 显示全部楼层
yxyxyx 发表于 2016-10-16 23:35
不是啊,我的算法仍然是4啊
111,000,000,011 (+1) -> 111,000,000,100 (往右进两位)-> 001,110,000,001 ...

你的思路跟我挺像的,不過你用+1 -1來說明,我想很難讓大家看懂。這題的關鍵在於可以用+1把多個1,ˊ轉化成兩個1。假設你有一個數是111...1 (n個1),原本的表示法需要用n個2^x來表示,但是+1之後,數字變成了1000...0 (1個1後面帶n個0),只需要1個2^x表示,加上你要把多加的1 (2^0) 扣回去,所以原數字可以用兩個2^x表示。-1並不是很必要,反正right shift都會被吃掉。

思路: 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
一開始count = 0
看least significant bit
->是0忽略
->是1的話,count++,然後往左看有無連續1 (實際上看左邊一位就行)
    ->左邊是1,+1讓他進位
    ->左邊是0忽略
往右shift一個bit,重複上述步驟ˋ直到number變成0

實際上遇到1個1就count++,為什麼呢?假如這個1是單獨的,那麼我們必定要用一個2^x表示它。假如是連續的,那麼如上面所說,我們可以用+1進位後,用兩個2^x來表示,這邊count++是先算你多加的1 (2^0),另外一個1因為被你進位跑去左邊了,所以之後遇到他會是單獨的1,到時候你還是會算到他,所以總共是兩個1。
回复 支持 1 反对 0

使用道具 举报

jfree811 发表于 2016-10-16 11:43:34 | 显示全部楼层
话说google面试的时候能和中国面试官说中文吗?之前看别人写的帖子有提到直接中文交流。
回复 支持 反对

使用道具 举报

jfree811 发表于 2016-10-16 11:50:49 | 显示全部楼层
第一问是不是就是让你求二进制数上面 所以1的个数?然后follow up的解法是不是从二进制数从最右开始有多少个连续的1 比如39 = 100111 最后连续3个1 所以可以简化成 2^5 + 2^3 - 2^0
不知道这样思路对不对啊?lz求回答
回复 支持 反对

使用道具 举报

EmilyMMMM 发表于 2016-10-16 11:57:18 | 显示全部楼层
jfree811 发表于 2016-10-16 11:43
话说google面试的时候能和中国面试官说中文吗?之前看别人写的帖子有提到直接中文交流。

不可以跟中国面试官说中文。至少你不要主动说,主动说会显得很不professional。
回复 支持 反对

使用道具 举报

yxyxyx 发表于 2016-10-16 12:07:33 | 显示全部楼层
jfree811 发表于 2016-10-15 23:50
第一问是不是就是让你求二进制数上面 所以1的个数?然后follow up的解法是不是从二进制数从最右开始有多少 ...

是这个意思。其实从某个角度上这题和Leetcode397很像。
回复 支持 反对

使用道具 举报

chestnut9919 发表于 2016-10-16 12:11:48 | 显示全部楼层
jfree811 发表于 2016-10-16 11:50
第一问是不是就是让你求二进制数上面 所以1的个数?然后follow up的解法是不是从二进制数从最右开始有多少 ...

你好机智啊 膜拜大神
回复 支持 反对

使用道具 举报

 楼主| 猫头鹰也是猫 发表于 2016-10-16 12:14:46 | 显示全部楼层
jfree811 发表于 2016-10-16 11:50
第一问是不是就是让你求二进制数上面 所以1的个数?然后follow up的解法是不是从二进制数从最右开始有多少 ...

第一问应该没问题,但第二问还不大对,你看7那个例子
回复 支持 反对

使用道具 举报

jfree811 发表于 2016-10-16 12:31:55 | 显示全部楼层
猫头鹰也是猫 发表于 2016-10-16 12:14
第一问应该没问题,但第二问还不大对,你看7那个例子

7 = 111 所以连续三个1的话 就是 2^3 - 2^0  应该是对的吧?
回复 支持 反对

使用道具 举报

jfree811 发表于 2016-10-16 12:31:59 | 显示全部楼层
猫头鹰也是猫 发表于 2016-10-16 12:14
第一问应该没问题,但第二问还不大对,你看7那个例子

7 = 111 所以连续三个1的话 就是 2^3 - 2^0  应该是对的吧?
回复 支持 反对

使用道具 举报

chestnut9919 发表于 2016-10-16 12:33:28 | 显示全部楼层
求问楼主第四题用了什么方法?用什么数据结构存的药片?
回复 支持 反对

使用道具 举报

yxyxyx 发表于 2016-10-16 12:39:30 | 显示全部楼层
第四轮的第二问是说最后还剩一整片的概率是多大嘛?
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
补充内容 (2016-10-16 00:40):
如果是的话那概率就是1/199吧
回复 支持 反对

使用道具 举报

Hmoon 发表于 2016-10-16 12:49:45 | 显示全部楼层
yxyxyx 发表于 2016-10-16 12:07
是这个意思。其实从某个角度上这题和Leetcode397很像。

我的理解是followup是如果有连续三个1后者更多就加个1,这样进位导致1的减少大于加个1带来的个数

补充内容 (2016-10-16 12:51):
oops,没看到后面内容,理解是一样的
回复 支持 反对

使用道具 举报

jfree811 发表于 2016-10-16 12:57:22 | 显示全部楼层
yxyxyx 发表于 2016-10-16 12:44
第二问做法和leetcode397很像:.1point3acres缃
对于当前的n如果n%2 == 0那就把n往右进一bit;
如果n%2 != 0那么分两种 ...

赞呀!!!!
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-10-16 16:11:44 | 显示全部楼层
给一个iterator: 2,3,1,5,1,8… 要求写一个iterator要能return 3,3,5,8…  . 1point 3acres 璁哄潧
why return 3,3,5,8 ?
回复 支持 反对

使用道具 举报

mad_air 发表于 2016-10-16 17:44:35 | 显示全部楼层
楼主好运

请问第四题第二问那个概率怎么求的啊?是直接写算式还是写代码啊?
回复 支持 反对

使用道具 举报

knight0clk 发表于 2016-10-16 22:54:16 | 显示全部楼层
yxyxyx 发表于 2016-10-16 12:44. 1point3acres.com/bbs
第二问做法和leetcode397很像:
对于当前的n如果n%2 == 0那就把n往右进一bit;
如果n%2 != 0那么分两种 ...

这个题目的确和LC397很像,但是有区别。但是都是通过贪心算法解决。个人认为@Hmoon的解法很对的,直接了当。至于你说的这种方法,存疑,感觉只记录n+1, n-1次数不对。比如说111,000,000,011。对于这个 case,答案是4,但是如果只记录加减次数,结果是3
回复 支持 反对

使用道具 举报

knight0clk 发表于 2016-10-16 22:57:14 | 显示全部楼层
猫头鹰也是猫 发表于 2016-10-16 12:14
第一问应该没问题,但第二问还不大对,你看7那个例子

楼主,可以解释下为什么不对吗?我没有想明白,感觉是正确的
回复 支持 反对

使用道具 举报

 楼主| 猫头鹰也是猫 发表于 2016-10-16 22:57:15 | 显示全部楼层
yxyxyx 发表于 2016-10-16 12:39
第四轮的第二问是说最后还剩一整片的概率是多大嘛?

补充内容 (2016-10-16 00:40):

后来在坛子里搜了原来有这个题的面经,思路大致就是用dfs+memoization。传送门http://www.1point3acres.com/bbs/ ... 2BOnsite&page=1
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 11:07

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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