一亩三分地论坛

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

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

Facebook二面跪经。。。

[复制链接] |试试Instant~ |关注本帖
zhenjieruan 发表于 2016-3-15 06:06:20 | 显示全部楼层 |阅读模式

2015(1-3月) 码农类 本科 实习@Facebook - 校园招聘会 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
刚面完的facebook二面,一个工作5年的印度小哥,infrastructure组的。。跪的很惨。。特别惨。。第一题瞬秒,follow up的第二题没写完。。。第一题:给一个array,给一个数字n,找出n个连续数字which和最大。. visit 1point3acres.com for more.
第二题:给一个array,给一个数字n,找出3个不overlap的n个连续数字使得和最大,比如说给 1 3 7 7 2 1 1 4 8 8 6 1 1 9,结果就是1 3 (7 7) 2 1 1 (4 8) (8 6) 1 1 9,输出他们的和。. visit 1point3acres.com for more.

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

评分

1

查看全部评分

nuanuan1208 发表于 2016-3-15 11:39:35 | 显示全部楼层
        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了
回复 支持 2 反对 0

使用道具 举报

nuanuan1208 发表于 2016-3-15 09:27:30 | 显示全部楼层
public class KWindow{
. From 1point 3acres bbs
        // 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);
        }
}
回复 支持 1 反对 0

使用道具 举报

guschen802 发表于 2016-3-15 08:28:12 | 显示全部楼层
這是我的想法,應該和他說的差不多吧@tk1322715, 簡單來說就是3個windows。我以中間的window為基準,往右滑動保持windows的合,然後,每次滑動,左右各用第一題的算法找出左邊最大以及右邊最大的windows合,3個相加后維護最大值,代碼如下:

  1. import java.util.*;
    .1point3acres缃
  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));. Waral 鍗氬鏈夋洿澶氭枃绔,
  6.     }
  7. . from: 1point3acres.com/bbs
  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];.1point3acres缃
  19.                 window.offer(nums[i]);
  20.                 max = Math.max(max,sum);
  21.                 sum-=window.poll();
  22.             }
  23.         }
  24.         return max;
  25.     }

  26.     public static int maxThreeWindowSum(int[] nums, int n) {
  27.         if (nums == null || nums.length < 3*n) throw new IllegalArgumentException();
  28.         //move the window in the middle and find max window at both side;
  29.         int max = Integer.MIN_VALUE;
  30.         int middle = 0;
  31.         Queue<Integer> window = new LinkedList<>();. 1point3acres.com/bbs
  32.         for (int i = n; i < nums.length-2*n; i++) {

  33.             if(window.size() < n-1) {
  34.                 middle+=nums[i];
  35.                 window.offer(nums[i]);
  36.             } else {
  37.                 middle+=nums[i];
  38.                 window.offer(nums[i]);
  39.                 int left = maxWindowSum(nums, 0, i-n, n);
  40.                 int right = maxWindowSum(nums, i+1, nums.length -1, n);. from: 1point3acres.com/bbs
  41.                 max = Math.max(max, left + middle + right);
  42.                 middle-=window.poll();
  43.             }
  44.         }
  45.         return max;. from: 1point3acres.com/bbs
  46.     }
  47. }
复制代码


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

补充内容 (2016-3-15 08:36):
33筆誤,應為i < nums.length -n;
回复 支持 1 反对 0

使用道具 举报

guschen802 发表于 2016-3-15 09:17:14 | 显示全部楼层
wtcupup 发表于 2016-3-15 09:15
请问你的代码第41行,求i左边的maxWindowSum为什么不是i-1而是i-n?

因為 i 指的是 當前中間windows的最後一位,不是第一位,所以左邊的邊界是 i-n,也就是中間windows的左邊界
代碼33行有筆誤,可能會造成無解,看最下面補充
回复 支持 1 反对 0

使用道具 举报

 楼主| zhenjieruan 发表于 2016-3-15 06:09:49 | 显示全部楼层
各位大神第二题给个思路呗。。。
回复 支持 反对

使用道具 举报

