eBay新鲜面经

格格笑 发表于 2017-11-14 23:53
backend  烙印黑的飞起来~

感谢楼主分享，能问一下就是backend组么，还是sre

1. int result = Integer.MIN_VALUE;
   
2.                 for (int i = 0; i < n - k; i++) {
   
3.                         int currMax = nums[i];
   
4.                         for (int j = i + 1; j < i + k; j++) {
   
5.                                 currMax = Math.max(nums[i], currMax + nums[j]);
   
6.                                 result = Math.max(result, currMax);
   
7.                         }
   
8.                 }

复制代码

只想到了nk的解法

求问面的是哪个组的backend

抄的geeks for geeks 烙印解法，o(n)
public class LongestSubArrayHavingSumK {
         public static int atMostSum(int[] nums,int k){
         int sum = 0;
         int cnt = 0, maxcnt = 0;
         for (int i = 0; i < nums.length; i++) {
             if ((sum + nums[i]) <= k) {
                 sum += nums[i];
                 cnt++;
             }
             else if(sum!=0){
                 sum = sum - nums[i - cnt] + nums[i];
             }
             maxcnt = Math.max(cnt, maxcnt);
         }
         return maxcnt;
     }

     public static void main(String[] args){
         int[] nums = { 1, 2, 1, 0, 1, 1, 0 };
         int k = 4;
         System.out.print(atMostSum(nums,k));
     }
}

翻到自己这页，给大家发个我当时写的完整版吧 233

import java.util.*;

public class eBayIllustration{
    public static void main(String[] args) {
        int[] input = new int[]{10, 30, -40, 3};
        eBayIllustration sol = new eBayIllustration();
        int[] res = sol.maxSubarrayAtMostK(input, 2);
        if (res == null) {
            System.out.println("no one was selected");
        } else {
            System.out.println(res[0] + "~" + res[1]);
        }
    }

    // basically, my idea is maintain a deque to contains currently valid min value
    // valid means the min value must be in the scope of k from current i
    // Time: O(N)
    // Space: O(N)
    public int[] maxSubarrayAtMostK(int[] input, int k) {
        if (input == null || input.length == 0) {
            return new int[0];
        }
        // Preprocessing
        // nums[i]  represents the sum : input[0] + ... input[i - 1]
        int[] nums = new int[input.length + 1];
        for (int i = 1; i < nums.length; i++) {
            nums[i] = nums[i - 1] + input[i - 1];
        }
        Deque<Integer> deque = new LinkedList<>();
        int max = 0;
        int[] candidate = null;
        for (int i = 0; i < nums.length; i++) {
            while (!deque.isEmpty() && nums[deque.peekLast()] >= nums[i]) {
                deque.pollLast();
            }
            deque.addLast(i);
            // out of scope
            if (deque.peekFirst() < i - k) {
                deque.pollFirst();
            }
            // if better subarray appear, update the result/candidate
            if (nums[i] - nums[deque.peekFirst()] > max) {
                max = nums[i] - nums[deque.peekFirst()];
                candidate = new int[]{deque.peekFirst(), i - 1}; //inclusive idx
            }
        }
        return candidate;// e.g  [1,3] 1 means the left bound 3 means the right bound of the subarray of input, bothe left and right bound are inclusive.
    }
}

楼主这题是 莉蔻 上 尔三舅 么？
Sliding Window Maximum

是道hard