Google Interview Question for Software Engineers


Country: United States
Interview Type: In-Person




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

A simple O(nlgn) solution using cumsum and Java navigable set's subset operation. The idea is that if the number itself falls between the range than its a subset and we count it. Otherwise, if cumsum at the position of the element falls between the range then there is a subset from the start to this position and we count it.

Note that, there might be many other subarray's in between start and current position that can sum to the given range. We can check if A[i..j] sums to S by checking if cumsum[j]-cumsum[i] = S. In other words, at each position i, we can check if cumsum[j]-S was seen earlier in some previous position i < j. We can easily do this using a hash to track each of the cumsum at each position.

Now, question is how to track the range of sum? Idea is to put the cumsums seen so far in a TreeSet (i.e. BST order) and for a position i we find how many elements fall in the range
by finding number of elements in the subMap from (cumsum[i]-b) to (cumsum[i]-a) (think why?). So, we increase count by this number.

Below is a O(nlgn) implementation of this logic. Note that, treeset is handled in such a way that we don't have to call size() method that is O(n) itself. Instead I keep index and calculate size by using simple formula of (endIndex-startIndex+1) .

Overall time complexity O(nlgn), overall space complexity O(n).

public static int subArrayWithSumInRange(int[] A, int a, int b){
	int count = 0;
	TreeSet<Pair> treeSet = new TreeSet<test.Pair>();
	int cumsum = 0;
	
	for(int i = 0; i< A.length; i++){
		cumsum+=A[i];
		
		if(A[i] >= a && A[i] <= b){
			count++;
		}

		NavigableSet<Pair> subSet = treeSet.subSet(new Pair(cumsum-b, i+1), true, new Pair(cumsum-a, i+1), false);
		if(!subSet.isEmpty()){
			count += Math.abs(subSet.first().second - subSet.last().second)+1;
		}
		treeSet.add(new Pair(cumsum, i));
	}
	
	return count;
}

private static class Pair implements Comparable<Pair>{
	public int first;
	public int second;
	
	public Pair(int first, int second){
		this.first = first;
		this.second = second;
	}

	@Override
	public int compareTo(Pair o) {
		if(this.first == o.first)
			return Integer.compare(this.second, o.second);
		else
			return Integer.compare(this.first, o.first);
	}

	@Override
	public String toString() {
		return "[" + first + "," + second + "]";
	}
}

- zahidbuet106 October 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

nice solution.

- dhs.du.08 October 02, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

what happens if there are 0's in the array?

- anonymous2k2cs October 02, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It's really a nice solution. I think it needn't to judge "a <= A[i] && A[i] <= b".

- malinbupt October 03, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

This solution does not work if array is (10,-10,10,-10) a=-10, b=10
And also when array is (100,-10,10,-10,10,-10) a=-1 b=1

- sandeep October 03, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

very nice. But, I would use a hashtable (a set or dic) when it comes to find the range of numbers in our list of cumulative sums:
1. BST insertion is O(logn) vs O(1) for hashtable
2. When you find the subset of BST btw [a,b] you actually do a search for all elements in that range in your BST which is O(mlogn) m being the size of [a:b]. Instead if you do a contains in for all [a:b] elemts in a hashtable it will be m times O(1) operation.

- SJ October 04, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It is very nice idea but I can't understand a few things
1) Why you do this
count += Math.abs(subSet.first().second - subSet.last().second)+1;
See, you have done
treeSet.add(new Pair(cumsum, i));
where i is index of element. It is NOT the index of cumsum in TreeSet and you put it into second field.
So the expression
'Math.abs(subSet.first().second - subSet.last().second)+1;' is equal to the number of ELEMENTS between Sa and Sb
Yes in case when cumsum is increasing because of only positive values it will be the same as size() but what about the negative values case? It will not work!
You can check this for example input {1,2,-3,4,5} a=-100,b=100
2) It seems there are some error in calculation
For instance for input { 5,2,4,7} a=0, b=10 your code will return 8 but the right answer is 6

- mger1979 October 04, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@SJ : subset is guaranteed O(lgn) because it uses headSet and tailSet to find the range , both of them are O(lgn).

