## Google Interview Question for Software Engineer / Developers

• -3

Country: United States
Interview Type: In-Person

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

easy job. use integration of the arrays from a[0] to a[i] ->b[i]
e.g.
b[0] = a0
b[1] = a0 + a1
...

the sum from a[i] to a[j] is b[j] - b[i]

search sum in range from 0 to n
record i = min position, j = max position that fits the sum range

note i and j only increase,

then search should be done in O(n)

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

Post your (from, to) linear psuedocode ?

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

to search all the sequence, you need to search:
i=0,j=0,1,2,3....n
i=1,j=1,2,3,....n
i=2,j=2,3,....n
i=n,j=n
the total the total iteration is 1+2+3.....+n = o(n^2)

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

It can be O(n* (2*logn)) if you only need the number of sums. Because you only need to find the first i and k for every j where the sum is out of the range. For that you can use binary search. Once you have those elements, you know the number of sums including j.

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

ok so with 3 indeces i, j, k and all number positive it indeed can be O(n) since then indeed all of them only increasing.

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

Counting the number of subsequences is O(n^2) in the general case as well.
If you assume non-negative values in the array or a sorted array then O(n) is achievable.

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

``````void printAllSeqSumInRange(int *arr, int size, int low, int high)
{
std::queue<int> q1;
int item;
printf("\nAll Continuous Subsequence in the array coming in Range %d--%d are:", low, high);
for(int i=0; i< size; i++)
{
if (sumInRange(q1, arr[i], low, high))
q1.push(arr[i]);
else
{
printf("\nRange is:");;
printQueue(q1);
while(! q1.empty())
{
q1.pop();
if(sumInRange(q1, arr[i], low, high))
{
q1.push(arr[i]);
break;
}
else
continue;
}
}
}
printf("\nRange is:");;
printQueue(q1);
}``````

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

what is the complexity of sumInRange,is not it o(n)?

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

Why post code that is >= N^2?

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

@All : I am a bit confused with the question you have mentioned

" find all continuous subsequences in the array which have sum in the range "

For a array : 4, 9,12,16,5,2,1,3,11

for this array : min, max is 1,16

so the output what i think is : " l the continuous subsequences whose sum in range" are : {4,9}, {12},{16},{5,2,1,3} ,{11}

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

is it a sorted array?

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

If you need to print every result, then No.

This is because in worst case, all number pairs needs to be printed. To print all subsquence, you need O(n^2).

However, if you just want to print a (from, to_rang), then it's possible in O(n)

e.g.
from = a[0]
to_range = (3,5) which means a[3]...a[5] are all fit.

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

Post your (from, to) linear algorithm ?

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

If we have to find all the subsequences then a soluction cannot be less than O(n^2). However if we only have to find out how many such subsequences are there then there is an O(nlogn) solultion for it.

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

``````public class p {

public static void main(String ap[]) {
( new p() ).checkRange(new int[]{3,4,5,7,0,10}, 2, 15) ;
}

public void checkRange(int[] array, int low, int high) {
ArrayList<Info> lists = new ArrayList<Info>();
int step = 0;
for (int i:array) {
Info info = new Info(); info.addNum(i);
}
for (int i: array){
int loop = 0;
for (Info iii:lists) {
if (loop == step) {
loop++;
continue;
}
loop++;
if (iii.checkSum(high, low)) {
System.out.println(iii.toString());
}
}
step++;
}
}

private class Info {
// can also use Stack or queues here.
private ArrayList<Integer> arr=new ArrayList<Integer>();
@Override
public int hashCode() {
int i = 23;

for (Integer ii:arr)
i = i + 3 * ii;

return i;
}

@Override
public boolean equals(Object o) {
if (o == null || ! (o instanceof Info) )
return false;
Info obj = (Info)o;
if (obj.getArr().size() != arr.size())
return false;

synchronized(arr) {
synchronized (obj.getArr()) {
for (int i: obj.getArr())
if ( ! arr.contains(i) )
return false;
for (int i: arr)
if ( ! obj.getArr().contains(i) )
return false;
}
}
return true;
}
public ArrayList<Integer> getArr() {
return arr;
}
synchronized(arr){
}
}
public void removeNum(int i) {
synchronized(arr){
if(arr.contains(i))
arr.remove(i);
}
}
public boolean checkSum(int high, int low)  {

if (high == low && arr.size() == 0)
return false;

int sum = 0;
synchronized(arr) {
for(Integer a:arr) {
sum=sum+a;
}
}
if (sum <=high && sum >= low)
return true;
return false;
}
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("[");
for (int i:arr)
sb.append(i).append(" ");
sb.append("]");
return sb.toString();
}
}
}``````

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

``````vector<pair<int, int>> find(vector<int> A, int low, int hight) {
vector<pair<int, int>> result;
int n = A.size();
int tail = 0;
int sum = 0;

while(tail < n){
int temp = sum + A[tail];
if(temp < low){
sum = temp;
tail++;
}else if(temp >=low && temp <=high){
sum = temp;
tail++;
}else{
sum = 0;
}
}
}

if(sum < low){
break;
}else if(sum >= low && sum <=high){
}
}

return result;
}``````

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

