## Google Interview Question for Software Engineers

Country: India
Interview Type: Phone Interview

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

Doing the sum of each number with the rest of numbers in the array will result in O(n^2).

To do better, you need to sort the array with a sorting criteria Abs(number) this will complete in O(nlog(n))

and will give a result like the following:

10, -50, -20, 1, 2 , -5, 51, 70 => 1, 2, -5, 10, -20, -50, 51, 70

Now adding each two consecutive numbers will take O(n-1) and will result in finding -50 and 51 as having the closest sum to zero

Total cost of the operation is n(1 + log(n)) which is way less than O(n^2)

It is also possible to optimize this further, by checking (while sorting) if the array contains only positive or negative numbers.

In this case the closest sum to zero is guaranteed to be the first 2 numbers in the sorted array

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

great solution!

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

Yep, I did the same thing without the optimisations:

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

using namespace std;

struct {
bool operator() (const int& a, const int& b) {
return abs(a)<abs(b);
}
} comparator;

int main() {

vector<int> a = {-23, -21, 12, 123, 11, 23, 1, -111, 44};
sort(a.begin(), a.end(), comparator);

int min = 100000;
for (int i=0; i<a.size()-1; ++i) {
if (min > abs(a[i]+a[i+1]))
min = abs(a[i]+a[i+1]);
}
cout << min;
return 0;
}``````

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

you could have just sorted the array regularly. Then have two indices i and j pointing to the start and end of the sorted array. Calculate the difference, move j to the left if difference is greater than zero and move i to the right if it is less than zero. Record and find the minimum difference on the way.

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

This does not work for -3 -2 0 2.
The answer should be -3, 2, while the above solution gives -2, 0.
Anonymous's idea should work.

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

Here's an O(n) solution which works with negative numbers.

``````int smallest_pair(int* array, int n)
{
int runningSum = array;
int globalMin = INT_MAX;
for(int i = 1; i < n; ++i)
{
runningSum += array[i];

if(abs(runningSum) < abs(globalMin))
{
globalMin = runningSum;
}

runningSum -= array[i - 1];
}
return globalMin;
}``````

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

Note: this assumes that you're wanting to find the minimum sum of two pairs that are TOGETHER.

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

Note: this assumes you're wanting to find a contiguous pair within the array.

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

Correct me if I am wrong, but I doubt that this solution will work. You only compare elements that are close to each other. So { 1, -3, 200 } with your algorithm will work and return -2. But {1, 100, -3, 200 } won't work and will return 97.

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

Correct me if I am wrong, but I doubt that this solution will work. You only compare elements that are close to each other. So { 1, -3, 200 } with your algorithm will work and return -2. But {1, 100, -3, 200 } won't work and will return 97.

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

Correct me if I am wrong, but I doubt that this solution will work. You only compare elements that are next to each other. So { 1, -3, 200 } with your algorithm will work and return -2. But {1, 100, -3, 200 } won't work and will return 97.

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

Correct me if I am wrong, but I doubt that this solution will work. You only compare elements that are close to each other. So { 1, -3, 200 } with your algorithm will work and return -2. But {1, 100, -3, 200 } won't work and will return 97.

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

``````using System;
using System.Collections.Generic;
using System.Linq;

public class Program
{
public static void Main()
{
var p = Find(new int[]{-4,1,2,3});
Console.WriteLine("{0}:{1}", p.Val1, p.Val2);
}

public static Pair Find(int[] arr){
List<Pair> lst = new List<Pair>();
for(int i=0; i< arr.Length; i++){
int d = int.MaxValue;
Pair closest = null;
for(int j =0; j < arr.Length; j++){
if(i != j && arr[i]+arr[j] < d){
d = Math.Abs(arr[i]+arr[j]);
closest = new Pair(){
D = d,
Val1 = arr[i],
Val2 = arr[j]
};
}
}
if(closest != null)
}
return lst.OrderBy(x => x.D).FirstOrDefault();
}
}

public class Pair{
public int D {get; set;}
public int Val1 {get; set;}
public int Val2 {get; set;}
}``````

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