@mger1979 : count += Math.abs(subSet.first().second - subSet.last().second)+1;

I am doing this to avoid calling size() method as Java currently do linear scan when you call size(). Instead I made my life difficult and kept index of an element in the second field of pair. So, you can calculate size using n=end-start+1 by O(1) time.

- zahidbuet106 October 04, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

You can add a dummy Pair (0, -1) in the Treeset and don't need to process for single element in each loop.

And count += Math.abs(subSet.first().second - subSet.last().second)+1;
should be count += subSet.size();

- williamyu October 29, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

nice job. here is the c++ implementation:

{{
size_t countinrange(vector<int>& arr, int a, int b) {
size_t N = arr.size();
vector<int> cumsum(N,0);
multiset<int> sumset;
size_t count = 0;
for (size_t i = 0; i < N; i++) {
int ai = arr[i];
if (ai >= a && ai <= b) {
count++;
}
cumsum[i] = arr[i];
if (i > 0) cumsum[i] += cumsum[i-1];
int ub = cumsum[i] - a;
int lb = cumsum[i] - b;
auto lbIter = sumset.lower_bound(lb);
if (lbIter != end(sumset)) {
auto ubIter = sumset.upper_bound(ub);
for (auto iter = lbIter; iter != ubIter; iter++) {
count++;
}
}
sumset.insert(cumsum[i]);
}
return count;
}

}}

- manazhao November 02, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@manazhao, your code is O(n^2) because of inner loop (for (auto iter = lbIter; iter != ubIter; iter++))

It's not possible to implement it with c++ set, in the same way as Java solution.

- MehrdadAP November 02, 2015 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

I could solve it with easier implementation in O(nlogn), thanks to @emb hint.

The idea is based on divide and conquer technique(like(almost the same as) what we do in merge sort).

Let's call prefix sums, S_i = arr[0]+arr[1]+..+arr[i]

Basically, I need to count all A<= (S_i - S_j) <=B and i>j, plus all A<=S_i<=B.

Now, let's think about it with divide and conquer(D&C) technique.

It means, assume we have split prefix sums array,S, into two equal parts.Also, assume each part is sorted individually.
Based on D&C, we can say we know the answer of left part and right part. We just need to find all S_i's in right part, and all S_j's in left part which satisfy A<= S_i - S_j <=B (note that since all S_i's are in right part so they already satisfy i>j).

We can find them with two approaches.

Approach 1)
For every i in right part, we can do two binary searches on left part array (which is sorted) and find a range which all of them satisfy the condition.(for more explanation, you could see my first solution based on BST)

In this approach the time complexity can be computed as following recurrence:
T(n) = 2T(n/2) + O(nlogn) --> Using Master theorem: T(n) = O(n*logn^2)

Approach 2)
In approach 1, we didn't take advantage of the fact that numbers in right part are also sorted.
So if for S_i we have p1 and p2 as a range that all numbers between [p1,p2] satisfy the condition, for finding the range for S_{i+1}, we just need to move p1 and p2 forward.(It needs a little bit playing with numbers to make sure that this fact is true!) So in this case we will visit all numbers of left part, twice (one for moving p1 and one for moving p2).

So the recurrence would be:
T(n) = 2T(n/2) + O(n) --> Using Master Theorem: T(n) = O(nlogn)

Very simple and cool question. Every time, I'm so excited about D&C solutions/problems :D

Here's my c++ implementation

int solve(int s,int e,int a,int b,vector<int> &arr)
{
	if (e<s) return 0;
	if (s==e) return (a<=arr[s] && arr[s]<=b);

	
	int mid=(e+s)>>1;

	int ans = solve(s,mid,a,b,arr) + solve(mid+1,e,a,b,arr);

	int p1=s,p2=s;
	
	for (int i=mid+1; i<=e;i++){
		while (p1<=mid && (arr[i]-arr[p1])>=a)
			p1++;

		while (p2<=mid && (arr[i]-arr[p2])>b)
			p2++;

                // now for all k>=p2 we have arr[i]-arr[k]<=b
		// and for all k<p1 we have arr[i]-arr[k]>=a

		if (p2<=mid && p2<=p1)
			ans+=(p1-p2);

		
		
	}

	//sort the array from (s,e)
	vector<int> tmp;
	p1=s,p2=mid+1;
	while (p1<=mid && p2<=e){

		if (arr[p1]<=arr[p2]){
			tmp.push_back(arr[p1]);
			p1++;
		}
		else{
			tmp.push_back(arr[p2]);
			p2++;
		}
	}

	while (p1<=mid){
		tmp.push_back(arr[p1]);
		p1++;
	}

	while (p2<=e){
		tmp.push_back(arr[p2]);
		p2++;
	}

	for (int i=0;i<tmp.size();i++){
		arr[i+s]=tmp[i];
	}

	return ans;
}

