近期论坛无法登录的解决方案


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 4328|回复: 36
收起左侧

Facebook二面跪经。。。

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

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

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

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

x
刚面完的facebook二面,一个工作5年的印度小哥,infrastructure组的。。跪的很惨。。特别惨。。第一题瞬秒,follow up的第二题没写完。。。第一题:给一个array,给一个数字n,找出n个连续数字which和最大。
第二题:给一个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,输出他们的和。

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

评分

1

查看全部评分

nuanuan1208 发表于 2016-3-15 11:39:35 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
        public int getMaxValue(int[] nums, int n, int k) {
                int len = nums.length;
. 鍥磋鎴戜滑@1point 3 acres        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];.鏈枃鍘熷垱鑷1point3acres璁哄潧
                // 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];
. 1point 3acres 璁哄潧                        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]);. Waral 鍗氬鏈夋洿澶氭枃绔,
                        }
            prev = dp;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                }
                return prev[len];
        }
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴优化了一下,希望不要再有bug了
回复 支持 2 反对 0

使用道具 举报

nuanuan1208 发表于 2016-3-15 09:27:30 | 显示全部楼层
关注一亩三分地微博:
Warald
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]; . 鍥磋鎴戜滑@1point 3 acres
                // 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]);
. from: 1point3acres.com/bbs                         }
                }
                return dp[k][len];
        }

        public static void main(String[] args) {
                KWindow window = new KWindow();. from: 1point3acres.com/bbs
                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.*;
  2. public class Solution {
  3.     public static void main(String[] args) {. 1point 3acres 璁哄潧
  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.     public static int maxWindowSum(int[] nums, int start, int end, int n) {.1point3acres缃
  8.         if (nums == null || end - start+1 < n) throw new IllegalArgumentException();. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  9.         int sum = 0;
  10.         int max = Integer.MIN_VALUE;
  11.         Queue<Integer> window = new LinkedList<>();
  12.         for (int i = start; i <= end ; i++) {
  13.             if(window.size() < n-1) {
  14.                 sum+=nums[i];
  15.                 window.offer(nums[i]);
  16.             } else {
  17.                 sum+=nums[i];
  18.                 window.offer(nums[i]);
  19.                 max = Math.max(max,sum);
  20.                 sum-=window.poll();
  21.             }
  22.         }
  23.         return max;
  24.     }

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

  32.             if(window.size() < n-1) {
  33.                 middle+=nums[i];
  34.                 window.offer(nums[i]);
  35.             } else {
  36.                 middle+=nums[i];
  37.                 window.offer(nums[i]);
  38.                 int left = maxWindowSum(nums, 0, i-n, n);
  39.                 int right = maxWindowSum(nums, i+1, nums.length -1, n);. Waral 鍗氬鏈夋洿澶氭枃绔,
  40.                 max = Math.max(max, left + middle + right);
  41.                 middle-=window.poll();
  42.             }
  43.         }
  44.         return max;
  45.     }
  46. }
复制代码

. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
补充内容 (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. 鍥磋鎴戜滑@1point 3 acres
请问你的代码第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. more info on 1point3acres.com
我有一个n^2的解法。待会儿用电脑打,期待大神的n解法
.1point3acres缃
我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
. From 1point 3acres bbs第一题需要O(N)吗?还是O(N^2)就行了,你是怎么做的?
. more info on 1point3acres.com
第一题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;.1point3acres缃
  }
  currMax = currSum;
  for (int i = k ; i < a.size(); ++i) {
    currSum -= window.front();
    window.pop_front();
    currSum += a;. more info on 1point3acres.com
    window.push_back(a);
    currMax = ::max(currSum, currMax);
  }
  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 ...
.鏈枃鍘熷垱鑷1point3acres璁哄潧
这第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.     }. 1point 3acres 璁哄潧
  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-google 1point3acres
我理解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
你设一个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
    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];
                sum[i - n + 1] = curSum;
                curSum -= array[i - n + 1];. from: 1point3acres.com/bbs
            }
        }
        int[][] dp = new int[3][sum.length];
        /*
         * dp[i][j] 的意思是,sum[j]之前的i个不overlap的n个array中连续数字的.1point3acres缃
         * 最大和+sum[j],所以basecase dp[0]就是sum数组本身 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
         */. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
        for (int i = 0; i < sum.length; i++) {
            dp[0][i] = sum[i];
        }
      
        for (int i = 1; i < 3; i++) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
            int curMax = 0;
            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];
            }
        }
        int max = 0;
        for (int j = 0; j < sum.length; j++) {
            max = max > dp[2][j] ? max : dp[2][j];. Waral 鍗氬鏈夋洿澶氭枃绔,
        }
        return max;
    }.1point3acres缃

代码写的匆忙可能有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];. 鍥磋鎴戜滑@1point 3 acres
这两行代买我有点疑惑。
根据你的定义,dp[i-1][j - i * n] =sum[j - i * n]之前的i个不overlap的n个array中连续数字的最大和 + sum(j - i*n);. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
那这个sum(j- i * n) 所代表的连续n个数可能和后面的sum(j)重合。然后你之后dp[j]又加一次sum[j]。我感觉就有可能加错了。
回复 支持 反对

使用道具 举报

tk1322715 发表于 2016-3-15 08:40:41 | 显示全部楼层
guschen802 发表于 2016-3-15 08:28. more info on 1point3acres.com
這是我的想法,應該和他說的差不多吧@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?
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-6-23 06:33

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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