Google Interview Question for Software Engineers


Country: India
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
15
of 15 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

- zsalloum April 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

great solution!

- SK April 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- nikolay.dimitrov April 13, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous April 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- zjzzjz September 20, 2015 | Flag
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[0];
    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;
}

- Miguel April 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Miguel April 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Miguel April 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Michael April 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Michael April 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Michael April 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Scavi April 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

What about this?

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)
				lst.Add(closest);
		}
		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;}
}

- ArtD April 12, 2015 | Flag Reply
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);
}

- mytestaccount2 April 13, 2015 | Flag Reply
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);
}

- mytestaccount2 April 13, 2015 | Flag Reply
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))

- Saurabh April 14, 2015 | Flag Reply
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)

- Saurabh April 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Could you please write your code?
(in java or C)

- Hengameh April 15, 2015 | Flag
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[0];
        int secnd = arr[1];
        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});
    }
}

- Scorpion King April 23, 2015 | Flag Reply
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] < 0 and xx[-1] < 0:
return xx[-2:]
# If list is all +ve
# Return the first two numbers
if xx[0] >= 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]]
}}}

- zingcat May 21, 2015 | Flag Reply
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] < 0 and xx[-1] < 0:
		return xx[-2:]
	# If list is all +ve
	# Return the first two numbers
	if xx[0] >= 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]]

- zingcat May 21, 2015 | Flag Reply
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

- Santhosh June 19, 2015 | Flag Reply
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[0], arr[1]) if insPoint == 0 else (arr[insPoint-1], arr[insPoint])

- AS July 28, 2015 | Flag Reply
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[0] + a[1];
}
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;
}

- Santosh August 06, 2015 | Flag Reply
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[0] + a[1];
  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;
}

- Santosh August 06, 2015 | Flag Reply
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;
}

- gime July 06, 2016 | Flag Reply
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?

- Alex April 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

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

- Alex April 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This would be O(N)

- Alex April 11, 2015 | Flag
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.

- Alex April 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

epic fail.... :)

- Alex April 11, 2015 | Flag
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].

- AP April 14, 2015 | 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