Google Interview Question Software Engineers
Country: United States
Interview Type: Phone Interview
Construct a cumulative sum array from the give array. C[i] = Sum (A[0]+A[1]+....A[i]). Observe C[i] is sorted.
For each C[i] search for a j (j < i) such that C[i]-C[j] falls within the range. You can use binary search for this. Once you find j, do not stop find all possible j's which satisfy the condition.
The second step should be similar to finding the start index and end index of a key in a sorted array with duplicates.
O(n^2) solution.
I assume that there is no negative value in the array.
public class Solution {
public static void main(String [] args) {
int [] array = {5,1,2,3,4,8,6,10};
System.out.println(Arrays.toString(getInterval(array, 5, 10)));
}
public static Object [] getInterval(int [] array, int low, int high) {
ImmutableList.Builder<Pair> listBuilder = ImmutableList.builder();
for (int i = 0; i < array.length; i++) {
int sum = array[i];
for (int j = i+1; j < array.length; j++) {
sum += array[j];
if (sum <= high && sum >= low) {
listBuilder.add(new Pair(i,j));
}
if (sum > high) {
break;
}
}
}
return listBuilder.build().toArray();
}
}
class Pair {
final int start;
final int end;
public Pair(int start, int end) {
this.start = start;
this.end = end;
}
@Override
public String toString() {
return "Pair{" +
"start=" + start +
", end=" + end +
'}';
}
}
A O(NlogN) solution is constructed on cpluspluslearning-petert.blogspot.co.uk/2016/08/data-structure-and-algorithm-finx-sub.html
Test
void Test_FindSubArrayWithSumInRange()
{
PairResultVect result;
{
const std::vector<double> input;
result = FindSubArrayWithSumInRange(input, 0, 1);
assert(result.empty() == true);
}
{
const std::vector<double> input = { 1.0, 2.0, 3.0, 4.0,
5.0, 6.0, 7.0, 8.0,
9.0, 10.0 };
result = FindSubArrayWithSumInRange(input, 20, 15);
assert(result.empty() == true);
result = FindSubArrayWithSumInRange(input, -10, 0);
assert(result.empty() == true);
result = FindSubArrayWithSumInRange(input, 15.0, 20.0);
assert(result.size() == 8);
}
{
const std::vector<double> input = {-1, 1, -1, 1, -1, 1};
result = FindSubArrayWithSumInRange(input, -1, 1);
assert(result.size() == 21);
}
}
vector<pair<int,int>> rangePairs(vector<int> vect, int low, int high) {
vector<pair<int,int>> result;
int sum = 0;
size_t j = 0;
for(size_t i = 0; i < vect.size(); i++) {
sum += vect[i];
while(sum > high && j < i) {
sum -= vect[j++];
}
int tmpSum = sum;
int tmpJ = j;
while(tmpSum >= low && tmpJ <= i) {
result.push_back(make_pair(tmpJ, i));
tmpSum -= vect[tmpJ++];
}
}
return result;
}
Since the questions about range i.e array between (i & j) - We need not do all combinations - Check this code : All I am trying is remove the first index element if sum gets larger than given sum - Yeah we need slight modification to check sum in range low & high
public static void O_N_SubSum(int[] array, int sum) {
int currSum = array[i];
int start = 0;
int currentEnd = start;
while (currentEnd < array.length) {
if (currSum == sum) {
System.out.println("O(N) array sum at : (" + start + "," + currentEnd + ")");
break;
} else if (currSum < sum) {
currentEnd++;
currSum += array[currentEnd];
} else {
currSum -= array[start];
start++;
}
}
}
Since the function needs to output the pairs, not just their count, it's impossible to get better than O(N^2) since the number of pairs which fulfill the condition is O(N^2). Maybe you mean that we need to output the number of pairs, not the pairs themselves? If not, the interviewer screwed up big time :D
var _ = require( 'lodash' );
var toSave = [];
function reduceSum( inp, sum, i, j, l, h ) {
var itr = i;
while( itr <= j && !_.inRange( sum, l, h+1)) {
sum = sum - inp[itr];
itr ++;
}
var obj = { sum : 0, i : i };
if( sum < 0 ){
obj.sum = 0;
} else {
obj.sum = sum;
}
if( itr > j ) {
obj.i = j;
} else {
obj.i = itr;
}
return obj;
}
function saveIfRequired( inpu, sum, i , j, l, h) {
sum = sum - inpu[j];
if( _.inRange( sum, l, h + 1) ) {
toSave.push( { low: i, high: j-1} );
}
}
function maxSubArray( inp, l, h ) {
var i = 0, j = 0;
var sum = 0;
while( j < inp.length ) {
sum = sum + inp[ j ];
if( _.inRange( sum, l, h + 1) ) {
if( j === inp.length - 1 ) {
toSave.push( { low : i, high:j } );
}
++j;
} else {
saveIfRequired( inp, sum, i, j, l, h);
var ret = reduceSum( inp, sum, i , j, l, h);
sum = ret.sum;
i = ret.i;
++j;
}
}
}
function driver() {
console.log( maxSubArray( [5,3], 2, 8));
console.log( toSave );
}
driver();
var _ = require( 'lodash' );
var toSave = [];
function reduceSum( inp, sum, i, j, l, h ) {
var itr = i;
while( itr <= j && !_.inRange( sum, l, h+1)) {
sum = sum - inp[itr];
itr ++;
}
var obj = { sum : 0, i : i };
if( sum < 0 ){
obj.sum = 0;
} else {
obj.sum = sum;
}
if( itr > j ) {
obj.i = j;
} else {
obj.i = itr;
}
return obj;
}
function saveIfRequired( inpu, sum, i , j, l, h) {
sum = sum - inpu[j];
if( _.inRange( sum, l, h + 1) ) {
toSave.push( { low: i, high: j-1} );
}
}
function maxSubArray( inp, l, h ) {
var i = 0, j = 0;
var sum = 0;
while( j < inp.length ) {
sum = sum + inp[ j ];
if( _.inRange( sum, l, h + 1) ) {
if( j === inp.length - 1 ) {
toSave.push( { low : i, high:j } );
}
++j;
} else {
saveIfRequired( inp, sum, i, j, l, h);
var ret = reduceSum( inp, sum, i , j, l, h);
sum = ret.sum;
i = ret.i;
++j;
}
}
}
function driver() {
console.log( maxSubArray( [5,3], 2, 8));
console.log( toSave );
}
driver();
var _ = require( 'lodash' );
var toSave = [];
function reduceSum( inp, sum, i, j, l, h ) {
var itr = i;
while( itr <= j && !_.inRange( sum, l, h+1)) {
sum = sum - inp[itr];
itr ++;
}
var obj = { sum : 0, i : i };
if( sum < 0 ){
obj.sum = 0;
} else {
obj.sum = sum;
}
if( itr > j ) {
obj.i = j;
} else {
obj.i = itr;
}
return obj;
}
function saveIfRequired( inpu, sum, i , j, l, h) {
sum = sum - inpu[j];
if( _.inRange( sum, l, h + 1) ) {
toSave.push( { low: i, high: j-1} );
}
}
function maxSubArray( inp, l, h ) {
var i = 0, j = 0;
var sum = 0;
while( j < inp.length ) {
sum = sum + inp[ j ];
if( _.inRange( sum, l, h + 1) ) {
if( j === inp.length - 1 ) {
toSave.push( { low : i, high:j } );
}
++j;
} else {
saveIfRequired( inp, sum, i, j, l, h);
var ret = reduceSum( inp, sum, i , j, l, h);
sum = ret.sum;
i = ret.i;
++j;
}
}
}
function driver() {
console.log( maxSubArray( [5,3], 2, 8));
console.log( toSave );
}
driver();
var _ = require( 'lodash' );
var toSave = [];
function reduceSum( inp, sum, i, j, l, h ) {
var itr = i;
while( itr <= j && !_.inRange( sum, l, h+1)) {
sum = sum - inp[itr];
itr ++;
}
var obj = { sum : 0, i : i };
if( sum < 0 ){
obj.sum = 0;
} else {
obj.sum = sum;
}
if( itr > j ) {
obj.i = j;
} else {
obj.i = itr;
}
return obj;
}
function saveIfRequired( inpu, sum, i , j, l, h) {
sum = sum - inpu[j];
if( _.inRange( sum, l, h + 1) ) {
toSave.push( { low: i, high: j-1} );
}
}
function maxSubArray( inp, l, h ) {
var i = 0, j = 0;
var sum = 0;
while( j < inp.length ) {
sum = sum + inp[ j ];
if( _.inRange( sum, l, h + 1) ) {
if( j === inp.length - 1 ) {
toSave.push( { low : i, high:j } );
}
++j;
} else {
saveIfRequired( inp, sum, i, j, l, h);
var ret = reduceSum( inp, sum, i , j, l, h);
sum = ret.sum;
i = ret.i;
++j;
}
}
}
function driver() {
console.log( maxSubArray( [5,3], 2, 8));
console.log( toSave );
}
driver();
Consider the list of integers as {a,b,c,d,e,f}
Iterate through sum set -
1) first level sum set which is a list of adjacent elements -
{a+b,b+c,c+d,d+e,e+f}
2) second level sum set is derived by using a combination of the original list and first level sum set -
{a+b-b-c+2c, b+c-c-d+2d, c+d-d-e+2e, d+e-e-f+2f}
also rewritten as
{a+c,b+d,c+e,d+f}
3) third level sum set -
{a+c+b+d-b-c,b+d+c+e-c-d,c+e+d+f-d-e}
also rewritten as
{a+d,b+e,c+f}
4) fourth level sum set -
{a+d+b+e-b-d,b+e+c+f-c-e}
also rewritten as
{a+e,b+f}
5) fifth level sum set -
{a+e+b+f-b-e}
also rewritten as
{a+f}
and you will see that it is no longer O(n^2)
Consider the following input:
Low: 8
High: 10
vals = [1, 1, 8, 5, 9, 14, 6, 5, 5, 22]
Assuming only positive numbers are provided this should be a suffice answer (python):
def findPositiveSubSumIdxs(values, low, high):
# The return pairs of indexes
idxPairs = []
for startIdx, startNum in enumerate(values):
rollingSum = 0
for endIdx, endNum in enumerate(values[startIdx:]):
rollingSum += endNum
if rollingSum > high:
break
if rollingSum >= low:
idxPairs.append( (startIdx, endIdx+startIdx) )
return idxPairs
high = 10
low = 8
values = [1,1,8,5,9,14,6,5,5,22]
print findPositiveSubSumIdxs(values, low, high)
This looks ripe for a dynamic programming solution, which I haven't come up with yet. This seems to be the best way to do this that I see (I haven't read other solutions yet). If the solution must work with negative numbers, then the break statement needs to be removed.
//Write a function that takes as input an array of integers A,
//and two integers low and high.
//Your function has to output pairs of indices: {(i,j), ...}
//Where each pair of indices denotes that the subarray of A[i...j] has
//a sum in the range low <= sum <= high.
//Apparently there are algorithms better than O(N^2).
// Olu Gbadebo
// Aug 22nd 2016
import java.util.*;
public class Careercup3 {
public static ArrayList sumInArray(ArrayList<Integer> list, int low, int high){
ArrayList<ArrayList<Integer>> answer = new ArrayList<ArrayList<Integer>>();
for(int i = 0; i < list.size(); i++){
for (int j = i + 1; j < list.size(); j++){
int sum = list.get(i) + list.get(j);
if (sum >= low && sum <= high){
ArrayList<Integer> temp = new ArrayList<Integer>();
temp.add(list.get(i));
temp.add(list.get(j));
answer.add(temp);
}
}
}
return answer;
}
}
You are computing the algorithm BigO time incorrectly... it is not about how long it takes to generate n*(n-1) pairs but the fact you can know that would be the answer in just O(n) time.. one can determine the max and min value of an array in O(n) time..so in O(n) time we would know that answer is all possible combinations
import java.util.HashMap;
class SumSubarrayCount {
// Counts the number of subarrays with sero sum
static int countZeroSumSubarrays(int arr[],int low,int high)
{
HashMap<Integer, Integer> hM = new HashMap<Integer, Integer>();
// Initialize sum of elements
int sum = 0;
for (int i = 0; i < arr.length; i++)
{
if(arr[i]>=low && arr[i]<=high)
hM.put(arr[i],0);
}
//Counter of subarrays
int count = 0;
// Traverse through the given array
for (int i = 0; i < arr.length; i++)
{
//Calculate new sum
sum += arr[i];
if (hM.containsKey(sum)){
if(arr[i]>=low && arr[i]<=high)
{
hM.put(sum, hM.get(sum) + 1);
count += hM.get(sum);
}
} else{
// If the sum has not been seen, we initialize its key.
hM.put(sum,0);
}
}
return count;
}
}
Returns all the pair of indices of a sub-array whose sum is such that
low <= sum <= high. For example, 2,1,4,3,1,2,8,5,3,6 with low 3 and high 8 starting at index 0 should return indices like [0..1]->3 (valid) [0..2]->7 (valid) [0..3]->10 (invalid) then start at index 1
[1..2]-> 5 (valid) [1..3]-> 8 (valid) [1..4]-> 9 (invalid) etc.
Time complexity: O(n^2)
public static List<Pair> getRangePairs(final int[] array, int low, int high) {
List<Pair> result = new ArrayList<Pair>();
int sum = 0;
for(int i =0; i<array.length; i++) {
// read the current value at i
sum = array[i];
// point j to next index of i and keep adding until sum > high
for(int j=i+1; j<array.length; j++) {
sum = sum + array [j];
if(sum >= low && sum <= high) {
result.add(new Pair(i,j));
} else if(sum > high) {
break;
}
}
}
return result;
}
public class Pair {
private int start;
private int end;
public Pair(int start, int end) {
this.start = start;
this.end = end;
}
public int getStart() {
return start;
}
public int getEnd() {
return end;
}
}
public static void main(String[] args) {
int[] array = new int[] {2,1,4,3,1,2,8,5,3,6};
List<Pair> pairs = getRangePairs(array, 3, 8);
for(final Pair p : pairs) {
System.out.println("[" + p.getStart() + ", " + p.getEnd() + "]");
}
}
// Output:
[0, 1]
[0, 2]
[1, 2]
[1, 3]
[2, 3]
[2, 4]
[3, 4]
[3, 5]
[4, 5]
[7, 8]
The question makes sense. But the constraint which you mention "apparently there are algorithms better than O(n^2) doesn't make sense to me.
Lets say an array of length n is given, then the ask is to return pair of indices for which the sub array's sum is less than low and high. Consider for example array = {1, 2, 3, 4, 5} and the low and high indices are -5000 and +5000. Then every combination of index is part of the list to be returned i.e. {{0,0}, {0,1}, {0,2}, {0,3} , {0,4} .... {4,4}}. Essentially at the max there can be N^2 entries in the returned list. So worst case is n^2.
Are you sure it seeks for answers with less that n^2 complexity>
Consider the list of integers as {a,b,c,d,e,f}
Iterate through sum set -
1) first level sum set which is a list of adjacent elements -
{a+b,b+c,c+d,d+e,e+f}
2) second level sum set is derived by using a combination of the original list and first level sum set -
{a+b-b-c+2c, b+c-c-d+2d, c+d-d-e+2e, d+e-e-f+2f}
also rewritten as
{a+c,b+d,c+e,d+f}
3) third level sum set -
{a+c+b+d-b-c,b+d+c+e-c-d,c+e+d+f-d-e}
also rewritten as
{a+d,b+e,c+f}
4) fourth level sum set -
{a+d+b+e-b-d,b+e+c+f-c-e}
also rewritten as
{a+e,b+f}
5) fifth level sum set -
{a+e+b+f-b-e}
also rewritten as
{a+f}
and you will see that it is no longer O(n^2)
This can be achieved using mergesort. You perform mergesort on the set, and then just before calling merge on the two sorted sublists, run through them (using two pointers) and collect all the pairs that correspond to the requirements. after that call merge and return the set of pairs. This is by no means trivial. But is achievable.
ok let's think min is - inf and max is + inf. so we need to return every possible pair. that means comb(n,2) which is o(n2). i don't think it can be done in better time.
- Anonymous August 01, 2016