一亩三分地论坛

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

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

10.23 Google/YouTube Onsite面筋

[复制链接] |试试Instant~ |关注本帖
peach=。= 发表于 2015-11-7 15:21:01 | 显示全部楼层 |阅读模式

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

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

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

x
大家嚎,今天晚上hr打电话告诉我正式通过了,超开心,来发面筋惹。

我参加的是10月23在MTV的YouTube College Weekend,感觉特别棒,送了各种东西

早上先是所有new grad拉到一个房间然后一个YouTuber来讲他在YouTube的经历和感受,然后面试官一个一个来带走candidate。

第一轮是一个中国小哥,在google干了一年多,这一轮我感觉答的最不好,最后feedback也确实如此,不过感觉小哥还是放了我一马的,感谢!!
1. 给一堆meeting(start_time, end_time),说假设你只有一个meeting room,问最多能有几个meeting。. 鍥磋鎴戜滑@1point 3 acres
2. Stock Price I
3. OO Design elevator.鏈枃鍘熷垱鑷1point3acres璁哄潧
.鏈枃鍘熷垱鑷1point3acres璁哄潧
第二轮是一个印度小哥。
1. warm up question, 很简单→_→所以忘记了,总之是一道leetcode原题
2. 这道题说起来比较复杂。假设你有一张表,这个表是每个字母在其他字母后面出现的概率。然后这个概率是根据一些东西算出来的,比如说一本字典。
举个例子吧
假设字典是 ["cat", "cap"]
那表格就会是
        a     c       p     t
a     0     0.5    0    0. visit 1point3acres.com for more.

c     0      0      0    0
p    0.25  0      0    0
t    0.25   0     0     0 . From 1point 3acres bbs
.鐣欏璁哄潧-涓浜-涓夊垎鍦
ok,不知道格式会不会坏><,总之就是你有这样一个表格,然后他们的概率加起来是1嘛,但你不用担心这个表格是怎么来的。
然后如果你有这本字典,让你返回长度是4的最可能出现的单词(保证只有一个)
follow up是如果没有这本字典,你如何算长度是4的最可能出现的单词(保证只有一个)
再follow up是,假设你现在根据比如说google search query有一个,2014年最经常搜索的单词list,然后根据这个list算出一个概率表格以及最可能出现的单词,然后现在你知道2015年添加了一些单词,如何更efficient的算出新的概率表格以及最可能出现的单词。
. from: 1point3acres.com/bbs
这一整道题,第一第二问都是写了pseudocode,后面再follow up就是讲一讲idea,没让实现code。真正写code的就是第一个warm up question

lunch这一轮白人小哥,特别特别nice,很能扯,跟我分享他以前的面试经验心得什么的,还一直鼓励我,我后来还问他google是不是真的有题库= =

第三轮白人大叔,人也特别nice,一直 very cool, very very cool. 鍥磋鎴戜滑@1point 3 acres
1. longest common prefix 没让写code,就谈了idea
2. longest common substring
follow up是优化空间(因为楼主一开始用了n*n的space,大叔让我用n). 1point 3acres 璁哄潧

第四轮是白人小哥,人也挺好的,全程狂写笔记
就一道题,滑雪。跑test case跑得楼主口干舌燥+腰疼.鐣欏璁哄潧-涓浜-涓夊垎鍦
follow up是如果这个matrix特别特别大,一个machine装不下要怎么办。

就酱,太高兴了,准备签了offer哈哈哈,这两天会再写一写这段时间找工作的经历和体会!今天让我先缓一缓~. visit 1point3acres.com for more.
祝找工的大家都好运!都拿到dream offer!!


评分

7

查看全部评分

本帖被以下淘专辑推荐:

say543 发表于 2015-11-11 15:33:40 | 显示全部楼层
peach=。= 发表于 2015-11-11 01:30
是的是的,你说的是对的!面试官后来就说了这个解法!

所以第三轮的longest common substring 是两个string 来求common的substring 吗? 而且substring 不用从头开始?
回复 支持 1 反对 0

使用道具 举报

say543 发表于 2015-11-10 06:03:12 | 显示全部楼层
楼主第三轮的第二题longest common substring. 我会用第一个string 建suffix trees , 然后剩余的string 一个一个用suffix tree检验如果string average length 是n 这样tree 的space 是<= o(n ^2) 这是面试官想要的答案吗? 还是follow up 有更好的答案?
回复 支持 1 反对 0

使用道具 举报

genghis 发表于 2015-11-7 16:50:46 | 显示全部楼层
第二题就是个Viterbi 算法吧
回复 支持 0 反对 1

