Amazon Interview Question
Quality Assurance EngineersTeam: AWS
Country: United States
Interview Type: Phone Interview
I think by "pairs" he means just 2 nos. summing to the value of N.
Store the values in a HashMap. Iterate over each value "x" in the array and find N-x in the HashMap. If found, you got a pair, store it in a HashSet (this will eliminate duplicates).
Time: O(n)
Not quite sure about this case: {0, 1, 2, 3, 4, 5}, N=4
Your solution will still print (0, 4), (1, 3), (2, 2) even though (2, 2) is not a correct answer. Or am I missing something?
Just an intern is right , vikx you are wrong here.
Hero is first storing all values in HashMap , instead he should store the value only when N-x is not found in the HashMap.Only then , (2,2) will not be printed.
Solution in Python
def FindPairs(array,N):
map={value:index for index,value in enumerate(array)}
pairs={(elem,N-elem) for elem in map if N-elem in map and elem>=N-elem}
Same solution in C++. Algorithm is same as hero's, linear time average complexity. Using unordered_map for true hash map and hast set at the same time.
std::unordered_map<double,double> FindPairs(std::vector<double>& input, double N){
std::unordered_map<double,double> i2v;
std::unordered_map<double,double> pairs;
std::for_each(input.begin(),input.end(),[&](double val){ i2v[val]=N-val;});
for (auto elem : i2v)
if (i2v.find(elem.second)!=i2v.end())
if (elem.first>=elem.second)
pairs.insert(elem);
return pairs;
}
Time Complexity - O(n)
2 pointer approach. one starts at the end of the array and other at the end.
1) if sum ( a[first pointer] , a[second pointer]) > N move second pointer left
2) if sum ( a[first pointer] , a[second pointer]) < N move first pointer right
keep moving untill 2 pointers meet each other.
How long do you think that it's appropriate to think about this question ? And how long to write it?
for(int j=0;j<=num-1;j++)
{
int val=i[j];
int temp=num2-val;
for(j=0;j<=num-1;j++)
{
if(temp==i[j])
System.out.println("["+val+","+temp+"]");
}
1. if you sort the array , then the running time is at least 0(nlogn).
2. Is all the number positive ?
if it was, we could count the appearance of 0,1,...N in O(n) running time, and let p(i) be the frequency of i , since 0+N==N,1+(N-1)==N,...then we have min(a(i),a(N-i)) pairs of (i,N-i);
if there're negative numbers, in O(n) running time(the first scannning) we can get each of them,and you can store its frequency too, the remaining similar. While you may scan the array twice, you still got the 0(n) running time.
#include <stdio.h>
#define MX 7 //max no of array
//target is value sum value
//let assume given array sequence[MX] ={0, 1, 2, 2, 3, 4, 5};//assuming array is not sorted
int main()
{
int array[MX];
for(count = 0; count<MX;count++)
{
array[MX] = 0;
}
for(count = 0; count<MX;count++)
{
array[sequence[count]] = 1;
}
for(count = 0; count<MX;count++)
{
index = target - sequence[count];
if(index > 0)
{
if(array[index] == 1)
{
print(pair(sequence[count],index));
array[index] = 0;
array[sequence[count]] = 0;
}
}
}
return 0;
}
complexity : 0(n)
public class PrintPairsThatSumUpToValueInArray {
public static void main(String[] args) {
PrintPairsThatSumUpToValueInArray pps = new PrintPairsThatSumUpToValueInArray();
int[] array = { 8, 0, 1, 2, 2, 3, 3, 3, 4, 5, 1, 4, 6, 4, 4, 4, 5 };
int TARGET_SUM = 10;
Map<Integer, Integer> map = pps.loadMap(array);
pps.printPairsFromMap(TARGET_SUM, map);
}
public Map loadMap(int[] array) {
Map<Integer, Integer> map = new HashMap<>();
for (int val : array) {
if (map.containsKey(val)) {
int count = (Integer) map.get(val);
map.put(val, ++count);
} else {
map.put(val, 1);
}
}
return map;
}
public void printPairsFromMap(int targetSum, Map<Integer, Integer> map) {
Iterator<Integer> itr = map.keySet().iterator();
while (itr.hasNext()) {
int key = itr.next();
int value = map.get(key);
if (key > targetSum)
continue;
int diff = targetSum - key;
if (!map.containsKey(diff))
continue;
else if (key < diff) {
System.out.println("(" + key + "," + diff + ")");
} else if (key == diff && value > 1) {
System.out.println("(" + key + "," + diff + ")");
}
}
}
}
public static void main(String[] args) {
final Map<Integer, Integer> values = new HashMap<Integer, Integer>();
final Map<Integer, Integer> sumOfPair = new HashMap<Integer, Integer>();
final int targetVal = 4;
int key = 0;
final int[] arrayOfNums = { 0, 1, 2, 2, 3, 4, 5 };
for (int i : arrayOfNums) {
values.put(key, i);
if ((values.containsValue(targetVal - i)) && ((targetVal - i) != i)) {
sumOfPair.put(i, (targetVal - i));
}
key++;
}
Iterator<Map.Entry<Integer, Integer>> entries = sumOfPair.entrySet().iterator();
while (entries.hasNext()) {
Map.Entry<Integer, Integer> entry = entries.next();
System.out.print("(" + entry.getKey() + "," + entry.getValue()+") ");
}
}
void printPair(int arr[],int size,int sum)
{
map<int,int> traversed;
map<int,int>::iterator it;
int i , remain;
for (i = 0 ; i < size ; i++)
{
remain = sum - arr[i];
it = traversed.find(remain);
if (it != traversed.end() && it->second > 0)
{
cout << "\n(" << it->first << "," << arr[i] << ")" ;
traversed.erase(it);
}
if(it != traversed.end())traversed[arr[i]]=1;
else (it->second)++
}
}
Assuming the array is sorted the following algorithm also works -
N - being the given sum.
1] Find x = sum(first , last)
2] if x = N print elts[first] and elts[last] and continue till u reach half the array.
if x < N then first++
if x > N then last--
public static void main(String[] args) {
int[] elts = {0, 1, 2, 2, 3, 4, 5};
int N = 4;
for (int i = 0,j=elts.length-1; i < (elts.length/2) && i!=j ;) {
if (elts[i]+elts[j] > N)
j--;
else if (elts[i]+elts[j] < N)
i++;
else {
System.out.println("(" + elts[i] + " , " + elts[j] + ")");
j--;
}
}
public static void main (String args[]){
int[] num = {0, 1, 2, 2, 3, 4, 5};
int input = 4;
find(num,input);
}
public static void find(int[] num, int input){
for(int i=0;i<num.length;i++){
for(int j=0;j<num.length-1;j++){
if(num[j]+num[i]==input){
System.out.println(num[i]+ " " +num[j] + " "+ input);
}
}
}
}
Sorting the array will give better time complexity than O(n^2). We can assume thant sorting is O(nlogn) + Iteration of the elements which are less than N (arr[i] + arr[j] < N) - I can not say how much time it takes, but I believe that it is better than O(n^2)
public class SumOfNums {
public static void main(String[] args) {
int[] arr = { 0, 1, 2, 2, 3, 4, 5 };
int N = 4; // (x+y==4 ?)
// sort the array
Arrays.sort(arr);
int i = 0;
while (i < arr.length-1) {
int j = i+1;
while (j < arr.length - 1 && arr[i] + arr[j] < N) {
j++;
}
if (arr[i] + arr[j] == N)
System.out.print("(" + arr[i] + "," + arr[j] + "), ");
i++;
}
}
}
Time Complexity = N^2
void findPair(int arr[], int size, int target, map<int, int> &data)
{
for(int i=0; i<size; i++)
{
int find = target - arr[i];
for(int j=i; j<size; j++)
{
if (find == arr[j])
{
pair<int, int> p(arr[i], arr[j]);
data.insert(p);
break;
}
}
if ( arr[i] + arr[i+1] >= target)
break;
}
}
here is the best simple solution:
public void findpairs(int ary[], int sum){
map<int,int>find=new hashmap<int,int>();
int i;
for(i=0;i<ary.length();i++){
find.put(ary[i],sum-ary[i]);
}
for(i=0;i<ary.length();i++){
if(find.containsValue(ary[i]){
system.out.println("here are the pairs",+ary[i],sum-ary[i]);
}
else{
system.out.println("sorry no pairs");
}
}
}
Time complexity: Worst case: (n)
Space complexity: If we want distinct pairs then Worst case: (n) else its O(1).
External methods used:
1.) void sort(int array[]); //QUICK SORT avg case running time is nlog(n)
2.) int search(int array[], int key, int lowerBound, int upperBound); //BINARY SEARCH. returns the index of the found element.
Additional datastructures:
1.) implementation of Set interface. //This is to check duplicates.
public void printPairs( int array[], int sum){
MySet set = new MySet();
int remainder;
int found = false;
int lowerBound = 0;
sort(array);
for( int i = array.length -1; i >= 0; i--){
if(k > array[i]){
remainder = k - array[i];
int index = search(array, remainder, lowerBound, i);
if(index > -1){
found = true;
if(!set.contains(Math.abs(array[i] - array[index]))){
System.out.print( "("+array[i] + ",(" + array[index] + ") ");
set.add(Math.abs(array[i] - array[index]));
lowerBound = index;
}
}
}
}
if(!found){
System.out.println("Sorry no pairs found.");
}
}
The set stores the absolute difference between the pairs. the difference and the sum (i.e. k) uniquely identifies the pair (idea is that, Xi + Yi = m, Xi - Yi = n, Xj + Yj = m and Xj - Yj = n, then i = j).
The lowerBound( prevents the binary search to check for previously checked lower numbers of the array.
int find(int a[],int start,int end,int num){
while(start<end){
if(a[start]+a[end]==num){
printf("(%d,%d) ",a[start],a[end]);
start++;
}
else if(a[start]+a[end]>num){
end--;
}
else{
start++;
}
}
}
import java.util.ArrayList;
import java.util.List;
public class Test {
public static void main(String[] args) {
int[] values = {0,1,1,2,3,4,5,6};
int target = 6;
outer: for(int i= 0; i<values.length; i++){
int sum = values[i];
List<Integer> sequence = new ArrayList<Integer>();
sequence.add(sum);
inner: for(int j = (values.length -1); j>i;j--){
sum = sum+values[j];
if(sum > target){
sum = sum-values[j];
continue inner;
} else if(sum <= target){
sequence.add(values[j]);
if(sum == target){
System.out.println(sequence);
sum = values[i];
sequence.clear();
sequence.add(values[i]);
}
}
}
}
}
}
Time Complexity = O(logN), if its sorted Array
package careerCupJava;
public class SumWith2Numbers {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int arry[] = {0,1,2,2,3,4,5};
int i=0, j=arry.length - 1;
System.out.println("j="+j);
int sum=4;
while(i <= j)
{
int k = sum-arry[i];
if(k == arry[j])
{
System.out.println("pair pair="+arry[i]+arry[j]);
i++;
j--;
}
if( k < arry[j])
{
j--;
}
}
}
}
# include <stdio.h>
# include <conio.h>
void all_sum_pair(int a[10],int start, int end, int suma)
{
int tempa=0;
if(start < end)
{
tempa = a[start]+a[end];
if(tempa == suma)
{
printf("(%d, %d), ",a[start],a[end]);
all_sum_pair(a, start+1, end, suma);
}else{
all_sum_pair(a, start, end-1, suma);
}
}
}
void main ()
{
int arr[10];
int i,nn,j,temp,sum;
nn=10;
sum=5;
printf("Enter 10 Numbers in a column\n");
for(i =0; i <10;i++)
{
scanf("%d",&arr[i]);
}
for(i=1;i<nn;i++)
{
for(j=i;j>0 && arr[j]<arr[j-1];j--)
{
temp=arr[j];
arr[j]=arr[j-1];
arr[j-1]=temp;
}
}
for (i=0; i<10;i++)
printf("%d\n",arr[i]);
all_sum_pair(arr,0,nn-1,sum);
printf("completed");
getch ();
clrscr();
}
public class PairNumber {
public int[] array =new int[]{0,1,2,3,4,5);
public void displayPairNumber(int value){
array ={0,1,2,3,4,5);
for (int i=0;i++;i<=value){
n=value;
if (i+n=value){
System.out.println(array(i)+,+array(n));
}
if (n==i){
break; } } }
Algo goes like this. Assuming array is sorted
1. point 1 reference to start of the array say i, 2nd reference to the end of the array say j
2. if a[i] + a[j] == N print pairs, else if a[i] + a[j] > N j-- else if a[i] + a[j] < N i++ till i < j
Thinking of better approach for un-sorted array
By assuming array elements are sorted in ascending order, below is the algorithm(which will take care of duplicate elements as well).
- SRB December 24, 2012