10月28,K神开课讲数据科学,你来吗?


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
Babeltime游戏工作室招工程师、美术和策划
Tubi TV招安卓、前端和机器学习工程师
把贵司招聘信息放这里
查看: 5045|回复: 56
收起左侧

Google 2015-10-2 MTV 另求教

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

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

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

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。
. From 1point 3acres bbs
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他就直接说出来,不给让我自己发现的机会。基本期望你写出来就必须是对的。唯一的国人,不但没有帮忙,反而上来就刁难。 为啥别人面试遇到中国人,感觉都比较和蔼可亲呢?好郁闷啊~~

这个肯定挂了。。。

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分钟,而且还有一些口头描述。我就不写了。不难,只要你基本概率知识知道,就能算出来。

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


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

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

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.

4. Use a queue to keep track of input sequence and a sum variable to maintain the whole
-google 1point3acres
5. Details see all kinds of different solution in leetcode discussion.

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?

. visit 1point3acres.com for more.

补充内容 (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,  ...
. 鍥磋鎴戜滑@1point 3 acres
找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。. more info on 1point3acres.com

这样的话,可以省掉一次检查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):. 1point3acres.com/bbs
我们new grad 直接onsite也是4轮
回复 支持 反对

使用道具 举报

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

我觉得面试官或多或少在只写code的时候会发呆怎么的吧,楼主如果是边写边说的话。。。是不是当时沉默太久没交流了。
回复 支持 反对

使用道具 举报

kelvinzhong 发表于 2015-10-3 10:56:55 | 显示全部楼层
a341265353 发表于 2015-10-3 10:42
有过两个面试官也全程严肃,面的时候心惊肉跳。。。但是最后还是给了好的feedback。这个面试官至少给了提示 ...
. Waral 鍗氬鏈夋洿澶氭枃绔,
层主是怎么知道哪个面试官给了什么样的feedback的呢?~我也想知道我得到什么样的feedback
回复 支持 反对

使用道具 举报

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

使用道具 举报

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

另外,中国人的那道题我觉得应该是用鸽笼原理做,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
. From 1point 3acres bbs
哦,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说吧。。

补充内容 (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. from: 1point3acres.com/bbs
层主是怎么知道哪个面试官给了什么样的feedback的呢?~我也想知道我得到什么样的feedback

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

使用道具 举报

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

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

使用道具 举报

 楼主| guzi 发表于 2015-10-4 01:23:40 | 显示全部楼层
nothingtrouble 发表于 2015-10-3 11:38
bless,不要太担心了,一面不好,还有其他的呢。lz你行的!. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

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

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

使用道具 举报

 楼主| guzi 发表于 2015-10-4 01:24:21 | 显示全部楼层
flyaway25 发表于 2015-10-3 12:00
我当时去google面onsite的时候也遇到这种中国人,题目明显没有事前准备,出得很不清楚,跟他confirm的时候 ...

你跟HR报告了么?你结果怎么样?
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-9-20 15:45

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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