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.

- Chander Ramesh January 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- buddy January 19, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- buddy January 19, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- oohtj January 20, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- rook January 29, 2016 | Flag
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)

- sonesh January 20, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- anand January 06, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- yhyyhyyyl March 24, 2014 | Flag
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);
			}			
		}
	}

- Shay January 20, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- mulin October 25, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- tushar2702 September 17, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Can you please add the actual question?
There might be various small changes to it...

- Anonymous January 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- laprovence27 January 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Hi can you please elaborate on the solution

- Anuj Agrawal January 19, 2013 | Flag Reply
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....

- Anuj Agrawal January 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Just check if there are pairs meeting the requirement.

- laprovence27 January 22, 2013 | Flag
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+")");
		}

- bvreddyb January 22, 2013 | Flag Reply
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)

- Janoubi March 06, 2013 | Flag
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;
    }

- doc.dominic January 22, 2014 | Flag Reply
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.

- Johnb July 26, 2014 | Flag Reply
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++) {
            set.add(array[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;
    }

- find2Sum May 25, 2016 | Flag Reply
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();
		System.out.println("\nQuadratic version\n");

		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);
			}
			row.add(i);
		}

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

- zeke June 21, 2016 | Flag Reply


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