新鲜YouTube Onsite面经

原帖地址:一亩三分地

今天刚面完来,还在酒店来发个面经吧, 生平第一次发,前两天还想发一个同学fb过了得面经来着结果那哥们不想太想发,就将自己亲身经历献上希望帮助后来者。
.1point3acres缃/span>首先要说的是楼主感觉基本肯定是跪了,一轮基本代码没写出来,思路也没讲太清楚,还有一轮根本没写出面试官满意的答案,以下来说题目。

第一轮,设计一个类似于消方块的游戏,通过滑动交换items, 每行每列都是凑够三个相同的item就消掉,然后让你初始化一个board,初始化后的board要能使用户能够做出firstmove 意思就是你不能一开始通过移动消掉任何方块。而且也不能产生三个连在一起能直接消掉的方块。楼主用的方法比较二逼,反正最后就是说你可以用dfs来产生这个方块,如果遇到违例的backtrack换另外一个item来产生。

第二轮,这是楼主感觉挂定的一轮。。 说你有三台接啤酒的机器,分别是small,medium, large. 这三种size的机器按一次button一次分别能distribute, say 100 – 150ml, 200 – 250ml, 300 – 350ml的啤酒,每台机器出来的啤酒量是区间里的任意一个数不确定。说现在一个顾客自带一个“杯子“,这个杯子任意大小但是有两个限制 就是min和max volume意思就是 你最少要接到min(ml)在杯子里,最大能只能接max(ml),然后你要想让顾客满意必须接在这个区间里面的那么多啤酒。比如说我有一个下限min是300ml 上限max是400ml, 那么我按一下small是接不够的, 我需要在按一下midium才能接够。但是有的时候我按midium可能也不行,比如说我midium的区间换成200 – 300ml, 那么我按一下small再按一下medium就可能接出(100 + 200)- (150 + 300)ml的酒,which is not valid cause (150 + 300 = 450) might exceed the max volume(400ml) of the cup。这种个情况或许你需要连续摁记下small或者摁一下或者记下small再摁下large解决。Anyway,楼主觉得这道题肯定是要递归回溯的,当时有点紧张,加上case实在有点多,关键是leetcode真心从来没做过类似,瞬间智商不够用了。总之这轮基本上只写出了basecase然后最后说了下我想大概怎么解决。。。

第三轮算简单,类似于LRU的感觉,说不断地给你push data stream你需要打印出这些data,但是呢如果当前data在过去十秒内出现呢就wait and skip to next,但是跳过不代表不管你仍然需要somehow记录他在这个时间点出现过,因为接下来十秒内可能又出现这个data, 而你要是用旧的最开始的那个data的话可能此时他已经在十秒外所以你就没管就把他打印出来了, 但其实你第一个十秒内遇到duplicate的时候应该记录一下那个时间点,所以说有可能不需要打印最新的这个repeated data。时间点的话假设你可以直接用一个什么Time.getTime()之类的方法get这不是重点。楼主基本上就是用一个queue来维护时间和data,然后没新来一个加到队尾同时把队首超过十秒的都通通poll, 同时用一个hashmap来不断更新data以及其出现的时间,如果超过十秒的就要随着queue一起也将超时的data从hashmap里删掉(必须删因为可能每秒的数据量非常大,你不删光保存并更新时间到最后内存会不够,这儿更新是个小trick我就懒得具体说了,我提到了更新大家应该都能知道什么意思), 没超时直接更新。基本就是这样其实不难。

第四轮也比较蛋疼我长话短说吧。你有一个sidewalk(你可以想成一段距离或者一个range 比如说一米),然后有一个raindrop随机生成器,没滴raindrop都有一个宽度比如说1cm 然后开始随机下雨,雨滴之间可能会compeletely or partially overlop,or totally seperate,三种case, 然后问你下多少滴雨才能让这个sidewalk完全淋湿,就是雨滴完全覆盖那1m。。 我一开始的思路是leetcode上longest consecutive numbers in a array那道具体名字我忘了,反正就是个hashmap维护一个边界和长度。我随意写了点基本上就是写了一个data structure维护一个雨滴edge x坐标,以及长度,通过最新产生的雨滴overlap情况选择新创建一个雨滴加入list(其实本来应该用某种排序的list按edge x排序的方便后来两两raindrop range之间合并) 还是与之前的某raindrops range合并(这个合并其实情况也蛮多 楼主当时都没时间说完了)。最后的话一直到这个list里所有raindrop range的总length >= length of sidewalk(1m) 那么就算完全覆盖了。

总的来说,楼主就是这么背, 都是新题!下来跟一起来的几个中国小伙伴聊他们有的被问到什么number of islands II 还有word break吧,即使是新题也是matrix里一些图的基本算法操作(bfs/dfs),感觉小伙伴们应该是ACE了。总之还算比较正常,楼主的题目呵呵,主要也是楼主太菜,智商真的是不够用哈哈哈。这次真的就是来旅个游了。希望这些面经可以帮后面面Google or Youtube的同学找个感觉吧。祝各位好运~~

最后就是希望各位多加点米啊,搜个面经都搜不了好闹心。