一亩三分地论坛

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

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

Google 2015-10-2 MTV 另求教

[复制链接] |试试Instant~ |关注本帖
guzi 发表于 2015-10-3 09:51:36 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Google - 猎头 - Onsite |Other在职跳槽

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

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

x
1. 印度人, 先问background
Question1:  Given two algorithms say A and B that solves the same problem, the time complexity of A is O(n) but B is O(logn), is there any reason you would pick A rather than B.

Question2: Given a list of boarding passes, each boarding pass contains two cities, say A-B, generate travel itinerary.  

写了整个code,整体表现感觉还可以。

2. 美国人, 先问background
Question3: Implement hasNext() and next() for an iterator, which takes an array such as [4,3,5,0,2,1] and its output should be [4,4,4,2]. Notice that a number with odd index is the number of items before it. 三个4, 零个5,一个2。

Question 4: moving range average. Given an input array,always output the average of k item, known as window size.

第二题没时间实现了,说了一下基本想法。他表示比较满意,临走前说了个well done。也不知道是客气,还是真的。在实现iterator的时候,有个地方纠结了半天。

3. 美国人,问了background, sort, binary search之类的time complexity
Question5: Another iterator problem. leetcode原题,Zigzag iterator but k iterators.
整体感觉还可以。

4. 中国人
Question6: Given a sorted input array, write an O(lgN) algorithm to find if there is a number has appears more than 1/4 times.

这个人进来的时候就一脸愁容, 而且特别严肃。看一眼就让人比较紧张。没有问background, 没有自我介绍,直接上题。本来以为可以套用find majority算法,结果一上来就说明要O(lgN) 算法。想了半天都没想出来,他就把问题简化成appears more than 1/2 times. 一开始觉得有思路了,但是写起来很多实际问题要处理。我在思考的时候,他就在玩手机(估计已经绝望了),好像还接了个电话(光顾想题了,没太注意,但是感觉他好像跟别人说话,absolutely not me),我可是边想边说的,真是无语。过了一会看我没想出来他期望的算法,直接告我算法,然后让我实现。其实算法不是特别难,但不知道为啥自己当时就没想出来,估计是一上来的1/4花了好久没想出来,加上他的愁眉苦脸,就越来越紧张。实现他给的算法的时候,有bug他就直接说出来,不给让我自己发现的机会。基本期望你写出来就必须是对的。唯一的国人,不但没有帮忙,反而上来就刁难。 为啥别人面试遇到中国人,感觉都比较和蔼可亲呢?好郁闷啊~~
. more info on 1point3acres.com
这个肯定挂了。。。

5. 美国人
Question 7:  rotate a pixel picture by 90 degree. Note, it is a little easy to make mistake, because x is column, y is row. 当时写index的时候就搞错了。

一开始思路错了,矫正了两次。后来问了各种关于image处理的问题,问我除了rotate, photoshop等图像处理软件menu上还有什么类似的操作。。。N年没用PS了,根本不知道啊。我就开始各种猜,提亮啊,扭曲,图像叠加,连delete picture都说了(对自己也是无语了,当时说出来的时候,自己都笑了,哈哈)。期望答案见下面solution sectoin.

Question 8: 一道概率题,基本就是数学题。题特别长,他写题就写了5-10分钟,而且还有一些口头描述。我就不写了。不难,只要你基本概率知识知道,就能算出来。

最后一面超时了好多,可能是因为最后一题比较长的缘故。因为中间他矫正了两次,不知道会不会影响,倒是对我在概率题的表现还比较满意。


总结一下:面试一个接一个过得好快,面完以后我以为只面了四个人。。。不知道为啥。。。第五个人进来说他是最后一个,我还说后面还有一个呢。大部分题不是特别难。 感觉在挂和不挂的边缘。。。那个中国同胞!!!哎~  ╮(╯▽╰)╭

PS: 见地里很多人都是四面,我是五面,可能因为是direct onsite. 至于direct onsite原因,至今不明,本来电面都约好了,电面前一周告我不用面了,直接来吧。顿时有一种走了狗屎运的感觉。
.鏈枃鍘熷垱鑷1point3acres璁哄潧

Solutions/Idea:
1. 各种brain storm for example, balance space with time.

2. Typical topology sort.

3. Idea: use a counter and cur variable to keep track of current information.
. more info on 1point3acres.com
4. Use a queue to keep track of input sequence and a sum variable to maintain the whole