int countPartialSums(vector<int> &nums,int a,int b)
{
	int N=nums.size();
	for (int i=1;i<N;i++){
		nums[i]=nums[i-1]+nums[i];
	}

	return solve(0,N-1,a,b,nums);
}

- MehrdadAP September 30, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

nice job :)

- emb September 30, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thank you:)

Your posted questions are all interesting. It seems you select the nice ones :D

- MehrdadAP September 30, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@MehradaAP, nice one. I came across the same approach as your second solution. However, I would like to point out that the run time analysis of the first solution is not correct. The use of master theorem there is wrong and master theorem won't apply for this case, since nlogn is not polynomially large than n^(log2(2)). Therefore, I doubt its efficiency.

- plutoman October 01, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@MehrdadAP , nice solution. I came up with the similar solution as your second one. However, I would like to point out that the use of master theorem for run time analyze of the first solution is wrong. Actually master theorem doesn't apply for this case as nlogn is not polynomially larger than n=n^(log2(2)). Therefore, I doubt what its real run time is.

- plutoman October 01, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@plutoman, Thanks.

There is another form of Master Theorem (in Wikipedia known as Generic Form and sometimes it's called Special Case) which includes the case that I used.
(See more explanation in Master Theorem page in Wikipedia)

Also, you could compute it without MT, using recurrence tree. It's the same as merge sort.

- MehrdadAP October 01, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@MehradaAP, thanks! I saw the version you mentioned. I was mislead by the CLRS book.

- plutoman October 04, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

It can be solved in O(nlogn) using cumulative sum and balanced binary search tree.

Start iterating from left to right. When we are at position i, we need to have cumulative sum of elements from 0..(i-1) in a balanced binary search tree.
For simplicity assume that we have cumulative(prefix) sums in a sorted array.

x_1, x_2, x_3, ..., x_(i-1)

which x_k = arr[0] + arr[1]+...+arr[s] (note that X is a sorted array of prefix sums)

(More clarification on X:
Let's say we have prefix sums as S_i = arr[0]+arr[1]+...arr[i]
Now X, is sorted version of S. Therefore X_1 is the smallest S_i and X_2 is the second smallest S_i and so on)


Now, for finding all possible answers for position i, we need to find all x_j provided that a<=x_i - x_j <=b.

Since array is sorted, we can do binary search on (x_i - a) and (x_i - b).

pos1 = position of greatest number which is smaller or equal than (x_i - b).
pos2 = position of smallest number which is greater or equal than (x_i - a).

now all numbers in range of [pos1,pos2] satisfy a<=x_i - x_j <=b. So we can add (pos2-pos1+1) to final answer.

We can't use a set container (in c++) instead of binary search tree, since we want to know the position of a given number in set, which is not provided in c++ set. So basically we need to write our own set (red-black BST) and at each node keep the number of its children.

Time Complexity would be O(nlogn) since we need binary search for each position.

- MehrdadAP September 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

If I understood your algorithm correctly, it seems like there is a small problem with your approach - it will output more ranges than there are.
Example

array: arr[0]=1 arr[1]=-2 arr[2]=3
cumulative: x_0=1 x_1=-1 x_2=2
a = b = -3
expected answer: 0

with balanced tree we look for suitable pair for x_1 and see that x_2 suits, since x_1 - x_2 = -3 that is in our range. But there is no cumulative sum -3 in this array, since we can only subtract x_i from x_j if i > j

- emb September 26, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Input: [1, 1, 1, 8] and interval [8, 10]. Need prefix and suffix sums.

- Noobie September 26, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@emb, That's not my approach. x_i are sorted at each step.

It was my bad on definition of x_k.

Let me explain more with your example.

x_0 is not between [a,b] --> no answer
at position 1: we have: x_0 = 1 --> no answer
at position 2: we have: x_1=-1, x_0 =1 --> no answer

So answer =0.

As an another example:
count([-2,5,-1],-2,2)

position 0: -2<=-2<=2 --> ans +=1
position 1: x_0=-2 --> ans+=0
position 2: x_0=-2 , x_1 = 3 --> (x_2=2, so x_2 - x_0 and x_2-x_1 satisfiy) ans+=2

finally: ans = 3

- MehrdadAP September 26, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yeah, you are right, sorry. The algorithm is correct, though, there exist simpler approaches (writing a self-balancing tree is not so easy?)

- emb September 26, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@emb, I got it! we can sort all the prefix sums and then sort them and do what I said on a sorted array instead of a self-balanced binary search tree!

The point is we don't care about answer of each position, we care about total answer.

- MehrdadAP September 26, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

But then my pre-previous comment about extra ranges would apply :)
As for balancing trees, we could probably use skip-lists instead of them, since they are much simpler, but there is O(n*log(n)) solution that doesn't use any complex data structures.

