## Amazon Interview Question for Software Engineer / Developers

Team: Kindle Device
Country: India
Interview Type: Phone Interview

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

Sort the array.
Initialize l = 0, r = size-1.
In each iteration compare a[l]+a[r] with closest sum to 0 ( min_sum ) found so far and update the min_sum if required.
If a[l]+a[r] < 0 => l++
else => r--

``````void fsum( int *a, int n )
{
//n = size of array a
sort( a, a+n ); //STL sort
int l, r, al, ar, sum, min_sum;
min_sum =  INT_MAX;
for( l = 0, r = n-1; l < r; sum < 0 ? l++ : ( r-- )  ) {
if( abs( sum = a[l]+a[r] ) < abs(min_sum) ) {
min_sum = sum;
al = l;
ar = r;
}
}
print( "%d %d\n", al, ar );
}``````

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

If you handle the base cases, then the best-case running time is O(n). If all integers are positive, find two smallest values. Otherwise, if all ints are negative, find two greatest values.

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

It works fine. I've checked for {7,-7} also.

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

Okay. You are correct. It works for 7, -7.

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

i don't think this solution is correct
for the data set -2,-1,3,5
ans-> 1
but according to this algo it would e -3

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

sorry my bad, i din think it through

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

sort the array and add first and last element.depending upon the sum,move from beginning or from end.
If sum is less than 0,move from beginning and if sum is greater than 0,move from end.store the minimum difference from 0.

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

Thank you Cerberuz and Abhishek,
I did it using two for loops in O(n^2). But the interviewer asked me to reduce the complexity.
As per your algorithm, it's O(n logn). Is it any possibility to reduce the complexity to O(n)?

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

Linear time can be achieved by using counting sort ( range of elements should be low ) OR hashing with counting sort.

If you can find a solution of closest pair of point problem in 2D in linear time then you can obtain the solution to this problem ( closest pair in 1D ) also in linear time.

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

First, counting sort may be optimized using a hashtable instead of an array, thereby reducing memory overhead and eliminating the concern of the input range.

For this problem, counting sort will not be good because some of the integers may be negative, thereby forcing you to create a hashcode for negative ints, which is not a simple task to do since the hashcode could collide with other values in the 32-bit integer range.

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

@Jack: how will you optimize counting sort using a hash table? Since a hash table maintains things in unsorted order, you'd still have to sort afterwards.

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

The hashtable would be used for storing counts, whereas another loop would iterate from 0 to m-1, where m is the largest value in the input. Example, if thr input is 1,50000, then store 2 entries for count, and iterate from 0 to 49999.

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

@Jack: I wouldn't say this "eliminates the concern of the input range". It reduces space requirements, but you'd be doing O(n+m) hash lookups, where n is the input size and m is the range. It's not like you've eliminated the m completely. And hash lookups are relatively slow in terms of the arithmetic required and because they're full of cache misses, so exacerbating the m factor with that is pretty bad. Still, it's an interesting idea.

I also don't see why hashing negative numbers is a problem. You can just use their 2s complement representation and treat them as positive numbers.

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

1. Okay. Creating a hashtable that would optimize counting sort's space overhead, but still be O(1) is not trivial, so maybe it's simpler to just use a plain array. Perhaps it's possible to allocate a hashtable via statistical benchmarks?

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

@Jack: what sort of benchmarks do you have in mind?

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

The bigger the table, the less # of collisions. It's naive and wasteful to create a count array of size Long.MAX_VALUE for two numbers like 1 and Long.MAX_VALUE. Instead, create multiple buckets(each a hashtable) partitioned by value. The number of buckets to create can be determined experimentally.

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

``````a = map(int,raw_input().split(" "))
res = [None,None]
large = float("inf")

for i in xrange(len(a)-1):
for j in xrange(i+1,len(a)):
dist = abs(a[i]+a[j])
if dist < large:
large = dist
res = a[i]
res = a[j]

print res``````

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

This works well for small datasets. For large datasets, it will degrade in O(n^2) running time.

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

@Jack: right. This is pretty much just the brute-force solution.

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

