The first step in the Indeed Software Engineering Full time interview is an online screening. The question asked is a typical hackerrank question. Typically, there is an online timer ticking and after 1 hour the interview is not available anymore.

Question

Given an array of integers, find the maximum consecutive elements whose sum is less than a given value, k.

Solution

The solution to this problem is pretty straightforward. The problem becomes simpler once you realize that this question can be solved using a sliding window. If the window is smaller than k, we know that we can still get a maximum. Hence we add an integer to the window. If the window is greater than k, we realize that the first element might be the element that is making the window bigger hence we need to remove the first element. The Big O of this solution is O(n).

The solution is as follows:

public static int maximumSum(int[] array, int t){
    int maxSum = 0;
    int curSum = 0;
    int start = 0;
    int end = 0;
    while(start < array.length){
        if(curSum > maxSum && curSum <= t){
            maxSum = curSum;
        }
        if(curSum <= t && end < array.length){
            curSum += array[end];
            end += 1;
        }
        else{
            curSum -= array[start];
            start+= 1;
        }
    }
    return maxSum;
}