tk1322715 发表于 2016-3-15 06:38:11 | 显示全部楼层
zhenjieruan 发表于 2016-3-15 06:09
各位大神第二题给个思路呗。。。
.鐣欏璁哄潧-涓浜-涓夊垎鍦
我有一个n^2的解法。待会儿用电脑打,期待大神的n解法
回复 支持 反对

使用道具 举报

 楼主| zhenjieruan 发表于 2016-3-15 06:44:42 | 显示全部楼层
tk1322715 发表于 2016-3-15 06:38
我有一个n^2的解法。待会儿用电脑打,期待大神的n解法

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

使用道具 举报

wtcupup 发表于 2016-3-15 06:56:12 | 显示全部楼层
第一题需要O(N)吗?还是O(N^2)就行了,你是怎么做的?
回复 支持 反对

使用道具 举报

 楼主| zhenjieruan 发表于 2016-3-15 06:59:23 | 显示全部楼层
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);.鐣欏璁哄潧-涓浜-涓夊垎鍦
    currSum += a;
  }
  currMax = currSum;
  for (int i = k ; i < a.size(); ++i) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
    currSum -= window.front();
    window.pop_front();
    currSum += a;. 1point 3acres 璁哄潧
    window.push_back(a);
    currMax = ::max(currSum, currMax);
  }. more info on 1point3acres.com
  return currMax;
}
回复 支持 反对

使用道具 举报

tk1322715 发表于 2016-3-15 07:08:28 | 显示全部楼层
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)
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-3-15 07:11:57 | 显示全部楼层
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. }
复制代码
回复 支持 反对

使用道具 举报

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

我理解0-x应该怎么做,但是x-size应该怎么做呢?是分治吗?
回复 支持 反对

使用道具 举报

 楼主| zhenjieruan 发表于 2016-3-15 07:15:33 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-3-15 07:11
这第1题,不就是max subarray sum么?
kadane 算法?

你的k在哪里?是k个连续数的和最大
回复 支持 反对

使用道具 举报

tk1322715 发表于 2016-3-15 07:31:31 | 显示全部楼层
zhenjieruan 发表于 2016-3-15 07:14
我理解0-x应该怎么做,但是x-size应该怎么做呢?是分治吗?

你设一个y,从x-size跑一遍,算出从x-y最大的n个连续数的和。然后让y从size-x倒着跑一遍算出y-size之间最大的n个连续数的和。然后再正向跑一遍得到y左边和右边加起来最大的和。总共跑了三遍。所以是o(n)
回复 支持 反对

使用道具 举报

 楼主| zhenjieruan 发表于 2016-3-15 07:35:39 | 显示全部楼层
tk1322715 发表于 2016-3-15 07:31.鏈枃鍘熷垱鑷1point3acres璁哄潧
你设一个y,从x-size跑一遍,算出从x-y最大的n个连续数的和。然后让y从size-x倒着跑一遍算出y-size之间最 ...

ok ok,让我想起了programming pearl里的一个算法,谢谢大神了!
回复 支持 反对

使用道具 举报

 楼主| zhenjieruan 发表于 2016-3-15 07:36:46 | 显示全部楼层
tk1322715 发表于 2016-3-15 07:31
你设一个y,从x-size跑一遍,算出从x-y最大的n个连续数的和。然后让y从size-x倒着跑一遍算出y-size之间最 ...

Sorry,如果问题有点多。。这个x和y怎么选择?是选k吗?肯定得比k大吧
回复 支持 反对

使用道具 举报

tk1322715 发表于 2016-3-15 07:42:09 | 显示全部楼层
zhenjieruan 发表于 2016-3-15 07:36
Sorry,如果问题有点多。。这个x和y怎么选择?是选k吗?肯定得比k大吧

大概就是x从0到size, y就是从x到size. 真正写的话还有corner case,具体的值就得看你是怎么实现的了。
回复 支持 反对

使用道具 举报

