Amazon Interview Question
SDE1sTeam: Amazon Fresh
Country: United States
Interview Type: Phone Interview
Doesn't work if the two numbers are the same ex: 5 + 5 = 10. You need to remove yourself from the set first before you test for sum - x.
for(int y : a){
if(st.contains(sum-y)){
System.out.println(y+", "+(sum-y));
st.remove(sum-y);
st.remove(y);
}
}
Removing (sum-y) and (y), ensures that we are printing only distinct sets.
Assuming you only need to find one pair, you only have to make one pass:
import java.util.*;
public class Sum {
public static void main(String args[]) {
int numbers[] = { 2, 5, 3, 7, 9, 8};
int sum = 11;
HashSet<Integer> opposingPair = new HashSet<Integer>();
for (int i = 0; i < numbers.length; i++) {
int n = numbers[i];
int diff = sum - n;
if (opposingPair.contains(new Integer(diff))) {
System.out.print(n);
System.out.print(",");
System.out.print(diff);
return;
} else {
opposingPair.add(new Integer(n));
}
}
}
}
awesome explanation @ coders-stop.blogspot.in/2011/01/sum-equals-k-for-sum-of-two-elements.html
O(n) time, O(n) memory..
#include <stdio.h>
#include <math.h>
#include <unordered_set>
#include <vector>
using namespace std;
vector< pair<int,int> > pair_sum(vector<int> arr, int n){
unordered_set<int> table;
vector< pair<int,int> > list_pair;
for(int i=0; i<arr.size(); i++){
table.insert(n-arr[i]);
}
for(int i=0; i<arr.size(); i++){
if (arr[i]>ceil(n/2))
continue;
if (table.find(arr[i]) != table.end()){
list_pair.push_back(make_pair(arr[i], n-arr[i]));
}
}
return list_pair;
}
int main(int argc, char* argv[]){
vector<int> arr = {2, 5, 3, 7, 9, 8};
vector< pair<int,int> > list_pair;
list_pair = pair_sum(arr, 11);
for (int i=0; i<list_pair.size(); i++){
printf("(%d, %d)\n", list_pair[i].first, list_pair[i].second);
}
}
Java code:
public class FindAllPairWithSum {
public static void main(String[] args) {
int[] numbers = {2,5,3,7,9,8};
final int sum = 11;
Map<Integer,Integer> numberMap = new HashMap<Integer,Integer>();
for(int i = 0; i < numbers.length; i++) {
numberMap.put(numbers[i], sum-numbers[i]);
}
for(int i = 0; i < numbers.length; i++) {
if(numberMap.containsKey(numberMap.get(numbers[i]))) {
System.out.println("("+numbers[i]+","+numberMap.get(numbers[i])+")");
numberMap.remove(numberMap.get(numbers[i]));
}
}
}
}
Assuming the array is not sorted...
public static void main(String[] args){
int[] input = {2,3,5,7,9,8,6};
int sum = 11;
HashMap<Integer,Integer> resultMap = new HashMap<Integer, Integer>();
//Get the values in a HashMap - Count
for(int i=0;i<input.length;i++){
int key = (sum - input[i]) > input[i] ? input[i] : (sum -input[i]);
Integer val = resultMap.get(key) == null ? 0 : resultMap.get(key);
resultMap.put(key,++val);
}
//Remove Unwanted Pairs
Iterator it = resultMap.entrySet().iterator();
while(it.hasNext()){
Map.Entry<Integer,Integer> pair = (Map.Entry) it.next();
if(pair.getValue()!= 2){
it.remove();
}else{
pair.setValue(sum - pair.getKey());
}
}
//Print them all
for(Map.Entry<Integer,Integer> entry : resultMap.entrySet()){
System.out.println("Pairs Are: ("+ entry.getKey()+","+entry.getValue()+")");
}
}
Simple solution is to store your values in a lookup table where each key is an int in the array, and the value for that key is the sum minus the int (its required match). You then do simple lookups for each element.
In python, this would look like:
def find_array_sum_matches(int_array, sum_val):
results = []
val_dict = {x: (sum_val - x) for x in int_array)
for a,b in val_dict.iteritems():
if val_dict.get(b):
results.append((a,b))
val_dict[a] = None
val_dict[b] = None
return results
this runs in O(n), the transform of elements from array to lookup table takes n (where n is elements i nthe array) and the lookup table scan takes O(n), at most it takes n time if each element in the array is unique
Because a number subtracted from another number always has one value, we only need to find one sum involving any two numbers to be able to safely remove them (or null them) from the lookup table.
Javascript implementation:
function sumPair(input, sum) {
var res = {};
for (var i = 0, len = input.length; i < len; i += 1) {
if (input.indexOf(sum - input[i]) !== -1 &&
!res.hasOwnProperty(input[i]) &&
!res.hasOwnProperty(sum - input[i])) {
res[input[i]] = sum - input[i];
}
}
return res;
}
It is not clear from the description of the task that all integers in the array are positive, so there is possible case when we have for example array {-1, 10, 1, 9, 2, 3, 8, 12, 100, 12} and the answer is {[1, 10], [-1, 12], [9, 2], [3, 8]}. If we solve more generally this task we can't use the simple array approach, we have to use hashtable data structure. Here is my solution which takes into account possibility of negative integers in the array.
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
/**
* Created by Igor_Sokolov on 3/12/2015.
*/
public class CarrerCup_5727163577794560 {
public static void main(String[] args) {
int[][] tests = {{2, 5, 3, 7, 9}, {-1, 10, 1, 9, 2, 3, 8, 12, 100, 12}, {}, {-1}};
int sum = 11;
for (int i = 0; i < tests.length; i++) {
System.out.println("test #" + (i + 1));
final List<int[]> pairs = findPairs(tests[i], sum);
for (int[] pair: pairs) {
System.out.printf("[%d, %d]%n", pair[0], pair[1]);
}
}
}
private static List<int[]> findPairs(int[] a, int sum) {
final List<int[]> result = new ArrayList<>();
final HashSet<Integer> set = new HashSet<>(a.length);
for (int i = 0; i < a.length; i++) {
set.add(a[i]);
}
final HashSet<Integer> used = new HashSet<>(a.length);
for (int i = 0; i < a.length; i++) {
final int first = a[i];
if (used.contains(first)) {
continue;
}
final int second = sum - first;
if (set.contains(second)) {
result.add(new int[] {first, second});
used.add(first);
used.add(second);
}
}
return result;
}
}
Following code has O(n) complexity, as there is only one loop and it prints only the distinct set.
public static void find_sum_pair(int[] arr, int sum) {
HashMap<Integer,Integer> map = new HashMap<>();
for (int i=0; i<arr.length; i++) {
if (map.containsKey(sum - arr[i])) {
System.out.println("("+ (sum - arr[i]) + ","+arr[i] + ")");
}
map.put(arr[i], 0);
}
}
import java.util.HashSet;
import java.util.Set;
public class TestSum {
public static void main(String[] args) {
// TODO Auto-generated method stub
int [] nums = {-1,-2,-3,2,5,3,7,9,8,13,16,6,15,44,4};
int sum = 12;
Set<Integer> dataset = new HashSet<Integer>();
for(int i=0; i<nums.length;i++){
// System.out.println("Index = "+i);
dataset.add(nums[i]);
if((nums[i] !=sum-nums[i] ) && dataset.contains(sum-nums[i]) ){
System.out.println("PAIR: "+nums[i] + " AND "+ (sum-nums[i]));
}
}
}
}
import java.util.HashSet;
import java.util.Set;
public class TestSum {
public static void main(String[] args) {
// TODO Auto-generated method stub
int [] nums = {-1,-2,-3,2,5,3,7,9,8,13,16,6,15,44,4};
int sum = 12;
Set<Integer> dataset = new HashSet<Integer>();
for(int i=0; i<nums.length;i++){
// System.out.println("Index = "+i);
dataset.add(nums[i]);
if((nums[i] !=sum-nums[i] ) && dataset.contains(sum-nums[i]) ){
System.out.println("PAIR: "+nums[i] + " AND "+ (sum-nums[i]));
}
}
}
}
import java.util.HashSet;
import java.util.Set;
public class TestSum {
public static void main(String[] args) {
// TODO Auto-generated method stub
int [] series = {-1,-2,-3,2,5,3,7,9,8,13,16,6,15,44,4};
int sum = 12;
checkSum(series, sum);
}
public static void checkSum(int[] series, int sum){
Set<Integer> dataset = new HashSet<Integer>();
for(int i=0; i<series.length;i++){
System.out.println("Index = "+i);
dataset.add(series[i]);
if((series[i] !=sum-series[i] ) && dataset.contains(sum-series[i]) ){
System.out.println("PAIR: "+series[i] + " AND "+ (sum-series[i]));
}
}
}
}
def find_sum_match(array, sum):
results = []
finalresults=[]
for x in array:
array=array[1:]
if (sum-x) in array:
sublist=list()
sublist.append(x)
sublist.append(sum-x)
results.append(sublist)
for i in results:
if i not in finalresults:
finalresults.append(i)
return finalresults
print find_sum_match([2,5,5,3,7,9,8],10)
O(n) time
O(n) memory
public static String findPairs( int sum, int[] nums ){
boolean[] numPresent = new boolean[sum+1];
for( int num : nums ){
if( num <= sum ){
numPresent[num] = true;
}
}
StringBuffer s = new StringBuffer();
for( int i = 0; i < sum/2; i++ ){
if( numPresent[i] && numPresent[sum-i] ){
s.append("(" + i + ", " + (sum-i) + ")" );
s.append("\n");
}
}
return s.toString();
}
/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
ArrayList<Integer> arr = new ArrayList<Integer>();
arr.add(2);arr.add(3);arr.add(4);arr.add(7);arr.add(8);arr.add(9);
System.out.println(arr.toString());
Iterator itr = arr.iterator();
int sum=11;
Integer a;
for(int i=0;i<arr.size();i++)
{
sum = sum - arr.get(i).intValue();
a = sum;
if(arr.contains(sum))
{
System.out.println(" "+sum+" "+arr.get(i).intValue());
}
sum=11;
}
}
}
import java.util.Arrays;
public class sumEqual {
public static void main(String[] args) {
Integer[] arr = new Integer[]{2,5,4,7,9,8};
int sum = 11;
Arrays.sort(arr);
for(int i = 0, j = arr.length-1; i != j ;)
{
int cal = arr[i] + arr[j];
if( cal == sum)
{
System.out.println(arr[i] + " " + arr[j]);
i++;
j--;
}
else if( cal > sum )
j--;
else if( cal < sum )
i++;
}
}
}
/// C++ implementation.
/// this problem can be solved by first indexing all elements
/// into an unordered_map. and for every element, try to find
/// its pair such that they add up to sum, i.e. sum = a[i]+a[k]
///
/// Time Complexity O(n).
/// Space Complexity O(n).
///
#include<cstdio>
#include<unordered_map>
using namespace std;
void print_all_sumpair(int *a, int size, int sum) {
/// enter every element into the unordered_map. this is get rid
/// of duplicates as well.
std::unordered_map<int,int> m;
for(int i=0;i<size;++i)
m[a[i]]=1;
for(int i=0;i<size;++i) {
std::unordered_map<int,int>::iterator it = m.find(sum-a[i]);
if (it != m.end()) {
/// remove the current element in the unordered_map so that we do
/// not end up printing duplicates.
m.erase(a[i]);
m.erase(sum-a[i]);
/// lastly. print the pair.
printf("%d %d\n", a[i], sum-a[i]);
}
}
return;
}
int main() {
int a[] = {2,5,3,2,9,7,8,9};
print_all_sumpair(a, sizeof(a)/sizeof(a[0]), 11);
return 0;
}
'''Find a pair of elements from an array whose sum equals a given number'''
import time
import numpy as np
input=np.arange(20000)
np.random.shuffle(input)
sm=35598
#Solution with complexity O(n)
t=time.time()
dc={}
for i in range(len(input)-1): #O(n)
dc[input[i]]=i
for i in range(len(input)-1): #O(1)
if dc.has_key(sm-input[i]):
print '#1 :elements are',input[i],sm-input[i],'with time :',time.time()-t
break
#Solution with complexity O(nlogn)
t=time.time()
input.sort()
s=0
e=len(input)-1
while s<e:
if input[s]+input[e]>sm:
e=e-1
elif input[s]+input[e]<sm:
s=s+1
else:
print '#2 :elements are',input[s],input[e],'with time :',time.time()-t
break
Sort the array first...then add the elements of lower index and higher index of array.
Do this until lower index is lesser than higher index
1- Sort the array in the ascending order.
2- Take the sum of the lower index and higher index value.
3- if (a[lower]+a[higher])>sum
{
higher--;
}
else{
lower++;
}
4- If the a[lower]+a[higher] = sum;
print the values of lower and higher.
I would propose the following:
Let's say that array int[] a can fit into the memory
The the set construction is O(N), query to the set, if implemented via hash, is O(1) amortized and finally last loop is O(N)
A sample code is shown below:
Notice that since the number is removed from the set, all possible pairs are printed only once. Notice also that this code works only for distinct integer values in the array.
- autoboli March 12, 2015