一亩三分地论坛

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

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

11/09 Google/Youtube onsite 面经

[复制链接] |试试Instant~ |关注本帖
yourway 发表于 2015-11-19 10:20:24 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 博士 全职@Google - 内推 - Onsite |Otherfresh grad应届毕业生

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

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

x
11/09 MTV onsite 的面经。
. more info on 1point3acres.com
第一轮,有人shadow
http://rosettacode.org/wiki/Maximum_triangle_path_sum

然后一个小印带我去吃午饭. From 1point 3acres bbs

第二轮,
先问了我 youtube 如果产生向用户推荐的视频列表。 我说了当前播放视频的{标题,内容,介绍},该用户的观看记录,观看了该视频的其他用户的观看记录,已及该用户的 IP 地址类型(家庭用户或企业用户)。又问如果是一个新用户怎么办,我就说可以随机推荐当前最热门的视频。似乎这不是他满意的答案,他提示说如果用户是从 facebook 中点击视频连接进来的呢?我就说那就可以获得该用户的社交网络信息,根据他的爱好来推荐视频。. From 1point 3acres bbs

然后就做题,字符串匹配,“.” 代表一个任意字符, “*” 代表0个或者多个任意字符。
例如 youtube.鏈枃鍘熷垱鑷1point3acres璁哄潧
y.u.u.e --> true
you*be --> true
you.. --> false
*u*u* --> true

第三轮,
小哥自我介绍他们组是根据用户播放的 MV 推荐相关 MV 播放列表。我说我知道这个功能,我很喜欢。
然后问我如何从 Youtube 的视频列表中找到圣诞相关的歌曲。我就先说哪些信息可以提取出来做特征来训练分类器,基本上跟上一轮说的差不多。
然后问如何选择training data
然后又问如果圣诞歌曲在所有的 MV 中所占的比例特别小怎么办,小于 1% 甚至 0.1%. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

然后聊了一下我的 thesis。最后剩的时间不多了,就让我实现了一下 sparse matrix 类。我说用 hash table 来保存非零元素,用 truple (x,y) 做 key。然后让我实现两个 matrix 相加的算法。做完以后,他提醒我如果 M1(x,y) = -M2(x,y) 怎么办。我发现如果 M[(x, y)] == 0 的话,应该将该元素从 hash table 中删除。

第四轮,
白人大叔一进来就看了看面试记录,说我先看看别人都问了什么问题,我别问重了。如何找圣诞歌曲,有意思。
然后说他的问题是开放性的。有一个图,图中每一个节点的label是一个整数,找到最长的连续整数序列的长度。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
例如 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  1
   \
. From 1point 3acres bbs 2- 3
\ /
  4
  |
  5-8
  |/
  7

最长连续数列是 2-3-4-5,就返回4(结点个数)或者3(边的个数)都行。

我就说先取出结点列表,然后对结点列表进行排序, 从最小的结点开始做 DFS 找到最长路径。他说好,开始 coding.
我就写了一个 recursive DFS。
问:如果图特别大这段代码会有什么问题么?
答:recursive 函数的调用次数有限制,如果路径的长度大于次数限制就会失败。我说也可以用 iterative DFS 来解决问题。

问:如果图特别大,超出了一台电脑的内存限制怎么办?
答:把图分成多个小图,分别计算再合并,例如上图中的 4-5 节点切断就可以将图分开。

问:如果3-8之间有 edge, 如果找到最合适的分割点?
答:先将图中无效的边都去掉,例如 1-3, 2-4, 3-8, 5-7, 5-8。将图简化后就容易找到分割点了。
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
问:如果这些子图在不同的服务器上分布,如果解决
答:每一台服务器分别计算自己图中所有的连续区间。另外一台电脑逐个询问这些服务器,对可以合并的区间进行合并,找到最长的区间。

问:如果有 n 台服务器,这个合并的时间复杂度是多少
答:O(n)

问:能不能优化?.鏈枃鍘熷垱鑷1point3acres璁哄潧
答:可以每两个服务器先合并自己的区间,这样做的时间复杂度是 O(logn)

问:如何配对两台将要合并区间的服务器?
答:按每台服务器上的最大区间的起始数字对服务器进行排序,选择相邻的区间进行合并。

问:为什么这么做?
答:凭直觉,每台服务器上的最大的区间更有可能是总区间的一份子。. from: 1point3acres.com/bbs


第五轮:
计算可能的 Android 解锁图案的个数。
限制条件: . 鍥磋鎴戜滑@1point 3 acres
i) 3x3 共九个点
ii) 最短图案包含 4 个点
iii) 最长图案包含 9 个点. 1point 3acres 璁哄潧
iv) 路径不得跨越未访问的点,但是可以跨越访问过的点. 1point3acres.com/bbs
例如, 0-2-6-8 就不合法(0-2 跨越了 1, 2-6 跨越 4, 6-8跨越了7)
0-1-2-4-6-7-8 或者 7-4-1-0-2-6-8 是合法的

0 1 2
3 4 5
6 7 8
. From 1point 3acres bbs

评分

2

查看全部评分

本帖被以下淘专辑推荐:

wxr.dal 发表于 2015-11-19 10:30:03 | 显示全部楼层
问一下lz,shadow是什么啊
回复 支持 反对

使用道具 举报

queeniejing 发表于 2015-11-19 10:57:26 | 显示全部楼层
题好难啊 55
回复 支持 反对

使用道具 举报

shuishuimiao 发表于 2015-11-19 14:02:24 | 显示全部楼层
楼主能说一下 第四轮的最后一问 如何配对两台将要合并区间的服务器 是如果两两合并的么?感觉不大理解 如果第一台机器的区间是0-2 第二台是4 第三台是5-6那两两merge的话 结果不就是0-2 或者 5-6 但是实际上不应该是4-6吗
回复 支持 反对

