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

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

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

nice solution.

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

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

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

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

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

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

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.

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

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

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

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

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

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

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

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

}}

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

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

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

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

nice job :)

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

Thank you:)

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

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

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

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

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

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

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

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

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

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.

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

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

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

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

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

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

@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

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

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

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

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

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

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

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.

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

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?

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

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

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

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

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

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?

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

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

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

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

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

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

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

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

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

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.

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

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

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

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.

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

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

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

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.

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

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?

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

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.

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

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.

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.

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++;
}
}
}
public void insert(int 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);
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);
}
}``````

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

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.

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

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

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

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

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

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

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

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

}

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

}``````

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

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

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.

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

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

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

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)

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

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.