Facebook二面跪经。。。

刚面完的facebook二面，一个工作5年的印度小哥，infrastructure组的。。跪的很惨。。特别惨。。第一题瞬秒，follow up的第二题没

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

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

唉，这是最后一个面试了，暑假没地方去了。。。好好学习申研究生去了。。。T T

        public int getMaxValue(int[] nums, int n, int k) {
                int len = nums.length;
        int[] sum = new int[len];
                for(int i = 0; i < len; i++) {
            sum[i] = (i == 0 ? 0 : sum[i-1]) + nums[i];
                }
                if(len <= n * k) return sum[len-1];
                // ask interviewer if the method should return 0 when len < n*k
        int[] prev = new int[len+1];
                for(int i = 1; i <= k; i++) {
            int[] dp = new int[len+1];
                        for(int j = i * n; j <= len; j++) {
                                if(j == i * n) dp[j] = sum[j-1];
                                else dp[j] = Math.max(dp[j-1], sum[j-1] - sum[j-n-1] + prev[j-n]);
                        }
            prev = dp;
                }
                return prev[len];
        }
优化了一下，希望不要再有bug了

這是我的想法，應該和他說的差不多吧@tk1322715， 簡單來說就是3個windows。我以中間的window為基準，往右滑動保持windows的合，然後，每次滑動，左右各用第一題的算法找出左邊最大以及右邊最大的windows合，3個相加后維護最大值，代碼如下：

1. import java.util.*;
   
2. public class Solution {
   
3.     public static void main(String[] args) {
   
4.         int[] nums = new int[]{1,3,7,7,2,1,1,4,8,8,6,1,1,9};
   
5.         System.out.println(maxThreeWindowSum(nums,2));
   
6.     }
   
7. 
   
8.     public static int maxWindowSum(int[] nums, int start, int end, int n) {
   
9.         if (nums == null || end - start+1 < n) throw new IllegalArgumentException();
   
10.         int sum = 0;
    
11.         int max = Integer.MIN_VALUE;
    
12.         Queue<Integer> window = new LinkedList<>();
    
13.         for (int i = start; i <= end ; i++) {
    
14.             if(window.size() < n-1) {
    
15.                 sum+=nums[i];
    
16.                 window.offer(nums[i]);
    
17.             } else {
    
18.                 sum+=nums[i];
    
19.                 window.offer(nums[i]);
    
20.                 max = Math.max(max,sum);
    
21.                 sum-=window.poll();
    
22.             }
    
23.         }
    
24.         return max;
    
25.     }
    
26. 
    
27.     public static int maxThreeWindowSum(int[] nums, int n) {
    
28.         if (nums == null || nums.length < 3*n) throw new IllegalArgumentException();
    
29.         //move the window in the middle and find max window at both side;
    
30.         int max = Integer.MIN_VALUE;
    
31.         int middle = 0;
    
32.         Queue<Integer> window = new LinkedList<>();
    
33.         for (int i = n; i < nums.length-2*n; i++) {
    
34. 
    
35.             if(window.size() < n-1) {
    
36.                 middle+=nums[i];
    
37.                 window.offer(nums[i]);
    
38.             } else {
    
39.                 middle+=nums[i];
    
40.                 window.offer(nums[i]);
    
41.                 int left = maxWindowSum(nums, 0, i-n, n);
    
42.                 int right = maxWindowSum(nums, i+1, nums.length -1, n);
    
43.                 max = Math.max(max, left + middle + right);
    
44.                 middle-=window.poll();
    
45.             }
    
46.         }
    
47.         return max;
    
48.     }
    
49. }

复制代码

补充内容 (2016-3-15 08:29):
時間應該是O(n^2)

补充内容 (2016-3-15 08:36):
33筆誤，應為i < nums.length -n;

public class KWindow{

