一亩三分地论坛

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

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

Youtube onsite 面经

[复制链接] |试试Instant~ |关注本帖
milanelllo13 发表于 2015-8-9 01:02:16 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 硕士 全职@Google - 网上海投 - Onsite |Otherfresh grad应届毕业生

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

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

x
一共面了五轮。。从中午带吃饭的小哥处打听到面五轮是因为没有内推海投的(供参考,不一定对!)!. more info on 1point3acres.com

第一轮:亚裔(听名字不像中国人?)   一堆人参加比赛,最开始谁和谁先比是确定的,比赛是两两配对,一轮一轮进行,print出若有round和可能的组合。比如 有 ABCD四个人比赛, 那结果是:
1  A - B.1point3acres缃
1  C - D
2  A - C
2  A - D
2  B - C
2  B - D. more info on 1point3acres.com

但是要考虑一个情况,就是有五个人比赛,比如 ABCDE五个人, 那么E这个人可能是在C和D比完后和他俩的胜者比,或者E 和 AB的胜者比。或者E 和 ABCD的胜者比。
问题:1.用什么数据结构存比赛者。 就说二叉树就行了,把比赛者存在叶子节点,怎么构成不需要你考虑。
          2. print出结果(应该就是postorder traversal了)

第二轮:1. largest substring with at most M distinct characters,但是输入的string是以stream的形式;    2: word abbreviation那题,给个字典,判断有没有和输入的词的abbreviation相同的词。
第三轮: 这轮不想提起,,我也不是很明白题目是啥。。没听懂。。。
第四轮:给了一个双链表,在给一个list,list里面装的是双链表里面的某些node,面试官说可以通过list里面的node直接访问双链表里面的node。  然后根据list,求双链表中有多少个components。
example:  A-B-C-D-E.  list:[A E D]  那么就有两个components: A 和 D - E
第五轮: 给了N个城市,和N-1条road,且这些road可保证城市间均两两互通。 比如 SF--SD--LA , 每个road都有长度,求所有两两之间的path的和,然后除以所有的path数得到平均值。。。(也就是: SF到SD + SF到LA+ SD到LA 再除以3)。  当时有点晕。。写了个brute force = = 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

下周要host match。。   
请问有经验的小伙伴们match上的几率高吗。。求好运!!!

评分

3

查看全部评分

本帖被以下淘专辑推荐:

stellari 发表于 2015-8-11 19:33:28 | 显示全部楼层
最后一道题我想可以这样:. Waral 鍗氬鏈夋洿澶氭枃绔,

1 先求出每个城市的“连接度”,即有多少个城市和当前城市相连。
2 把连接度==1的城市看作是 叶节点。和叶节点相邻的节点看作是第二层, 和第二层相邻的是第三层,以此类推,直到最内层的节点即为根节点。

  1. 如  A -- B -- C -- D
  2.                  |
  3.                  E   
复制代码
这种情况,A, D, E为叶节点,B或C为根节点。

3 在每个节点处储存以其为根的子树中的节点数目。如上例中,A,D,E的子树就是自身,所以节点数为1;
选C做根节点的话,B的子节点数为2(A和B),C的子节点数为5。

4 从叶节点开始,逐层删除节点和其与之父节点相邻的路径。如果一个节点的子节点数目为k,那么有下列规律:

每一个节点与其父节点的路径被走过的次数 = K * (N - K)

. 1point 3acres 璁哄潧
这条结论我没有严格证明,但应该是正确的。

这样每删除一条路径,就能在O(1)时间内知道其总共被走了多少次。最后取sum(路径走过的次数 x 路径长度)/ 路径总数即得答案。时间复杂度为O(N)

如上例
先删除叶节点A D E,可知,路径AB,DC,EC均被走了1* (5-1) = 4次. 1point3acres.com/bbs
再删除第二层节点B,因其子节点数目为2,可知路径BC被走了2 * (5-2) = 6次。

补充内容 (2015-8-11 19:34):
E节点是直接连到C上的,抱歉排版时有些错位了。

评分

1

查看全部评分

回复 支持 6 反对 0

使用道具 举报

iverson1122 发表于 2015-8-13 05:41:52 | 显示全部楼层
最后一道题某一条路径被走的次数其实就是断开这条路径左边城市数*右边城市数吧。楼上的方法挺好的…
回复 支持 1 反对 0

