Amazon Interview Question for SDE1s


Team: Amazon Fresh
Country: United States
Interview Type: Phone Interview




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

I would propose the following:
Let's say that array int[] a can fit into the memory

(i)  	use all numbers as a key and put it in a set
(ii) 	for each j in length a[]
                compute x = sum - a[j]
                if x is in the set
                        print pair a[j], x
                        remove x from the set

The the set construction is O(N), query to the set, if implemented via hash, is O(1) amortized and finally last loop is O(N)

A sample code is shown below:

public static void printPairs(int a[], int sum) {
	HashSet<Integer> st = new HashSet<Integer>();
	
	for (int x : a)
		st.add(x);
	
	for(int y : a) {
		st.remove(y);
		if (st.contains(sum-y)) {
			System.out.println(y + ", " + (sum-y));
			st.remove(sum-y);
		}
	}
}

Notice that since the number is removed from the set, all possible pairs are printed only once. Notice also that this code works only for distinct integer values in the array.

- autoboli March 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Doesn't work if the two numbers are the same ex: 5 + 5 = 10. You need to remove yourself from the set first before you test for sum - x.

- babesh March 13, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

for(int y : a){
	if(st.contains(sum-y)){
		System.out.println(y+", "+(sum-y));
		st.remove(sum-y);
		st.remove(y);
	}
}

Removing (sum-y) and (y), ensures that we are printing only distinct sets.

- Dhaya March 13, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@ ninhnnsoc, babesh, Dhaya: Thank you guys for useful comments! As you suggested I've modified a line of code such that we first remove 'y' and then check for 'sum-y'. As @babesh pointed out, the code handles only distinct keys.

- autoboli March 13, 2015 | Flag
Comment hidden because of low score. Click to expand.
4
of 4 vote

public static void subsets(int a[],int sum){
HashMap<Integer, Integer>hm=new HashMap<Integer,Integer>();
for(Integer i:a)
if(hm.get(sum-i)==null)
hm.put(i,0);
else hm.put(i, sum-i);

System.out.println(hm);
}

- gowtham kesa March 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 vote

Assuming you only need to find one pair, you only have to make one pass:

import java.util.*;

public class Sum {
    public static void main(String args[]) {
        int numbers[] = { 2, 5, 3, 7, 9, 8};
        int sum = 11;

        HashSet<Integer> opposingPair = new HashSet<Integer>();
        for (int i = 0; i < numbers.length; i++) {
            int n = numbers[i];
            int diff = sum - n;
            if (opposingPair.contains(new Integer(diff))) {
                System.out.print(n);
                System.out.print(",");
                System.out.print(diff);
                return;
            } else {
                opposingPair.add(new Integer(n));
            }
        }
    }
}

- babesh March 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 3 vote

awesome explanation @ coders-stop.blogspot.in/2011/01/sum-equals-k-for-sum-of-two-elements.html

- f00l March 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

nicely explained, all the approaches, would help to bluff the interviewer :P

- coder March 12, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n) time, O(n) memory..

#include <stdio.h>
#include <math.h>
#include <unordered_set>
#include <vector>

using namespace std;

vector< pair<int,int> > pair_sum(vector<int> arr, int n){
    unordered_set<int> table;
    vector< pair<int,int> > list_pair;

    for(int i=0; i<arr.size(); i++){
        table.insert(n-arr[i]);
    }

    for(int i=0; i<arr.size(); i++){
        if (arr[i]>ceil(n/2))
            continue;
        if (table.find(arr[i]) != table.end()){
            list_pair.push_back(make_pair(arr[i], n-arr[i]));
        }
    }
    return list_pair;
}

int main(int argc, char* argv[]){
    vector<int> arr = {2, 5, 3, 7, 9, 8};
    vector< pair<int,int> > list_pair;

    list_pair = pair_sum(arr, 11);
    for (int i=0; i<list_pair.size(); i++){
        printf("(%d, %d)\n", list_pair[i].first, list_pair[i].second);
    }
}

- Anonymous March 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

-Create a hash set by going over the input array once.
-loop from i = 0 to sum/2
-if the hash set contains i as well as sum-i, output that pair

- Anonymous March 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Java code:

public class FindAllPairWithSum {
public static void main(String[] args) {
int[] numbers = {2,5,3,7,9,8};
final int sum = 11;
Map<Integer,Integer> numberMap = new HashMap<Integer,Integer>();
for(int i = 0; i < numbers.length; i++) {
numberMap.put(numbers[i], sum-numbers[i]);
}
for(int i = 0; i < numbers.length; i++) {
if(numberMap.containsKey(numberMap.get(numbers[i]))) {
System.out.println("("+numbers[i]+","+numberMap.get(numbers[i])+")");
numberMap.remove(numberMap.get(numbers[i]));
}
}
}
}