使用道具 举报

snowwolf 发表于 2015-11-19 15:34:14 | 显示全部楼层
楼主结果出来了没?
回复 支持 反对

使用道具 举报

hjh1011 发表于 2015-11-19 15:44:30 | 显示全部楼层
LZ这面的是什么职位?
回复 支持 反对

使用道具 举报

gorilazz 发表于 2015-11-19 15:45:38 | 显示全部楼层
第五轮这题怎么做呢?
回复 支持 反对

使用道具 举报

 楼主| yourway 发表于 2015-11-19 22:23:07 | 显示全部楼层
wxr.dal 发表于 2015-11-18 21:30
问一下lz,shadow是什么啊
. 1point 3acres 璁哄潧
主面试官的面试次数少于10,还在训练阶段。有一个有经验的人跟他一起面就叫shadow。
回复 支持 反对

使用道具 举报

 楼主| yourway 发表于 2015-11-19 22:36:16 | 显示全部楼层
shuishuimiao 发表于 2015-11-19 01:02
楼主能说一下 第四轮的最后一问 如何配对两台将要合并区间的服务器 是如果两两合并的么?感觉不大理解 如果 ...

我说得“合并”是指将所有结果收集起来,然后将重叠的区间merge。“合并”后所以的区间都保留,直到最后一次合并完成后才能确定最大的区间。

按你的例子,第一、二台服务器合并后的结果0-2,4;这个结果再和第三台服务器(5-6)合并,得到最终结果0-2,4-6,然后确认4-6是最终结果。

或者可以先第二、三台合并得到 4-6,再跟第一台合并,得到0-2和4-6。

在这个例子里,1, (2, 3) 的执行效果是要比 (1, 2), 3 好一点。所以最后两问就是问如何找到这个最优的合并顺序。
回复 支持 反对

使用道具 举报

 楼主| yourway 发表于 2015-11-19 22:40:40 | 显示全部楼层
snowwolf 发表于 2015-11-19 02:34. visit 1point3acres.com for more.
楼主结果出来了没?

HC没过,recruiter说先找组,找到合适的组以后再送一次HC
回复 支持 反对

使用道具 举报

 楼主| yourway 发表于 2015-11-19 22:41:38 | 显示全部楼层
hjh1011 发表于 2015-11-19 02:44 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
LZ这面的是什么职位?

new grad SDE. more info on 1point3acres.com

字数字数字数.exe
回复 支持 反对

使用道具 举报

 楼主| yourway 发表于 2015-11-19 22:53:29 | 显示全部楼层
gorilazz 发表于 2015-11-19 02:45. 鍥磋鎴戜滑@1point 3 acres
第五轮这题怎么做呢?
.1point3acres缃
我的做法是选一个点(例如结点0)开始做 BFS。当访问到第四层的结点时开始计算访问过结点数量,直到结束。从第四层开始访问过的结点个数就是可能的图案个数。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

起始结点可以选择0 , 1, 4,得到N0, N1, N4

最终结果是4*N0+4*N1+N4

我的解法应该不是最优的。面完以后上网搜了一下,发现网上有人讨论这个题。不过我已经无心再看别人的解法了。
https://www.google.com/search?cl ... =UTF-8&oe=UTF-8
回复 支持 反对

使用道具 举报

shuishuimiao 发表于 2015-11-20 00:18:31 | 显示全部楼层
yourway 发表于 2015-11-19 22:36
我说得“合并”是指将所有结果收集起来,然后将重叠的区间merge。“合并”后所以的区间都保留,直到最后 ...

那这样合并完了还是要找一遍最大区间 最坏的情况 如果区间一直不连续一直没有合并 不是就是O(n)了么
回复 支持 反对

使用道具 举报

 楼主| yourway 发表于 2015-11-20 00:26:39 | 显示全部楼层
shuishuimiao 发表于 2015-11-19 11:18
那这样合并完了还是要找一遍最大区间 最坏的情况 如果区间一直不连续一直没有合并 不是就是O(n)了么

1. 你说的没错,所以最后两问面试官就问我如何找到最优的合并顺序。

2. 即使在最坏的情况下,因为是多台机器并行运算,还是要比我之前提出的用一台机器轮流查询所有服务器要快一点吧。
回复 支持 反对

使用道具 举报

weixc1234 发表于 2015-11-20 00:32:00 | 显示全部楼层
求问LZ是HC刚过线在找组吗?还是没过HC也可以team match?
回复 支持 反对

使用道具 举报

 楼主| yourway 发表于 2015-11-20 00:51:43 | 显示全部楼层
weixc1234 发表于 2015-11-19 11:32
求问LZ是HC刚过线在找组吗?还是没过HC也可以team match?

不知道,recruiter 没有细说。
回复 支持 反对

使用道具 举报

bill701 发表于 2015-11-23 14:28:04 | 显示全部楼层
祝楼主好运!
回复 支持 反对

使用道具 举报

 楼主| yourway 发表于 2015-11-23 23:31:48 | 显示全部楼层
bill701 发表于 2015-11-23 01:28. From 1point 3acres bbs
祝楼主好运!
. 1point 3acres 璁哄潧
谢谢你的祝福!
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-12-4 23:46:23 | 显示全部楼层
第五轮可以每个数字维护一个自己可以访问的数字的列表,然后就行dfs吧,当每个数字被访问了以后就看能否加入其他数字可访问数字列表中?
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-12-4 23:55:35 | 显示全部楼层
regular expression那一题就是leetcode Wildcard Matching
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 21:15

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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