一亩三分地论坛

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

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

Yelp onsite 面经,跪了一道题

[复制链接] |试试Instant~ |关注本帖
zsz1990ustc 发表于 2016-4-19 03:04:50 | 显示全部楼层 |阅读模式

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

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

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

x
. visit 1point3acres.com for more.
. 1point 3acres 璁哄潧
上周五下午1点半面的yelp。是downtown里的一栋楼,8楼是吃饭休闲的地方,9楼是HR的地方,13楼是engineer的工作区域,yelp的工作环境是一排大桌子,没有隔间,员工还是蛮多的,很多白人,也有些华人。HR说近两年主要招的都是 new grads.

第一轮面,上来就问 why yelp,然后问简历的project。完了之后做题目,leetcode 121 best time to buy and sell stock 原题。我一上来居然想到了trapping water那题。。。用了两个数组来存某个位置其左边最小值,和其右边最大值。在面试官引导优化了空间,最后其实不用额外空间就可以的。。。

第二轮面,还是问 why yelp,然后问简历的project。然后是一道 smallest k elements in an array的题,用个max heap搞定。我感觉挺满意。结果面试官又来一题。简易版的 lc 290 word pattern, 比如 foo 对应 app 就是对的,要是 foo 对应 apg 那就是错啦。很简单吧。结果我上来只用了一个HashMap,写完了后,他让我写test case,我自己写了下,发现不对,赶紧又加了一个HashMap.. 险过。。


第三轮面,还是问 why yelp,然后问简历的project。需要提一下,每轮面试官结束后,他会和下个面试官交流个两三分钟,然后下个面试官再进来。我前两轮介绍的project都是我最熟的那个,结果第三个面试官就直接问我,你咋总是讲那一个project。。。 好吧,换个project开始侃了。侃完了后,出一道题,懵了。

你们帮我看一看。题目是:给一串movie,假定每个movie都是一个小时,并且都在整点播放;给你一个List的movies,让你安排播放时间,如果没有答案throw一个exception。


比如
电影A: 14, 15, 16, 17-google 1point3acres
电影B: 14, 15, 16
电影C: 14, 15
电影D: 14, 15, 17

返回一个解就行,比如 A 14, B 16, C 15, D 17。 如果你要 A 14, B 15, 后面 C就没法看了。


这可是yelp电面出现了两次的面经题。当时我看到面经时,除了backtracking没别的思路。当时心里还想,谁电面碰到这题,也是真够背的。我不会做就不会做吧,我应该不会这么背。。结果还真遇到了23333。。。 当时临场发挥,就是硬生生的 dfs 来把所有情况撸一遍的。那code写的叫一复杂,然后时间到了还没写完。。 我跟面试官讲了后面的思路,然后他说,嗯, it works。然后结束了。.1point3acres缃
鏉ユ簮涓浜.涓夊垎鍦拌鍧.

求地里的大神能给这题一个靠谱的解法。我真的很好奇。


第四轮,还是问 why yelp,然后问还有什么feature可以加到yelp里。那好多feature啊,你yelp不能买票吧,你yelp不能叫外卖吧,你yelp不能直接付款吧,你yelp不能团购吧,你yelp没有饭店哭胖吧。。。
然后上题,设计一个Rate limitor。就是一小时内访问第六次时,就返回false。这也没啥算法啊,我没太明白,就是HashMap,存访问的IP和ArrayList<TimeStamp>,然后同一个IP一小时内访问第六次,那就返回 false呗。面试官说就是这样的,然后我用java把这个函数写出来。然后讨论了些他做的工作啊什么的,结束了。
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

发现了没,全是地里面yelp出现过的原题。要好好看面经啊,也要多来发面经啊,大家要团结。算法题都是讲完了思路,然后写白板code的,写完后带着对方walk through一下。讲思路的时候可以乱一点,先来个brute force也行。但开始写的时候就不能乱来了,要尽量别出错。哎,我平时题目刷的不不够熟,表现的一般吧。还跪了第三轮。。. 鍥磋鎴戜滑@1point 3 acres
-google 1point3acres
面我的大多是做backend的,我正好最近在研究谷歌三剑客,把GFS, MapReduce和他们讲了一通,感觉还好。

面试结束后HR有和我聊了一阵,然后说负责我的HR没来,下周二她回来上班,然后如果positive的话,会问我要reference。不知道跪没跪。。哎,求人品~~~


. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

评分

3

查看全部评分

missing 发表于 2016-4-20 09:06:09 | 显示全部楼层
同上周五面的,不过我是Data mining team,虽然一道面经都没有但是不难,最后碰到个三哥又被坑了下。同祝好运啊~
回复 支持 1 反对 0

使用道具 举报

ninacc 发表于 2016-4-19 03:57:40 | 显示全部楼层
上周五电面完,不知道能不能onstie, 觉得楼主答的妥啊!祝好运~~~~!!!!电影那个,要我也只会dfs。。。觉得是不是可以greedy?但是还没想明白,求大神解答!
回复 支持 反对

