Amazon Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
An interesting case is if array contains duplicate numbers. Above code will report only one such pair.
e.g. Let the sorted array be 2,5,5,5,6,8,9 and we are searching for elements adding up to 10. This will report only one such pair.
Following Algorithm will help get rid of that issue:
1. Sort
2. For each a[i], Get j = BinarySearch for (x-a[i]) in array between indices i+1 & n-1
3. Print i,j
public class KTestSearch {
private int[] knumber={1,2,3,4,5,6,7,8,9};
public KTestSearch(int knumber[]) {
this.knumber=knumber;
}
public void startLogic(int target)
{
for(int i=0;i<knumber.length;i++)
{
int val=knumber[i];
if(2*val>=target)
break;
int currentFlag=i;
int lastFlag=knumber.length;
findPair(val,target,currentFlag,lastFlag);
}
}
private void findPair(int val,int target,int currentFlag,int lastFlag)
{
int mid= (currentFlag+lastFlag)/2;
if(val+knumber[mid]>target)
{
findPair(val,target,currentFlag,mid);
}
else if(val+knumber[mid]<target&&(lastFlag-mid)>1)
{
findPair(val,target,mid,lastFlag);
}
else
if(target==(val+knumber[mid]))
System.out.println("The pair of numbers is :: "+val+" + "+knumber[mid]+" == "+target);
}
public static void main(String[] args) {
int[] knumber={1,2,3,4,5,6,7,8,9};
KTestSearch ki=new KTestSearch(knumber);
ki.startLogic(11);
}
}
complexity :: Sort(nlogn) + Searching (nlog n) = 2nlogn
Output: The list of all possibles
The pair of numbers is :: 2 + 9 == 11
The pair of numbers is :: 3 + 8 == 11
The pair of numbers is :: 4 + 7 == 11
The pair of numbers is :: 5 + 6 == 11
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.List;
public class AdderPair {
public static void main(String[] args) {
int[] inputArr = {1, 2, 3, 45, 50, 55, 56, 76, 98, 99};
List<Map<String, Integer>> output = addPairs(inputArr, 100);
for(Map<String, Integer> eachMap : output) {
System.out.println(eachMap.get("val1") + " and "+ eachMap.get("val2"));
}
}
private static List<Map<String, Integer>> addPairs(int[] inputArr, int addition) {
int i = 0;
int j = inputArr.length-1;
List<Map<String, Integer>> output = new ArrayList<Map<String, Integer>>();
for(; i<j; ) {
Map<String, Integer> outputMap = new HashMap<String, Integer>();
int sum = inputArr[i]+inputArr[j];
if(sum== addition) {
outputMap.put("val1", inputArr[i]);
outputMap.put("val2", inputArr[j]);
i++;
j--;
} else if(sum < addition) {
i++;
continue;
} else {
j--;
continue;
}
output.add(outputMap);
}
return output;
}
}
No additional space
complexity < O(n2)
Assumption: The actual array can be changed
void FindPairs(int []A, int length, int s)
{
if(length <= 1) {Console.write("No Pairs. Length is {0}, length}
QuckSort(A);
for (int i =0; i < length; ++i)
{
int v = s - A[i];
if(BinarySearch(A,v)) Console.Write(v);
}
}
#! /usr/bin/perl
use strict;
my $num=$ARGV[0];
my @arr=qw|15 18 6 5 9 1 4 13 16 2|;
print "@arr\n";
for(my $i=2;$i<=scalar(@arr);$i++){
#print $arr[$i],"\n";
my $less=$arr[$i-1];
#print "\tLESS::$less\n";
for(my $j=$i-2;$j>=0;$j--){
#print "\t\t$arr[$j] \+ $less\n";
print "$arr[$j] \+ $less = $num\n" if (($arr[$j]+$less) == $num );
}
}
public static int binarySearch(int[] a, int value, int l, int h) {
if (l <= h) {
int mid = (l + h) >> 1;
if (a[mid] == value) {
return mid;
} else if (a[mid] > value) {
return binarySearch(a, value, l, mid - 1);
} else {
return binarySearch(a, value, mid + 1, h);
}
} else {
return -1;
}
}
public static void findTwoSumAll(int[] a, int sum) {
if (a == null) {
return;
}
if (a.length < 2) {
return;
}
for (int i = 0; i < a.length; i++) {
int otherVal = sum - a[i];
int otherIdxRight = binarySearch(a, otherVal, i + 1, a.length - 1);
if (otherIdxRight != -1) {
System.out.println(a[i] + " - " + a[otherIdxRight] + " at indices: " + i + " - " + otherIdxRight);
}
}
}
1) Sort the array in ascending order in O(n log n).
2) Scan array using two indices one from start and other from end of array
3) Complexity is O(nlogn) + O(n)
}
- Say March 06, 2012