Amazon Interview Question for Interns


Country: United States




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

target:
132

First, sort the array.
3 21 32 67 89 100 128 130

Index the start and the end of the array and calculate the sum
If too small, increment the start index; if too large, decrement the end index.
>3 21 32 67 89 100 128 130< (130+3 = 133)
>3 21 32 67 89 100 128<130 (128+3 = 131)
3 >21 32 67 89 100 128<130 (128+21 = 149)
3 >21 32 67 89 100< 128130 (100+21 = 121)
3 21 >32 67 89 100< 128130 (100+32 = 132)

So we've found two values that add up to 132.

Complexity of sort O(N*logN) and complexity of finding step O(N) so total is O(N*logN).

- Anonymous March 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

The reason it works is because for example when we decrement the end pointer, we do this because it's too large to work with the current beginning pointer and hence too large to work with any of the subsequent beginning values since they're only going to get larger.

- Anonymous March 27, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you kindly explain why it would not work for 4 numbers adding to target?

- EK MACHCHAR May 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
7
of 9 vote

Idea:

Take each element of the array, put it in a hash map: O(n)
Loop the array once more: check if (target - element) is in the hash map: O(n) for the loop, O(1) for the subtraction and existence check in the map.

Total: O(n)

Thoughts? FWIW, a Python set would do nicely for this, rather than a hash map.

- jay March 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

I think You can use hashset instead of hashmap

- Anonymous March 27, 2013 | Flag
Comment hidden because of low score. Click to expand.
3
of 3 votes

This approach is good, but 2 comments.

1) You are better of checking before inserting into hashmap, so you can break early if needed. Only one pass needed. Also, you won't have the problem of dealing with the case when you add the same element to get the target (eg. array is [2] and you are looking for 4).

2) This is worst case quadratic (bad input for hash function).

- Loler March 27, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Loler:

1) Clever, I like that shortcut.

2) Can you expand? My impression is we can assuming a good uniform non-colliding hash when using hashmaps/sets, otherwise a lot of algorithms stop becoming linear.

- jay March 27, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@jay: It is only _expected_ linear. Theoretically it is worst case (emphasis on worst case) quadratic.

Note that, I am not at all saying that we should reject the hash based solution for that reason. In fact, this is a very practical solution!

Just mentioning a possible reason why people are not upvoting :-)

- Loler March 27, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Loler:

Thanks, that makes a lot of sense.

- jay March 27, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

What if the array contains duplicate values and their sum is target vaue
i.e. 1 2 3 3 4 and the target value is 6.

I guess this Hashmap wont work in that case.!!

- Rahul April 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

From the first comment by Loler:

"Also, you won't have the problem of dealing with the case when you add the same element to get the target (eg. array is [2] and you are looking for 4)."

- jay April 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

So to handle duplicate value case we need to have 2 iteration over hashmap, and while inserting if we get duplicate value then compare twice of it with sum.

- Rahul April 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Rahul nice idea. I actually solved the problem this way in java, it assumes no duplicate values in the array.

public static boolean addsUp(int [] array, int sum){ 
		
		if(array==null)
			return false; 
		
		Set<Integer> targetSet = new HashSet<Integer>();
		Set<Integer> arraySet= new HashSet<Integer>(); 
		
		for(int i=0; i<array.length; i++){ 
			targetSet.add(sum - array[i]); 
			arraySet.add(array[i]); 
		}
		
		arraySet.retainAll(targetSet); 
			
		return arraySet.size()>1; 
		
		
	}

- nimatohid April 09, 2013 | Flag
Comment hidden because of low score. Click to expand.
4
of 4 vote

--- sort the array - O(n*logn)
--- loop through the array and for every element call binary search on that same array to find target - array[i] (of course ignore the element on the same index) - O(n*logn)

So in the end you have O(n*logn) + O(n*logn) = O(2*(n*logn)) = O(n*logn)

- srdjan March 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 votes

Is my O(n) solution wrong? If not - why does and O(nlogn) solution get more votes than an O(n) one? I just really want to know if I missed something here :-)

- jay March 27, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Jay, your answer isn't wrong but it's space complexity is O(N) whereas this and the other sorting solution would use O(1) space. Both are good answers and either could be the best depending on other factors.

- dasbachc April 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can we take that all the integers are +ve

- Lokesh August 03, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

public static boolean addsSum(int[] a, int target) {
		HashSet set = new HashSet();
		for(int i=0; i<a.length; i++) {
			int b = target - a[i];
			set.add(new Integer(a[i]));
			if (!set.contains(new Integer(b))) {
				set.add(new Integer(b));
			} else {
				return true;
			}
		}
		
		
		return false;
	}