s = open("s.txt")
list = [int(x) for x in arr]
sum = 100000;
min = 100000
min_sum = 0
le = len(list)
index1 = -1
index2 = -1
for i in range(le):
for j in range(i + 1, le):
sum = list[i] + list[j]
min_sum = abs(sum - 0)
if(min_sum < min):
min = min_sum
index1 = i
index2 = j

print list[index1], " ",list[index2]

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

package client;

import java.util.ArrayList;
import java.util.List;

public class MinimumSumPair {
public MinimumSumPair() {
super();
}

public static void main(String[] args) {
MinimumSumPair minimumSumPair = new MinimumSumPair();
int[] a = {2,5,-7,8,4,6};
List l = minimumSum(a);
System.out.println(l.toString());
}
public static List minimumSum(int[] a){
int[] arr = a;
int sum = 0,minsum =Integer.MAX_VALUE;
int l=0,r=0;
for(int i = 0; i < a.length; i++){
for(int j = i+1; j < a.length; j++){
sum = a[i] + a[j];

if(minsum > sum && sum >= 0){
minsum = sum ;
l=a[i];
r=a[j];
}
}
}
List arrList = new ArrayList();
return arrList;
}
}

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

``````def findMinAbsSum( array ):
best = ( float( "inf" ), float( "inf" ) )

for i in range( 0, len( array ) ) :
for j  in range( i + 1, len( array ) ) :
if array[i] + array[j] == 0:
return ( array[i], array[j] )
if abs( array[i] + array[j] ) < abs( sum( best ) ) :
best = ( array[i], array[j] )

return best

if __name__ == "__main__" :
print( findMinAbsSum( [2,5,8,-7,2,9] ) )
print( findMinAbsSum( [2,5,8,-7,2,9,7] ) )
print( findMinAbsSum( [] ) )``````

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

``````Best-case: O(n)
public static void pair(final int[] array) {
int max1st = array;
int max2nd = array;
int min1st = array;
int min2nd = array;
boolean isAllNeg = true;
boolean isAllNatural = true;

for (int iter = 1; iter < array.length; iter++) {
final int currValue = array[iter];

if (currValue < 0) {
isAllNatural = false;
} else {
isAllNeg = false;
}

if (currValue < min1st) {
min2nd = min1st;
min1st = currValue;
} else if ((min2nd == min1st) && (currValue < min2nd)) {
min2nd = currValue;
}

if (currValue >= max1st) {
max2nd = max1st;
max1st = currValue;
} else if ((max2nd == max1st) && (currValue > max2nd)) {
max2nd = currValue;
}
}

if (isAllNatural) {
System.out.println(min1st + " " + min2nd);

return;
} else if (isAllNeg) {
System.out.println(max1st + " " + max2nd);

return;
} else {
// Java's randomized quicksort, avg nlogn
Arrays.sort(array);

int leftIter = 0;
int rightIter = array.length - 1;

boolean modified = true;

while ((leftIter < rightIter) && modified) {
modified = false;

if ((array[leftIter] + array[rightIter]) == 0) {
System.out.println(array[leftIter] + " " +
array[rightIter]);

break;
} else if (((array[leftIter] + array[rightIter]) > 0) &&
(Math.abs((array[leftIter] + array[rightIter - 1])) < Math.abs((array[leftIter] +
array[rightIter])))) {
rightIter--;
modified = true;
} else if (((array[leftIter] + array[rightIter]) < 0) &&
(Math.abs((array[leftIter + 1] + array[rightIter])) > Math.abs((array[leftIter] +
array[rightIter])))) {
leftIter++;
modified = true;
}
}

System.out.println(array[leftIter] + " " + array[rightIter]);
}
}``````

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

#include <stdio.h>
#include <conio.h>
#include <math.h>

void foo()
{
int arr[] = {2,5,8,-7,2,9};
int temp;

int len = sizeof(arr)/sizeof(int);
int min_sum = 10000;
int sum = 0;

for (int i = 0; i < len; i++)
{
for (int j = i + 1; j < len ; j++)
{
sum = arr[i] + arr[j];

if (abs(sum) < min_sum)
{
min_sum = abs(sum);
temp = arr[i];
temp = arr[j];
}
}
}

printf("%d, %d result = %d",temp, temp, min_sum);
}

void main()
{

foo();
getch();
}

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