使用道具 举报

agneshanlu 发表于 2015-8-9 01:14:14 | 显示全部楼层
给楼主点赞!请问有电话面试的面经吗?可以分享一下吗?
回复 支持 反对

使用道具 举报

 楼主| milanelllo13 发表于 2015-8-9 01:16:33 | 显示全部楼层
agneshanlu 发表于 2015-8-9 01:14. 1point3acres.com/bbs
给楼主点赞!请问有电话面试的面经吗?可以分享一下吗?

谢谢!!. from: 1point3acres.com/bbs
http://www.1point3acres.com/bbs/thread-136675-1-1.html  
回复 支持 反对

使用道具 举报

danchou 发表于 2015-8-9 10:36:44 | 显示全部楼层
楼主能把第一题详细说一下吗?多谢!!!
回复 支持 反对

使用道具 举报

jasusy 发表于 2015-8-11 10:53:10 | 显示全部楼层
congs! 第一题有点晕,楼主能更细的解释一下吗?楼主是怎么做的?
回复 支持 反对

使用道具 举报

zxy_snow 发表于 2015-8-11 14:34:02 | 显示全部楼层
第一轮:输出所有组合这个要怎么输出。。。比如E和AB的胜者或者E和ABCD胜者比
回复 支持 反对

使用道具 举报

qjx026 发表于 2015-8-13 10:18:04 | 显示全部楼层
stellari 发表于 2015-8-11 19:33
最后一道题我想可以这样:

1 先求出每个城市的“连接度”,即有多少个城市和当前城市相连。

感觉你的思路很好。
这道题, N 个结点, N-1 个path 而且两两互通。
我感觉就是一个 无环的连通图的遍历, 用BFS遍历就可以解决了。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
不知道我是否想的过于简单了
回复 支持 反对

使用道具 举报

bluestarwing 发表于 2015-8-13 10:51:08 | 显示全部楼层
请教lz,google和youtube是一个系统吗?有冷冻期么?比如YouTube挂了还可以投Google吗
回复 支持 反对

使用道具 举报

 楼主| milanelllo13 发表于 2015-8-14 03:37:58 来自手机 | 显示全部楼层
bluestarwing 发表于 2015-8-13 10:51
请教lz,google和youtube是一个系统吗?有冷冻期么?比如YouTube挂了还可以投Google吗

我觉得是一个系统。你可以试试。也没有损失。
回复 支持 反对

使用道具 举报

djjkobe 发表于 2015-11-2 14:45:22 | 显示全部楼层
第一题能否详细说一下?
回复 支持 反对

使用道具 举报

bensvage1989 发表于 2015-11-3 00:03:05 | 显示全部楼层
stellari 发表于 2015-8-11 19:33
最后一道题我想可以这样:

1 先求出每个城市的“连接度”,即有多少个城市和当前城市相连。

求问所有path数应该怎么求呢?
回复 支持 反对

使用道具 举报

sonicgu 发表于 2015-11-18 11:17:22 | 显示全部楼层
第一题不太明白,楼主可以详细说下思路嘛,为什么用后续遍历就可以输出结果呢,谢谢
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-12-6 11:28:38 | 显示全部楼层
请问第一题是要先建树吗,然后再遍历打印吗?
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-12-6 13:26:58 | 显示全部楼层
stellari 发表于 2015-8-11 19:33
最后一道题我想可以这样:

1 先求出每个城市的“连接度”,即有多少个城市和当前城市相连。

可以具体分享下代码吗?
回复 支持 反对

使用道具 举报

xiaoniuona 发表于 2015-12-8 02:39:06 | 显示全部楼层
请问楼主第二题那个如果是stream的要怎么做呢?
回复 支持 反对

使用道具 举报

wildchild 发表于 2015-12-10 12:24:21 | 显示全部楼层
可以请问下lz电面是什么题目么?

下周电面,网上搜到的都是onsite的题目……
回复 支持 反对

使用道具 举报

xiaoniuona 发表于 2015-12-12 07:39:55 | 显示全部楼层
第四轮是要用dfs嚒?就是list里每个node在双链表里找它的prev和next node,如果也在list里就继续dfs下去,这样行么?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 21:09

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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