一亩三分地论坛

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

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

新鲜YouTube Onsite面经

[复制链接] |试试Instant~ |关注本帖
wangmengcathy 发表于 2015-12-5 15:32:07 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Google - 内推 - Onsite |Otherfresh grad应届毕业生

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

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

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

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

第二轮,这是楼主感觉挂定的一轮。。 说你有三台接啤酒的机器,分别是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我就懒得具体说了,我提到了更新大家应该都能知道什么意思), 没超时直接更新。基本就是这样其实不难。
. From 1point 3acres bbs
第四轮也比较蛋疼我长话短说吧。你有一个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的同学找个感觉吧。祝各位好运~~

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

评分

8

查看全部评分

本帖被以下淘专辑推荐:

 楼主| wangmengcathy 发表于 2015-12-5 15:36:49 | 显示全部楼层
Sorry 啊 第二轮写的太醉忘了说输出了。输出就是你能不能找到通过按任意size啤酒机button的组合,例如(小,或者小中大, 小小小,中大大),最后使顾客能满意的,就是接的酒落在顾客杯子的min-max区间内。能找到这样的组合返回true,找不到false.
回复 支持 反对

使用道具 举报

zxyviopond 发表于 2015-12-5 16:06:05 | 显示全部楼层
感觉像凑硬币题,给你无限多的1,2,5硬币,问能不能凑出某个钱数,这个题1,2,5变成了range, 某个钱数也变成了range了
回复 支持 反对

使用道具 举报

 楼主| wangmengcathy 发表于 2015-12-5 16:14:54 | 显示全部楼层
zxyviopond 发表于 2015-12-5 16:06
感觉像凑硬币题,给你无限多的1,2,5硬币,问能不能凑出某个钱数,这个题1,2,5变成了range, 某个钱数也变成 ...

对的 就是这种感觉 基本上就是回溯吧 没往贪婪什么的想可能也可以不确定 这道题我就是被各种边界小于怎么办大于怎么办给弄的有点晕。。
回复 支持 反对

使用道具 举报

zxyviopond 发表于 2015-12-5 16:23:30 | 显示全部楼层
深夜抛砖,不一定对, 而且感觉很没效率
dp(i, j) 定义为能否满足min is i, max is j的要求
dp(i, j) = dp(i-smallMax, j - smallmin) || dp(i-mediumMax, j - mediumMin) || dp(i-largeMax, j - largeMin). 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
只要按一下小、中、大之一就能满足要求。

if j > i return false;
if i < 0 || j < 0 false
if i = 0, true min is 0,那么我什么也不按就能满足. 1point3acres.com/bbs
dp(smallMin, smallMax) = true. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
dp(mediumMin, mediumMax) = true
dp (largeMin, largeMax) = true
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
i 从smallMin loop to 杯子min
j 从i loop到杯子max
   算dp(i,j)
. visit 1point3acres.com for more.
result is dp(杯子min, 杯子max). 1point3acres.com/bbs


. 1point3acres.com/bbs
补充内容 (2015-12-5 16:25):
if j < i return false;

补充内容 (2015-12-5 16:46):
好像不大对~~
比如说只有small 1 - 100
杯子 100 - 200 其实不行,但是按照上面目测又行了,所以不对,0的情况好tricky
. 鍥磋鎴戜滑@1point 3 acres
补充内容 (2015-12-5 16:51):
原来是写反了,应该是
dp(i, j) = dp(i-smallmin, j - smallmax) || dp(i-mediumMin, j - mediumMax) || dp(i-largeMin, j - largeMax)
回复 支持 反对

使用道具 举报

 楼主| wangmengcathy 发表于 2015-12-5 16:51:14 | 显示全部楼层
zxyviopond 发表于 2015-12-5 16:23
深夜抛砖,不一定对, 而且感觉很没效率
dp(i, j) 定义为能否满足min is i, max is j的要求
dp(i, j) = d ...

同学你好厉害,当时要有你附体就好了哈哈~~ 我甚至都想不出dp思路!求指教~
回复 支持 反对

使用道具 举报

haifengc 发表于 2015-12-5 23:35:22 | 显示全部楼层
第四轮和我一样
回复 支持 反对

使用道具 举报

 楼主| wangmengcathy 发表于 2015-12-6 01:02:28 | 显示全部楼层

我们一天面的?
回复 支持 反对

使用道具 举报

haifengc 发表于 2015-12-6 01:14:58 | 显示全部楼层

我2号面的
回复 支持 反对

使用道具 举报

 楼主| wangmengcathy 发表于 2015-12-6 01:28:58 | 显示全部楼层

哥们儿你应该发个面经的
回复 支持 反对

使用道具 举报

haifengc 发表于 2015-12-6 05:46:26 | 显示全部楼层
我是应该发
回复 支持 反对

使用道具 举报

cszeus 发表于 2015-12-6 05:59:24 | 显示全部楼层
第四轮,merge interval吧
回复 支持 反对

使用道具 举报

haifengc 发表于 2015-12-6 08:30:25 | 显示全部楼层
cszeus 发表于 2015-12-6 05:59
第四轮,merge interval吧

我当时用merge interval 做的
回复 支持 反对

使用道具 举报

LifeGoesOn 发表于 2015-12-6 11:42:02 | 显示全部楼层
LZ 第一题有好的方法判断可以有first move吗
回复 支持 反对

使用道具 举报

tianshaobo47 发表于 2015-12-6 12:15:20 | 显示全部楼层
感觉楼主答得都不错啊,还有机会!
回复 支持 反对

使用道具 举报

 楼主| wangmengcathy 发表于 2015-12-6 12:16:30 | 显示全部楼层
LifeGoesOn 发表于 2015-12-6 11:42
LZ 第一题有好的方法判断可以有first move吗

我是空板直接生成的  然后你push items的时候判断一下已放还是没放就行了(0 or > 0)放了的话就return
回复 支持 反对

使用道具 举报

LifeGoesOn 发表于 2015-12-6 12:38:00 | 显示全部楼层
wangmengcathy 发表于 2015-12-6 12:16
我是空板直接生成的  然后你push items的时候判断一下已放还是没放就行了(0 or > 0)放了的话就return

不大明白, 生产的板必须保证用户可以有first move, 也就是说用户必须可以第一步通过交换item来凑3个相同的item。 我理解的判断方式是 找三个连在一起的block, 看是否有两个block 相同, 如果有的话, 看另一个不同的block的neighbor是否有相同的block 有的话那用户可以move? 还是我理解错了
回复 支持 反对

使用道具 举报

orangepie 发表于 2015-12-6 12:45:39 | 显示全部楼层
楼主 最后一轮,   rain drop 落到那个range里面的时候,rain drop的起始位置 可能是一个无限位数的小数啊;  起始位置应该怎么算呢。
回复 支持 反对

使用道具 举报

jkingxt 发表于 2015-12-6 12:51:19 | 显示全部楼层
关于第三题,有一个疑问。。为什么要使用到LRU?为什么不直接用hashmap来存呢。key为data,value为他的上一次的时间点。如果没有出现过,或者和上一次出现的时间差大于10,则直接输出,不然就更新map而不输出。请问,如果这样的话可以么?
回复 支持 反对

使用道具 举报

cszeus 发表于 2015-12-6 14:38:16 | 显示全部楼层
LifeGoesOn 发表于 2015-12-6 11:42
LZ 第一题有好的方法判断可以有first move吗
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
超级简单,先放一个有效的,然后填充其他的,就能保证了
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 04:05

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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