## Google Interview Question for Software Engineer / Developers

• 7

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)

Comment hidden because of low score. Click to expand.
0

Thanks.

Comment hidden because of low score. Click to expand.
0

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.

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)

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

/* 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;
}
}
}``````

Comment hidden because of low score. Click to expand.
0

what if the input sum is negative?

Comment hidden because of low score. Click to expand.
0

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;
}``````

Comment hidden because of low score. Click to expand.
0

// 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;
}``````

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!

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.

Comment hidden because of low score. Click to expand.
0

thanks!
I edited my post.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

I found it complicated for negative case.

Any one can fix it?

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;

}``````

Comment hidden because of low score. Click to expand.
0

Great job! That was beautiful :-)

Comment hidden because of low score. Click to expand.
0

Hi uuuouou and iroodaz:

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

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.

Comment hidden because of low score. Click to expand.
0

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

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?

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.

Comment hidden because of low score. Click to expand.
0

@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?

Comment hidden because of low score. Click to expand.
0

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)

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;``````

}

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.

Comment hidden because of low score. Click to expand.
0

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!!

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

Good question!
I think if we can check for all possible windows, then just record whatever minimum we want.

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);
}``````

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.

Comment hidden because of low score. Click to expand.
0

Can it work for negative values?

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
2

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.

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))``````

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]);
}
}
}``````

}

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 {
PrintWriter out = new PrintWriter(System.out);

int[] A = new int[N];

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

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);
}
}``````

Comment hidden because of low score. Click to expand.
0

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

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;

}``````

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.

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;

}

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;
}``````

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

removing the post as I misunderstood the problem. thanks srini

Comment hidden because of low score. Click to expand.
0

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

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 {
}

}
/// 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();
}

}``````

Comment hidden because of low score. Click to expand.
0

just noticed this doesnt handle zero case

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);
}``````

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``````

Comment hidden because of low score. Click to expand.
0

``````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``````

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");
}``````

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} );
}

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;
}
}``````

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

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
}``````

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){
}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;
}
}``````

Comment hidden because of low score. Click to expand.
0

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

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;
}``````

}

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;
}
}
}

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);
}

}``````

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

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;
}``````

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;

}

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);

}
}``````

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;
}``````

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);

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;
}``````

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.
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;
}``````

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;
}``````

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.

### 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.