一亩三分地论坛

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

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

FB新题求解答

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

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

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

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

x
马上onsite了,看到新题好抓狂。。。。
引用帖子:
第二道题:
面试官说是道新题  finding ali baba. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
就是ali baba是个怪兽,他可能在[0,1, ..., numCaves-1]出现,他每隔一天就要换
一个地方,但他每次只能移左右一格。
然后给你一个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){-google 1point3acres
  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.         }. from: 1point3acres.com/bbs


  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. .1point3acres缃
  14.                         }else{.鐣欏璁哄潧-涓浜-涓夊垎鍦
  15.                                 res[i][j] = res[i][j] || (res[i - 1][j - 1] &&  res[i + 1][j - 1]);
  16.                         }                                               
  17.                 }
  18.         }

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

  26.         }

  27.        

  28. }
复制代码

补充内容 (2015-5-29 02:29): 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
刚开始的是res[j], 为什么提交了之后变了

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


补充内容 (2015-5-29 02:33):-google 1point3acres
忘记写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):
  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). 1point3acres.com/bbs
  10.                 if pos < numCaves - 1:
  11.                         res = res and helper(pos + 1, curr + 1)
    . from: 1point3acres.com/bbs
  12.                 return res
  13.         for i in xrange(numCaves):. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  14.                 if helper(i, 0) is False:. visit 1point3acres.com for more.
  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

查看全部评分

回复 支持 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 | 显示全部楼层
我只想说. 1point 3acres 璁哄潧

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

使用道具 举报

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)。
回复 支持 反对

使用道具 举报

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. 鍥磋鎴戜滑@1point 3 acres
我觉得可以用res[j] 来表示 第j 天在Cave i能不能捉到马云。如果捉到,则为true, 否则为false。
然后状态 ...

上面文字部分是
  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];. From 1point 3acres bbs
  8.                 for(i=1;i<numCaves-1;i++){.1point3acres缃
  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];
  12.                 dp[strategy[j]][j] = true;
  13.         }
  14.         -google 1point3acres
  15.         for(i=0;i<numCaves;i++){
  16.                 if(!dp[i][0]) return false;. 鍥磋鎴戜滑@1point 3 acres
  17.         }
  18.         return true;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  19. }
  20.        
  21. public static void main(String[] args){
  22.         System.out.println(catchAlibaba(3, new int[]{1,1}));. 1point 3acres 璁哄潧
  23.         System.out.println(catchAlibaba(4, new int[]{1,1,2,2,1}));
  24. }
复制代码
回复 支持 反对

使用道具 举报

mjq04 发表于 2016-1-5 10:19:57 | 显示全部楼层
mrno5zzz 发表于 2015-5-29 02:28
我觉得可以用res[j] 来表示 第j 天在Cave i能不能捉到马云。如果捉到,则为true, 否则为false。.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++) {. Waral 鍗氬鏈夋洿澶氭枃绔,
  4.       q.offer(i);
  5.     }
  6.     int day = 0;
  7.     while (!q.isEmpty() && day < strategy.length) {
    . more info on 1point3acres.com
  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;. visit 1point3acres.com for more.
  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]) {
  18.           added[cur + 1] = true;
  19.           q.offer(cur + 1);
  20.         }. From 1point 3acres bbs
  21.       }
  22.       day++;
  23.     }.鐣欏璁哄潧-涓浜-涓夊垎鍦
  24.     return q.isEmpty();
  25.   }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 02:40

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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