Amazon Interview Question
SDE1sTeam: Marketplace Team
Country: United States
Interview Type: Phone Interview
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.
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));
}
}
}
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
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.
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);
}
}
}
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
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.
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
Above solution is not efficient. It will take O(n2) time. list.contains() operation will take O(n) for each iteration.
//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;
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);
}
}
}
}
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>
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>
1. Sort the Array A
- Ajay Singh September 20, 20142. 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