Google Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
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.
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)
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
/* 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;
}
}
}
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;
}
// 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;
}
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!
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.
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.
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;
}
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.
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?
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
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.
@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?
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)
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;
}
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.
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!!
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.
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);
}
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.
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))
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);
}
}
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;
}
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;
}
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();
}
}
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);
}
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
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
// 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");
}
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;
}
}
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
}
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;
}
}
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;
}
}
/*
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;
}
}
}
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);
}
}
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;
}
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;
}
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);
}
}
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;
}
#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;
}
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 "SLIDING WINDOW" proposed by ninhnnsoc is a great idea. But his answer is not the best.
- xuyan.nus May 05, 2014Basically, "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)