- newspecies March 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Assuming the array is not sorted...

public static void main(String[] args){
        
        int[] input = {2,3,5,7,9,8,6};
        int sum = 11;

        HashMap<Integer,Integer> resultMap = new HashMap<Integer, Integer>();
        //Get the values in a HashMap - Count
        for(int i=0;i<input.length;i++){
            int key = (sum - input[i]) > input[i] ? input[i] : (sum -input[i]);
            Integer val = resultMap.get(key) == null ?  0 : resultMap.get(key);
            resultMap.put(key,++val);
        }
        //Remove Unwanted Pairs
        Iterator it = resultMap.entrySet().iterator();
        while(it.hasNext()){
            Map.Entry<Integer,Integer> pair = (Map.Entry) it.next();
            if(pair.getValue()!= 2){
                it.remove();
            }else{
                pair.setValue(sum - pair.getKey());
            }
        }
        //Print them all
        for(Map.Entry<Integer,Integer> entry : resultMap.entrySet()){
            System.out.println("Pairs Are: ("+ entry.getKey()+","+entry.getValue()+")");
        }
    }

- ss444 March 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Simple solution is to store your values in a lookup table where each key is an int in the array, and the value for that key is the sum minus the int (its required match). You then do simple lookups for each element.

In python, this would look like:

def find_array_sum_matches(int_array, sum_val):
    results = []
    val_dict = {x: (sum_val - x) for x in int_array)
    for a,b in val_dict.iteritems():
        if val_dict.get(b):
            results.append((a,b))
            val_dict[a] = None
            val_dict[b] = None
    return results

this runs in O(n), the transform of elements from array to lookup table takes n (where n is elements i nthe array) and the lookup table scan takes O(n), at most it takes n time if each element in the array is unique

Because a number subtracted from another number always has one value, we only need to find one sum involving any two numbers to be able to safely remove them (or null them) from the lookup table.

- Javeed March 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void find_pairs(int *a, int len, int sum) {
    int sum_hash[sum];
    int i = 0;
    int next_pair = 0;

    memset(sum_hash, 0, sizeof(sum_hash));

    for (i = 0; i < len; i++) {
        next_pair = 11 - a[i];
        if (sum_hash[next_pair]) {
            printf("%d %d\n", a[i], next_pair);
        } else {
            sum_hash[a[i]] = 1;
        }   
    }    
}

- Mohowk March 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void find_pairs(int *a, int len, int sum) {
    int sum_hash[sum];
    int i = 0;
    int next_pair = 0;

    memset(sum_hash, 0, sizeof(sum_hash));

    for (i = 0; i < len; i++) {
        next_pair = sum - a[i];
        if (sum_hash[next_pair]) {
            printf("%d %d\n", a[i], next_pair);
        } else {
            sum_hash[a[i]] = 1;
        }   
    }    
}

- jay.desai22 March 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

function sumPair(input, sum) {
    var res = {};
    for (var i = 0, len = input.length; i < len; i += 1) {
        if (input.indexOf(sum - input[i]) !== -1 &&
            !res.hasOwnProperty(input[i]) &&
            !res.hasOwnProperty(sum - input[i])) {
            res[input[i]] = sum - input[i];    
        }    
    }
    return res;
}

- Si Pham March 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Javascript implementation:

function sumPair(input, sum) {
    var res = {};
    for (var i = 0, len = input.length; i < len; i += 1) {
        if (input.indexOf(sum - input[i]) !== -1 &&
            !res.hasOwnProperty(input[i]) &&
            !res.hasOwnProperty(sum - input[i])) {
            res[input[i]] = sum - input[i];    
        }    
    }
    return res;
}

- Si Pham March 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

It is not clear from the description of the task that all integers in the array are positive, so there is possible case when we have for example array {-1, 10, 1, 9, 2, 3, 8, 12, 100, 12} and the answer is {[1, 10], [-1, 12], [9, 2], [3, 8]}. If we solve more generally this task we can't use the simple array approach, we have to use hashtable data structure. Here is my solution which takes into account possibility of negative integers in the array.

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

/**
 * Created by Igor_Sokolov on 3/12/2015.
 */
