Facebook电面

能约的最早的日子已经在国内了，所以就约了加州时间4点开始，也就是今天早上8点的。挺珍惜这个机会的结果就是昨天11点半睡到两点醒了就再也睡不着了。
接电话一听是个三哥，先让做了自我介绍然后开始码题。
第一道check if there

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

in 2d matrix。其实有点像第一题的follow up，把search sum从一维变到二维，subarray变成sub rectangle

ohyline 发表于 2016-1-16 05:16
第二题可以用第一种方法 做成O(n^2)
先算个cumulative matrix （每一个元素就是从左上角到当前元素的sub ...

有个问题哦，为什么sum > target反而要扩大submatrix的范围呢，这时候不是应该缩小吗

1. return subMatrixSum(cumMatrix, 0, 0, 0, 0);
   
2. 
   
3. Map<String, Boolean> dp = new HashMap<String, Boolean>();
   
4. boolean subMatrixSum(int[][] cum, int headi, int headj, int taili, int tailj, int target) {
   
5.         String key = headi + ":" + headj + ":" + taili + ":" + tailj;
   
6.         if (map.containsKey(key)) {
   
7.                 return map.get(key);
   
8.         } else {
   
9.                 boolean res = false;
   
10.                 if (headi < taili || headj < tailj) {
    
11.                         res = false;
    
12.                 } else {
    
13.                         int sum = subsum(cum, headi, headj, taili, tailj);
    
14.                         if (sum == target) {
    
15.                                 res = true;
    
16.                         } else if (sum > target) {
    
17.                                 res = subMatrixSum(cum, headi, headj, taili + 1, tailj, target) || sumMatrixSum(cum, headi, headj, taili, tailj + 1, target);
    
18.                         } else {
    
19.                                 res = sumMatrixSum(cum, headi + 1, headj, taili, tailj) || sumMatrixSum(cum, headi, headj + 1, taili, tailj, target);
    
20.                         }
    
21.                 }
    
22.                 map.put(key, res);
    
23.                 return res;
    
24.         }
    
25. }
    

复制代码

可以用DP优化一下，但是感觉复杂度还是O(n^4)

1. (taili, tailj) * * * * * * * * *
   
2. * * * * * * * * * * * * * * * *
   
3. * * * * * * * * * * * * * * * *
   
4. * * * * * * * * *(headi, headj)
   
5. 
   
6. return subMatrixSum(cumMatrix, 0, 0, 0, 0);
   
7. 
   
8. boolean subMatrixSum(int[][] cum, int headi, int headj, int taili, int tailj, int target) {
   
9.         if (headi < taili || headj < tailj) {
   
10.                 return false;
    
11.         }
    
12.         int sum = subsum(cum, headi, headj, taili, tailj);
    
13.         if (sum == target) {
    
14.                 return true;
    
15.         } else if (sum > target) {
    
16.                 return subMatrixSum(cum, headi, headj, taili + 1, tailj, target) || sumMatrixSum(cum, headi, headj, taili, tailj + 1, target);
    
17.         } else {
    
18.                 return sumMatrixSum(cum, headi + 1, headj, taili, tailj) || sumMatrixSum(cum, headi, headj + 1, taili, tailj, target);
    
19.         }
    
20. }
    

复制代码

重排一下前面的代码

擦。。摸摸谭神

好难啊。。follow-up有什么解法么0.0

lz有消息了吗

http://www.geeksforgeeks.org/find-subarray-with-given-sum/
第一题是这个？

搞个map 存一下子数组的和，算到sum[j]的时候，看看 满足sum[j] - sum[i]的值是不是出现过。
二维，类似。。扫一遍，存[0][0]到[i][j],然后加加减减,算出来子矩阵的和。。就是写起来 麻烦  二维的应该不用 写代码

楼主， 我刚刚跟你遇到了完全一样的情况！！！题目一样， 三哥也一样。没啥耐心，第二题你做出来了么，我只写出了bruteforce（On^4）。。。被鄙视了啊 你结果出来了么

Howie 发表于 2016-1-13 17:16
http://www.geeksforgeeks.org/find-subarray-with-given-sum/
第一题是这个？

第一题类似吧，主要是要考虑sum = 0的时候的边界条件

ohyline 发表于 2016-1-15 05:40
楼主， 我刚刚跟你遇到了完全一样的情况！！！题目一样， 三哥也一样。没啥耐心，第二题你做出来了么，我只 ...

第二题不知道有啥好方法。到现在没结果早就不抱希望了

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies