Google Interview Question for Software Engineer / Developers


Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
7
of 7 vote

The "SLIDING WINDOW" proposed by ninhnnsoc is a great idea. But his answer is not the best.
Basically, "SLIDING WINDOW" has four key attributes:
1) window_sum: sum of all numbers in the window.
2) wL: left index of the window, initialized to be 0;
3) wR: right index of the window, initialized to be 0, also;
4) minimum_sequence_length: the final answer, initialized to be INT_MAX;

The algorithm is basically a while-loop.
while (wR < array_size) {
Move_wR(); // Find the next wR, window_sum > S;
Move_wL(); // Remove unnecessary left numbers;
UpdateMinimumSequenceLength();
}

//Note the window_sum should always larger than S, except:
1) in the initialization phase.
2) There is no solution to the question, (minimum_sequence_length == INT_MAX)

- xuyan.nus May 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thanks.

- xyz May 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thanks for providing a better answer. Your basic while-loop is really nice!

One thing I was concerned is how to work with negative numbers. (My implementation does).

Your answer can also deal with negative numbers, with a bit elaboration.

- ninhnnsoc May 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Hi, ninhnnsoc, Thanks, It is a lot fun to code here.
I append the Logic in Move_wR():
1) At least move +1 to the right.
2) If array[wR] < 0, (negative), keep going to the right.
("negative numbers in boundary" never be a solution, so no need to check)
3) If window_sum < 0, start a new window. wR + 1 and wL = wR;
(It means "The left side will never be part of a solution", so drop the numbers and strat over)

- xuyan.nus May 06, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

how about move_wL(), is there anything to clarify?

- ninhnnsoc May 06, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

move_wR() guarantees that window_sum > S, the responsibility of move_wL() is to shrink the left side to find the minimum size.
It is exactly the same with your solution. hah

- xuyan.nus May 06, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

/* here is the code
n is number of elements in array
wl is left boundry of minimum sequence initailly passed as zero
wr is right boundry of minimum sequence initailly passed as zero
S is the given sum
*/

void find_Minseq(int arr[],int n,int *wl,int *wr, int s)
{
	int i;
	int l=*wl;
	int r=*wr;
	int sum=0;
	int min=n+1;
	for(i=0;i<n;i++)
	{
		sum =sum+arr[i];
		if(sum<0)
		{
			sum=0;
			l=i+1;
			continue;
		}
		if(sum<=s)
		{
			r=i;
			continue;
		}
		else
		{
			while(sum>s && l<=i)
			{
				sum=sum-arr[l];
				l++;
			}
			l--;
			r=i;
			sum=sum+arr[l];
		}
		if(min>(r-l+1) && sum>s)
		{
			*wl=l;
			*wr=r;
			min=*wr-*wl+1;
		}
	}
}

- sandeep May 06, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

what if the input sum is negative?

- Anonymous May 08, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Implementation below - it seems to work fine.

int shortestSq(int A[], int n, int target) {
	int minLen=INT_MAX;
	int sum=A[0], left=0, right=0, len=1;
	// initialize
	while(sum<target) {
		right++;
		len++;
		sum+=A[right];
	}
	minLen=min(minLen, len);
	// sliding window
	while(right<n) {
		right++; sum+=A[right]; len++;
		while(sum-A[left]>=target) {
			left++; sum-=A[left]; len--;
		}
		minLen=min(minLen, len);
	}
	return minLen;
}

- Shiyu Luo August 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

// minseq.java

public static int findMinSequence(int[] a, int v)
{
    int i, j, sum;
    i = j = sum = 0;
    int min = Integer.MAX_VALUE;

    while (j < a.length) {
        if (a[j] > v) {
            min = 1;
            break;
        }
        
        sum += a[j];
        
        if (sum < 0 || sum > v) {
            
            if (sum > v) {
                min = Math.min(min, ((j - i) + 1));
            } else if (sum < 0 && a[j] < 0) {
                 j++;
            }
            
            sum = 0;
            i = j;
            continue;
        }
        
        j++;
    }

    return min;
}

- mbyta August 18, 2014 | Flag
Comment hidden because of low score. Click to expand.
3
of 3 vote

I have an idea, using SLIDING WINDOW: I use a "window" from index wL to wR to slide on the array, while keeping track of its sum and the minimum window size that satisfied sum > S.

While the sum of numbers inside the window is not greater than S, slide the right side (wR++). At any moment, while the sum is greater than S, record the minimum so far and then slide into the left side (wL++).

This takes O(n) since the window is always sliding into 1 direction (left to right), which stops at most O(n) steps.

This works for array with negative values as well.

O(n) time, O(1) space.

EDITED:
It doesn't work for negative values, AS WELL!

EDITED (2nd time): For negative values:

If the sum is <=0 at position v, then start new window at v+1;

If the sum is <=S: sliding the right side wR++;

If the sum is >S: try to shrink the left side to find the minimum size.

Please see my code below and tell if it doesn't work. Thanks!

- ninhnnsoc April 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Sorry man, but I don't think it works well for negative values. Think of such case: arr[] = {-1, 1} and threshold = 0. The result should be 1, but according to your algorithm:
(1)at first winleft = 0, winright = 0, winsum = arr[0] = -1.
(2)winsum < threshold, so we slide to right, ++winright.
(3)now winsum = winsum + arr[1] = 0 <= threshold, yet we can not slide to right any more, so there exists no such sequence.

- uuuouou April 21, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

thanks!
I edited my post.

- ninhnnsoc April 21, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

How about this:

I try to expand the window to the right, but if at any position, say v, the sum become non-positive, I skip all the current window and start a NEW window at position v+1.

If the sum is > S:
I try to shrink the window by sliding the left side wL++ iteratively, to find the minimum size.

- ninhnnsoc April 21, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I found it complicated for negative case.

Any one can fix it?

- ninhnnsoc April 21, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

This can work for NEGATIVE values:

#include <iostream>

using namespace std;

int main()
{
    const int Nmax = 10;
    int Arr[Nmax];

    int n = 6; //size of input Arr;
    Arr = {7, -3, 8, 4, 13,-5};
    int S = 15;

    int Sum = Arr[0];
    int wR = 0, wL = 0;
    int minSize = n+10;


    while(true){// make sure that Arr[wL] and Arr[wR] are positive.
        if (Sum<=0 and wR <n){
            wR++;
            wL = wR;
            Sum = Arr[wR];
            continue;
        };

        if (Sum <=S and wR<n){
            wR++;
            Sum += Arr[wR];
            continue;
        };

        if (Sum>S){
            minSize = min(minSize, wR-wL);
            Sum -= Arr[wL];wL++;

            while(Arr[wL] <=0 and wL < wR){
                Sum -= Arr[wL];
                wL++;
                if (Sum>S){
                    minSize = min(minSize, wR-wL);
                }
            };
        };
        if (wR>=n) break;
    };

    if (minSize>n) cout <<"No solution"<<endl;
    else cout <<"minimum sequence length is "<<minSize+1<<endl;

    return 0;

}

- ninhnnsoc April 21, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Great job! That was beautiful :-)

- iroodaz April 21, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi uuuouou and iroodaz:

Please look at my code and tell if it's wrong.
Thanks!

- ninhnnsoc April 21, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

This does the trick in your code:

// make sure that Arr[wL] and Arr[wR] are positive.

Nice one!
Couldn't find a bad test case for the code.

- iroodaz April 21, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Arr[] = {2, 1, 1, 4, 3, 1, 4} Sum = 6

your code will give answer 4 = (2,1,1,4)
because wr will be 3 after it has find the above answer. Now wl will also become 3 in the inside while loop, sum becomes 0 and when outside loop starts wr =4.

Answer should be 2 = (4,3)

correct me if I am wrong?

- Anonymous April 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

oops...for the above input it will give output 3 = {3, 1, 4} which is still wrong.

- Anonymous April 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It's really a good answer.
However, since you want to solve negative input at the same time, you might want to handle the solution when S < 0 ?
For example, S= -5, array is {-1}, the result should be 1.
I guess that is asking too much :P

- babula April 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

I ran your program.

int n = 7; //size of input Arr;
int Arr[] = {2, 1, 1, 4, 0, 1, 4};
int S = 6;

It gives answer 3 which is wrong.

- Anonymous April 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@babula: I think the case S < 0 is trivial to handle, isn't it?

Or do you mean the case when S<0 and we need to find a sequence that its sum is LESS THAN S? For this, we can do the same, except that we need to negate all the numbers (including S) first. Right?

- ninhnnsoc May 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@ Anonymous: Please double-check!

- ninhnnsoc May 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

package com.google.practice;

public class Subseqsum {
	public static void main(String[] arg){
		int[] a =  { 1, 2, 3, 4, -10, -2 };
		int sum = 8;
		
		findMinSeq(a,sum);
	}
	
	public static void findMinSeq(int[] a, int sum){
		int minSoFar = Integer.MAX_VALUE;
		int start=0,end=0;
		int pStart=0,pEnd=0;
		int seqSum = 0;
		while(true){
			
			if(end<a.length)
			seqSum = seqSum + a[end];
			
			if(seqSum<=sum){
				//no need check anymore
				if(end==a.length-1)
					break;
				end++;
			}
			else{
				//if sequence length is shorter than previously found
				if(end-start < minSoFar){
					minSoFar = end - start;
					pStart = start;
					pEnd = end;
				}
				seqSum = seqSum - a[start] - a[end];
				start++;
			}
			
			//another term condition when all sequence is checked
			if(end==a.length-1 && start == a.length){
				break;
			}
		}
		if(minSoFar>a.length)
			System.out.println("no subsequence");
		else{
			System.out.print("{");
			for(int i=pStart;i<=pEnd;i++){
				System.out.print(" "+a[i]);
			}
			System.out.print(" }");
		}
	}
}

start and end move n positions each. O(n+n) = O(n)

- AlgoAlgae April 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

public int MiniArray(int num[], int max)
{
	int i=0;
	int j=0;

	for(int i =0; i<num.len(); i++ )
		if num[i] >max
			return 1;

	//for length of a sub array is greater than 1
	for( i = 1; i<num.len(); i++)
		for( j=0; j<=num.len() - i +1; j++)
		{
			a[j] += a[j+i]; //add the next integer on right side
			if( a[j] > max )
				return i+ 1;
		}

	return 0; // if there is no such a sub array;

}

- Mike Lu April 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

I am not sure why you assume that the question ask for the sequence with the lowest sum above threshold and not the one with the min length.

- grandGodessXXX April 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

assuming ur response is to my solution, the lowest sum above the threshold would make sure that the window is minimal in length. Just pick the window with the minimal size and that is your answer. I think its elaborate enough for you to understand now!!

- mayankme0077 April 27, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I was referring to the original post.

mayankme0077,
min length and lowest sequence above the bound is two different things. Your solution is broken for both.
It does not return lowest seq : gives {15} for {2, 1, -7, 7, 15},6 instead of 7.
It also does not return the shortest seq: gives {2, -7, 7, 5 } for {2,-7, 7, 5},6 instead of 7.

All the best.

- grandGodessXXX April 27, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Good question!
I think if we can check for all possible windows, then just record whatever minimum we want.
Depends on which question is asked, we have to adjust accordingly.

- ninhnnsoc May 06, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

n^2 algorithm is straight forward I think. I don't know if I can come up with a DP one. Incidentally, does anyone know if brute force is good enough for a phone interview?

private void findMinSequenceWithSum(int[] array, int input) {
	Tuple<int, int> minRange = null;
	for (int i = 0; i < array.Length; i++) {
		int sum = 0;
		for (int j = i; j < array.Length; j++) {
			sum = sum + array[j];
			if (sum > input) {
				Tuple<int, int> range = new Tuple<int, int>(i, j);
				if (this.isRangeSmaller(range, minRange)) {
					minRange = range;
				}
				break;
			}
		}
	}
}

private bool isRangeSmaller(Tuple<int, int> source, Tuple<int, int> target) {
	if (source == null) {
		return false;
	}
	if (target == null) {
		return true;
	}
	return (source.Item2 - source.Item1 < target.Item2 - target.Item1);
}

- tejaswi.yvs April 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 4 vote

int minSeq(int ar[], int n, int sum)
{
	int sumL = 0;
	for(int i = 0; i < n; i++)
		sumL += ar[i];
	int minSeq = n;
	if (sumL < sum)
		return 0;
	int front = 0, end = n-1;
	while(sumL > sum)
	{
		if(ar[front] < ar[end])
		{
			front++;
			sumL -= ar[front - 1];
		}
		else 
		{
			end--;
			sumL -= ar[end + 1];
		}
		minSeq--;
	}
	return ++minSeq;
}

O(n) solution taking off min of the end of arrays.

- Anonymous April 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can it work for negative values?

- ninhnnsoc April 21, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Doesn't work for: { 1, 2, 3, 4, -10, -2, 22 },7, 10
O/P is 4 should be 3

- Anonymous April 21, 2014 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 votes

I think this gets caught on large numbers even if they're all positive. With array = {4, 4, 1, 1, 5} and sum = 7, the loop will move the front of the window and conclude {4, 1, 1, 5} is the min sequence of length 4. When {4, 4} is the min.

- Ev April 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

def min_seq(vector, sum):
    result = None
    left = 0
    workSum = 0
    right = 0
    resultInterval = (None, None)
    for right in range(0, len(vector)):
        workSum += vector[right]
        if workSum > sum:
            if result == None:
                result = right - left
                resultInterval = (left, right)
            while left < right-1 and workSum > sum:
                if workSum - vector[left] > sum:
                    workSum -= vector[left]
                    left +=1
                else:
                    break
            if left != right and right-left < result:
                result = right-left
                resultInterval = (left, right)

    return result+1, resultInterval

print(min_seq((1, 1, 7, 1, 7, 3, 2, 3, 8, 0, 0), 8))
(2, (4, 5))

- Pepper April 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public void minSeq(int [] a, int sum){
		int k = a.length;
		int temp = 0;
		
		for(int i = 0; i < k-1 ; i++){			
			for(int j = 0; j <k; j++){				
				temp = a[i] + a[j];				
				if((temp > sum) && ((j-i)==1)){
					System.out.println("pair found "+a[i]+" and "+a[j]);
				 }			  
			}
		}

}

- Job April 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

On solution

import java.io.*;
import java.util.*;

public class Qs5653018213089280 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);

        int N = Integer.parseInt(br.readLine());
        int[] A = new int[N];
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; ++i)
            A[i] = Integer.parseInt(st.nextToken());

        int S = Integer.parseInt(br.readLine());

        int i = 0;
        int j = 0;
        int temp = 0;
        int count = 0;
        int minCount = N+1;
        int startIndex = -1;

        while(j < N) {
            temp += A[j];
            j++;
            
            while (temp > S && i <= j) {
                if (minCount > j-i) {
                    minCount = j-i;
                    startIndex = i;
                }
                temp -= A[i];
                i++;
            }
        }

        if (minCount == N+1)
            out.println(-1);
        else
            out.println(minCount);

        out.flush();
        out.close();

        System.exit(0);
    }
}

- srikantaggarwal April 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What is the Big-O notation for this? Since you iterate array at most 2 times, it will be 2n, so O(n)?

- soodongStudying April 26, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int functions(int[] a, sum){
        arrays.sort(a);    sort  O(nlogn)
         Int count;
         int last = length-1;   // the maximum in the array

          for(int i=length-2;i>-1;i++){
              if(a[i]+a[last]<=sum){
                 count++;
              }
          }

          return count;

}

- pchomphoosang April 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Hi dude,

You are not supposed to sort the array, it should remain as the original order. Check the question dude.

- mikezebin April 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int functions(int[] a, sum){
arrays.sort(a); sort O(nlogn)
Int count;
int last = length-1; // the maximum in the array

for(int i=length-2;i>-1;i++){
if(a[i]+a[last]<=sum){
count++;
}
}

return count;

}

- pchomphoosang April 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int smallestNumberOfAdjacentValuesAddingUpToMoreThanGivenInteger(int array[], int arrayLength, int testInt){
  int candidate = 0;
  int retVal = arrayLength;
  if (arrayLength > 0) {
    int sum = 0;
    for (int idx = 0; idx < arrayLength; idx++) {
      if (array[idx] > testInt) { // instant winner
        return 1;
      }else{
        candidate++;
        sum += array[idx]; // add next item
        if (sum > testInt) { // see if we can shorten
          while ((sum - array[idx - (candidate - 1)]) > testInt) {
            sum -= array[idx - --candidate];
          }
          retVal = MIN(candidate, retVal);
        }
      }
    }
  }
  return retVal;
}

- Ben April 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

removing the post as I misunderstood the problem. thanks srini

- biswajit.86 April 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

After heapification, the order of the elements is lost. Isn't it?

- srini April 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

n^2 algorithm. works with negatives

public class SmallestSequence {

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        List<Integer> variables = new ArrayList<Integer>();
        int sum = Integer.parseInt(s.nextLine());
        while(s.hasNextLine()) {
            String input = s.nextLine();
            if(input.equals("exit")) {
                break;
            }
            else {
                variables.add(Integer.parseInt(input));
            }

        }
        /// all the variables are now in the array
        int counter = 0;
        int smallestSequence = Integer.MAX_VALUE;
        for(int i = 0; i <  variables.size(); i++) {
            counter = 1;
            int total = variables.get(i);
            if(total > sum) {
                smallestSequence = 1;
                break;
            }
            for(int j = i + 1; j < variables.size(); j++) {
                total += variables.get(j);
                counter++;
                if(total > sum) {
                    if(counter < smallestSequence) {
                        smallestSequence = counter;
                    }
                    break;
                }
            }

        }
        System.out.println(smallestSequence);
        s.close();
    }

}

- evonsdesigns April 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

just noticed this doesnt handle zero case

- evonsdesigns April 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

int min_seq_larger_than_sum(vector<int> &a, int sum){
    int L = 0, R = 0, tempSum = a[0], minSeq = INT_MAX;
    while(R < a.size()){
        if (tempSum > sum){
            minSeq = min(R-L+1, minSeq);
            tempSum -= a[L];
            L++;
        } else{
            R++;
            if (R < a.size()){
                tempSum += a[R];
            }else break;
        }
    }
    return (minSeq == INT_MAX? -1: minSeq);
}

- Jie Feng April 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def min_subseq(arr, tgt):
  running_sum = 0
  stop_idx = 0
  start_idx = 0
  arr_len = len(arr)
  min_len = arr_len

  while start_idx < arr_len:
    # move right edge
    while running_sum <= tgt and stop_idx < arr_len:
        running_sum += arr[stop_idx]
        stop_idx += 1
   
    if stop_idx == arr_len and running_sum <= tgt:
       min_len = 0

    if running_sum  > tgt:
      cur_min_len = stop_idx - start_idx
      if cur_min_len < min_len:
        min_len = cur_min_len
    running_sum -= arr[start_idx]
    # move left edge
    start_idx += 1
   
  return min_len

- Anonymous April 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

def min_subseq(arr, tgt):
  running_sum = 0
  stop_idx = 0
  start_idx = 0
  arr_len = len(arr)
  min_len = arr_len

  while start_idx < arr_len:
    # move right edge
    while running_sum <= tgt and stop_idx < arr_len:
        running_sum += arr[stop_idx]
        stop_idx += 1
   
    if stop_idx == arr_len and running_sum <= tgt:
       min_len = 0

    if running_sum  > tgt:
      cur_min_len = stop_idx - start_idx
      if cur_min_len < min_len:
        min_len = cur_min_len
    running_sum -= arr[start_idx]
    # move left edge
    start_idx += 1
   
  return min_len

assert min_subseq([2,1,1,3,4, 6], 8) == 2 
assert min_subseq([0, 0, 0, 0, 0], 1) == 0
assert min_subseq([2, 1, -1, 4], 3) == 1

- avidprog4982 April 25, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

// 2,1,1,4,3,6
// sum = 8

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;

struct window {
	int l;
	int r;
	int s;
};

typedef struct window window_t;
int main () {
	window_t w, ans;
	int A[] = {2, 1, 1, 4, 0, 1, 4};
	int sum = 6;
	int len_a = sizeof(A)/sizeof(int);
	memset(&w, 0, sizeof(w));
	// set window
	while (w.s <= sum) {
		w.s += A[w.r];
		w.r++;
	}
	w.r--;
	// set window from behind
	while (w.s > sum) {
		w.s -= A[w.l];
		w.l++;
	}
	w.l--;
	w.s += A[w.l];
	int min_l = w.r - w.l + 1;
	memcpy(&ans, &w, sizeof(w));
	for (int i = w.r+1; i < len_a; i++) {
		w.s += A[i];
		w.r++;
		while (w.s > sum) {
			w.s -= A[w.l];
			w.l++;
		}
		w.l--;
		w.s += A[w.l];
		if (min_l > w.r - w.l + 1) {
			memcpy(&ans, &w, sizeof(w));
			min_l = w.r - w.l + 1;
		}
	}	
	printf ("l = %d, r = %d, s = %d, min_l = %d\n", ans.l, ans.r, ans.s, min_l);
	printf ("The corresponding elements in the sequence are : {");
	for (int i = ans.l; i <= ans.r; i++) printf ("%d, ", A[i]);
	printf("}\n"); 
}

Right now my code maintains the invariant that the sum inside the window after every iteration is greater than the given sum and is the window is "tight" from both the ends.

This solution won't work for negative numbers as the invariant fails in that case. There should be a simple modification to maintain that invariant. I will update soon.

EDIT :
This modification maintains the invariant as mentioned above and the solution should work for negative numbers as well.

// 2,1,1,4,3,6
// sum = 8

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;

struct window {
	int l;
	int r;
	int s;
};

typedef struct window window_t;
int main () {
	window_t w, ans;
	int A[] = {2, 1, 1, 4, 0, 1, 4};
	int sum = 6;
	int len_a = sizeof(A)/sizeof(int);
	memset(&w, 0, sizeof(w));
	// set window from the front
	while (w.s <= sum) {
		w.s += A[w.r];
		w.r++;
	}
	w.r--;
	// set window from behind
	while (w.s > sum) {
		w.s -= A[w.l];
		w.l++;
	}
	w.l--;
	w.s += A[w.l];
	int min_l = w.r - w.l + 1;
	memcpy(&ans, &w, sizeof(w));
	for (int i = w.r+1; i < len_a; i++) {
		w.s += A[i];
		w.r++;
		if (w.s <= sum) {
			// we encountered a negative number which reduces w.s to become smaller than/ equal to sum
			// keep adding numbers until you are able to make sure that w.s > sum
			while (w.s <= sum) {
				w.s += A[w.r];
				w.r++;
				i++;
			}
			w.r--;
			i--;
		}
		while (w.s > sum) {
			w.s -= A[w.l];
			w.l++;
		}
		w.l--;
		w.s += A[w.l];
		if (min_l > w.r - w.l + 1) {
			memcpy(&ans, &w, sizeof(w));
			min_l = w.r - w.l + 1;
		}
	}	
	printf ("l = %d, r = %d, s = %d, min_l = %d\n", ans.l, ans.r, ans.s, min_l);
	printf ("The corresponding elements in the sequence are : {");
	for (int i = ans.l; i <= ans.r; i++) printf ("%d, ", A[i]);
	printf("}\n"); 
}

- mayankme0077 April 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

That said this is the solution to what you are trying to do in nlong.
You are not expected to understand this.

#include <vector>
#include <iostream>
#include <limits>
#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <iterator>
#include <sstream>
#include <iomanip>

using namespace std; 

struct point_t
{
  int sum;
  vector<int>::iterator pos;
  bool operator<( const point_t& p) const { return sum < p.sum || ( !(sum > p.sum) && pos > p.pos); } // last point of min sum
};

vector<int> upper_bound_range(  vector<int> v, int min_sum)
{ 
  if ( v.empty() ) 
      return v;
  v.push_back(0); //dummy
  partial_sum( v.rbegin(), v.rend(), v.rbegin() );
  
  set<point_t> prev;
  auto begin_best = v.begin(), end_best = v.begin();
  int best_diff = numeric_limits<int>::max();
  
  for (auto i=v.begin(); i != v.end(); ++i)
  {
      auto j = prev.lower_bound( point_t{*i, i}); // last point j so that sum[j,i) is the lowest possible sum above min_sum  
      int diff = j->sum - *i;
      if ( j != prev.end() &&  (diff < best_diff || (diff == best_diff && i - j->pos < end_best-begin_best))) 
	begin_best = j->pos, end_best = i , best_diff = j->sum - *i;
      prev.insert( point_t{ *i - min_sum - 1, i} );
  }
  
  adjacent_difference( v.rbegin(), v.rend(), v.rbegin() );
  return vector<int>( begin_best, end_best); 
}

string v2str( const vector<int>& v)
{
  stringstream ss;
  ostream_iterator<int> out_it ( ss, " ");
  copy( v.begin(), v.end(), out_it); 
  return ss.str();
}

int main()
{   
  vector< pair< vector<int>, int> > cases =  {  
       /*vector*/		      /*min_sum*/
    { { 2,1,1,4,3,6 },			8},
    { {4, 4, 1, 1, 5},			7},
    { {2, 1, 1, 4, 3, 1, 4},		6},
    { { 1, 2, 3, 4, -10, -2, 22 }, 	10},
    { {2, 1, 1, 4, 0, 1, 4},            6},
  };
    
  for (auto vp : cases)
  { 
         auto result = upper_bound_range(vp.first, vp.second);        
	 cout << setw(20) << v2str(vp.first)  << " exp.sum=" << setw(5) << vp.second << " res=" << setw(20) << v2str(result) 
	      << " sum=" << accumulate(result.begin(), result.end(), 0) << endl;
  }
}

- grandGodessXXX April 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

arr = [2,1,1,4,3,6]
sum=8
s = []
for i in range(sum+1):
	s.append(1000)
s[0] = 0
for i in range(sum+1):
	for j in arr:
		if j<=i and s[i-j]+1<s[i]:
			s[i] = s[i-j]+1
print s[sum]

python code with O(n^2) dynamic programming

- dp April 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This code runs in O(n) time and O(1) space:

public int GetSequence(int[] arr, int sum)
        {
            if (arr.Length == 0)
                return -1;
            if (arr.Length == 1)
            {
                if (arr[0] < sum)
                    return -1;
                else
                {
                    return 1;
                }
            }
            int total = arr.Sum();
            if(total < sum)
            {
                return -1;
            }
            //Make a window initially with the full length of the array, then shrink it step by step
            int startIndex = 0;
            int lastIndex = arr.Length - 1;
            while (total > sum && lastIndex > startIndex)
            {
                if (arr[startIndex] > arr[lastIndex])
                {
                    if (total - arr[lastIndex] < sum)
                    {
                        return lastIndex - startIndex + 1;
                    }
                    total -= arr[lastIndex--];
                }
                else if (arr[startIndex] < arr[lastIndex])
                {
                    if (total - arr[startIndex] < sum)
                    {
                        return lastIndex - startIndex + 1;
                    }
                    total -= arr[startIndex++];
                }
                else
                {
                    if (total - arr[startIndex] < sum)
                    {
                        return lastIndex - startIndex + 1;
                    }
                    //Find the next minimum
                    if (lastIndex - startIndex > 1)
                    {
                        if (arr[lastIndex - 1] > arr[startIndex + 1])
                        {
                            total -= arr[startIndex++];
                        }
                        else
                        {
                            total -= arr[lastIndex--];
                        }
                    }
                }
            }
            return -1; //Error happened
        }

- Sehs April 30, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package examples.algorithms;

import java.util.Arrays;

public class FindMinSequenceWithSum {
	public static void main( String[] args )
    {
        int arr[] = {0,-2,-1,-4,-6,-1,4,-1,1,2,9};
        int sum = 0;
        int lastIndex=-1;
        int firstIndex=0;
        int noOfElements=Integer.MAX_VALUE;
        
        for(int i=0;i<arr.length;i++){
        	int lastIndexInLoop = findMinSeq(arr,i,sum);
        	if(((lastIndexInLoop != -1) && (noOfElements>lastIndexInLoop-i))){
        		noOfElements=lastIndexInLoop-i;
        		lastIndex=lastIndexInLoop;
        		firstIndex=i;
        	}
        }
        if(lastIndex==-1){
        	System.out.println("Sum not found");
        }else{
        	if((firstIndex==lastIndex) || ((lastIndex+1 == arr.length))){
        		lastIndex=lastIndex+1;
        	}
        	System.out.println("min sequence is:"+Arrays.toString(Arrays.copyOfRange(arr, firstIndex, lastIndex)));
        }
    }
	
	public static int findMinSeq(int arr[], int startIndex, int sum){
		int temp = arr[startIndex];
		int tempIndex = startIndex;
        for(int i=startIndex+1; i<arr.length; i++){
        	tempIndex = i;
        	if(temp==sum){
    			break;
        	}else{
        		temp+=arr[i];
        	}
        }
    	if(temp==sum){
    		return tempIndex;
    	}
        return -1;
	}
}

- sari April 30, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

discard above code. it is printing the set numbers that equals sum not greater than sum which is asked in the question.

- sari May 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class MakeSumUseMinElements {
    public static void main(String[] args){
//        int[] A= {2,1,1,4,3,6};
        int[] A={7, -3, 8, 4, 13,-5};
        int n=A.length;
        int sum=15,cSum=0;
        int wl=0,wr=0;
        int i=0;
        int minLen=Integer.MAX_VALUE;
        while(true){
            if(cSum<=sum && wr<n){
                cSum=cSum+A[wr++];
                }
            else if(cSum>sum && wl<n){
                minLen=min(minLen,wr-wl);
                while(cSum>sum){
                    cSum=cSum-A[wl++];
                    if(cSum>sum)
                    minLen=min(minLen,wr-wl);
                    }
                }
            else 
                break;
            }
        if(minLen==Integer.MAX_VALUE)
            System.out.println("No solution exists");
        else
            System.out.println("Min Length Seq is "+minLen);
        }
    
    public static int min(int a, int b){
        return a<b ? a : b;
        }

}

- Anonymous May 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*
n is number of elements in array
wl is left boundry of minimum sequence initailly passed as zero
wr is right boundry of minimum sequence initailly passed as zero
S is the given sum
*/

void find_Minseq(int arr[],int n,int *wl,int *wr, int s)
{
int i;
int l=*wl;
int r=*wr;
int sum=0;
int min=n+1;
for(i=0;i<n;i++)
{
sum =sum+arr[i];
if(sum<0)
{
sum=0;
l=i+1;
continue;
}
if(sum<=s)
{
r=i;
continue;
}
else
{
while(sum>s && l<=i)
{
sum=sum-arr[l];
l++;
}
l--;
r=i;
sum=sum+arr[l];
}
if(min>(r-l+1) && sum>s)
{
*wl=l;
*wr=r;
min=*wr-*wl+1;
}
}
}

- sandeep May 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class MinWindow {
	
	private static int array[] = {2,1,3,5,3,-6,-6,3};
	// private static int array[] = {-2,-9,-3,-5,-3,-6,-6,-3};
	
	public MinWindow(){
		
	}
	
	public static void main(String[] args){
		int wl =0, wr = 0;
		int min_length = Integer.MAX_VALUE; // a large number
		int sum = 0;
		int check = 8;
		while(wr < array.length){
			if(check < 0 && array[wr] < check){
				wl = ++wr;
				sum = 0;
			}
			else{
			    sum += array[wr];
			    
			    while(sum > check){
			    	int len = wr-wl+1;
				    if(len <  min_length){
					    min_length = len;
				    }
				    System.out.println(wl+","+wr+","+min_length);
				    sum -= array[wl];
				    wl++;
			    }
			     wr++;
		    }
		}
		System.out.println(""+min_length);
	}


}

- Anonymous May 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def minadjsum(n, arr=[1,2,3,5,6,7,8,9]):
    #sliding windows
    for size in range(len(arr)):
        for index in range(len(arr)):
            if sum(arr[index:index+size]) > n:
                return arr[index:index+size]
    return False
print minadjsum(10)

- Peerakit May 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static int getMinimumSequence(int[] inp, int sum)
	{
		int left=0,right=0,min=Integer.MAX_VALUE;
		int[] cummInp=new int[inp.length];
		cummInp[0]=inp[0];
		for(int i=1; i < inp.length;i++)
			cummInp[i]=cummInp[i-1]+inp[i];
		
		while(right < inp.length)
		{
			if(cummInp[right]-cummInp[left] >= sum)
			{
				min=Math.min(min, (right-left));
				if(left==right)
					right++;
				else
					left++;
			}else{
				if(left==right)
					right++;
				else if(left+1 < cummInp.length && cummInp[left+1] < cummInp[left])
					left++;
				else
					right++;
			}
		}
		return min;
	}

- Dinesh June 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int main(){

int arr[] = {2,1,1,4,3,6,5,7,3,18,3,5,7};


int sum = 0;
int minstart = 0;
int minseq = 0,i,tempminseq;


for(i=0;i<sizeof(arr);i++){

// k = 0;
tempminseq = 0;
sum = 0;
while((sum < 18) &&((i+tempminseq) < sizeof(arr)){

sum+= arr[i+tempminseq];
tempminseq++;
}

if((tempminseq < minseq ) || (minseq == 0)){

minseq = tempminseq;
minstart = i;

}


}

printf(" minstart %d minseq %d ",minstart,minseq);
tempminseq = 0;
for(i = minstart;i<sizeof(arr);i++){
printf(" %d ",arr[i]);

tempminseq++;
if(tempminseq >= minseq)
break;

}

return 0;


}

- Kuch June 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class MinSequenceSumAboveTarget {

	static void identifyMinSequenceSumAboveTarget(int arr[], int target){
		int size = arr.length;
		
		int currSum=0;
		int currWindowStart=0;
		int currSolnStart=-1, currSolnEnd=-1;
		
		int begin=0;
		while(begin < size){
			int x = arr[begin]+currSum; 
			if(x > 0){
				if(x<target){
					currSum = x;
				} else {
					// keep moving start if sum keeps above target
					while(x-arr[currWindowStart] >= target){
						x -= arr[currWindowStart];
						currWindowStart++;
					}
					if((currSolnStart==-1) || ((begin-currWindowStart) < (currSolnEnd - currSolnStart))){
						currSolnStart=currWindowStart;
						currSolnEnd=begin;			
					}
					currSum = x;
				}
			}
			begin++;
		}
		
		if(currSolnStart>=0){
			System.out.println("Best solution\t"+currSolnStart + " -> " + currSolnEnd);
		}
	}
	
	public static void main(String[] args) throws Exception{
		int testcase[] = { 1,2,1,1,4,3,6 };
		int target = 8;
		
		System.out.println(Arrays.toString(testcase));
		identifyMinSequenceSumAboveTarget(testcase, target);
		
		int testcase2[] = { 1,2,9,1,1,4,3,6 };
		int target2 = 9;

		System.out.println(Arrays.toString(testcase2));
		identifyMinSequenceSumAboveTarget(testcase2, target2);

	}
}

- just_do_it July 30, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n) solution