        // n is the number of consecutives, k is the number of counts
        public int getMaxValue(int[] nums, int n, int k) {
                int len = nums.length;
                for(int i = 1; i < len; i++) {
                        nums[i] += nums[i-1];
                }
                if(len <= n * k) return nums[len-1];
                // ask interviewer if the method should return 0 when len < n*k
                int[][] dp = new int[k+1][len+1];
                for(int i = 1; i <= k; i++) {
                        for(int j = 1; j <= len; j++) {
                                if(j <= n) dp[i][j] = nums[j-1];
                                else dp[i][j] = Math.max(dp[i][j-1], nums[j-1] - nums[j-n-1] + dp[i-1][j-n-1]);
                        }
                }
                return dp[k][len];
        }

        public static void main(String[] args) {
                KWindow window = new KWindow();
                int[] nums = new int[] {1,3,7,7,2,1,1,4,8,8,6,1,1,9};
                int n = 2, k = 3;
                System.out.println(window.getMaxValue(nums, n, k) == 40);
        }
}

各位大神第二题给个思路呗。。。

zhenjieruan 发表于 2016-3-15 06:09
各位大神第二题给个思路呗。。。

我有一个n^2的解法。待会儿用电脑打，期待大神的n解法

tk1322715 发表于 2016-3-15 06:38
我有一个n^2的解法。待会儿用电脑打，期待大神的n解法

我n^2的解法都没想出来。。是不是generate所有可能的non－overlap的combination然后输出最大的那个，但是这个是n^3。。。面试官的意思是n^2最优了。。

第一题需要O(N)吗？还是O(N^2)就行了，你是怎么做的？

wtcupup 发表于 2016-3-15 06:56
第一题需要O(N)吗？还是O(N^2)就行了，你是怎么做的？

第一题O(n)啊，超级简单的，你保持一个deque，size＝k，然后一个currentSum一个maxSum，每次就是pop front，减掉，currentSum加目前数，pushback目前数。代码（面试时候写的，不知道有没有bug）：
int maxSum(vector<int>& a, int k) {
  if (a.size() < k) return -1;
  int currMax = 0, start = a[0],  currSum = 0;
  deque<int> window;
  for (int i = 0; i < k; ++i) {
    window.push_back(a[i]);
    currSum += a[i];
  }
  currMax = currSum;
  for (int i = k ; i < a.size(); ++i) {
    currSum -= window.front();
    window.pop_front();
    currSum += a[i];
    window.push_back(a[i]);
    currMax = ::max(currSum, currMax);
  }
  return currMax;
}

zhenjieruan 发表于 2016-3-15 06:44
我n^2的解法都没想出来。。是不是generate所有可能的non－overlap的combination然后输出最大的那个，但是 ...

大概思路就是设一个变量x,算出0-x之间一个连续n个数求和最大值。 然后在x-size之间算出两个non overlap n numbers 求和的最大值。这一步是o(n)的，所以总的是o(n^2)

zhenjieruan 发表于 2016-3-15 06:59
第一题O(n)啊，超级简单的，你保持一个deque，size＝k，然后一个currentSum一个maxSum，每次就是pop fron ...

这第1题，不就是max subarray sum么？
kadane 算法？

1. public static int maxSubArray(int[] A) {
   
2.     int maxSoFar=A[0], maxcurrent=A[0];
   
3.     for (int i=1;i<A.length;++i){
   
4.         maxcurrent= Math.max(current+A[i],A[i]);
   
5.         maxSoFar=Math.max(maxSoFar, maxcurrent);
   
6.     }
   
7.     return maxSoFar;
   
8. }

复制代码

tk1322715 发表于 2016-3-15 07:08
大概思路就是设一个变量x,算出0-x之间一个连续n个数求和最大值。 然后在x-size之间算出两个non overlap n ...

我理解0-x应该怎么做，但是x－size应该怎么做呢？是分治吗？

xiaozhuxiaozhu 发表于 2016-3-15 07:11
这第1题，不就是max subarray sum么？
kadane 算法？

你的k在哪里？是k个连续数的和最大