We may like to add a condition that if the first element of a sorted array is not negative then the first two numbers of a sorted array will give the lowest possible sum and that will eventually be a answer to this... What's say?

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

I say crap.

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

Why do you think this is crap? This is not a solution but just a condition to check which will definitely optimize the logic in case an array in question doesn't have any negative nos in it?

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

sort the array by Absolute value desc, print the min sum of each adjacent pair. O(nlogn)
e.g.

{2 5 8 -7 2,9}
sort-> {2,2,5,-7,8,9}

min sum of adjacent pair: {-7, 8} = 1

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

In one traverse find positive minimum and negative maximum ,in second traverse find sum using both.ex {-17,0,1,2,5,7} pm=0,nm=-17 using these two find min absolute sum using 0 we get sum=1 using -17 we get 10 so (0,1) selected

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

If all the numbers are negative or all numbers are positive then the pair (min value, next to min value) will be the unique answer. Below is a sorting based approach to arrive the pairs whose sum is closest to zero. I used merge sort here. Actually any nlogn sort can be used.

``````package arrays;

/**
*
* Imagine arranging the numbers in the array on an integer number line.
* If all the numbers are towards the positive side or the negative side
* of the number line, the pair (min, next min) would be the unique answer.
*
* If we have numbers towards both +ve and -ve sides, then pair (x,y)
* would be a candidate for the answer where x any y are on opposite side
* of the number line with diff(abs(x) -abs(y)) close to zero.
*
* The approach is
* 1) sort the numbers based on the abs value of the data - O(nlogn)
* 2) in the sorted array by abs value pairs like (x,y) discussed above would be
* 3) prepare the sum of adjacent pairs in this array. The pair with min
*
*
* I ran this code for
* {2,-3,-5,4,-6,-1,8}
* {2,5,8,-7,2,9};
* {-2,-3,-5,-4,-6,-1,-8}
* {1,2,3,4,5,6}
*
*
*/
public class FindPairsClosestToZero {

// we want to sort the data by abs value and use the
//original data while forming pairs. So create this type
private static class Int_data {
private int data;
private int absData;

public Int_data(int t){
data = t;
absData = Math.abs(t);
}
}

public static Int_data [] sorted_data;
public static void main(String [] args) {
int a[] = {2,5,8,-7,2,9};
Int_data[] data = new Int_data[a.length];
for (int i=0;i<a.length;i++) {
Int_data temp = new Int_data(a[i]);
data[i] = temp;
}
sorted_data = new Int_data[data.length];
merge_sort(data, 0, data.length-1);

int[] closestPairSum = new int[a.length-1];

//form the closest pair sums
for(int i=0;i<closestPairSum.length;i++){
closestPairSum[i] = Math.abs(sorted_data[i].data+sorted_data[i+1].data);
}

for (int i = 0; i < closestPairSum.length; i++) {
System.out.println(closestPairSum[i]+ " formed by ["+ sorted_data[i].data+ ", "+ sorted_data[i+1].data+"]");
}
}

public static void merge_sort(Int_data[] a, int low, int high) {
if (high - low > 1) {
// more than two element

int mid = (int) Math.floor((high + low) / 2);

merge_sort(a, low, mid);
merge_sort(a, mid + 1, high);

// merge the data
int i = low;
int j = mid + 1;
int count = low;
while (i <= mid && j <= high) {
if (a[i].absData <= a[j].absData) {
sorted_data[count++] = a[i];
i++;
} else if (a[i].absData > a[j].absData) {
sorted_data[count++] = a[j];
j++;
}
}

if (j <= high) {
while (j <= high) {
sorted_data[count++] = a[j];
j++;
}
}
if (i <= mid) {
while (i <= mid) {
sorted_data[count++] = a[i];
i++;
}
}
} else {
// we have to deal with less than two elements
if (high == low + 1) {
if (a[low].absData > a[high].absData) {
Int_data tmp = a[low];
a[low] = a[high];
a[high] = tmp;
}
} else if (high == low) {
//System.out.println("One element no sorting needed");
sorted_data[low] = a[low];
}
}
}
}``````

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

If all the numbers are negative or all numbers are positive then the pair (min value, next to min value) will be the unique answer. Below is a sorting based approach to arrive the pairs whose sum is closest to zero. I used merge sort here. Actually any nlogn sort can be used.