使用道具 举报

diudiuchen 发表于 2016-4-19 12:26:56 | 显示全部楼层
请问lz是怎么学习谷歌三剑客,GFS, MapReduce这些内容的?上公开课还是lincode?. visit 1point3acres.com for more.
谢谢
回复 支持 反对

使用道具 举报

ykwwind 发表于 2016-4-20 09:34:46 | 显示全部楼层
放电影那题,其实用dfs, backtracking复杂度反正就那样了...但是代码写出来应该很简洁..1point3acres缃
回复 支持 反对

使用道具 举报

lfzh123 发表于 2016-4-20 12:57:52 | 显示全部楼层
非常有用的面经~
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-4-20 13:57:26 | 显示全部楼层
问一下各位,电影这道题的时间复杂度应该怎样答呢?
回复 支持 反对

使用道具 举报

zlqiszlq 发表于 2016-4-20 14:51:17 | 显示全部楼层
电影么 二分图最大匹配 O(N^3)
回复 支持 反对

使用道具 举报

huangrui199126 发表于 2016-4-27 01:55:13 | 显示全部楼层
非常同意楼主的那句话!大家要团结!!我马上去onsite ,店面也全是原题,都是感谢大家的智慧!求问楼主后来怎么样了
回复 支持 反对

使用道具 举报

qjw1992 发表于 2016-4-29 13:55:59 | 显示全部楼层
请问楼主面的是哪个组的呀?
回复 支持 反对

使用道具 举报

 楼主| zsz1990ustc 发表于 2016-4-29 14:21:44 | 显示全部楼层
huangrui199126 发表于 2016-4-27 01:55. from: 1point3acres.com/bbs
非常同意楼主的那句话!大家要团结!!我马上去onsite ,店面也全是原题,都是感谢大家的智慧!求问楼主后来 ...

不幸收到拒信了。。祝你好运啊!!
回复 支持 反对

使用道具 举报

 楼主| zsz1990ustc 发表于 2016-4-29 14:22:00 | 显示全部楼层
huangrui199126 发表于 2016-4-27 01:55. 1point 3acres 璁哄潧
非常同意楼主的那句话!大家要团结!!我马上去onsite ,店面也全是原题,都是感谢大家的智慧!求问楼主后来 ...

不幸收到拒信了。。祝你好运啊!!
回复 支持 反对

使用道具 举报

 楼主| zsz1990ustc 发表于 2016-4-29 14:22:42 | 显示全部楼层
qjw1992 发表于 2016-4-29 13:55
请问楼主面的是哪个组的呀?

做后端的应该是。别人帮我推的,我也不知道哪个组。。
回复 支持 反对

使用道具 举报

Janet.Ding 发表于 2016-4-30 05:34:54 | 显示全部楼层
我觉得可以用BFS,基本数据类型设置为[not seen movie(set), movie schedule(list)],然后在每个时刻根据这个时刻上映的电影进行遍历,根据上面的例子可以写成这样. 1point 3acres 璁哄潧
第一层在14点:[(B,C,D), [A]], [(A,C,D), [B]], [(A,B,D), [C]], [(A,B,C), [D]]
第二层在15点:[(C,D), [A,B]], [(B,D), [A,C]], [(B,C), [A,D]], ...
直到最后一层17点,如果有则返回movie schedule,否则返回false
回复 支持 反对

使用道具 举报

huangrui199126 发表于 2016-5-1 00:01:27 | 显示全部楼层
zsz1990ustc 发表于 2016-4-29 14:22.鐣欏璁哄潧-涓浜-涓夊垎鍦
做后端的应该是。别人帮我推的,我也不知道哪个组。。

哎,感觉楼主很牛啊。。。yelp onsite果然难啊
回复 支持 反对

使用道具 举报

xiaoyehhuang23 发表于 2016-5-10 13:34:02 | 显示全部楼层
想到一种greedy的做法,是把问题表示成矩阵,每行代表一个电影,每列代表一个时间段。1代表这个时间这个电影可以放,0代表不能放。然后每次迭代都去找行sum和列sum中最小的。如果最小sum是1就挑那个1的元素。如果最小sum不为1就挑另外一个维度最小对应的元素。挑中之后把对应的行和列删掉,继续迭代。。过程中一旦某行或列的sum为0就throw exception。不晓得靠不靠谱
回复 支持 反对

使用道具 举报

BrilliantBean 发表于 2016-5-13 05:38:56 | 显示全部楼层
楼主有详细的解答吗 关于看电影的那道题
回复 支持 反对

使用道具 举报

bcc 发表于 2016-10-5 01:44:45 | 显示全部楼层
Greedy O(n)方法:电影那个题可以先从最短的时间列表看起,例如,电影C: 14, 15 随便选一个,电影c时间确定,然后把那个时间点从所有的list里边除去。. visit 1point3acres.com for more.
不知道这样对不对啊?. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 16:45

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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