回复: 24
跳转到指定楼层
上一主题 下一主题
收起左侧

FB新题求解答

全局:

2015(4-6月) 码农类General 硕士 全职@meta - 内推 - Onsite  | | Other | 在职跳槽

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
马上onsite了,看到新题好抓狂。。。。
引用帖子:
第二道题:
面试官说是道新题  finding ali baba
就是ali baba是个怪兽,他可能在
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

化~~~

我感觉这题是DP,但不知道转移方程怎么写,不知走过路过的大神能给点idea咩?谢谢!

评分

参与人数 3大米 +24 收起 理由
raccoon + 1 感谢分享!
mmliu + 3 感谢分享!
whdawn + 20

查看全部评分


上一篇:求问 FB Production Engineer 面经
下一篇:刚结束的Epic OA 面经

本帖被以下淘专辑推荐:

推荐
ryancooper 2015-5-28 23:01:04 | 只看该作者
全局:
这道其实是老题了,之前就有出现过。很快这道题就会放到leetcode上的,你到时可以去试试。对于这道题,既然是判断时候稳赢,意思就是对于无论ali的起始位置在哪儿,我们都能抓到它。所以很自然,ali所在的位置肯定会作为状态的一部分。另外一个显然的需要记录的状态,就是strategy的当前位置。所以我们可以很容易写下如下的代码:
  1. def canFind(numCaves, strategy):
  2.         def helper(pos, curr):
  3.                 if curr == len(strategy):
  4.                         return False
  5.                 if pos == strategy[curr]:
  6.                         return True
  7.                 res = True
  8.                 if pos > 0:
  9.                         res = res and helper(pos - 1, curr + 1)
  10.                 if pos < numCaves - 1:
  11.                         res = res and helper(pos + 1, curr + 1)
  12.                 return res
  13.         for i in xrange(numCaves):
  14.                 if helper(i, 0) is False:
  15.                         return False
  16.         return True
复制代码
由于我们要稳赢,所以对于原问题helper(pos, curr),它的解依赖于helper(pos - 1, curr + 1)(对应往左跳一格,如果可以的话)与上helper(pos + 1, curr + 1)(同理,往右一格)。然后我们对于ali所在的每个位置都算一遍就好了。

按照这样的设计方式,我们很快就能看出有许多的重复计算,所以可以加上cache,这样时间复杂度就是O(numCaves * len(strategy))。如果你改成bottom up的计算方式,就是直接填表,那么注意状态间的依赖方式,我们可以使用滚动数组,这样空间就可以从O(numCaves * len(strategy))优化到O(numCaves)。

评分

参与人数 2大米 +13 收起 理由
hzyslddm + 10 感谢分享!
mjq04 + 3 回答的很好!

查看全部评分

回复

使用道具 举报

推荐
mrno5zzz 2015-5-29 02:28:45 | 只看该作者
全局:
我觉得可以用res[i][j] 来表示 第j 天在Cave i能不能捉到马云。如果捉到,则为true, 否则为false。
然后状态转换方程就是res[i][j] = res[i][j] || res[i - 1][j - 1] && res[i + 1][j - 1] 。 然后最后再check res[i][days - 1]是不是全是true, 是的话就代表work
  1. public boolean alibaba(int numCaves, int[] strategy){
  2.         int days = strategy.length;
  3.         boolean[][] res = new boolean[numCaves][days];
  4.         for(int i = 0; i < days; i++){
  5.                 res[strategt[i]][i] = true;
  6.         }


  7.         for(int i = 0; i < numCaves;i++){
  8.                 for(int j = 1; j < days; j++){
  9.                         if(i == numCaves - 1){
  10.                                 res[i][j] = res[i][j] || res[i - 1][j - 1];
  11.                         }else if(i == 0){
  12.                                 res[i][j] = res[i][j] || res[i + 1][j - 1];


  13.                         }else{
  14.                                 res[i][j] = res[i][j] || (res[i - 1][j - 1] &&  res[i + 1][j - 1]);
  15.                         }                                               
  16.                 }
  17.         }

  18.         boolean result = true;
  19.         for(int i = 0; i < numCaves; i++){
  20.                 if(!result){
  21.                         break;
  22.                 }else{
  23.                         result = result && res[i][days - 1];
  24.                 }

  25.         }

  26.        

  27. }
复制代码

补充内容 (2015-5-29 02:29):
刚开始的是res[i][j], 为什么提交了之后变了

补充内容 (2015-5-29 02:30):


补充内容 (2015-5-29 02:33):
忘记写return了

评分

参与人数 1大米 +3 收起 理由
mjq04 + 3 回答的很好!

查看全部评分

回复

使用道具 举报

全局:
有可能有稳赢的吗?就算一个一个扫过去,那马云也可能藏在你旁边的山洞,然后下一天跟你调换位置,所以也会错过啊
回复

使用道具 举报

🔗
xhuaoe 2015-5-28 18:25:43 | 只看该作者
全局:
是说ali的每天的位置必须是前一天位置加减1吗?

最简单的想法就是开一个numCaves大小的数组来保存某一天某个位置是否可到达,然后从第一天开始往后推,如果某一天所有位置都不能到达strategy就是正确的。空间复杂度O(numCaves),每次推需要时间O(numCaves),如果天数为d,总时间O(d * numCaves)。

但如果题意确实如此的话,不可达位置的分布会有规律,所以可能可以优化到常数空间和O(d)时间。
回复

使用道具 举报

🔗
notbad 2015-5-28 19:28:34 | 只看该作者
全局:
感觉可以BFS,分别计算第i天的可能位置,注意需要把strategy[i]从第i天可能的位置删除,如果遍历到某一天i,后发现可能的位置只有strategy[i],则说明必胜,最欢时间复杂度是O(days * numCaves)。
回复

使用道具 举报

🔗
calalia 2015-5-29 00:21:06 | 只看该作者
全局:
我只想说

alibaba是怪兽这个梗 实在是好搞笑好可爱啊n(*≧▽≦*)n
回复

使用道具 举报

🔗
EchoO 2015-5-29 00:47:54 | 只看该作者
全局:
notbad 发表于 2015-5-28 19:28
感觉可以BFS,分别计算第i天的可能位置,注意需要把strategy从第i天可能的位置删除,如果遍历到某一天i,后 ...

请问为什么要“把strategy从第i天可能的位置删除”?

补充内容 (2015-5-29 01:07):
好像get到你的回答了~
回复

使用道具 举报

🔗
mrno5zzz 2015-5-29 02:31:02 | 只看该作者
全局:
mrno5zzz 发表于 2015-5-29 02:28
我觉得可以用res[j] 来表示 第j 天在Cave i能不能捉到马云。如果捉到,则为true, 否则为false。
然后状态 ...

上面文字部分是
  1. res[i][j]
复制代码
回复

使用道具 举报

🔗
ccgogo123 2015-6-24 01:12:31 | 只看该作者
全局:
枚举每天的可能性,因为每天的可能性都是一定的,如果当遇到某一天小偷没地方去了,那么就说明这个序列ok,否则无法找到小偷。
回复

使用道具 举报

🔗
milanelllo13 2015-6-29 03:59:42 | 只看该作者
全局:
请问使用BFS做吗。。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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