``````package arrays;

/**
*
* Imagine arranging the numbers in the array on an integer number line.
* If all the numbers are towards the positive side or the negative side
* of the number line, the pair (min, next min) would be the unique answer.
*
* If we have numbers towards both +ve and -ve sides, then pair (x,y)
* would be a candidate for the answer where x any y are on opposite side
* of the number line with diff(abs(x) -abs(y)) close to zero.
*
* The approach is
* 1) sort the numbers based on the abs value of the data - O(nlogn)
* 2) in the sorted array by abs value pairs like (x,y) discussed above would be
* 3) prepare the sum of adjacent pairs in this array. The pair with min
*
*
* I ran this code for
* {2,-3,-5,4,-6,-1,8}
* {2,5,8,-7,2,9};
* {-2,-3,-5,-4,-6,-1,-8}
* {1,2,3,4,5,6}
*
*
*/
public class FindPairsClosestToZero {

// we want to sort the data by abs value and use the
//original data while forming pairs. So create this type
private static class Int_data {
private int data;
private int absData;

public Int_data(int t){
data = t;
absData = Math.abs(t);
}
}

public static Int_data [] sorted_data;
public static void main(String [] args) {
int a[] = {2,5,8,-7,2,9};
Int_data[] data = new Int_data[a.length];
for (int i=0;i<a.length;i++) {
Int_data temp = new Int_data(a[i]);
data[i] = temp;
}
sorted_data = new Int_data[data.length];
merge_sort(data, 0, data.length-1);

int[] closestPairSum = new int[a.length-1];

//form the closest pair sums
for(int i=0;i<closestPairSum.length;i++){
closestPairSum[i] = Math.abs(sorted_data[i].data+sorted_data[i+1].data);
}

for (int i = 0; i < closestPairSum.length; i++) {
System.out.println(closestPairSum[i]+ " formed by ["+ sorted_data[i].data+ ", "+ sorted_data[i+1].data+"]");
}
}

public static void merge_sort(Int_data[] a, int low, int high) {
if (high - low > 1) {
// more than two element

int mid = (int) Math.floor((high + low) / 2);

merge_sort(a, low, mid);
merge_sort(a, mid + 1, high);

// merge the data
int i = low;
int j = mid + 1;
int count = low;
while (i <= mid && j <= high) {
if (a[i].absData <= a[j].absData) {
sorted_data[count++] = a[i];
i++;
} else if (a[i].absData > a[j].absData) {
sorted_data[count++] = a[j];
j++;
}
}

if (j <= high) {
while (j <= high) {
sorted_data[count++] = a[j];
j++;
}
}
if (i <= mid) {
while (i <= mid) {
sorted_data[count++] = a[i];
i++;
}
}
} else {
// we have to deal with less than two elements
if (high == low + 1) {
if (a[low].absData > a[high].absData) {
Int_data tmp = a[low];
a[low] = a[high];
a[high] = tmp;
}
} else if (high == low) {
//System.out.println("One element no sorting needed");
sorted_data[low] = a[low];
}
}
}
}``````

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

Solution: Sort -- O(nlogn), Find Pair in Sorted Array -- O(n)

``````0. First sort the array
1. Maintain two references: low and high
2. Keep global minimum = gMin = absSum( low, high )
3. while ( low < high ) {
4. lMin = absSum( low, high )
while( low < high && absSum(low, high) < lMin ) high--;
high++;
if (absSum(low, high) < gMin ) gMin = absSum(low, high);
low++;
}``````

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

Sort the arrry ignoring the sign of the integer. lets say the input is {2 5 8 -7 2,9} and it will be sorted as {2,2,5,-7,8,9} and iterate the array as the minimum sum lies with next element. Let me know if there is any bug in the code.

