一亩三分地论坛

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

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

Google Onsite 10.13

[复制链接] |试试Instant~ |关注本帖
lordofone 发表于 2015-10-14 05:47:41 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 本科 全职@Google - 网上海投 - Onsite |Otherfresh grad应届毕业生

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

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

x
于是楼主蹭着goolge的网帮你们发面经. Waral 鍗氬鏈夋洿澶氭枃绔,

1. 老白1号,冲进来寒暄两句就说这是网络设计题(OOD)。。你听说过TCP和UDP?我表示略知一二。。然后说设计个firewall,给一个config表(装满了source 和target的map以及allow and deny),让我写个function,take一个source ip 和 port和 target port and ip, 能return 是否allow access。自己设计各种东西from scratch。说白了就是把config表变成一个hashtable,并且不需要写parser(parse config假设已经完成了)。然后follow up,如果config给的是 src ip-> dest ip以及 src ip range->dest ip range (比如126.115.0.*)的混合,你怎么判断一个request是否allow。这还扯到了什么ip mask之类的东西,反正我也不知道在说啥。。。反正我就不停的搞hashtable,各种map,然后各种假设有loop up function,比如给ip和set能知道是否ip在set里,给ip能知道对应set。。最后他居然表示很满意


2. 老白2号,多年刷题终于遇到原题了,上来 welcome to google变成google to welcome。。。果断写完,然后问我inplace咋搞,我偷懒说把input变成string array可好?他居然同意了。。那还做毛,直接换就行了,他表示不错,那如果给你char array呢,比如google变成[g,o,o,g,l,e],我表示sub出头单词和尾单词,中间recursion return,然后换位子 append就行。 他表示满意,问了一下复杂度和test case。然后出现了merge k sorted array(居然不是list?),欣喜若狂的我最终还是没能忍住。。piorityqueue拍脸秒杀。然后居然还有一题,说会不会多线程?然后提到blockingqueue里边的设计,比如如何唤醒blocking线程,我说用轮询flag,他表示能不能不用flag,我说signal。。他表示api是啥,我居然忘了。。wait/notifyall是答案。然后问我如果加一个timeout,你怎么知道是wait timeout继续运行了还是notifyall唤醒之后继续运行?我表示取时间差,如果和timeout一样就是timeout否则就是notifyall提前唤醒(口胡的)。然后他表示很对。。。


3. 中国人坑我。。上来就是题,给list of edge还原成tree(可能多个child,非balance,非bst),我用hashtable存<int,node>因为他给我的edge里边放的不是node,是unique int id。再建立一个hashtable存node与incoming edge数量。扫一遍edges,唯一一个没incoming edge的就是root。他居然没听懂。。表示我思想很吊,让我先code。然后别人都拍照,这哥们手打我的代码。。让我写formal每行,巨浪费之间。follow up是如果给你的edges不一定能form一个valid tree怎么办?我就说不valid一共三种,多个root,loop,一node多parent。然后我说我那个存incoming edges的table是不是碉堡了?然后我分别check三种情况,这时候出问题了。只看incoming edges还不够,如果1->2  3<->4这种tree,符合只有root没incoming edge但是这里有两颗树,所以应当找出所有node里的可能成为root的,以他做dfs,如果能访问到所有node(one head)且没有visit到已访问node(loop,two parent),那就可以了。。。时间到了,他说再给你5分钟,给爸爸写出DFS。。。你在逗我?


4.  吃饭遇到今天唯一一个三哥,人很nice一路聊天十分开心。还讨论了硅谷面试只考算法是否正确等等问题。然后被晒死了。。


5.   老白3号,给一个没sort的list, sort成 1<2>3<4>5....的形式。绝壁有这么一题,我绝壁没看解法orz。。只能说sort然后swap,还是nlgn。。然后果然要求写linear time,然后就嗝屁了,提示说顺序有毛关系,你写几个例子试试,恍然大悟,只要查看当前位要求然后和后边swap或者continue就行,swap上来也绝不会screw up之前的已经排好序的(要求说为什么,举个例子就行)。然后写代码,bug free。第二题说json的转换,给string转class,给class转string。最近学校作业才做过,写的一点问题没有。然后follow up说我要一个generalize的能用于所有class的这个方法,我说跪求得到class内部结构的API,不然写P?他说默认有了。。然后我说一共8个基本类型,重载8个,然后class一个,用你那个API,给每一个成员变量call对应的重载方法,parse我就不写了你看着办,结果append就行。他表示很好,路子很对,代码就不要你写了。. more info on 1point3acres.com
. From 1point 3acres bbs

综上,google果然天马行空。。然后本科绝壁比硕士,博士什么的简单。。前几天看你们的面经真是一题不会。然后十分注重基础和代码是否考虑的comprehensive。。。每个input必须check null,不然到时候被问到what‘s ur test case就呵呵了.

