Google Interview Question Software Engineers
Country: India
Interview Type: Phone Interview
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;
}
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.
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;
}
Note: this assumes that you're wanting to find the minimum sum of two pairs that are TOGETHER.
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.
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.
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.
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;}
}
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);
}
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);
}
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)
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});
}
}
(((
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]]
}}}
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]]
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
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])
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;
}
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;
}
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;
}
Could we do a search for the two smallest numbers in the array and add them together?
Would this work?
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);
}
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.
Doing the sum of each number with the rest of numbers in the array will result in O(n^2).
- zsalloum April 10, 2015To 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