- lin March 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

When was your interview

- girish March 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool 2sum(a, target):
       i  = 0
       j = len(a) - 1
       while i < j :
            if a[i] + a[j] == target :
                return True
            else if a[i] + a[j] > target :
                j -= 1
            else :
                i += 1
       return False

- Anonymous July 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool 2sum(a, target):
       i  = 0
       j = len(a) - 1
       while i < j :
            if a[i] + a[j] == target :
                return True
            else if a[i] + a[j] > target :
                j -= 1
            else :
                i += 1
       return False

- Anonymous July 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Used the idea presented by @Jay. Expected O(n) time, O(n^2) worst case, and O(n) memory.

#include <iostream>
#include <vector>
#include <unordered_set>
#include <time.h>
#include <cstdlib>

bool addsUp(std::vector<int> input, int target){
    std::unordered_set<int> temp_set;
    for (int i = 0; i < input.size(); i++){
        if (temp_set.find(target - input[i]) != temp_set.end()){
            std::cout << "\n" << target - input[i] << " " << input[i];
            return true;
        }
        temp_set.insert(input[i]);
    }
    return false;
}

int main(){
    srand(time(NULL));

    std::vector<int> my_vector;
    for (int i = 0; i < 10; i++){
        my_vector.push_back(rand() % 10);
        std::cout << my_vector.back() << " ";
    }
    
    std::cout << "\nadds up to 13: " <<  addsUp(my_vector, 13) << "\n";
}

- mihaibogdan10 October 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I consider the numbers are previously added in the hash.

bool addsUp(vector <int> &input, int target) {
	for (int i = 0; i < input.size(); i++) {
		int index = abs(target - input[i]) % KEY;
		for (int j = 0; j < hash[index].size(); j++) {
			if (target - input[i] == hash[index][j])
				return true;
		}
	}
	return false;
}

- Alexandru Mihai October 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

You could have added the numbers in the hash as you were doing this, so that you would be able to stop early (e.g. with a target of 10, you can stop after the first two elements if the input is 1 9 4 4 ...)

- mihaibogdan10 October 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class AddsUp {

	public boolean checkSorted(int[] array, int target){
		int l = 0; 
		int r = array.length - 1;
		while(l<r){
			int sum = array[l] + array[r];
			if(sum == target){
				return true;
			}else if(sum < target){
				++l;
			}else{
				--r;
			}
		}
		
		return false;
	}
	
	public boolean checkNotSorted(int[] array, int target){
		Set<Integer> values = new HashSet<>();
		for(int val: array){
			if(values.contains(target - val)){
				return true;
			}
			values.add(val);
		}
		
		
		return false;
	}
	
}

- Anonymous December 09, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.Arrays;

public class ArraySumPair {

	public static void main(String[] args) {
		
		int [] a={1,2,3,4,1,5,6,0,9,8,1,2};
		int [] arr={6,5,7,3,6,7,3,4,2,5,6,8,7,9,4,5,6,3};
		Arrays.sort(arr);
		getPair2(arr,14);
		
	}
	  /**
	 * Find the pair in an array whose sum with complexity O(n). This assumes
	 * the array passed is sorted array and there are no duplicates in the array
	 * 
	 * @param arr
	 *            input array of elements
	 * @param k
	 *            sum for which pair of array elements needs to be searched
	 */
	public static void getPair2(int[] arr, int k) {
	    int start = 0;
	    int end = arr.length - 1;
	    int sum = 0;
	 
	    // output array to record matching pairs
	    StringBuilder arrs = new StringBuilder();
	 
	    while (start < end) {
	        sum = arr[start] + arr[end];
	        if (sum == k) {
	            // we have found one pair, add it to our output array
	            arrs.append(arr[start] + "," + arr[end] + ";");
	            start++;
	            end--;
	        } else if (sum < k) {
	           
	            start++;
	        } else {
	            end--;
	        }
	    }
	    System.out.println(arrs.toString());
	}
	
	
}

- Bharat Savani March 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 3 vote

Bool AddsUp(Array<int> input, int target)
{
	for(int i = 0; i < input.size(); i++)
	{
		int nAnotherOne = target - input[i];
		for(int j= i+1; j<input.size(); j++)
		{
			if(nAnotherOne == input[j])
				return true;
		}
	}
	return false;
}

- outdoor March 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is worst-case O(n^2), it can easily be more efficient than that (see both answers already posted).

- jay March 27, 2013 | 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