最后,如果没过,那绝壁是第三轮坑了。。剩下几轮不是strong也必须是good。。。吧,人生发挥最好一次面试 鏉ユ簮涓浜.涓夊垎鍦拌鍧.



补充内容 (2015-10-14 11:38):
最后一面我发现居然地理有面经。。那个sort叫做 wiggle sort
第二道叫做 java 序列化接口实现。。。面经地址 http://www.1point3acres.com/bbs/ ... =89355&do=index 这哥们的G家电面
. visit 1point3acres.com for more.
补充内容 (2015-10-15 10:09):
第三轮的代码。楼主飞机上写了一下,在25楼,22楼有大神用disjoint set的解法

评分

8

查看全部评分

本帖被以下淘专辑推荐:

怪兽岛 发表于 2015-10-22 01:31:07 | 显示全部楼层
say543 发表于 2015-10-21 14:58
可是union 的worst case 是o(n) 每一次的update 你worst 的union 就是o(n) 我不觉得有比较快~~?

恩, 1->2, 3->2的话也能判断是无效的啊~~ 因为作为子节点的2已经属于某个多于1个元素的并查集了,而不是自己(这个判断很快,就是看2->root是否是自己,因为初始化时2->root == 2)。也就是说:如果新加边的右侧的节点(即对应树的子节点)的root不为自己的话,那么这个树就是不合法的,直接返回false;

另外并查集的优势在频繁操作上绝对是有的。你说的worst case是O(n)是针对的啥都不优化的并查集,而其实并查集是可以优化的。刚从wiki上确认了一下,最终是能使union和find都到O(alpha(n)),而alpha函数增长极为缓慢,因此基本可以当做是O(1)了(wiki上说了当n很大时alpha(n)还是5)。

我前两周google电面时被问到另外一道并查集的题了,和这个有点像,不频繁操作时用dfs是比较方便的;但他的follow up就是如果频繁操作怎么办?我一开始没反应过来,后来他提示有一种特殊的data structure,我就知道是并查集了

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

leixiang5 发表于 2015-10-14 09:09:24 | 显示全部楼层
谢谢楼主分享。 祝楼主offer在路上
回复 支持 反对

使用道具 举报

aiweiwei 发表于 2015-10-14 09:26:57 | 显示全部楼层
楼主在mountain view面的吗
回复 支持 反对

使用道具 举报

aiweiwei 发表于 2015-10-14 09:29:19 | 显示全部楼层
忽略我的白痴问题。。。。。
回复 支持 反对

使用道具 举报

 楼主| lordofone 发表于 2015-10-14 09:29:32 | 显示全部楼层
aiweiwei 发表于 2015-10-14 09:26
楼主在mountain view面的吗

对啊。。明天回家咯
回复 支持 反对

使用道具 举报

 楼主| lordofone 发表于 2015-10-14 09:29:45 | 显示全部楼层
leixiang5 发表于 2015-10-14 09:09
谢谢楼主分享。 祝楼主offer在路上
. Waral 鍗氬鏈夋洿澶氭枃绔,
谢谢~~~
回复 支持 反对

使用道具 举报

aiweiwei 发表于 2015-10-14 09:59:17 | 显示全部楼层
lordofone 发表于 2015-10-14 09:29
对啊。。明天回家咯

你家在哪啊,飞很远去加州面试会影响状态和发挥吗?   对mountain view感觉怎么样啊?   我没去过加州,原谅我土~~   所以我很好奇知道呢. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

而且google给报销几天呢,比如能不能早一两天到那边倒倒时差再面试
回复 支持 反对

使用道具 举报

 楼主| lordofone 发表于 2015-10-14 10:01:56 | 显示全部楼层
aiweiwei 发表于 2015-10-14 09:59.1point3acres缃
你家在哪啊,飞很远去加州面试会影响状态和发挥吗?   对mountain view感觉怎么样啊?   我没去过加州, ...

芝加哥飞的。。没啥感觉,有offer垫着,面的十分淡定。天气极热,环境极好,午餐一坨色拉。提前一天早上飞,下午到,早点睡
回复 支持 反对

使用道具 举报

nothingtrouble 发表于 2015-10-14 10:08:02 | 显示全部楼层
lz答得不错,估计offer马上有了!~~问一句,list of edges建树,是有向图吗?如果是,topological sort应该就可以了,然后看看最后看看visited node数目是不是等于总定点数。如果是无向图edge,那就比较麻烦了,也就是说edge (a,b)也可表示b是a的parent
回复 支持 反对

使用道具 举报

 楼主| lordofone 发表于 2015-10-14 10:11:36 | 显示全部楼层
nothingtrouble 发表于 2015-10-14 10:08
lz答得不错,估计offer马上有了!~~问一句,list of edges建树,是有向图吗?如果是,topological sort应 ...

