一亩三分地论坛

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

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

RocketFuel 电面被虐

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

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

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

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

x
skype面试。老印面试官迟到了……所以skype接通之后啥都没说直接上题目:

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

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

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

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

评分

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)。
如果(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人一组. from: 1point3acres.com/bbs
if (x,y) = true, 排除x. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
if (x,y)  = false, 排除y
返回potential candidate,x or y or neither

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


补充内容 (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
这题好像还挺经典的,就是楼上说的那个 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
    else:
        two = two + 1
到array底部的时候return one

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

补充内容 (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
这题好像还挺经典的,就是楼上说的那个 celebrity problem。听RF里面的员工说,面试只要不遇到烙印,就还好 ...

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

使用道具 举报

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

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 12:02

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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