Facebook二面跪经。。。

nuanuan1208 发表于 2016-3-15 09:27
public class KWindow{

        // n is the number of consecutives, k is the number of counts

我靠！膜拜大神！！！

tk1322715 发表于 2016-3-15 08:34
层主看了你的答案。我感觉可能有点不对的地方。
curMax = curMax > dp[j - i * n] ? curMax : dp[j - i  ...

代码确实有点问题，应该是
curMax = curMax > dp[i-1][j - n] ? curMax : dp[i-1][j - n];

O(N) implement
-------
def max3window(arr, n):
    X = len(arr)
    if n * 3 > X: return -1 # impossible
    dp = [-0x80000000] * X
    dp[n-1] = sum(arr[:n]) # sum first n elements
    print  dp
    for i in range(n, X):
        print "---", dp[i-1]
        dp[i] = dp[i-1] + arr[i] - arr[i-n]
    # move 2nd window
    max_v = -0x80000000 # very small
    for i in range(2*n-1, X-n):
        left = dp[n-1:i-n+1]
        right = dp[i+n:]
        print left, right
        sum_v = max(left) + dp[i] + max(right)
        max_v = max(max_v, sum_v)
    return max_v

arr = [1, 3, 7, 7, 2, 1, 1, 4, 8, 8, 6, 1, 1, 9]
print max3window(arr, 2)

第一题不用queue写了一下

1. def findSum(nums, n):
   
2.     currentSum, maxSum = 0, 0
   
3.     for i in xrange(len(nums)):
   
4.          currentSum += nums[i]
   
5.          if n: n-=1
   
6.          else: currentSum -= nums[i-n]
   
7.          maxSum = max(maxSum, currentSum)
   
8.     return maxSum

复制代码

ericLaw 发表于 2016-3-16 13:28
第一题不用queue写了一下

有个bug，maxSum 应该初始成 -float('INF')

nuanuan1208 发表于 2016-3-15 11:39
public int getMaxValue(int[] nums, int n, int k) {
                int len = nums.length;
        int[] sum = n ...

拜大神，拜大神，

2.
假设window size M, f(nums[], M)就是第一问的解， O(M)
dp[i, j] 表示，nums[0...i] 里求j个的最大和, dp[i, j] = Math.max(dp[k, j-1] + f(nums[k+1...j], M)) (where  (k+1) >= (j-1)*M  且  (j-k) >= M)，然后填表row by row就行，最后dp[nums.length-1, 3]就是答案， 假设f的cost O(M)看做常数，整个的cost就是O(mn)

nuanuan1208 发表于 2016-3-15 11:39
public int getMaxValue(int[] nums, int n, int k) {
                int len = nums.length;
        int[] sum = n ...

谢lz
惊为天人..

楼主加油