int min_len(const vector<int>& v, int sum) {
  int curr_sum = 0;
  int len = INT_MAX;
  for (int i = 0, back = 0; i < v.size(); i++) {
    curr_sum += v[i];
    while (curr_sum > sum) {
      if (len > i - back + 1)
        len = i - back + 1;
      curr_sum -= v[back];
      back++;
    }
  }
  return len;
}

- zprogd August 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int[] a= {2,1,1,4,3,9};
int min = 50;

for(int i = 0 ; i < a.length;i++)
{
int sum = 0;
int count = 0;
for (int j = i; j< a.length ; j ++)
{
count = count + 1;
sum = sum + a[j];
if(sum>8 && count < min)
{
min = count;
break;
}
}
}
System.out.println(min);

- anonymous September 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

worst case complexity will N^2 but in general it will be less than that

findminseq(arr, sum)
{
  int minsequeence = Integer.Max;
  for(int i=0;i<arr.length;i++)
  {
    minsequence = Minimum(findminseq(arr, sum-arr[i], i+1) - i + 1, minsequence);
  }
  return minsequeence;
}

findminseq(arr, sum, index)
{
  for(int i=index;i<arr.length;i++)
  {
    if(arr[i]-sum>=0)
      return index;
    else
      return findminsequence(arr, sum-arr[i], i+1);
  }
  return Integer.Max;
}

- aditya.eagle059 February 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>
#include <limits.h>

/// to find the solution, we need a start and end index.
/// lets first assume the start index is 0. then we can
/// find the end index by going over the array and stop
/// at the position where the sum of all previous #s are
/// greater than the sum.
//
/// once we reach this. it makes no sense to go forward
/// more as that will increase the sequence length.
/// so we try to adjust the start index.
///
/// as we are shrinking the start index, we do seqsum - a[s].
/// NOTE. there is some sort of dynamic programming going on here.
/// as when we shrink the start index, we do NOT recompute the seqsum
/// for the entire subsequence, instead we only factor in the
/// delta, i.e. a decrease of 1 element.
///
/// we will eventually run into when the seqsum falls below sum.
/// when this happens, we need to increase the end index.
///
//////////////////////////////////
/// WHY DOES THIS WORK ?       ///
//////////////////////////////////
///
/// we are essentially computing for every start index, whats the
/// best end index we can have.
///
/// e.g. a[] = {2,1,1,4,3,6} target sum = 8.
///
/// we first try to find end index for startindex = 0. endindex is 4
/// here as 2+1+1+4+3>8.
///
/// now what about startindex=1, if endindex is 4. seqsum is 1+1+4+3=9>8
///
/// now what about startindex=2, if endindex is 4, seqsum is 1+4+3=8==8
/// so we need to increase endindex.
///
/// Everytime we move startindex, we have a O(1) cost to recompute seqsum.
/// so Time Complexity O(n) && Space complexity O(1).
///
/// Below is the implementation.
///
int minsum_length(int *a, int size, int sum) {
    int minlen = INT_MAX;
    int s=0,e=0;
    int seqsum = 0;
    for(s=0;s<size;++s) {
       while(1) {
           /// current seqsum still bigger than sum. update minlen ?
           if (seqsum > sum) {
              minlen = minlen > (e-s) ? (e-s) : minlen;
              break;
           }
           /// current seqsum falls below sum. need to see whether we can.
           /// advance e.
           if (e<size)
              seqsum += a[e++];
           else
              break;
       }
       /// advancing start index. kick out current start element.
       seqsum-=a[s];
    }
    return minlen;
}

int main() {
   int a[] = {2,1,1,4,3,6};
   printf("%d\n", minsum_length(a, sizeof(a)/sizeof(a[0]), 8));
   return 0;
}

- trent.tong May 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

C++ solution, O(n^2):

#include <vector>
#include <array>
#include <limits>
#include <iostream>

using std::vector;
using std::array;
using uint = unsigned int;

// Returns UINT_MAX if none is found
uint minAdjacentSeq(const vector<uint> &a, uint n) {
  uint minSpan = std::numeric_limits<uint>::max();
  // End is when we have traversed the whole a
  for(size_t i = 0; i < a.size(); ++i) {
    uint sum = 0;
    for(size_t j = i; j < a.size(); ++j) {
      sum += a[j];
     
      if (sum > n) {
        if ((j - i) < minSpan) {
          minSpan = j - i;
        }

        break;
      }
    }
  }

  if (minSpan == std::numeric_limits<uint>::max()) {
    return 0;
  }

  return minSpan + 1;
}

int main() {
  vector<uint> vals = {2, 1, 1, 4, 3, 6};
  vector<uint> vals2 = {2, 1, 1};
  
  std::cout << minAdjacentSeq(vals, 8) << "\n";
  std::cout << minAdjacentSeq(vals2, 8) << "\n";

  return 0;
}

- the_lobster February 20, 2018 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More