- emb September 26, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I still don't get the overall algorithm. how it works.

at each i pos we need to do sort
this iteration is O(n)
sort is O(N*logn)
then overall time complexity is O(n^2) already .

did i miss something?

- nberserk September 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@emb, @MehrdadAP Can anybody explain how would you compute the cumulative prefix sums and update the tree at each iteration in constant time? Wouldn't it take O(n) time to do that at each iteration resulting in O(n*2) total time?

- Bug-E September 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Bug-E
en.wikipedia.org/wiki/Red%E2%80%93black_tree
insertion and search is not constant, it's log(n), so the overall algorithm is O(n*log(n))

- emb September 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Also here is a tip about simpler solution.
Suppose you have an array of partial sums
p1 p2 ... pn
Then you divide it in two equal parts by index.
p1 p2 ... pm and pm+1 .... pn
And then suppose you have both arrays sorted in increasing order.
What happens if we take one partial sum from left array and another from right?

- emb September 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Do you mean cumulative sum by partial sum?
Because then if we divide the cumulative sum array at an index and sort, how do we ensure contiguous results only (leading back to your first doubt in this algorithm).
or do you mean something else by partial sum...

- Anonymous September 28, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Do you mean cumulative sum by partial sum?
Dividing cumulative array at an index and sorting..will it not make it difficult to show results for contiguous elements only.
And why divide at middle index...

- curiosity September 28, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Your algorithm is not right, because when you compare a<=x_i - x_j <=b, i is not guaranteed to be greater than j.

- Larry September 28, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@MehrdadAP Could you please elaborate that with a step-by-step example. It is still difficult to understand what you are trying to do. Would appreciate that. Thanks!

- myzn September 29, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Assuming the numbers between pos2 and pos1 to be monotonically increasing sequence seems wrong. Basically, pos2 - pos1 + 1 includes more subarrays than it should.

For instance, ([4, 100, -100, 3], 3, 7) = 2, but your algorithm would yield 4.

- jar September 30, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Larry: it's guaranteed because based on what I said, when we are at position i, we just have prefix sums before i in the BST.

@myzn: I came up with another solution, and I tried to explain it more coherently. Part of new solution is the same as above solution. I hope it could help.

@Jar: Because the right answer is 4 :D
[4] [4,100,-100] [4,100,-100,3] [3]

Let's do it step by step for more clarification:

0: X_0 = 4 --> ans=1
1: X_0=4 -> pos1=pos2=null
2:X_0 = 4,X_1 = 104 -> pos1=pos2=null
3:X_0=4,X_1=4,X_2=104 -> X_4=7 so ans++ and pos1=0,pos2=1 so ans+=2

total ans = 4.
probably in case of equal numbers we need to define the pos1 and pos2 more accurate. But the whole idea works.

- MehrdadAP September 30, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

How you will handle the negative values ? in this case the cumulative array will not be increasing !

and if we deal with positive values only ,we can just use binary search instead of binary search tree to get the indices.

- ahmed0ameen0elfiky October 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@ahmed, I said assume that X_i's are sorted version of cumulative sums(prefix sums). And it can be done using binary search tree.

Yes, If they were positive, binary search worked.

- MehrdadAP October 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

How about this algorithm:

1. find the min of the array. If the min <= 0, go to 2; otherwise go to 3.
2. add the abs(min) + 1 to each element so all elements > 0. add abs(min) + 1 to (a,b) so it becomes (a+abs(min)+1, b+abs(min)+1).
3. use the naive algorithm with early termination. When considering an element, if the sum of a sub array > b + min, then stop scanning forward.

The complexity is O(nk) where k is the number of sub arrays whose sum < b + abs(min) + 1. In the worst case it can be O(n^2) but now the complexity is output sensitive.

- Anonymous September 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

So we have an array
-4 2 -5 3 -1 and a=-1 b=0
min =-5 so new array is
1 7 0 8 4 a=4 b=5
and now I don't get it, will the naive algorithm account 2 -5 3, that is 7 0 8 ?
Isn't the problem is that when you add min to every element, the sum of range becomes sum(old_range) + min * len(old_range) and not sum(old_range) + min?

- emb September 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Looks like that won't work, at least with the current implementation:
example:
{-1; 2; -3}; -2; 2; subsets are: {-1}; {2}; {-1, 2;}; {2; -3}; {-1, 2 ,-3};
Algorithm:
min({-1; 2; -3}) = -3 =>
{3; 6; 1}; 2; 6; subsets are: {3}, {6} which is evidently incorrect.

- Alex M. November 10, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

How about this:
1. find the min of the whole array. If min <= 0, go to 2. otherwise, go to 3.
2. add abs(min) + 1 to each element and (a, b) so that all element > 0 and the range becomes (a+abs(min)+1, b+abs(min)+1).
3. use naive algorithm with early termination. If the sum of a sub array > b+abs(min)+1, then stop scanning longer sub array.

The complexity is O(nk) where k is the number of subarray whose sum < b+abs(min)+1. It can be O(n^2) in worst case but is output sensitive.

- jiangok2006 September 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

sorry for the duplication, the website made me think my previous post did not go through.

- jiangok2006 September 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Same idea as MehrdadAP, but with code.

static class RedBlackTree {
        static class Node {
            Node left, right;
            int value, numLeft, numRight;
            public Node(int val) {
                value = val;
            }
            public void insert(Node n) {
                // TODO: make sure that the tree is balanced while inserting
                if (n.value < this.value) {
                    if (this.left == null) this.left = n;
                    else this.left.insert(n);
                    this.numLeft++;
                } else {
                    if (this.right == null) this.right = n;
                    else this.right.insert(n);
                    this.numRight++;
                }
            }
        }
        Node head;
        public void insert(int value) { 
            if (head == null) head = new Node(value);
            else head.insert(new Node(value));
        }
        public int numBetween(int lower, int higher) {
            return numBetween(lower, higher, Integer.MIN_VALUE, Integer.MAX_VALUE, head);
        }
        public int numBetween(int lower, int higher, int treeLower, int treeHigher, Node n) {
            if (n == null) return 0;
            if (treeLower >= lower && treeHigher <= higher) return 1 + n.numLeft + n.numRight;
            int count = 0;
            if (lower <= n.value && n.value <= higher) count++;
            count += numBetween(lower, higher, treeLower, n.value, n.left);
            count += numBetween(lower, higher, n.value, treeHigher, n.right);
            return count;
        }
    }

    public static int numSubarraysInRange(int[] ints, int a, int b) {
        int sum = 0;
        int min = Math.min(a, b), max = Math.max(a, b);
        a = min;
        b = max;
        RedBlackTree tree = new RedBlackTree();
        tree.insert(0);
        int answer = 0;
        for (int i = 0; i < ints.length; i++) {
            sum += ints[i];
            // Query the tree for the number of intervals between sum - b and sum - a
            answer += tree.numBetween(sum - b, sum - a);
            tree.insert(sum);
        }
        return answer;
    }

- dasun September 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

How your tree is self-balancing?

- MehrdadAP September 30, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

The algorithm is not right because you cannot make sure that when you compare a<=x_i - x_j <=b, i is guaranteed to be greater than j.

- Larry September 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public void findSubarray(int[] nums, int start, int end) {
		int n = nums.length;
		int j = 0, i = 0;
		int sum = nums[0];
		while (i < n) {
			
			// Take out one from start
			while (sum < start && end < sum && j < i) { 
				sum -= nums[j];
				j++;
			}
			
			// Answer
			if (start <= sum && sum <= end) { 
				if (j < i)
					System.out.print(j + " - " + i);
				else
					System.out.print(j);
				System.out.println("");
			}
			
			sum += nums[i];
			i++;
			
			// complete j if i is over
			if (i == n && j < n - 1) {
				j++;
				i = j;
				sum = nums[j];
			}
		}
	}

- Satish September 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public void findSubarray(int[] nums, int start, int end) {
		int n = nums.length;
		int j = 0, i = 0;
		int sum = nums[0];
		while (i < n) {
			
			// Take out one from start
			while (sum < start && end < sum && j < i) { 
				sum -= nums[j];
				j++;
			}
			
			// Answer
			if (start <= sum && sum <= end) { 
				if (j < i)
					System.out.print(j + " - " + i);
				else
					System.out.print(j);
				System.out.println("");
			}
			
			sum += nums[i];
			i++;
			
			// complete j if i is over
			if (i == n && j < n - 1) {
				j++;
				i = j;
				sum = nums[j];
			}
		}
	}

- Satish September 30, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Could someone explain me the algo with a clear example,i am not able to understand the x_k notation

- dash September 30, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I added another clarification for x_k:

Let's say we have prefix sums as S_i = arr[0]+arr[1]+...arr[i]
Now X, is sorted version of S. Therefore X_1 is the smallest S_i and X_2 is the second smallest S_i and so on

- MehrdadAP September 30, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int count(int[] array, int min, int max) {
return count(array, 0, array.length-1, min, max);
}

private int count(int[] array, int s, int e, int min, int max) {
if( s == e ){
if( array[s]>=min && array[e]<=max ){
return 1;
} else {
return 0;
}
}

int mid = (e-s)/2 + s;

int[] sum = new int[e-mid];
for(int i=mid+1,j=0;i<=e;i++,j++){
if( j==0 ){
sum[j] = array[i];
} else {
sum[j] = array[i]+sum[j-1];
}
}

Arrays.sort(sum);

int count=0;
int total = 0;
for(int i=mid;i>=s;i--){
total += array[i];
count += range(sum, min-total, max-total);
}

return count+count(array, s, mid, min, max)+count(array, mid+1, e, min, max);
}

private int range(int[] array, int min, int max){
int a = Arrays.binarySearch(array,min);
int b = Arrays.binarySearch(array,max);

if( a>=0 && b<0){
while ( a-1>=0 && array[a-1] == array[a]){
a--;
}

return Math.abs(b)-a-1;
} else if( a>=0 && b>=0 ){
while ( a-1>=0 && array[a-1] == array[a]){
a--;
}

while ( b+1<array.length && array[b+1] == array[b]){
b++;
}
return b-a+1;
} else if( a<0 && b>=0 ){
while ( b+1<array.length && array[b+1] == array[b]){
b++;
}

return b-Math.abs(a)+2;
} else { // a<0 && b<0
return a-b;
}

}