public class FindPairWithSumClosestToZero {

public static void main(String[] args){
int a[] = {2, 5, 8, -7, 2, 9};
qSort(a, a.length);
int l=0,min = abs(a+a);
for(int i = 1; i < a.length - 1; i++ ){
if(abs(a[i]+a[i+1]) < min){
min = abs(a[i]+a[i+1]);
l = i;
}
}
System.out.println(a[l]+","+a[l+1]);
}

private static void qSort(int[] a, int n) {
recQuickSort(a, 0, n-1);
}

private static void recQuickSort(int[] arr, int left, int right) {
if(right - left <= 0)
return;
else{
int pivot = abs(arr[right]);
int partition = partitionIt(arr,left, right, pivot);
recQuickSort(arr, left, partition-1);
recQuickSort(arr, partition+1, right);
}

}

private static int abs(int i) {
return i<0?-i:i;
}

private static int partitionIt(int[] arr, int left, int right, int pivot) {
int leftPtr = left - 1;
int rightPtr = right;
int temp;
while(true){
while(abs(arr[++leftPtr])<pivot);
while(rightPtr > 0 && abs(arr[--rightPtr])>pivot);
if(leftPtr >= rightPtr)
break;
else{
temp = arr[leftPtr];
arr[leftPtr]= arr[rightPtr];
arr[rightPtr]= temp;
}
}
temp = arr[leftPtr];
arr[leftPtr]= arr[right];
arr[right] = temp;
return leftPtr;

}

}

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

public static int pair(int arr[]) {

int index = 0;
int current_sum = 0;
int previous_sum = Integer.MAX_VALUE;
for (int i = 0; i < arr.length-1; i++) {
current_sum = arr[i] + arr[i+1];
if (current_sum < previous_sum){
index = i;
previous_sum = current_sum;
}
}
return index;
}

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

public int pair(int arr[]) {

int index = 0;
int current_sum = 0;
int previous_sum = Integer.MAX_VALUE;
for (int i = 0; i < arr.length-1; i++) {
current_sum = arr[i] + arr[i+1];
current_sum = Math.abs(current_sum);
if (current_sum < previous_sum){
index = i;
previous_sum = current_sum;
}
}
return index;
}

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

Here is the code which worked fine in vs2005...i have printed the indices...

void pairsum_nearzero(int temp[],int n)
{
int least,sum,indexi,indexj;
least = 0;
indexi=0;
indexj =0;
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
sum = temp[i] + temp[j];
if(sum >=0)
{
if(sum <= least )
{
least = sum;
indexi = i;
indexj = j;

}
}
else if(sum <0)
{
if(-sum <= least )
{
least = sum;
indexi = i;
indexj = j;

}
}
}
}
cout<<"the pairs ur looking for are"<<indexi<<indexj<<endl;

}

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

here is O(n) solution. challenge accepted :)

``````/*
* File:   main.cpp
* Author: vsirohi
*
* Created on September 8, 2012, 9:21 PM
*/

#include <cstdlib>
#include<iostream>
using namespace std;
int mod(int a) // returns a positive integer
{
if(a<0)
a*=(-1);
return a;
}
int min(int a , int b) // returns the integer with  min magnitude of two
{                       // this do not consider sign (-ve or +ve
int aa= mod(a);
int bb= mod(b);
if(aa<bb)
{ return a; }
else
return b;
}
int  ZeroSumSubArry(int array[], int length)
{
int  minsum=4444, sumsofar = 4444;
int start =0, end=0;
for(int i=0; i<length; i++)   // O[(n)
{
if((mod(array[i]))<(min(sumsofar,sumsofar+array[i])))
{start = i;end = i;}
minsum = min(array[i],minsum+array[i]) ;
if(mod(sumsofar)>mod(minsum))
{
end = i;
}
sumsofar = min(sumsofar, minsum);
}
/// print the sub array. from range start to end.
cout<< " the min sum array is : "<<endl;
for(int k = start; k<=end; k++)
{
cout<<" "<<array[k]<<" ";
}
return sumsofar;
}

int main(int argc, char** argv) {
int arr = {5, -3, -2, 8, 15, -5, 3};
// some random test cases.
//int arr = {5, 3, -2,8,15,-5,3};
//int arr = {1, -1, -2, -1, 2, -1,2};
//int arr = {-1, -2, -3, -1, -2, -2, -1};
// int arr = {0,-1,-2,5, 6,3,1};
int sum=0;
sum = ZeroSumSubArry(arr, 7);
cout << " the sum is  : "<<sum<<endl;
return 0;
}``````

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

-100, -50, -1, 1, 50, 100.

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.