Amazon Interview Question for SDE1s


Team: Marketplace Team
Country: United States
Interview Type: Phone Interview




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

1. Sort the Array A
2. Have 2 pointers, left(starting at 0) and right(starting at last element of array)
3. Start the loop - while left < right
a. if A[left] + A[right] == sum then return A[left] and A[right]
b. if A[left] + A[right] < sum then left++
c. if A[left] + A[right] > sum then right--
4. Else return 0

- Ajay Singh September 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You are assuming that Array A is sorted, which is not given.

- anonymous September 20, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

To me this is not obvious. It might or might not work. I think the logic is faulty. There may be a few solutions. E.g. {1, 2, 3, 4, 5} 6 = 1+6 = 2+4. Your algorithm finds just one. So, some combinations might be overlooked.

- Rutishauser September 29, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Not handling negative integers.

- Anonymous July 10, 2015 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

public static void main(String[] args) {
		int number = 10;
		int[] array = new int[]{2,3,5,7,8,10};
		
		HashMap<Integer,Integer> tempHash = new HashMap<Integer, Integer>();
		
		for(int i =0 ;i<array.length;i++)
		{
			tempHash.put(array[i], 0);
		}
		for (int i : array)
		{
			tempHash.remove(i);
			if (tempHash.containsKey(number-i))
			{
				System.out.println("" + i + "," + (number-i));
			}
		}
	}

- gaurav September 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

1. HashMap and use the numbers as keys
2. Now scan the HashMap and check existence of (Sum - Key) keys in HashMap
3. Return all pairs that satisfy 2

Thats O(n) time and O(n) space

- Mahmud September 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

No need to use a hashMap if you are not mapping anything. Just use a hashSet.

- graham September 20, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

You can actually do this online in a single pass using hashset

lookup Sum-current value
if hit you found a pair
add current value to the set and continue.

- Anonymous September 21, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

public static void findMatches(int[] arr,int sum) {
HashSet<Integer> pairs = new HashSet<>();
int pair=0;
for(int i=0;i<arr.length;i++) {
if(pairs.contains(arr[i]) ) {
pair = sum-arr[i];
System.out.println("Pair: " + arr[i] + " - "+ pair);
pairs.remove(arr[i]);
}
else {
pair = sum-arr[i];
pairs.add(pair);
}
}

}

- Pringles September 21, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

A brute force method would probably be something like
1. 2 loops, both iterating through the array, say "i" and "j"
1.2. If both iterator indexes are equal, just continue
1.3. If i+j = the certain number we are looking for then we return the two values

- Anonymous September 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A = SORT(A)
n = length[A]
for i =0 to n do
if A[i] > 0 and BINARY-SEARCH(A;A[i] - x; 1; n) then
return A[i] and x-A[i]
end if
end for
return false

- Anurag Panwar September 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This algorithm will take O(nlgn) time in total

- Anurag Panwar September 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

seems, you are not considering time complexity for sorting.

- Anonymous September 20, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Anonymous: Huh?

- Anonymous September 20, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

N -- number of elements in array
S -- SUM
for (int i = 0;i < N;i++)
for (int j = i+1;j < N;j++)
if (array[i] + array[j] = SUM)
{
found = true;

}

- Kamal September 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Kamal

Definitely your algorithm return true when any pair found but you have to pay attention to few things

1. Efficiency of the algorithm : your solution is O(n*n) running time with O(1) space. Can you make it better with more space? Yes look at my first comment.
2. Also you need to look at the requirements. So you need to return the indexes of element probably not just only true.

- Mahmud September 20, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

int[] input = {10,20,60,58,45,10,200,2001,485,95,85,545,458,487,545,120,121,2020,1,2,10,20};
    int sum = 210;
    
    List<int> list = new List<int>(input.Length);
    for(int i=0;i<input.Length;i++){
        list.Add(input[i]);
    }
    Console.WriteLine("Finding pairs");
    
    for(int i=0;i<input.Length;i++){
      if(list.Contains(sum-input[i]))     {
            Console.WriteLine("Pair :"+input[i] + "+"+(sum-input[i]))      ;
      }
    }         


Executing the program....
$mono demo.exe 
Finding pairs
Pair :10+200
Pair :10+200
Pair :200+10
Pair :10+200

- poweruser September 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Above solution is not efficient. It will take O(n2) time. list.contains() operation will take O(n) for each iteration.

- gdb September 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes. Instead of List<T>, HashSet<T> can be used to make search o(1).

- poweruser2003 September 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

//This will work in O(logn)
#include<stdio.h>
int search(int *arr_temp,int diff)
{
int i;
for(i=0;*(arr_temp+i);i++)
if (*(arr_temp+i) == diff)
return diff;
return 0;
}

int main()
{
int arr[]={5,7,1,50,17,2,9,11};
int x,i,diff,num2=0;
printf("enter number to be searched");
scanf("%d",&x);
for(i=0;i<sizeof(arr)/4;i++)
{
diff=x-arr[i];
if (arr[i+1] && (num2=search(arr+i+1,diff) ))
{
break;
}
}
if (num2 > 0)

printf("\nnumber found,(%d:%d)",num2,arr[i]);
else
printf("\nnot found");

return 0;

- tauqir0007 September 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void sumFindingOfTwoNo(Integer[] array, Integer sum) {
        HashSet<Integer> sets = new HashSet<Integer>(Arrays.asList(array));
        for(Integer no : sets) {
            if(sets.contains(sum-no)) {
                System.out.println(no+","+(sum-no));
            }
        }

    }

- rewati October 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.HashMap;
import java.util.Map;


public class TwoIntgerThatSumToAGivenNumber {
	
	public static void main(String[] args) {
		int[] array = new int[]{2,3,5,7,8,10};
		printPairs(array, 10);
		
	}
	static void printPairs(int[] arr , int sum) {
		
		Map<Integer, Integer> map = new HashMap<Integer, Integer>();
		
		for(int i : arr)
			map.put(i, 0);
		
		for(int i=0;i<arr.length;i++) {
			
			if(map.containsKey(sum-arr[i])) {
				
				System.out.println(arr[i]+"+"+(sum-arr[i])+"="+sum);
			}
		}
	}

}

- shukad333 October 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

How HastSet will handle duplicate numbers say set is {1 2 2 10} and sum is 4
HashSet will store only {1 2 10} and it will fail to find any pair with sum 4 or if you say this not fail them it will give false Positive result for sum = 20.

Seems we need yo use Hashtable< number as Key, count as value>

- Pradeep January 25, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

How HastSet will handle duplicate numbers say set is {1 2 2 10} and sum is 4
HashSet will store only {1 2 10} and it will fail to find any pair with sum 4 or if you say this not fail them it will give false Positive result for sum = 20.

Seems we need yo use Hashtable< number as Key, count as value>

- tiwaripradeep123 January 25, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void sum(int[] ar, int num) {
int sum = 0;
for (int i = 0; i < ar.length; i++) {
for (int j = i + 1; j < ar.length; j++) {
if (ar[i] + ar[j] == num) {
System.out.println(ar[i] + " " + ar[j] + " = "
+ (ar[i] + ar[j]));
}
}
}
}

- sona February 07, 2015 | 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