public class CarrerCup_5727163577794560 {
    public static void main(String[] args) {
        int[][] tests = {{2, 5, 3, 7, 9}, {-1, 10, 1, 9, 2, 3, 8, 12, 100, 12}, {}, {-1}};
        int sum = 11;

        for (int i = 0; i < tests.length; i++) {
            System.out.println("test #" + (i + 1));
            final List<int[]> pairs = findPairs(tests[i], sum);
            for (int[] pair: pairs) {
                System.out.printf("[%d, %d]%n", pair[0], pair[1]);
            }
        }
    }

    private static List<int[]> findPairs(int[] a, int sum) {
        final List<int[]> result = new ArrayList<>();

        final HashSet<Integer> set = new HashSet<>(a.length);
        for (int i = 0; i < a.length; i++) {
            set.add(a[i]);
        }

        final HashSet<Integer> used = new HashSet<>(a.length);
        for (int i = 0; i < a.length; i++) {
            final int first = a[i];
            if (used.contains(first)) {
                continue;
            }

            final int second = sum - first;
            if (set.contains(second)) {
                result.add(new int[] {first, second});

                used.add(first);
                used.add(second);
            }
        }

        return result;
    }
}

- igor.s.sokolov March 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Following code has O(n) complexity, as there is only one loop and it prints only the distinct set.

	public static void find_sum_pair(int[] arr, int sum) {
		HashMap<Integer,Integer> map = new HashMap<>();
		for (int i=0; i<arr.length; i++) {
			if (map.containsKey(sum - arr[i])) {
				System.out.println("("+ (sum - arr[i]) + ","+arr[i] + ")");
			}
			map.put(arr[i], 0);
		}
	}

- getPDat March 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This brings complexity of O(n).

- getPDat March 13, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.HashSet;
import java.util.Set;

public class TestSum {

public static void main(String[] args) {
// TODO Auto-generated method stub
int [] nums = {-1,-2,-3,2,5,3,7,9,8,13,16,6,15,44,4};
int sum = 12;
Set<Integer> dataset = new HashSet<Integer>();

for(int i=0; i<nums.length;i++){
// System.out.println("Index = "+i);
dataset.add(nums[i]);
if((nums[i] !=sum-nums[i] ) && dataset.contains(sum-nums[i]) ){
System.out.println("PAIR: "+nums[i] + " AND "+ (sum-nums[i]));
}
}

}

}

- Ravi P March 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.HashSet;
import java.util.Set;

public class TestSum {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int [] nums = {-1,-2,-3,2,5,3,7,9,8,13,16,6,15,44,4};
		int sum = 12; 
		Set<Integer> dataset = new HashSet<Integer>();
		
		for(int i=0; i<nums.length;i++){
		//	System.out.println("Index = "+i);
			dataset.add(nums[i]);
			if((nums[i] !=sum-nums[i] ) && dataset.contains(sum-nums[i]) ){
				System.out.println("PAIR: "+nums[i] + " AND "+ (sum-nums[i]));
			}
		}

	}

}

- Ravi P March 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.HashSet;
import java.util.Set;

public class TestSum {
public static void main(String[] args) {
		// TODO Auto-generated method stub
		int [] series = {-1,-2,-3,2,5,3,7,9,8,13,16,6,15,44,4};
		int sum = 12; 
		checkSum(series, sum);
	}

	public static void checkSum(int[] series, int sum){
		
		Set<Integer> dataset = new HashSet<Integer>();		
		for(int i=0; i<series.length;i++){			
			System.out.println("Index = "+i);			
			dataset.add(series[i]);			
			if((series[i] !=sum-series[i] ) && dataset.contains(sum-series[i]) ){
				System.out.println("PAIR: "+series[i] + " AND "+ (sum-series[i]));
			}
		}
	}

}

- Ravi P March 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1.Initialize an array temp[] of the size of the target sum.

2.Iterate over the array

3.If arr[i] = k then
i.if temp[k] == 0
ii. mark temp[k] = 1 and temp[target sum - k] = -1
iii. if temp[k] == -1 then pair found print k and target sum - k

- roykanti.blr March 20, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def find_sum_match(array, sum):
    results = []
    finalresults=[]
    for x in array:
        array=array[1:]
        if (sum-x) in array:
            sublist=list()
            sublist.append(x)
            sublist.append(sum-x)
            results.append(sublist)
    for i in results:
        if i not in finalresults:
            finalresults.append(i)
    return finalresults
print find_sum_match([2,5,5,3,7,9,8],10)

