一亩三分地论坛

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

FB新题求解答

[复制链接] |试试Instant~ |关注本帖
yuxrose 发表于 2015-5-28 13:53:04 | 显示全部楼层 |阅读模式

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

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

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

x
马上onsite了,看到新题好抓狂。。。。
引用帖子:
第二道题:. from: 1point3acres.com/bbs
面试官说是道新题  finding ali baba
就是ali baba是个怪兽,他可能在[0,1, ..., numCaves-1]出现,他每隔一天就要换. more info on 1point3acres.com
一个地方,但他每次只能移左右一格。
然后给你一个strategy[]数组,数组里面是猜测每天ali baba的位置。如果里面有一个
猜中了,这个strategy就是正确的。.鐣欏璁哄潧-涓浜-涓夊垎鍦
问题就是让你写一个判断函数 alibaba(int numCaves, int[] strategy)来判别这个
strategy数组是不是稳赢的策略。写完后问时间复杂度,然后问了下大概怎么样可以优
化~~~

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

评分

3

查看全部评分

本帖被以下淘专辑推荐:

mrno5zzz 发表于 2015-5-29 02:28:45 | 显示全部楼层
我觉得可以用res[j] 来表示 第j 天在Cave i能不能捉到马云。如果捉到,则为true, 否则为false。
然后状态转换方程就是res[j] = res[j] || res[i - 1][j - 1] && res[i + 1][j - 1] 。 然后最后再check res[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.         }. 鍥磋鎴戜滑@1point 3 acres


  7.         for(int i = 0; i < numCaves;i++){
  8.                 for(int j = 1; j < days; j++){. more info on 1point3acres.com
  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. . From 1point 3acres bbs
  14. . 1point 3acres 璁哄潧
  15.                         }else{
  16.                                 res[i][j] = res[i][j] || (res[i - 1][j - 1] &&  res[i + 1][j - 1]);
  17.                         }                                               
  18.                 }
  19.         }

  20.         boolean result = true;
  21.         for(int i = 0; i < numCaves; i++){
  22.                 if(!result){
  23.                         break;
  24.                 }else{
  25.                         result = result && res[i][days - 1];. 1point3acres.com/bbs
  26.                 }.1point3acres缃
  27. . more info on 1point3acres.com
  28.         }

  29.        
  30. . 1point 3acres 璁哄潧
  31. }
复制代码
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
补充内容 (2015-5-29 02:29):
刚开始的是res[j], 为什么提交了之后变了

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


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

评分

1

查看全部评分

回复 支持 3 反对 0

使用道具 举报

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):. more info on 1point3acres.com
  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. 1point 3acres 璁哄潧
  16.         return True
复制代码
由于我们要稳赢,所以对于原问题helper(pos, curr),它的解依赖于helper(pos - 1, curr + 1)(对应往左跳一格,如果可以的话)与上helper(pos + 1, curr + 1)(同理,往右一格)。然后我们对于ali所在的每个位置都算一遍就好了。
. from: 1point3acres.com/bbs
按照这样的设计方式,我们很快就能看出有许多的重复计算,所以可以加上cache,这样时间复杂度就是O(numCaves * len(strategy))。如果你改成bottom up的计算方式,就是直接填表,那么注意状态间的依赖方式,我们可以使用滚动数组,这样空间就可以从O(numCaves * len(strategy))优化到O(numCaves)。

评分

2

查看全部评分

回复 支持 3 反对 0

使用道具 举报

kinggarden2001 发表于 2016-1-9 08:09:51 | 显示全部楼层
我在想一个稳赢的策略是不是就是从头开始每天往右猜一步到最后一个位置,这样迟早能碰到?
回复 支持 0 反对 1

使用道具 举报

lancelot981 发表于 2016-2-5 11:50:42 | 显示全部楼层
有可能有稳赢的吗?就算一个一个扫过去,那马云也可能藏在你旁边的山洞,然后下一天跟你调换位置,所以也会错过啊
回复 支持 1 反对 0

使用道具 举报

ccgogo123 发表于 2015-7-4 11:05:45 | 显示全部楼层
milanelllo13 发表于 2015-6-29 04:27. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
觉得楼上的DP是对的。。。

Let's define a boolean array of the length n as pos. If pos is true, it means alibaba can be in the ith house at this moment. For each day, we update the pos. If we find that there is no where alibaba can be, it turns out to be successful.
回复 支持 1 反对 0

使用道具 举报

ccgogo123 发表于 2015-6-24 01:12:31 | 显示全部楼层
枚举每天的可能性,因为每天的可能性都是一定的,如果当遇到某一天小偷没地方去了,那么就说明这个序列ok,否则无法找到小偷。
回复 支持 1 反对 0

使用道具 举报

calalia 发表于 2015-5-29 00:21:06 | 显示全部楼层
我只想说

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

使用道具 举报