使用道具 举报

chwcrazy 发表于 2015-11-11 16:47:42 | 显示全部楼层
say543 发表于 2015-11-11 02:44
如果两个string 的和为什么suffix tree 是o(n+m) 的space而不是o(n+m)^2 呢? 另外弱弱的问一下如果和再一 ...

time complexity 是O(M+N), space 应该是 tree的node的个数吧,当建立好suffix tree的时候,再对每一个node进行标记, 如何标记呢?意思就是 从root到该node的substring 如果都在s1 和s2的话,标记为s1,s2 .  如果只在s1里,就标记成s1, 如果只在s2, 就标记成 s2,  这样对于每一个node 就有标记,然后dfs 找到最深的node 且标记为 s1,s2,这样如果只有一个最深的node是满足这个条件,就直接返回 root到该node的所有string,这就是LCS,如果有多个最深的node,就找string最长的那一个。就ok了。
回复 支持 1 反对 0

使用道具 举报

genghis 发表于 2015-11-7 15:49:01 | 显示全部楼层
您好,能不能具体说下电梯那题是怎么样的呀,多谢啦
回复 支持 反对

使用道具 举报

Augustus 发表于 2015-11-7 16:09:45 | 显示全部楼层
楼主,你那个第二轮的第二题怎么解?求答案
回复 支持 反对

使用道具 举报

nelson16 发表于 2015-11-7 16:24:56 | 显示全部楼层
第二题没看懂 。。。可以再说一次吗
:D
回复 支持 反对

使用道具 举报

guoqinlong 发表于 2015-11-7 20:01:45 | 显示全部楼层
楼主好~第二题没有看懂,求解释~~还有滑雪时什么题啊`
回复 支持 反对

使用道具 举报

宝贝忆彼岸 发表于 2015-11-8 01:11:01 | 显示全部楼层
感谢分享,请问YouTube College Weekend和一般google面试有什么区别吗?还有那个滑雪问题如果matrix太大,machine装不下是什么解法?求LZ指点!!

补充内容 (2015-11-8 01:54):
还有滑雪问题是必须descending的还是non-ascending的都可以?
回复 支持 反对

使用道具 举报

hj867955629 发表于 2015-11-8 02:35:30 | 显示全部楼层
2.2能详细说说嘛?表感觉不太对。。
回复 支持 反对

使用道具 举报

marthew777 发表于 2015-11-8 02:45:05 | 显示全部楼层
楼主,第二题,用trie做可以么,除了root以外的每个node有一个count记录出现过几次, eg: c(null)->a(2)->t(1)->p(1), P(a) = 2/4; P(t)=1/4;  这样算下来update/create/query都是树高
回复 支持 反对

使用道具 举报

 楼主| peach=。= 发表于 2015-11-8 06:26:17 | 显示全部楼层
genghis 发表于 2015-11-7 15:49
您好,能不能具体说下电梯那题是怎么样的呀,多谢啦
. 1point3acres.com/bbs
电梯那题是很经典的oo design哇,就是设计一个电梯系统,我写了building,floor, button, elevator几个class。然后用了一个queue装这个elevator接下来要去几层这样。你可以设计的很复杂,也可以很简单。我写了最简单的就是,queue里面是先来后到的。
我记得还有一种比较复杂(但是智能)的设计是用状态机。= =然后我觉得太复杂惹就没有管它直接写了最简单的~
回复 支持 反对

使用道具 举报

 楼主| peach=。= 发表于 2015-11-8 06:29:18 | 显示全部楼层
Augustus 发表于 2015-11-7 16:09
楼主,你那个第二轮的第二题怎么解?求答案
. 1point3acres.com/bbs
有字典的我就说最简单暴力的方法说把字典遍历一遍所有单词的概率算一遍最后得出最可能的单词

然后没有字典的,有点像trie tree的感觉,dfs算最可能的单词
回复 支持 反对

使用道具 举报

 楼主| peach=。= 发表于 2015-11-8 06:29:32 | 显示全部楼层
nelson16 发表于 2015-11-7 16:24
第二题没看懂 。。。可以再说一次吗
:D

喵?哪里没懂
回复 支持 反对

使用道具 举报

 楼主| peach=。= 发表于 2015-11-8 06:31:50 | 显示全部楼层
genghis 发表于 2015-11-7 16:50
第二题就是个Viterbi 算法吧

这是啥高端算法!><默默google了一下,看着有点像……搞不好这个小哥就是想问这个= =楼主就用了最暴力最直接的dfs一个一个默默算的。。。。唉
回复 支持 反对

使用道具 举报

 楼主| peach=。= 发表于 2015-11-8 06:33:18 | 显示全部楼层
guoqinlong 发表于 2015-11-7 20:01. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
楼主好~第二题没有看懂,求解释~~还有滑雪时什么题啊`

