Google Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
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)
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.
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.
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);
}
@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}
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.
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();
}
}
}
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;
}
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;
}
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];
}
}
}
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;
}
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));
}
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.
The point is by iterating each number, i and j only increase from the previous positino, so its complexity is not O(n^2).
Hi, can you explain with comments in code or pseudocode or summary of algorithm? [I don't now C++]
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)
easy job. use integration of the arrays from a[0] to a[i] ->b[i]
- guest.guest March 22, 2014e.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)