## Google Interview Question for Software Engineer / Developers

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

1.The idea is to find (a,b,c) such that a-b=c ..in other words, a=b+c;

2. We know that if an array is sorted, we can find two numbers(b,c) which sum up to a
particular value(a) in O(n) time.

3. So start from the end of the array.For each value a[i], search for sum=a[i] between a[0] and a[i-1]. Starting from the end makes sure we can eliminate any option to the right of that element as such an element will not satisfy the equation a=b+c

4. Complexity =n*O(n) =O(n^2);

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

The solution is correct, however, another tricky part is a-b=c is not completely equals to a=b+c, because given a=b+c, you can have both a-b=c and a-c=b. So don't forgot to output two results when you found a a=b+c.

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

This all depends on what sort of output interviewer wants.
Are the tuples 5-3=2[5,3,2] would be considered same as 5-2=3[5,2,3] as both sets have same set of values.

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

Here is the output for above example:

``````-12 = -7 - 5
-12 =  3 - 15
-7 = -4 - 3
-7 =  3 - 10
-7 =  9 - 16
-4 =  5 - 9
3 = -4 - -7
5 = -7 - -12
5 = 15 - 10
10 = 3 - -7
10 = 15 - 5``````

You should assume that no number is repeated.

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

Forgot to add 2 more outputs:

``````15 = 3 - (-12)
16 = 9 - (-7)``````

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

found one more.
9 = 5 - -4

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

I find a similar problem (appeared on google interview) here:
careercup.com/question?id=9449188

However, that problem is simpler as it asks to output pair of integers from a given sorted array A (with no duplicates) such that a - b = k (given integer). I could come up to solve it in O(n) as below. However, the scenario for above case is different, as the target is a variable (not a fixed value k).

``````void diffOfTwo (int a[], int n, int k)
{											for (int j = 1, i = 0; j < n; j++)
{
while ( i < j)
{
if ( a[j] - a[i] == abs (k) )
{
//solution found
i++, j++;
}

else if ( a[j] - a[i] > abs(k) )
i++;

else j++;
}
}
}``````

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

How would you solve it in O(n) when there are O(n^2) sums or differences?

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

Essentially - find the triplets that a = b+c.
If the elements are integers and have an upperbound, i.e., array contains integers less than 'K', then it is easy to do this O(n^2)
We need to check for every pair of numbers if their sum is already in the array.
Given the array length is n, we have O(n^2) checks to make.
But then, each check will take atmost K checks -- O(1). Here's how:
If we are analysizing say b and c. Because it is sorted integer array, the sum (b+c) must lie within 'c'-distance of 'b' or 'b'-distance of 'c'.
The direction of search will depend on the sign of either of b or c.
So, we have an O(n^2) solution.

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