><哪里哪里没看懂。。。。
. from: 1point3acres.com/bbs
滑雪是lintcode longest Increasing Continuous subsequence II
http://www.lintcode.com/en/probl ... ous-subsequence-ii/

感觉google特别喜欢考这道题
回复 支持 反对

使用道具 举报

 楼主| peach=。= 发表于 2015-11-8 06:41:45 | 显示全部楼层
宝贝忆彼岸 发表于 2015-11-8 01:11. more info on 1point3acres.com
感谢分享,请问YouTube College Weekend和一般google面试有什么区别吗?还有那个滑雪问题如果matrix太大,m ...

College Weekend 和一般google面试没区别!就是前后会多一些活动,其实到最后那个tech talk和live band的时候楼主已经炒鸡累炒鸡想肥家,不过还是硬撑着T^T
除此以外,都挺好的,有很多new grad和你一起去,然后会送很多东西,管了一天的饭. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

matrix太大那个后来很多思路都是面试官在说,感觉他只是想和你讨论讨论,看看你有没有什么思路。
我当时说的是,把matrix分成四份,在四个machine上分别计算longest subsequence,然后边界要特殊处理,因为边界有可能会连接到另一个小matrix。
在边界处理这边,后来是面试官提供了一个思路,他说可以用类似hashmap的数据结构把边界上在这个小matrix连着的点存起来(一头,一尾),然后一个一个小matrix的边界再连接起来算。. 鍥磋鎴戜滑@1point 3 acres

我讲的有点乱><,当时面试官也没有再go to detail,讨论了一下思路,然后问我比如那个大matrix上最长的一条是一个U型啊,或者画个其它形状,问我会怎么实现刚刚讨论的 算法。

我当时问他matrix里面有没有重复,他说先不考虑重复。实现code实现的是descending的,然后让我稍微讲了下有重复该怎么办,没让写code
回复 支持 反对

使用道具 举报

 楼主| peach=。= 发表于 2015-11-8 06:44:14 | 显示全部楼层
marthew777 发表于 2015-11-8 02:45
楼主,第二题,用trie做可以么,除了root以外的每个node有一个count记录出现过几次, eg: c(null)->a(2)->t( ...

我觉得我当时是用了类似trie tree的结构的,但只是用来dfs而已
我觉得你是不是理解错题意了,他不是让我们算那个概率,概率是已经算好的,让我们算的是长度为4的最可能出现的单词。
. from: 1point3acres.com/bbs
感觉和 genghis (地下室)说的有点点像,但是我完全没用复杂的算法T^T暴力dfs解的
回复 支持 反对

使用道具 举报

DeniLi 发表于 2015-11-8 07:26:22 | 显示全部楼层
谢谢楼主分享
回复 支持 反对

使用道具 举报

say543 发表于 2015-11-8 15:24:23 | 显示全部楼层
peach=。= 发表于 2015-11-8 06:29. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
有字典的我就说最简单暴力的方法说把字典遍历一遍所有单词的概率算一遍最后得出最可能的单词

然后没有 ...

弱弱的问一下暴力搜寻怎么evaluate 哪个单词的概率是最高的? 能不能用个简单的example 解释一下多谢多谢
回复 支持 反对

使用道具 举报

genghis 发表于 2015-11-8 16:06:28 | 显示全部楼层
我觉得维特比算法能应用到这题的吧。. 鍥磋鎴戜滑@1point 3 acres
维特比算法就是给你一个状态转移概率矩阵,求最大概率的路径,可以用dp来做。
状态转移概率矩阵可以由lz这里的矩阵得到,它是每行概率和为1,即 sigma(j) a[i][j] = 1。a[i][j]表示从字母i转移到j的概率,这里对j遍历求和是1。
. From 1point 3acres bbs
f[k][i]表示长度为k的单词并且最后以第i个字母结尾的概率。  f[k][i] = max(f[k-1][j] * a[j][i]).鏈枃鍘熷垱鑷1point3acres璁哄潧

然后一般默认初始分布是个均匀分布,这样子就能把最大路径的概率求出来了,另外做dp的时候记得保存下路径,就能求出最大概率的那条路径了。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

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

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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