``````void findPairThatSumsCloseToZero(vector<int> a)
{
int i, j, best, cur_best, n = a.size();
int best_start, best_end;
if (n < 2) return;

sort(a.begin(), a.end());
i=0, j=n-1;
best = a[i] + a[j], best_start = i, best_end = j;

while (i < j) {
cur_best = a[i] + a[j];
if (abs(cur_best) < abs(best)) {
best = cur_best;
best_start = i, best_end = j;
}

if (cur_best < 0) {
i++;
} else if (cur_best > 0) {
j--;
} else {
break;
}
}

printf("closest to zero=%d found at index %d and %d\n", best, best_start, best_end);
}``````

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

``````void findPairThatSumsCloseToZero(vector<int> a)
{
int i, j, best, cur_best, n = a.size();
int best_start, best_end;
if (n < 2) return;

sort(a.begin(), a.end());
i=0, j=n-1;
best = a[i] + a[j], best_start = i, best_end = j;

while (i < j) {
cur_best = a[i] + a[j];
if (abs(cur_best) < abs(best)) {
best = cur_best;
best_start = i, best_end = j;
}

if (cur_best < 0) {
i++;
} else if (cur_best > 0) {
j--;
} else {
break;
}
}

printf("closest to zero=%d found at index %d and %d\n", best, best_start, best_end);
}``````

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

Sort the array nlogn...Use binary search and at every mid element sum mid with mid-1..if sum < 0 move to mid+1 else move mid-1 ..

I think this might do O(n(1+lgn))

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

Sort and get O(nlgn) and use binary search - if the mid+mid-1>0 move to binarySearch(min,mid-1) else binarySearch(mid+1,max) to reach a point where the sum is near to zero..then you just need to check in the vicinity to find the final answer...

I think this might do better than O(n+nlogn) - maybe O(lgn+nlgn)

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

(in java or C)

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

``````class SolutionSumClosestToZero {
public void solution(int[] arr) {
if(arr.length <=1) {
System.out.println("NOT ENOUGH ELEMENTS IN THE GIVEN ARRAYS");
return;
}

Arrays.sort(arr);
int first = arr;
int secnd = arr;
int min = Math.abs(first) + Math.abs(secnd);
for(int i = 2; i < arr.length; i++) {
if(min > Math.abs(arr[i-1]) + Math.abs(arr[i])) {
min = Math.abs(arr[i-1]) + Math.abs(arr[i]);
first = arr[i-1];
secnd = arr[i];
}
}

System.out.println("FIRST: " + first + "\t SECOND: " + secnd);
}
}

public class GoogleSumClosestToZero {

public static void main(String[] args) {
SolutionSumClosestToZero mSol = new SolutionSumClosestToZero();
mSol.solution(new int[] {-1,-4,-9,-8,-10,4,2,5,8,9,3,0});
mSol.solution(new int[] {9,9,9});
mSol.solution(new int[] {-1,-5,-2,-9,-6,-4});
mSol.solution(new int[] {-9,-9,-9,-9,-9});
mSol.solution(new int[] {9,8,7,6,5,4,3,2,1});
}
}``````

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

(((
def NearZeroPair(x):
xx = sorted(x)
l, r = 0, len(xx) -1
# If list is all -ve
# Return the last two numbers
if xx < 0 and xx[-1] < 0:
return xx[-2:]
# If list is all +ve
# Return the first two numbers
if xx >= 0 and xx[-1] >= 0:
return sorted(x)[:2]
# If list is a mix of +ve and -ve
# Traverse the sorted array from both ends
# Find the minimum sum
# Return the pair with the minimum sum
min_l, min_r = l, r
min_sum = xx[l] + xx[r]
while l < r:
s = xx[l] + xx[r]
if abs(s) < abs(min_sum):
min_sum = s
min_l, min_r = l, r
if sum < 0:
l += 1
else:
r -= 1
return [xx[min_l], xx[min_r]]
}}}

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

``````def NearZeroPair(x):
xx = sorted(x)
l, r = 0, len(xx) -1
# If list is all -ve
# Return the last two numbers
if xx < 0 and xx[-1] < 0:
return xx[-2:]
# If list is all +ve
# Return the first two numbers
if xx >= 0 and xx[-1] >= 0:
return sorted(x)[:2]
# If list is a mix of +ve and -ve
# Traverse the sorted array from both ends
# Find the minimum sum
# Return the pair with the minimum sum
min_l, min_r = l, r
min_sum = xx[l] + xx[r]
while l < r:
s = xx[l] + xx[r]
if abs(s) < abs(min_sum):
min_sum = s
min_l, min_r = l, r
if sum < 0:
l += 1
else:
r -= 1
return [xx[min_l], xx[min_r]]``````

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

