Amazon Interview Question Software Engineer / Developers
Team: Kindle Device
Country: India
Interview Type: Phone Interview
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.
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
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.
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)?
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.
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.
@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.
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.
@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.
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?
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.
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[0] = a[i]
res[1] = a[j]
print res
This works well for small datasets. For large datasets, it will degrade in O(n^2) running time.
s = open("s.txt")
arr = s.read().split(' ')
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]
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();
arrList.add(l);
arrList.add(r);
return arrList;
}
}
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( [] ) )
Best-case: O(n)
public static void pair(final int[] array) {
int max1st = array[0];
int max2nd = array[0];
int min1st = array[0];
int min2nd = array[0];
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]);
}
}
#include <stdio.h>
#include <conio.h>
#include <math.h>
void foo()
{
int arr[] = {2,5,8,-7,2,9};
int temp[2];
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[0] = arr[i];
temp[1] = arr[j];
}
}
}
printf("%d, %d result = %d",temp[0], temp[1], min_sum);
}
void main()
{
foo();
getch();
}
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?
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
* adjacent to each other
* 3) prepare the sum of adjacent pairs in this array. The pair with min
* sum is the answer
*
*
* 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];
}
}
}
}
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
* adjacent to each other
* 3) prepare the sum of adjacent pairs in this array. The pair with min
* sum is the answer
*
*
* 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];
}
}
}
}
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++;
}
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[1]+a[0]);
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;
}
}
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;
}
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;
}
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;
}
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[7] = {5, -3, -2, 8, 15, -5, 3};
// some random test cases.
//int arr[7] = {5, 3, -2,8,15,-5,3};
//int arr[7] = {1, -1, -2, -1, 2, -1,2};
//int arr[7] = {-1, -2, -3, -1, -2, -2, -1};
// int arr[7] = {0,-1,-2,5, 6,3,1};
int sum=0;
sum = ZeroSumSubArry(arr, 7);
cout << " the sum is : "<<sum<<endl;
return 0;
}
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--
- Cerberuz September 07, 2012void 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 ); }