5. Details see all kinds of different solution in leetcode discussion.
.1point3acres缃
6. Binary search. Say value of current mid is k, search first appearance index of k on left and last index of mid element on right. The number of times k appears is rightIndex-leftIndex+1.

7. 常见rotate question. build a mapping function between old index and new index. CC 和leetcode上好像都有


求问: 像那个中国人这种情况,要告知recruiter 么?感觉打小报告不太好,但是如果真是因为他本人的原因挂了,只能认倒霉了么?不过也是我不够优秀,如果一开始就刷刷刷把他的问题答出来,他估计会more engaged?



补充内容 (2015-10-5 07:18):
看在是当天报面经,而且比较详细,给点米吧。。。

评分

7

查看全部评分

本帖被以下淘专辑推荐:

 楼主| guzi 发表于 2015-10-9 10:59:40 | 显示全部楼层
第三题很多人没看懂,解释一下:index为偶数的是值,会出现在结果中,就是你call next()时有可能输出,index为奇数的是它前面那个数出现的次数。不知道说清楚了没。。
回复 支持 1 反对 0

使用道具 举报

sevensevens 发表于 2015-10-9 02:58:38 | 显示全部楼层
airwindow 发表于 2015-10-7 08:35
受四楼启发...
我觉得Question6可以这么来做:
假设数组的size为len,a = len / 8;分别检测以下9个坐标 ...

确实是这么做
回复 支持 0 反对 1

使用道具 举报

stellari 发表于 2015-10-3 16:44:51 | 显示全部楼层
LawranceH 发表于 2015-10-3 12:24
求问下中国人那题的解法, Question6。 我自己想到个解法不知道对不对。 比如Given a sorted input array,  ...

找1/2majority的话,其实没必要移整个范围。可以先取得a[(size-1)/2] == midval的值,如果1/2majority存在,那么必定是midval。理由是,大于和小于midval的数最多也只有(size-1)/2个,所以除midval以外,其他数都不可能是1/2majority。然后在数组左半二分找midval开始的位置begin,在数组右半找midval结束的位置end。如果(end-begin + 1) > sizel/2, 那么midval就是1/2maj,否则就没有1/2maj。

这样的话,可以省掉一次检查4个点的麻烦。

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

头像被屏蔽
bitware 发表于 2015-10-3 16:06:27 来自手机 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 1 反对 0

使用道具 举报

kelvinzhong 发表于 2015-10-3 10:07:47 | 显示全部楼层
楼主怎么五轮面试?是因为不是new grad多加了一轮? 我觉得这个..没法跟hr说吧。。

补充内容 (2015-10-3 10:08):
我们new grad 直接onsite也是4轮
回复 支持 反对

使用道具 举报

a341265353 发表于 2015-10-3 10:42:56 | 显示全部楼层
有过两个面试官也全程严肃,面的时候心惊肉跳。。。但是最后还是给了好的feedback。这个面试官至少给了提示。
. from: 1point3acres.com/bbs
我觉得面试官或多或少在只写code的时候会发呆怎么的吧,楼主如果是边写边说的话。。。是不是当时沉默太久没交流了。
回复 支持 反对

使用道具 举报

kelvinzhong 发表于 2015-10-3 10:56:55 | 显示全部楼层
a341265353 发表于 2015-10-3 10:42
有过两个面试官也全程严肃,面的时候心惊肉跳。。。但是最后还是给了好的feedback。这个面试官至少给了提示 ...
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
层主是怎么知道哪个面试官给了什么样的feedback的呢?~我也想知道我得到什么样的feedback
回复 支持 反对

使用道具 举报

sevensevens 发表于 2015-10-3 11:00:47 | 显示全部楼层
请问楼主 第二题的问题到底是啥呀 要写hasNext() 和next()么?那为啥会有那样的输入输出?谢谢!
回复 支持 反对

使用道具 举报

nothingtrouble 发表于 2015-10-3 11:38:16 | 显示全部楼层
bless,不要太担心了,一面不好,还有其他的呢。lz你行的!.1point3acres缃

另外,中国人的那道题我觉得应该是用鸽笼原理做,split array into 4 parts, 重复元素在每一个part的头尾,或者是相邻part的尾或者头。
回复 支持 反对

使用道具 举报