- Anonymous October 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int count(int[] array, int min, int max) {
        return count(array, 0, array.length-1, min, max);
    }
    
    private int count(int[] array, int s, int e, int min, int max) {
        if( s == e ){
            if( array[s]>=min && array[e]<=max ){
                return 1;
            } else {
                return 0;
            }
        }

        int mid = (e-s)/2 + s;

        int[] sum = new int[e-mid];
        for(int i=mid+1,j=0;i<=e;i++,j++){
            if( j==0 ){
                sum[j] = array[i];
            } else {
                sum[j] = array[i]+sum[j-1];
            }
        }

        Arrays.sort(sum);

        int count=0;
        int total = 0;
        for(int i=mid;i>=s;i--){
            total += array[i];
            count += range(sum, min-total, max-total);
        }

        return count+count(array, s, mid, min, max)+count(array, mid+1, e, min, max);
    }

    private int range(int[] array, int min, int max){
        int a = Arrays.binarySearch(array,min);
        int b = Arrays.binarySearch(array,max);

        if( a>=0 && b<0){
            while ( a-1>=0 && array[a-1] == array[a]){
                a--;
            }

            return Math.abs(b)-a-1;
        } else if( a>=0 && b>=0 ){
            while ( a-1>=0 && array[a-1] == array[a]){
                a--;
            }

            while ( b+1<array.length && array[b+1] == array[b]){
                b++;
            }
            return b-a+1;
        } else if( a<0 && b>=0 ){
            while ( b+1<array.length && array[b+1] == array[b]){
                b++;
            }

            return b-Math.abs(a)+2;
        } else { // a<0 && b<0
            return a-b;
        }

    }

- Mike October 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class GG_SubArraySumInRange {
    // This java code uses segment tree. TC: O(n*lgn*lgn)
    
    // O(n*lgn*lgn)
    int getSubArr(int[] nums, int low, int high)
    {
        if(nums==null || nums.length==0)
            return 0;

        //get the sum array. O(n)
        Sum[] sums = new Sum[nums.length];
        for(int i=0; i<nums.length;++i) {
            if(i==0) {
                sums[i] = new Sum(nums[i], 0);
            }
            else {
                sums[i] = new Sum(sums[i-1].val + nums[i], i);
            }
        }

        //O(nlgn)
        Arrays.sort(sums);

        //build segment tree on the sorted sum array. O(nlgn)
        TreeNode segTree = buildSegTree(sums, 0, sums.length-1, null);

        TreeNode[] map = new TreeNode[nums.length];
        //create a map of original index to its corresponding segment tree node. O(n)
        populateMap(segTree, map);

        int count = 0;
        int prevSum = 0;
        //O(n*lgn*lgn)
        for(int i=0; i<nums.length; ++i)
        {
            // get updated range for searching in segment tree.
            int low2 = low + prevSum;
            int high2 = high + prevSum;

            // search the segment for each updated range. O(lgn*lgn)
            count += searchRange(sums, segTree, low2, high2);
            prevSum += nums[i];

            // After handling this num, excluding it from the segment tree. O(lgn)
            excludeNode(map[i]);
        }

        return count;
    }

    // data structure for sum sorting.
    class Sum implements Comparable<Sum> {
        int val;
        int ind; // the index in the original nums array.
        Sum(int val, int ind)
        {
            this.val = val;
            this.ind = ind;
        }

        public int compareTo(Sum s)
        {
            return this.val - s.val;
        }
    }

    class TreeNode {
        ArrayList<Integer> sumInd = new ArrayList<>();
        int ind;  // the original index in nums array.
        boolean excluded; // indicate if current node is excluded.
        TreeNode parent; // for segment tree update in O(lgn)
        TreeNode left;
        TreeNode right;
        public TreeNode(TreeNode parent, int ind)
        {
            this.parent = parent;
            this.ind = ind;
            this.excluded = false;
            this.left = this.right = null;
        }
    }

    boolean isValid(int n, int low, int high) {
        return low<=n && n<=high;
    }

    void excludeNode(TreeNode node)
    {
        node.excluded = true;
        int st = node.sumInd.get(0);
        int end = node.sumInd.get(node.sumInd.size()-1);

        while(true)
        {
            node = node.parent;
            if(node == null)
                break;
            int st1 = bs(node.sumInd, 0, node.sumInd.size()-1, st);
            int end1;
            if(st == end)
                end1 = st1;
            else
                end1 = bs(node.sumInd, 0, node.sumInd.size()-1, end);
            
            for(int i=end1; i>st1-1; --i)
                node.sumInd.remove(i);
            
            // if all children have been excluded, then current node is excluded also.
            if(node.sumInd.size()==0)
                node.excluded = true;
        }
    }

    // regular binary search
    int bs(ArrayList<Integer> sumInd, int st, int end, int target)
    {
        if(st>end)
            return -1;
        int mid = st + (end-st)/2;
        if(target == sumInd.get(mid))
            return mid;

        if(target < sumInd.get(mid))
        {
            return bs(sumInd, st, mid-1, target);
        }

        return bs(sumInd, mid+1, end, target);
    }

    // populate the map for original indexes in nums to TreeNodes.
    void populateMap(TreeNode segTree, TreeNode[] map)
    {
        //preorder dfs
        if(segTree == null)
            return;

        if(segTree.ind != -1)
            map[segTree.ind] = segTree;

        populateMap(segTree.left, map);
        populateMap(segTree.right, map);
    }

    TreeNode buildSegTree(Sum[] sums, int st, int end, TreeNode parent)
    {
        if(st > end)
            return null;

        if(st == end) {
            TreeNode root = new TreeNode(parent, sums[st].ind);
            root.sumInd.add(st);
            return root;
        }

        int mid = st + (end-st)/2;
        TreeNode root = new TreeNode(parent, -1);
        root.left = buildSegTree(sums, st, mid, root);
        root.right = buildSegTree(sums, mid+1, end, root);
        for(int i=st; i<end+1; ++i) // this loop does not change tree build complexity O(nlgn)
            root.sumInd.add(i);

        return root;
    }

    int searchRange(Sum[] sums, TreeNode segTree, int low, int high) {
        if(segTree == null)
            return 0;

        int lowSum = sums[segTree.sumInd.get(0)].val;
        int highSum = sums[segTree.sumInd.get(segTree.sumInd.size()-1)].val;

        if(high < lowSum || highSum < low)
            return 0;

        if(low <= lowSum && highSum <= high)
            return segTree.sumInd.get(segTree.sumInd.size()-1) - segTree.sumInd.get(0) + 1;

        int count = 0;
        count += searchRange(sums, segTree.left, low, high);
        count += searchRange(sums, segTree.right, low, high);
        if(segTree.ind!=-1 && isValid(sums[segTree.ind].val, low, high))
        {
            count+=1;
        }

        return count;
    }
}