xhuaoe 发表于 2015-5-28 18:25:43 | 显示全部楼层
是说ali的每天的位置必须是前一天位置加减1吗?
-google 1point3acres
最简单的想法就是开一个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)。
回复 支持 反对

使用道具 举报

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。
然后状态 ...
.鏈枃鍘熷垱鑷1point3acres璁哄潧
上面文字部分是
  1. res[i][j]
复制代码
回复 支持 反对

使用道具 举报

milanelllo13 发表于 2015-6-29 03:59:42 | 显示全部楼层
请问使用BFS做吗。。
回复 支持 反对

使用道具 举报

milanelllo13 发表于 2015-6-29 04:23:38 | 显示全部楼层
感觉DFS可以。。
回复 支持 反对

使用道具 举报

milanelllo13 发表于 2015-6-29 04:27:35 | 显示全部楼层
觉得楼上的DP是对的。。。
回复 支持 反对

使用道具 举报

milanelllo13 发表于 2015-7-4 11:08:46 | 显示全部楼层
ccgogo123 发表于 2015-7-4 11:05
Let's define a boolean array of the length n as pos. If pos is true, it means alibaba can be in th ...

终于明白了!太感谢了~!!!
回复 支持 反对

使用道具 举报

mlfma 发表于 2015-9-30 06:34:57 | 显示全部楼层
有没有方法可以找一个稳赢的策略?
回复 支持 反对

使用道具 举报

nothingtrouble 发表于 2015-10-31 04:21:28 | 显示全部楼层
ryancooper 发表于 2015-5-28 23:01
这道其实是老题了,之前就有出现过。很快这道题就会放到leetcode上的,你到时可以去试试。对于这道题,既然 ...

牛, 根据你的思路,写了个bottomup的dp
  1. public static boolean catchAlibaba(int numCaves, int[] strategy){
  2.         int i,j,l=strategy.length;
  3.         boolean[][] dp = new boolean[numCaves][l];
  4.         dp[strategy[l-1]][l-1] = true;
  5.        
  6.         for(j=l-2;j>=0;j--){
  7.                 dp[0][j] = dp[1][j+1];
  8.                 for(i=1;i<numCaves-1;i++){
  9.                         dp[i][j] = dp[i-1][j+1] && dp[i+1][j+1];
  10.                 }
  11.                 dp[numCaves-1][j] = dp[numCaves-2][j+1];.1point3acres缃
  12.                 dp[strategy[j]][j] = true;
  13.         }. more info on 1point3acres.com
  14.         鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  15.         for(i=0;i<numCaves;i++){
  16.                 if(!dp[i][0]) return false;
  17.         }
  18.         return true;
  19. }
  20.        
  21. public static void main(String[] args){
  22.         System.out.println(catchAlibaba(3, new int[]{1,1}));
  23.         System.out.println(catchAlibaba(4, new int[]{1,1,2,2,1}));-google 1point3acres
  24. }
复制代码
回复 支持 反对

使用道具 举报

mjq04 发表于 2016-1-5 10:19:57 | 显示全部楼层
mrno5zzz 发表于 2015-5-29 02:28
我觉得可以用res[j] 来表示 第j 天在Cave i能不能捉到马云。如果捉到,则为true, 否则为false。
然后状态 ...
-google 1point3acres
层主代码横纵坐标貌似搞反了,用例子:{1, 1, 2, 2, 2, 2, 1}, 4个cave。 跑不过去
回复 支持 反对

使用道具 举报

dummyshooter 发表于 2016-1-7 03:50:07 | 显示全部楼层
notbad 发表于 2015-5-28 19:28
感觉可以BFS,分别计算第i天的可能位置,注意需要把strategy从第i天可能的位置删除,如果遍历到某一天i,后 ...

I think your solution is right.
回复 支持 反对

使用道具 举报

eonian 发表于 2016-1-11 12:17:44 | 显示全部楼层
bfs的方法~
  1. public boolean canFindAlibaba(int numCaves, int[] strategy) {
  2.     Queue<Integer> q = new LinkedList<>();
  3.     for (int i = 0; i < numCaves; i++) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  4.       q.offer(i);
  5.     }
  6.     int day = 0;
  7.     while (!q.isEmpty() && day < strategy.length) {
  8.       int size = q.size();
  9.       boolean[] added = new boolean[numCaves];
  10.       for (int i = 0; i < size; i++) {
  11.         int cur = q.poll();
  12.         if (cur == strategy[day]) continue;
  13.         if (cur - 1 >= 0 && !added[cur - 1]) {
  14.           added[cur - 1] = true;
  15.           q.offer(cur - 1);
  16.         }
  17.         if (cur + 1 < numCaves && !added[cur + 1]) {. more info on 1point3acres.com
  18.           added[cur + 1] = true;
  19.           q.offer(cur + 1);
  20.         }
  21.       }
  22.       day++;
  23.     }
  24.     return q.isEmpty();. visit 1point3acres.com for more.
  25.   }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-12-14 03:04

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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