一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 1806|回复: 11
收起左侧

RocketFuel 电面被虐

[复制链接] |试试Instant~ |关注本帖
pro 发表于 2014-11-7 05:02:41 | 显示全部楼层 |阅读模式

2014(10-12月) 码农类 硕士 全职@RocketFuel - 内推 - 技术电面 |Fail

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

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

x
skype面试。老印面试官迟到了……所以skype接通之后啥都没说直接上题目:. 1point 3acres 璁哄潧

有n个人互相送礼物。可以通过 bool gift(int i, int j); 查询i是否给j送了礼物。那么是否有这么一个人,其他人都给他送了礼物,同时他却没有送任何人礼物。

很容易能想到O(n^2)的解。面试官认为太慢,问我能不能更快。我做了一些剪枝,他说剪枝也不能优化worst-case。需要时间复杂度更低的解法。. from: 1point3acres.com/bbs

我想了半天没头绪,他给了个提示,即gift(i, j)如果是true,其实也说明了i不可能是答案。同样的如果gift(i, j)是false,说明j不可能是答案。

我照着这个思路写了个很丑的扫(i, j)的方法,但worst-case还是O(n^2)的。而且bug百出……最后折腾到时间到了也没把O(n)的想出来(真的有O(n)解法吗?)。
-google 1point3acres

评分

2

查看全部评分

 楼主| pro 发表于 2014-11-8 11:35:51 | 显示全部楼层
我想到根据他的提示这套题接下来的思路应该是怎么样的了:

根据他的提示,其实应该归纳出的信息是“每次调用gift(i, j),我都可以排除掉一个错误答案”。那么应该想到的是,我应该通过调用n-1次gift(i, j)来得到正确答案。
这样的话就可以从(0, 1)开始。如果0不认识1,就毙掉1,看(0,2),如果0还不认识2,就毙掉2,继续看(0, 3)。. 1point3acres.com/bbs
如果(0, x)的时候发现0认识x,那就从(x, x+1)继续。此时没有必要验证(x, [0, x-1])是因为之前0不认识他们已经都被毙掉了……这样下去最后剩下的就是正确答案。

唉这样看看还是蛮straightforward的。还是我自己反应不够快吧。
回复 支持 反对

使用道具 举报

圆梦梦剧场 发表于 2014-11-7 05:07:31 | 显示全部楼层
divide & conquer ? O(nlogn)?

补充内容 (2014-11-7 05:10):
怎么没法编辑了。。。
如果k是那个收到所有人礼物,但一个礼物都没送的
那么把总的n个人 分成2个subset, k肯定也是他所在的n/2人数的那个subset里 “收到所有人礼物,但没送一个礼物” 的人。



补充内容 (2014-11-7 05:12):
base case:
divide到2人一组
if (x,y) = true, 排除x
if (x,y)  = false, 排除y
返回potential candidate,x or y or neither

merge的时候比较两个subset返回的potential candidate..


. 1point 3acres 璁哄潧补充内容 (2014-11-7 05:20):
哦。。时间复杂度算错了。。这个divide & conquer 就是O(n)的时间复杂度
回复 支持 反对

使用道具 举报

22691482 发表于 2014-11-7 05:14:31 | 显示全部楼层
The Celebrity Problem: http://www.geeksforgeeks.org/the-celebrity-problem/

我准备FB面试的时候看机经也碰到了这题。
回复 支持 反对

使用道具 举报

haoranliu1990 发表于 2014-11-7 05:58:11 | 显示全部楼层
这题好像还挺经典的,就是楼上说的那个 celebrity problem。听RF里面的员工说,面试只要不遇到烙印,就还好,遇上了就靠发挥加人品了。。。bless
回复 支持 反对

使用道具 举报

 楼主| pro 发表于 2014-11-7 06:15:25 | 显示全部楼层
haoranliu1990 发表于 2014-11-7 05:58. more info on 1point3acres.com
这题好像还挺经典的,就是楼上说的那个 celebrity problem。听RF里面的员工说,面试只要不遇到烙印,就还好 ...

那我算不走运的了……我也知道这题我看到过但就是怎么都想不起来解法了。唉昨天晚上还刚通宵赶due都没睡觉……面试的时候基本就是晕的
回复 支持 反对

使用道具 举报

haoranliu1990 发表于 2014-11-7 06:43:20 | 显示全部楼层
pro 发表于 2014-11-7 06:15
那我算不走运的了……我也知道这题我看到过但就是怎么都想不起来解法了。唉昨天晚上还刚通宵赶due都没睡 ...

其实很正常啊,我听说烙印占一半比例。。。大家都懂的。。
回复 支持 反对

使用道具 举报

liuzhe1218 发表于 2014-11-7 07:26:45 | 显示全部楼层
找名人的变形。。。
回复 支持 反对

使用道具 举报

真爱你的云 发表于 2014-11-7 07:54:31 | 显示全部楼层
用两个pointer 可以么 one=0 two = 1
while(one 和  two 都在n范围内):
    if (gift(one,two)):
        one = two + 1-google 1point3acres
    else:
        two = two + 1.1point3acres缃
到array底部的时候return one

用的是这个提示: 即gift(i, j)如果是true,其实也说明了i不可能是答案。同样的如果gift(i, j)是false,说明j不可能是答案。
不知道对不对 就一看到就这么想了。。。


补充内容 (2014-11-7 08:01):
用了几个test case 试了一下 果然是不行的。。。。。
回复 支持 反对

使用道具 举报

xx8833 发表于 2014-11-8 06:25:10 | 显示全部楼层
不看答案还真挺难想到的
回复 支持 反对

使用道具 举报

285845348 发表于 2014-11-10 09:01:56 | 显示全部楼层
haoranliu1990 发表于 2014-11-6 13:58. From 1point 3acres bbs
这题好像还挺经典的,就是楼上说的那个 celebrity problem。听RF里面的员工说,面试只要不遇到烙印,就还好 ...

应该不可能吧,我一共遇到了5个烙印从电面到onsite,我看旁边的人都至少一半面的烙印。一共6轮,至少的有3个
回复 支持 反对

使用道具 举报

haoranliu1990 发表于 2014-11-12 23:12:39 | 显示全部楼层
285845348 发表于 2014-11-10 09:01. 鍥磋鎴戜滑@1point 3 acres
应该不可能吧,我一共遇到了5个烙印从电面到onsite,我看旁边的人都至少一半面的烙印。一共6轮,至少的有 ...

是的,每个组都很多,只能说尽量少遇到吧,他们公司三哥挺多的。。
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-12-15 05:08

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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