- Ankit March 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n) time
O(n) memory

public static String findPairs( int sum, int[] nums ){
        
        boolean[] numPresent = new boolean[sum+1];
        
        for( int num : nums ){
            if( num <= sum ){
                numPresent[num] = true;
            }
        }
        
        StringBuffer s = new StringBuffer();
        for( int i = 0; i < sum/2; i++ ){
            if( numPresent[i] && numPresent[sum-i] ){
                s.append("(" + i + ", " + (sum-i) + ")" );
                s.append("\n");
            }
        }
        
        return s.toString();
        
        
    }

- lindenjk April 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		ArrayList<Integer> arr = new 	ArrayList<Integer>();
		arr.add(2);arr.add(3);arr.add(4);arr.add(7);arr.add(8);arr.add(9);
		System.out.println(arr.toString());
		
		  Iterator itr = arr.iterator();
		  int sum=11;
		  Integer a;
		  
		  for(int i=0;i<arr.size();i++)
		  {
		  	sum = sum - arr.get(i).intValue();
		  	a = sum;
		  	if(arr.contains(sum))
		  	{
		  		System.out.println(" "+sum+" "+arr.get(i).intValue());
		  		
		  	}
		  	sum=11;
		  }
		  
	}
}

- Akash Surana April 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.Arrays;

public class sumEqual {

public static void main(String[] args) {

Integer[] arr = new Integer[]{2,5,4,7,9,8};
int sum = 11;

Arrays.sort(arr);

for(int i = 0, j = arr.length-1; i != j ;)
{
int cal = arr[i] + arr[j];
if( cal == sum)
{
System.out.println(arr[i] + " " + arr[j]);
i++;
j--;
}
else if( cal > sum )
j--;
else if( cal < sum )
i++;
}
}
}

- yathish.manjunath6 April 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/// C++ implementation.
/// this problem can be solved by first indexing all elements
/// into an unordered_map. and for every element, try to find
/// its pair such that they add up to sum, i.e. sum = a[i]+a[k]
///
/// Time  Complexity O(n).
/// Space Complexity O(n).
///
#include<cstdio>
#include<unordered_map>

using namespace std;

void print_all_sumpair(int *a, int size, int sum) {
     /// enter every element into the unordered_map. this is get rid
     /// of duplicates as well.
     std::unordered_map<int,int> m;
     for(int i=0;i<size;++i)
        m[a[i]]=1;

     for(int i=0;i<size;++i) {
        std::unordered_map<int,int>::iterator it = m.find(sum-a[i]);
        if (it != m.end()) {
           /// remove the current element in the unordered_map so that we do
           /// not end up printing duplicates.
           m.erase(a[i]);
           m.erase(sum-a[i]);

           /// lastly. print the pair.
           printf("%d %d\n", a[i], sum-a[i]);
        }
     }
     return;
}

int main() {
    int a[] = {2,5,3,2,9,7,8,9};
    print_all_sumpair(a, sizeof(a)/sizeof(a[0]), 11);
    return 0;
}

- trent.tong May 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

'''Find a pair of elements from an array whose sum equals a given number'''
import time
import numpy as np

input=np.arange(20000)
np.random.shuffle(input)

sm=35598

#Solution with complexity O(n)
t=time.time()
dc={}
for i in range(len(input)-1): #O(n)
    dc[input[i]]=i

for i in range(len(input)-1): #O(1)
    if dc.has_key(sm-input[i]):
        print '#1 :elements are',input[i],sm-input[i],'with time :',time.time()-t
        break
    
#Solution with complexity O(nlogn)
t=time.time()
input.sort()
s=0
e=len(input)-1
while s<e:
    if input[s]+input[e]>sm:
        e=e-1
    elif input[s]+input[e]<sm:
        s=s+1
    else:
        print '#2 :elements are',input[s],input[e],'with time :',time.time()-t
        break

- Tanay Chowdhury May 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Sort the array first...then add the elements of lower index and higher index of array.
Do this until lower index is lesser than higher index

- Learner March 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

"Sort the array first" means O(N log N) time complexity.

- autoboli March 12, 2015 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

1- Sort the array in the ascending order.
2- Take the sum of the lower index and higher index value.
3- if (a[lower]+a[higher])>sum
{
higher--;
}
else{
lower++;
}

4- If the a[lower]+a[higher] = sum;
print the values of lower and higher.

- AMIT KUMAR March 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorting makes it

O(n log n)

. We shouldn't sort.

- ss444 March 13, 2015 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More