Good approach. I should think in that way :(

A follow up question was like "find triplet <a,b,c> such that (a+b+c) is closest to 0". Any idea how to solve this?

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

This is pseudo polynomial O(n^2*K). I don't think it is correct.

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

You can hash the values of the array.
And for each pair, check if their sum too is present in the hash table.
Hence complexity is O(n^2)

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

@anony.. the second question is related to the first one.

3 numbers can sum to 0 under the following conditions
1. A[a] == -A[b], c== 0 exist
2. A[a] == -(A[b]+A[c]) exist
3. 0, 0, 0

so the so the 1 and 3 are easy to be checked. and for 2 you have already the sums a = c+b

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

add all the possible sums i.e. a+b from the array to a set. Now check the array if the element is in the set.
eg: a[]={2,3,5,4,9};
set: { 5,6,7,8,9,11,12,13,14 }
ans: 2,3,5 and 4,5,9
complexity: O(n**2 + n) ~ O(n**2)

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

How come the second check is O(n). I think this is wrong.

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

``````#include <iostream>
using namespace std;
void binder(int*a, int n) {
for (int i = 0; i < n; i++) {
int current = a[i];
int left = 0;
int right = n-1;
while (left < right) {
if ( left == i ) {
left++;
continue;
}

if (right == i) {
right--;
continue;
}

if (a[left] + a[right] < current) {
left++;
} else if (a[left] + a[right] > current) {
right--;
} else {
cout << current << " = " << a[left] << " + " << a[right] <<endl;
left++;
right--;
}
}
}
}

int main() {
int a[] = {-12, -7, -4, 0, 3, 5, 9, 10, 15, 16};
binder(a, 10);
return 0;
}``````

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

Looks ok to me.
Idea is - for every number A[i[, check if it can be expressed as a sum of A[j] & A[k], i!=j, i!=k.
Each such check will start with left = 0, right = n-1 and incrementing left or decrementing right, if A[left] + A[right] is lesser than (or greater than) A[i].
So O(n) for 1 element, O(n^2) for n elements.

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

it wont work for all test cases!

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

1. insert array to a hash table. O(n)
2. select a and b in two loops. O(n^2)
3. check if there is c in the hash table such that c = a-b. O(1)

=> O(n^2)

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

since no. are in increasing order and not repeated ,triplet(a,b,c) must be unique.
think a=b-c as b=a+c
let i=0,j=lastindex,k=lastindex of array
while(i<j)
{ j=k=last;
while(i<k)
{ if(a[i]+a[j]==a[k])
{ //a triplet found
j--;k--;
}
else if(a[i]+a[j]<a[k])
k--;
else
j--;
}
}

my idea is similar to anonymous on August 04, 2011(given above) modified for a-b=c;
complexity=O(n^2).

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

we should solve the a=b+c problem.
1-for each pair compute b+c and store it in another data structure(e.x. array). it takes O(n^2).
notion: Since the input array is sorted the summation array which keeps b+c can be easily computed in such a way to be sorted too!
2-match the input array with the summation array to find a=b+c. do this by binary search on the summation array per each number in input array. it takes O(n*log(2^n))=O(2n*log(n))

so the complexity is O(n^2)+O(nlogn)= O(n^2)

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

Really good answer. :) Works perfectly.. :) Guess the trick is using which array for binary search.

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

Wait!! I take back my comment. How will keep the sum array sorted? It will take (n^2*log n) to keep the sum array sorted.(merging n sorted lists of size n each)

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

You can always keep the array sorted, by considering the loop 0<=i<N and i<j<=N, the modification to the binary search is: you can merge the lists of size n^2 and n. Merging sorted list tells us the collisions. That will give us a O(n) + O(n^2) solution too.

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

``````public void FindTriplets(int[] inp)
{
//all a-b=c combinations
Hashtable ht = new Hashtable();
for (int i = 0; i < inp.Length; i++)
{
ht[inp[i]] = 1;
}
for (int i = 0; i < inp.Length; i++)
{
for (int j = 0; j < inp.Length; j++)
{
if (i != j)
{
int diff = inp[i] - inp[j];
if (!(diff == inp[i] || diff == inp[j]))
{
if (ht.Contains(diff))
{
Console.WriteLine(inp[i].ToString() + "-" + inp[j].ToString() + "=" + diff.ToString());
}
}
}
}
}
}``````

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

Looks good. It seems to be straight forward.
Although i think there might be a better solution just because this solution doesn't really use the fact that the array is sorted or may be using less space.

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

1. Find all pairs of sum c = a + b, a is from the first array and b is from the second array ----- this cost O(N^2);
2. Sort the set which contains all the pair sum using radix sort. It costs O(N^2);
3. Find the common elements between the sorted array in step 2 and the first array or the second array by merging.

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

for a-b = c:
#include <iostream>
using namespace std;

void getTriple(int *array, int n)
{
for (int i = 0; i < n; ++i)
{
int sum = array[i];
int j = 0;
int k = n - 1;
while (j < k)
{
if (array[j] + array[k] < sum)
{
++j;
}
else if (array[j] + array[k] > sum)
{
--k;
}
else
{
if (i != j && i != k)
{
cout << sum << " " << array[j] << " " << array[k] << endl;
}
++j;
--k;
}
}
}
}

int main()
{
int n;
int array[1000];
cin >> n;
for (int i = 0; i < n; ++i)
{
cin >> array[i];
}
getTriple(array, n);
return 0;
}

for a+b+c=0

#include <iostream>
using namespace std;

void getTriple(int *array, int n)
{
for (int i = 0; i < n; ++i)
{
int sum = -1 * array[i];
int j = i + 1;
int k = n - 1;
while (j < k)
{
if (array[j] + array[k] < sum)
{
++j;
}
else if (array[j] + array[k] > sum)
{
--k;
}
else
{
cout << sum << " " << array[j] << " " << array[k] << endl;
++j;
--k;
}
}
}
}

int main()
{
int n;
int array[1000];
cin >> n;
for (int i = 0; i < n; ++i)
{
cin >> array[i];
}
getTriple(array, n);
return 0;
}

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.