novice00 发表于 2016-3-15 07:42:27 | 显示全部楼层
分享一个我的想法,用的是dp, 可以把3换成其他数字,时间复杂度 3*n,空间3*n,但是空间可以优化到n.鏈枃鍘熷垱鑷1point3acres璁哄潧
    int maxSum(int[] array, int n) {
        int len = array.length;
        //sum[i] 是数组 array[i] 到 array[i+n-1] 的和
        int[] sum = new int[len - n + 1];
        int curSum = 0;
        for (int i = 0; i < len; i++) {
            if (i < n - 1) curSum += array[i];
            else {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                curSum += array[i];. Waral 鍗氬鏈夋洿澶氭枃绔,
                sum[i - n + 1] = curSum;
                curSum -= array[i - n + 1];
            }.鏈枃鍘熷垱鑷1point3acres璁哄潧
        }
        int[][] dp = new int[3][sum.length];
        /*
         * dp[i][j] 的意思是,sum[j]之前的i个不overlap的n个array中连续数字的
         * 最大和+sum[j],所以basecase dp[0]就是sum数组本身
         */.鏈枃鍘熷垱鑷1point3acres璁哄潧
        for (int i = 0; i < sum.length; i++) {
            dp[0][i] = sum[i];
        }
      
        for (int i = 1; i < 3; i++) {
            int curMax = 0;. 1point 3acres 璁哄潧
            for (int j = 0; j < sum.length; j++) {
                if (j - i * n < 0) continue;
                curMax = curMax > dp[i-1][j - i * n] ? curMax : dp[i-1][j - i * n];
                dp[i][j] = curMax + sum[j];. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
            }
-google 1point3acres        }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
        int max = 0;
        for (int j = 0; j < sum.length; j++) {
            max = max > dp[2][j] ? max : dp[2][j];
        }. From 1point 3acres bbs
        return max;. from: 1point3acres.com/bbs
    } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

代码写的匆忙可能有bug,欢迎大家讨论
回复 支持 反对

使用道具 举报

tk1322715 发表于 2016-3-15 08:34:48 | 显示全部楼层
novice00 发表于 2016-3-15 07:42
分享一个我的想法,用的是dp, 可以把3换成其他数字,时间复杂度 3*n,空间3*n,但是空间可以优化到n
     ...

层主看了你的答案。我感觉可能有点不对的地方。
curMax = curMax > dp[i-1][j - i * n] ? curMax : dp[i-1][j - i * n];
dp[j] = curMax + sum[j];
这两行代买我有点疑惑。
根据你的定义,dp[i-1][j - i * n] =sum[j - i * n]之前的i个不overlap的n个array中连续数字的最大和 + sum(j - i*n);.1point3acres缃
那这个sum(j- i * n) 所代表的连续n个数可能和后面的sum(j)重合。然后你之后dp[j]又加一次sum[j]。我感觉就有可能加错了。
回复 支持 反对

使用道具 举报

tk1322715 发表于 2016-3-15 08:40:41 | 显示全部楼层
guschen802 发表于 2016-3-15 08:28
這是我的想法,應該和他說的差不多吧@tk1322715, 簡單來說就是3個windows。我以中間的window為基準,往右 ...

厉害厉害。哈哈,感觉这道题能有leetcode的hard里偏简单的。而且实现起来可能还有很多小技巧。不然的话代码可能会很乱。
回复 支持 反对

使用道具 举报

guschen802 发表于 2016-3-15 09:00:56 | 显示全部楼层
tk1322715 发表于 2016-3-15 08:40
厉害厉害。哈哈,感觉这道题能有leetcode的hard里偏简单的。而且实现起来可能还有很多小技巧。不然的话代 ...

我覺得還能再優化,每次左右都有重複的搜索,如果能保存歷史的話,例如左邊,每多一個數字,組成一個新的window,和歷史最大比就好,不用從頭開始掃..不過想想就覺得有點複雜
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-3-15 09:15:07 | 显示全部楼层
guschen802 发表于 2016-3-15 09:00
我覺得還能再優化,每次左右都有重複的搜索,如果能保存歷史的話,例如左邊,每多一個數字,組成一個新的 ...

请问你的代码第41行,求i左边的maxWindowSum为什么不是i-1而是i-n?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 13:07

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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