那必须是有向的,edge(b,a)就是说b是a的parent,a是b的child。然后topological sort这词昨天晚上才知道。。这玩意儿干嘛的,求详解。我这题的解法并不是他期望的,只不过居然能用而且复杂度还可以
回复 支持 反对

使用道具 举报

aiweiwei 发表于 2015-10-14 10:22:02 | 显示全部楼层
请问楼主其他offer是哪些,给多长时间decide呢
回复 支持 反对

使用道具 举报

 楼主| lordofone 发表于 2015-10-14 10:23:01 | 显示全部楼层
aiweiwei 发表于 2015-10-14 10:22
请问楼主其他offer是哪些,给多长时间decide呢

下周due。。。offer我就不说了,太伤感,new grad每人鸟啊
回复 支持 反对

使用道具 举报

say543 发表于 2015-10-14 14:24:32 | 显示全部楼层
lordofone 发表于 2015-10-14 10:23
下周due。。。offer我就不说了,太伤感,new grad每人鸟啊
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
LZ最后一题的 json 转换能说说吗? 需要考虑到什么serialize or deserialize吗?
回复 支持 反对

使用道具 举报

say543 发表于 2015-10-14 14:26:58 | 显示全部楼层
LZ 还原tree那题如果只能有一棵树那不是可能有一个root吗? 怎么可能会有多个roots ?
回复 支持 反对

使用道具 举报

say543 发表于 2015-10-14 14:27:37 | 显示全部楼层
LZ 还原tree那题如果只能有一棵树那不是可能有一个root吗? 怎么可能会有多个roots ?
回复 支持 反对

使用道具 举报

宝贝忆彼岸 发表于 2015-10-14 22:17:59 | 显示全部楼层
LZ好厉害,感觉offer妥妥的,请问能否再详细说一下第一题,主要是考OOD还是考算法?config表是一个map吗还是什么数据结构?最后一题的序列化lz还有代码么?一直没动这种题
回复 支持 反对

使用道具 举报

 楼主| lordofone 发表于 2015-10-14 22:52:23 | 显示全部楼层
say543 发表于 2015-10-14 14:24
LZ最后一题的 json 转换能说说吗? 需要考虑到什么serialize or deserialize吗?
.鏈枃鍘熷垱鑷1point3acres璁哄潧
额就是oracle那个simplejsonobject.jar包干的事情。。把json string变成对应的class,反之把class内部的数据结构变成json string。所谓考虑什么,一上来写的是一个class对应一个特有的serialize(),直接hard code就行,这里看看code能力和corner cases(后边说)。不过他希望的是一个通用于所有class的。然后就说提供一个能遍历所有内部数据结构的东西,比如有int a;sting b; char c; Class d;那么提供的东西能从a到d一个个return我。那这样就可以拿一个serialize一个,然后一共8种基本类型,再加struct和class俩个自带serialize的家伙,那么拿一个我call对应的重载后的serialize function就行了。。至于反序列化,那就烦了,牵扯到regex已经substring matching等等细节。json string他说是根据空格分隔的,但要考虑 string variable自带空格的corner case,我就说regex 判断是不是内部空格还是json 空格。遇到{找对应},截取出来 recursive call,这样return 对应 object (这里也有corner case,{} 也可能是string内部的,但我们都没管这东西,管起来太烦)。大概就是这样,他觉得很满意,但我觉得真正coding起来要能达到jar那样绝对很烦

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| lordofone 发表于 2015-10-14 22:53:53 | 显示全部楼层
say543 发表于 2015-10-14 14:26
LZ 还原tree那题如果只能有一棵树那不是可能有一个root吗? 怎么可能会有多个roots ?

这是followup问的,给的list of edges本来一定能确定一颗valid树,但是followup里不一定了。要我判断,如果能生成一棵树,return root;else return null;比如给你个edges (5,2);(2,1);(2,5)就爆炸了
回复 支持 反对

使用道具 举报

 楼主| lordofone 发表于 2015-10-14 22:57:56 | 显示全部楼层
宝贝忆彼岸 发表于 2015-10-14 22:17
LZ好厉害,感觉offer妥妥的,请问能否再详细说一下第一题,主要是考OOD还是考算法?config表是一个map吗还 ...

根本就没算法在这里边。。纯粹的OOD,config可以是任何东西(我提出txt,准备IO),但是他不care,他表示有人parse,你的input随你喜欢。最后达成共识,搞一个rule数据结构表示其中每一行。rule自带5个variable,src port,ip;dest port,ip;pass_or_deny; 然后加入hashtable就行了。

至于说最后一题,我纯粹hard code,然后讲思想。。你要NB代码去网上找个jsonobject.jar看代码吧,课上允许使用这种jar。。

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

怪兽岛 发表于 2015-10-15 05:44:17 | 显示全部楼层
你说的第5轮面试那个sort是leetcode原题。Wiggle Sort。确实不难,在leetcode里通过率44%。。。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 14:58

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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