## 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).

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.

Comment hidden because of low score. Click to expand.
0

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

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.

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

I think You can use hashset instead of hashmap

Comment hidden because of low score. Click to expand.
3

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).

Comment hidden because of low score. Click to expand.
0

@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.

Comment hidden because of low score. Click to expand.
0

@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 :-)

Comment hidden because of low score. Click to expand.
0

@Loler:

Thanks, that makes a lot of sense.

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.!!

Comment hidden because of low score. Click to expand.
0

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)."

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

@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++){
}

arraySet.retainAll(targetSet);

return arraySet.size()>1;

}``````

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)

Comment hidden because of low score. Click to expand.
2

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 :-)

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

Can we take that all the integers are +ve

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];
if (!set.contains(new Integer(b))) {
} else {
return true;
}
}

return false;
}``````

Comment hidden because of low score. Click to expand.
0
of 2 vote

When was your interview

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``````

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``````

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";
}``````

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;
}``````

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 ...)

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;
}
}

return false;
}

}``````

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());
}

}``````

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;
}``````

Comment hidden because of low score. Click to expand.
0

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

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.

### 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.