- jiangok2006 November 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Assuming the array has unique numbers we need to only find the largest sequences.
Then the number of total sequences is n(n+1)/2.

- EasternMonk June 19, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

I think it can be done in O(n) time.

Given an arr of len=5 such as {-2, 5, -1, -2, -1}, imagine all the sums you need to calculate organized like this, where each number on lines 1-4 is the sum of the length of numbers on line 0 if you draw a triangle to it. So the -1 on line 4 is a sum of all the numbers on line 0. And the -4 on line 2 is a sum of {-1, -2, -1} and the 4 on line 1 is a sum of {5, -1}

0:  -2    5    -1    -2    -1
1:      3     4    -3     -3
2:         2      2     -4
3:             0      1
4:                 -1

You can rotate to its side and represent the above in an n x n matrix:

0   1   2   3   4

0     -2
1      3   5
2      2   2  -1
3      0   2   0  -2
4     -1  -4   1 -1  -1

And the algorithm to populate it and count the number of subarrays is something like

int[][] sums = new int[len][len];
int count = 0;

// populate the middle diagonal with arr, and along the way,
// check whether the number is between a and b
for (int i =0; i < len; i++) {
    sums[i][i] = arr[i];
    if (arr[i] >= a && arr[i] <= b) {
        count++;
    }

// now populate "lines" 1-4
for (int line=1; i < len; i++) {
    int tmp = sums[line-1][line-1] + sums[line][line];
    sums[line -1][line] = tmp;
    if (tmp >= a && tmp <= b) {
        count++;
    }
}

System.out.println(count);

It takes two unnested for loops, so that's O(n);

This is my first time answering Career Cup. Please be nice:)

- lindat September 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

it seems like there are O(n^2) elements in triangle.

- emb September 29, 2015 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 vote

Put suffix and prefix sums in a map. Then iterate the map to find what falls in the range. O(n)

- Noobie September 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

Put suffix and prefix sums in a map. Then iterate the map.Put suffix and prefix sums in a map. Then iterate the map to find what falls in the range. O(n)

- Noobie September 26, 2015 | 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