Google Interview Question for Software Engineer / Developers


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)

- guest.guest March 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Post your (from, to) linear psuedocode ?

- Anonymous March 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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)

- liufeng2013fall June 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- megmondoEmber October 04, 2014 | Flag
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.

- Anonymous October 04, 2014 | Flag
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.

- javierturek October 13, 2014 | Flag
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);
}

- AgentMac March 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous March 21, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Why post code that is >= N^2?

- Anonymous March 21, 2014 | Flag
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}

- Anonymous March 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

is it a sorted array?

- pradeek.k March 22, 2014 | Flag Reply
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.

- guest.guest March 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Post your (from, to) linear algorithm ?

- Anonymous March 24, 2014 | Flag
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.

- kr.neerav March 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Comments/feedback appreciated.

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);
            lists.add( info );            
        }
        for (int i: array){
            int loop = 0;
            for (Info iii:lists) {
                if (loop == step) {
                    loop++;
                    continue;                    
                }
                loop++;
                iii.addNum(i);
                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;
        }
        public void addNum(int i) {
            synchronized(arr){
                arr.add(i);
            }
        }
        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();
        }
    }
}

- SIDHU March 25, 2014 | Flag Reply
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 head = 0;
	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++;
			result.push_back(make_pair(head, tail));
		}else{
			sum -= A[head];
			head++;
			if(head > tail){
				tail = head;
				sum = 0;
			}
		}
	}

	while(head <= tail){
		sum -= A[head];
		head++;
		if(sum < low){
			break;
		}else if(sum >= low && sum <=high){
			result.push_back(make_pair(head, tail);
		}
	}

	return result;
}

- babula April 18, 2014 | Flag Reply
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;
}

- Anonymous May 02, 2014 | Flag Reply
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];
        }
    }
}

- thiago.xth1 June 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

sliding window problem

- allen.lipeng47 December 31, 2014 | Flag Reply
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.

- AbhiR April 17, 2015 | Flag Reply
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?

- Anonymous March 21, 2014 | Flag Reply
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

- Ubbus El March 21, 2014 | Flag Reply
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)
    return; // not found

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

- guest.guest March 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- ctash March 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- ctash March 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- guest.guest March 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Suhani garg March 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- guest.guest March 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 vote

OBIWANA!
Did the google interviewer ask you for a certain time complexity???????????

- Suhani garg March 21, 2014 | Flag Reply
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)

- guest.guest March 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous March 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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)

- Anonymous March 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 votes

Obiwana has to look up glassdoor to find out.

- Ubbus El March 21, 2014 | Flag


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