## Amazon Interview Question for Software Engineer / Developers

Country: United States
Interview Type: Phone Interview

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

The 2 sum problem is a classic variation of the subset sum problem. It is defined as the following:
You have an unsorted array, and you are given a value S. Find all pairs of elements in the array that add up to value S.
2 solutions - one minimizes space complexity, and the other time. As stated in the "hint", one approach is to hash the entire array, and then for each element check if S-array[j] is in the hash table. This takes O(n) time and O(n) space to store the array.
Alternatively, if one wishes to minimize space complexity, simply sort the array. Then, have two pointers - one initialized to array[0] and the other array[length-1]. Then check the sums; if the sum is > S, decrement the right pointer. If it is < S, increment the left pointer.

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

Could you please tell me how space complexity will be o(n)? What would be the hash function in this case? If we take number as index in array then array size would be more than n, probably we need to find some good hash function but this will complicate the problem. Thoughts?

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

Could you please tell me how space complexity will be o(n)? What would be the hash function in this case? If we take number as index in array then array size would be more than n, probably we need to find some good hash function but this will complicate the problem. Thoughts?

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

Actually, space complexity is not O(n), that's O(M), M is the range of the given numbers.

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

Hashing n items is O(n) space. For the first guy, buddy, even if you hash items into an array of size 100n that's still O(n). For the second guy, oohtj, the range of numbers is not relevant.

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

simple solution :

``````sort the array, take two index keep one at start node, another at end node, call then i and j
count = 0;
if A[i] + A[j] > sum
j--;
else if A[i] + A[j] < sum
i++;
else
output i and j and set increment count;
do the same untill j > i
if count == 0 output node present;``````

complexity : O(nlogn)

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

this is wrong. wont work for a case like {1,1,1,1,1} i.e. all elemnts are same

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

It is ok for this method if the requirement is that return true or false, namely if exist question. Once we detect the sum we return true.

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

jnklj

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

``````public static void two_sum_problem(int arr[], int sum) {

// store all the elements of arr in a hashmap
HashMap hm = new HashMap();
for (int i = 0; i < arr.length; i++) {
hm.put(arr[i], arr[i]);
}

// go through the array, and check if the difference sum-arr[i] is in the hashmap
// if sum-arr[i] is in the hashmap, you have found two numbers that add upto sum.
for (int i = 0; i < arr.length; i++) {
int lookFor = sum - arr[i];
boolean hasValue = hm.containsValue(lookFor);
if (hasValue) {
System.out.println("Found: "+ arr[i] + "+" + lookFor + "=" + sum);
}
}
}``````

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

Will this work if I give a set{2,3} and target 4?

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

What if the array is {2,3,5} and my sum = 6. The array has number 3 in it - at that point, it will do hashmap.containsKey(sum – array[ i ]) = 3 and it will say it is present in the hashmap and the pair will be 3,3 that sums up to 6. But we don't want that as we have just one 3 in the array and not two of them.

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

There might be various small changes to it...

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

No problem. The question is to find if there is a pair in the array whose sum is equal to a given value. No need to find them.
My answer is using hash table, as Chander Ramesh said. However, one point to take care is that if the given number is 4 and there is a 2 in the array, S - array[j] exists in the hash table. To avoid that, the frequency for each number can be recorded in the hash table. For that case, see if the frequency for 2 is 2, then it's ok, otherwise it's not the right case.

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

Hi can you please elaborate on the solution

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

I am confused whether you need to find all subset whose sum is equal to S or just pairs of element..if pairs then the solution is pretty straightforward....

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

Just check if there are pairs meeting the requirement.

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

``````int[] in = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int i ,j,n;
n = 10;

for (i = 0, j = in.length - 1; j > i; i++, j--) {
if (in[i] + in[j] > n)
j--;
else if (in[i] + in[j] < n)
i++;
else
System.out.println("Pair(i+j=n) = ("+(i+","+j)+"="+n+")");
}``````

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

The code above has a bug. It works fine if the for loop is replaced with

``while (i<j)``

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

Be sure to take care the permutation of same numbers in a row.

e.g.

(90 , 99) : 9 + 9 = 18
(90 , 98) : 9 + 9 = 18
(90 , 97) : 9 + 9 = 18
(90 , 96) : 9 + 9 = 18
(91 , 100) : 9 + 9 = 18
(91 , 99) : 9 + 9 = 18
(91 , 98) : 9 + 9 = 18
(91 , 97) : 9 + 9 = 18
(91 , 96) : 9 + 9 = 18
(92 , 100) : 9 + 9 = 18
(92 , 99) : 9 + 9 = 18
(92 , 98) : 9 + 9 = 18
(92 , 97) : 9 + 9 = 18
(92 , 96) : 9 + 9 = 18