flyaway25 发表于 2015-10-3 12:00:51 | 显示全部楼层
我当时去google面onsite的时候也遇到这种中国人,题目明显没有事前准备,出得很不清楚,跟他confirm的时候发现他又往里面加了好多东西,花了30分钟才搞明白他要我干的事,后来面着面着就出去打电话了,内容还是非工作的都是家里面的事。如果要反应就尽早,不要等到HC出结果后反应这个情况。
回复 支持 反对

使用道具 举报

a341265353 发表于 2015-10-3 12:01:43 | 显示全部楼层
kelvinzhong 发表于 2015-10-3 10:56
层主是怎么知道哪个面试官给了什么样的feedback的呢?~我也想知道我得到什么样的feedback

哦,hr说给的feedback是好的
回复 支持 反对

使用道具 举报

Yunying 发表于 2015-10-3 12:02:41 | 显示全部楼层
中国人那道是我Google电面时候做的题。。。。
回复 支持 反对

使用道具 举报

blactangeri 发表于 2015-10-3 12:03:54 | 显示全部楼层
回复 支持 反对

使用道具 举报

LawranceH 发表于 2015-10-3 12:24:13 | 显示全部楼层
求问下中国人那题的解法, Question6。 我自己想到个解法不知道对不对。 比如Given a sorted input array, write an O(lgN) algorithm to find if there is a number has appears more than 1/2 times, 如果找1/2 的话, 我们把1/2 的这个区间在0到n 上面平移,那么不管怎么分布, 检测 0, 1/4,2/4,3/4,4/4. 这4个点的值, 如果其中有2个点相等的话,那么就存在 有个数出现超过1/2 次。 这样类推到找数超过1/4 就检测0,1/8,2/8 .....到8/8 。
回复 支持 反对

使用道具 举报

头像被屏蔽
bitware 发表于 2015-10-3 16:07:01 来自手机 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

 楼主| guzi 发表于 2015-10-4 01:04:44 | 显示全部楼层
kelvinzhong 发表于 2015-10-3 10:07
楼主怎么五轮面试?是因为不是new grad多加了一轮? 我觉得这个..没法跟hr说吧。。. more info on 1point3acres.com

补充内容 (2015-10-3 1 ...

我不知道为什么
回复 支持 反对

使用道具 举报

 楼主| guzi 发表于 2015-10-4 01:09:59 | 显示全部楼层
a341265353 发表于 2015-10-3 10:42
有过两个面试官也全程严肃,面的时候心惊肉跳。。。但是最后还是给了好的feedback。这个面试官至少给了提示 ...

我是全程都在讲话,连思考的时候也在讲。他并没有给我任何提示,而是见我一直没想出来,就直接告我算法了。如果他稍微提示一下,我是可以做出来的。其实这道题并不是特别难。
回复 支持 反对

使用道具 举报

 楼主| guzi 发表于 2015-10-4 01:10:23 | 显示全部楼层
kelvinzhong 发表于 2015-10-3 10:56
层主是怎么知道哪个面试官给了什么样的feedback的呢?~我也想知道我得到什么样的feedback

你什么时候面的
回复 支持 反对

使用道具 举报

 楼主| guzi 发表于 2015-10-4 01:23:08 | 显示全部楼层
sevensevens 发表于 2015-10-3 11:00. From 1point 3acres bbs
请问楼主 第二题的问题到底是啥呀 要写hasNext() 和next()么?那为啥会有那样的输入输出?谢谢!

是实现hasNext() 和next(). 结果是call next() 时的结果
回复 支持 反对

使用道具 举报

 楼主| guzi 发表于 2015-10-4 01:23:40 | 显示全部楼层
nothingtrouble 发表于 2015-10-3 11:38-google 1point3acres
bless,不要太担心了,一面不好,还有其他的呢。lz你行的!

另外,中国人的那道题我觉得应该是用鸽笼原理 ...

谢谢安慰!也祝你早日拿到dream offer
回复 支持 反对

使用道具 举报

 楼主| guzi 发表于 2015-10-4 01:24:21 | 显示全部楼层
flyaway25 发表于 2015-10-3 12:00
我当时去google面onsite的时候也遇到这种中国人,题目明显没有事前准备,出得很不清楚,跟他confirm的时候 ...
. more info on 1point3acres.com
你跟HR报告了么?你结果怎么样?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 08:11

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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