Hi Everyone. Here is some code that does the job in O(n^2):

``````#include<iostream>
#include<vector>

void getAllSubSequencesInRange(int low, int high, int *list, int lengthOfList, std::vector<std::vector<int> >& subSequences){
for (int iMax=0; iMax<lengthOfList; iMax++){
int sum=list[iMax];
int iMin=iMax;
while((sum<=high) && (iMin>=0)){
if (sum>=low) {
std::vector<int> subSequence(2);
subSequence[0]=iMin;
subSequence[1]=iMax;
subSequences.push_back(subSequence);
};
iMin--;
sum+=list[iMin];
};
};
}

int main(){
int list[10] = {11,2,3,5,6,7,2,1,0,0};
std::vector<std::vector <int> > subSequences;
getAllSubSequencesInRange(2,6,list,10,subSequences);
for (int i=0; i<subSequences.size(); i++)
std::cout << subSequences[i][0] << ", " << subSequences[i][1] << std::endl;
}``````

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

My solution has O(Nˆ2) time complexity and O(1) memory complexity for the worst case.
Furthermore this algorithm is optimized relatively to the output size. So, if a given instance have output O(N) the algorithm will works in O(N).

I think that are not a better solution then O(Nˆ2), because there are instances that the output is O(Nˆ2), like this following:
range: [1 3]
Vector: 1, 1, 1, 1, 1, 1

``````#include <vector>
#include <iostream>
using namespace std;

// time: O(Nˆ2)
// memory: O(1)
void find_interval(const vector<int> &v, int min_v, int max_v) {
int begin = 0;
int end = 0;
int curr_sum = 0;
for (end = 0; end < v.size(); end++) {
curr_sum += v[end];
// remove elements from beging
while (begin < end && curr_sum > max_v) {
curr_sum -= v[begin];
begin++;
}

int ns = curr_sum;
int nb = begin;
while (ns >= min_v && ns <= max_v && nb <= end) {
cout<<nb<<" "<<end<<endl;
nb++;
ns -= v[nb];
}
}
}``````

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

sliding window problem

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

The problem could be solved in O(nlogn) using Dynamic Programming if one were only to determine count of such sub-sequences.

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

Find all continuous sequences? Better than O(n^2) is not possible. Why do you ask? Was the problem different? Perhaps a count instead of a list?

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

There are O(n^2) continue subsequences in an array. So finding them all is at minimum n^2

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

Here is a solution, with print format like
i -> (from, to) indicating i to from, i to from + 1, i to ... to are all possible squences. This runs in O(n) time. If you need to print all sequence individually, then it can't be done in less than O(n^2), suppose in worst case, all kinds of sequences are within the defined range, you need to print that number of times.

``````#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

void print(int from, std::pair<int, int> range)
{
std::cout << from << "->" << range.first << "..." << range.second << "\n";
}

void find_sum_in_range(int* array, int size, int low, int high)
{
int* integration = new int[size];
memset(integration, 0, sizeof(int) * size);

int sum = 0;

for (int i = 0; i < size; ++i)
{
sum += array[i];
integration[i] = sum;
}

int i = 0, j = size;
sum = 0;

while (i < size && (integration[i] - sum < low)) i++;
if (i == size)

j = i;
while (j < size && integration[j] - sum <= high)
{
++j;
}

print(0, std::pair<int, int>(i, j - 1));

for (int p = 0; p < size; ++p)
{
sum = integration[p];

while (i < size && integration[i] - sum < low) ++i;
if (i == size) return; // end
while (j < size && integration[j] - sum <= high) ++j;

print(p + 1, std::pair<int, int>(i, j - 1));
}
}

int main()
{
int array[] = {3,1,2,5,6,4,3,7};
find_sum_in_range(array, sizeof(array) / sizeof(int), 10, 20);
return 0;
}``````

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

You have good idea, but your program is still running in O(n^2) time because of

``````for (int p = 0; p < size; ++p)
{
sum = integration[p];

while (i < size && integration[i] - sum < low) ++i;
if (i == size) return; // end
while (j < size && integration[j] - sum <= high) ++j;

print(p + 1, std::pair<int, int>(i, j - 1));
}``````

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

I guess you have to find the closest match for each index with binary search, but that only works if the numbers are not negative.

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

The point is by iterating each number, i and j only increase from the previous positino, so its complexity is not O(n^2).

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

Hi, can you explain with comments in code or pseudocode or summary of algorithm? [I don't now C++]

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

If all numbers are positive or negative, then it can be achieved in sub O(n^2), however if there are mix of nubers, O(n^2) is the lower boundary.

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

OBIWANA!

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

easy job. use integration of the arrays from a[0] to a[i] ->b[i]
e.g.
b[0] = a0
b[1] = a0 + a1
...

the sum from a[i] to a[j] is b[j] - b[i]

search sum in range from 0 to n
record i = min position, j = max position that fits the sum range

note i and j only increase,

then search should be done in O(n)

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

Post your (from, to) linear code(with comment) ?

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

Linear time is not possible. This is nonsense (though the initial part is good and can be used to get O(n log n) time for counting the number)

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

Obiwana has to look up glassdoor to find out.

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.