Is this as simple as
If input has negative elements
Min( biggestPositive+smallestNegative , smallestPositive+biggestNegative) . So basically go through array and find four variables
1. biggest Positive
2. smallest Positive
3. biggest Negative
4. smallest Negative

and do above comparison whichever pair satisfies that is the required pair

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

Just a sort followed by binary search for insertion point of zero. Works if array is all positive or all negative or mixed. O(n log n + log n).

``````from bisect import bisect_left
def pairClosestToZero(arr):
arr.sort()    # O (n log n)
insPoint = bisect_left(arr, 0)   # O(log n)
return (arr, arr) if insPoint == 0 else (arr[insPoint-1], arr[insPoint])``````

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

Here is a C++ solution. This is O(nlogn).

int close_to_zero( vector< int > & a){
int i = 0, j = 0;
int min = INT_MAX;
bool has_neg = false, has_pos = false;
size_t size = a.size();

for(i = 0; i < size ; i++)
cout << a[i] << ", " ;

sort( a.begin(), a.end(), less< int >() );

for(i = 0; i < size; i++){
if( a[i] < 0 ){
has_neg = true;
}
else if( a[i] > 0 ){
has_pos = true;
}

if( has_neg && has_pos )break;
}

if( has_neg && ! has_pos ){
min = a[size-2] + a[size-1];
}
else if( !has_neg && has_pos ){
min = a + a;
}
else{
i = 0;
j = size - 1;
int sum = 0;
for(; i < j ;){
sum = a[i] + a[j];
if( abs( sum ) < min ){
min = abs(sum);
}

if( sum < 0 )i++;
else if( sum > 0 )j--;
else break;
}
}

return min;
}

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

Here is an O(nlogn) solution in C++

``````int close_to_zero( vector< int > & a){
int i = 0, j = 0;  int min = INT_MAX;  bool has_neg = false, has_pos = false;
size_t size = a.size();

sort( a.begin(), a.end(), less< int >() );

for(i = 0; i < size; i++){
if( a[i] < 0 )has_neg = true;
else if( a[i] > 0 )has_pos = true;

if( has_neg && has_pos )break;
}

if( has_neg && ! has_pos )min = a[size-2] + a[size-1];
else if( !has_neg && has_pos )min = a + a;
else{
i = 0;j = size - 1;int sum = 0;
for(; i < j ;){
sum = a[i] + a[j];
if( abs( sum ) < min )min = abs(sum);
if( sum < 0 )i++;
else if( sum > 0 )j--;
else break;
}
}
return min;
}``````

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

here is the linear solution, assuming that array is already sorted;
if it's not sorted there is no better solution than O(n*log(n))

``````class Pair <T,T> {
<T> first;
<T> second;
public Pair(<T> first, <T> second) {
this.first = first;
this.second = second;
}
}

Pair<Integer, Integer> findPair(int[] arr) {
int i = 0;
int j = arr.length - 1;
Pair<Integer, Integer> ans = new Pair(i, j);

while ( i + 1 < j ) {
cur = Math.abs( arr[i] + arr[j] );
if ( cur < Math.abs(arr[ans.first] + arr[ans.second]) ) {
ans.first = i;
ans.second = j;
}
if ( Math.abs(arr[i+1] + arr[j]) > Math.abs(arr[i] + arr[j-1]) ) {
i++;
} else {
j--;
}
}
return ans;
}``````

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

Could we do a search for the two smallest numbers in the array and add them together?
Would this work?

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

``````int smallestSum(int arr[N])
{
int min1 = arr;
int min2 = arr;

for(int i=2;i<N;i++)
{

if(arr[i] < min1)
{
if(min1 < min2)
{
min2 = min1;
}

min1 = arr[i];
}
else if(arr[i] < min2)
{
if(min2 < min1)
{
min1 = min2;
}

min2 = arr[i];
}

}

return (min1+min2);
}``````

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

This would be O(N)

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

Actually just realized this wouldn't work if we have negative numbers...

But maybe the function can be modified to find the two numbers closest to zero and add them together.

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

epic fail.... :)

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

"Find the two numbers closest to zero and add them together" is not correct. For example, it fails on [-10, -1, 2, 10].

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.