``````vector<int> sumarray;

const int size = 1000;
const int maxNum = 100;

for (int i = 0; i < size; i++) {
sumarray.push_back(ARC4RANDOM(maxNum));
}

sort(sumarray.begin(), sumarray.end());

const int sum = 2 * ARC4RANDOM(maxNum);

int count = 0;

{
unsigned int i = 0;
unsigned int j = (unsigned int)sumarray.size() - 1;

while (j > i) {
if (sumarray[i] + sumarray[j] > sum) {
j--;
} else if (sumarray[i] + sumarray[j] < sum) {
i++;
} else {

const unsigned int indexI = i;
const unsigned int indexJ = j;
while (j > i) {
if (sumarray[i] != sumarray[indexI] && sumarray[j] != sumarray[indexJ]) {break;}
if (sumarray[i] == sumarray[indexI]) {i++;}
if (sumarray[j] == sumarray[indexJ]) {j--;}
}

for (int c = indexI; c < i; c++) {
for (int b = indexJ; b > j; b--) {
cout << DebugLog << "(" << c << " , " << b << ") : " << sumarray[c] << " + " << sumarray[b] << " = " << sum << endl;
count++;
}
}
}
}

cout << DebugLog << "Sum Count:" << count << endl;
}``````

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

``````public static int[] arrayPairSumIndices(int[] a, int k)
{
HashMap<Integer, Integer> hashMap = new HashMap<Integer, Integer>();
for (int i = 0; i < a.length; i++)
{
if (hashMap.containsKey(k - a[i]))
{
return new int[]{hashMap.get(k - a[i]), i};
}
hashMap.put(a[i], i);
}
return null;
}``````

I'm pretty sure this is the best. O(n) time complexity and O(n) space. This returns the indices at which the two values are at.

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

``````public String find2Sum(int[] array, int sum) {
Set<Integer> set = new HashSet<Integer>();
for (int i = 0; i < array.length; i++) {
}
for (int j = 0; j < array.length; j++) {
if (set.contains(sum - array[j])) {
return "first " + array[j] + " second " + (sum - array[j]);
}
}
return null;
}``````

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

Here's an O(n^2) and O(n) algorithms. Run them on your computer and see the difference

``````import java.util.ArrayList;
import java.util.Hashtable;
import java.util.Iterator;

public class TwoSumTest {

public static void main(String[] args) {
int max = 200_000;
int sum = 20000;
int[] a = new int[max];
for (int i = 0; i < max; i++) {
a[i] = (int) (max * Math.random());
}

TwoSumTest ts = new TwoSumTest();

System.out.println("\nHash version\n");
long now = System.currentTimeMillis();
StringBuffer sbh = ts.twoSumHash(a, sum);
System.out.println(System.currentTimeMillis() - now);

now = System.currentTimeMillis();

StringBuffer sb2 = ts.twoSumN2(a, sum);
System.out.println(System.currentTimeMillis() - now);

System.out.println("sbh: " + sbh.length() + " sb2: " + sb2.length());
if (sbh.toString().equals(sb2.toString())) {
System.out.println("Same output");
}
}

public StringBuffer twoSumN2(int[] a, int sum) {
StringBuffer sb = new StringBuffer();
for (int i = 0; i < a.length - 1; i++) {
for (int j = i + 1; j < a.length; j++) {
if (a[i] + a[j] == sum)
sb.append("(" + i + ":" + a[i] + "," + j + ":" + a[j] + ")");
}
}

return sb;
}

public StringBuffer twoSumHash(int[] a, int sum) {

Hashtable<Integer, ArrayList<Integer>> ht = new Hashtable<>();
StringBuffer sb = new StringBuffer();

for (int i = 0; i < a.length; i++) {
ArrayList<Integer> row = ht.get(a[i]);
if (row == null) {
row = new ArrayList<>();
ht.put(a[i], row);
}
}

for (int i = 0; i < a.length; i++) {
ArrayList<Integer> row = ht.get(sum - a[i]);
if (row != null) {
Iterator<Integer> it = row.iterator();
while (it.hasNext()) {
int j = it.next();
if (i < j) {
sb.append("(" + i + ":" + a[i] + "," + j + ":" + a[j] + ")");
}
}
}
}

return sb;
}
}``````

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

1234

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.