Amazon Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
Yup agree here is code in java
public static int [] returnSum(List<Integer> list, int sum){
int [] temp = new int[2];
HashSet<Integer> set = new HashSet<Integer>();
for(int i =0;i<list.size();i++){
Integer val = list.get(i);
if(set.contains(val)){
temp[0] = val;
temp[1] = sum-val;
break;
}
else{
set.add(sum-val);
}
}
return temp[0] == 0 ? null : temp;
}
Complexity - O(n)
Space O(n)
The sample given in the problem description implies the output should list all the pairs that sum to s. The code returns only one pair, doesn't it?
It's Hashset not a set if we assume a good hash mapping fuction then contains is O(1) so its O(n)
and if you want to take all the pairs then instead of returning integer array return List of Set.
Why HashTable? we can use same List passed in argument to check if s-a[i] exist or not. And above code dose not give all output
public static void findSumHashMap(int[] arr, int key) {
Map<Integer, Integer> valMap = new HashMap<Integer, Integer>();
for(int i=0;i<arr.length;i++)
valMap.put(arr[i], i);
for(int i=0;i<arr.length;i++) {
if(valMap.containsKey(key - arr[i]) && valMap.get(key - arr[i]) != i) {
int diff = key-arr[i];
System.out.println(arr[i] + " " +diff);
}
}
}
#include<stdio.h>
main()
{
int y;
int input[9]={1,2,3,4,5,6,7,8,9};
int sum=11;
int tempArr[10000];
for(int i=0 ; i < sizeof(input)/sizeof(int); i++)
{
tempArr[input[i]]= input[i];
}
for(int i=0 ; i < sizeof(input)/sizeof(int); i++)
{
int temp = sum - input[i];
if(temp==tempArr[temp])
printf("(%d,%d)\n",input[i],temp);
}
}
public ArraySum(int size)
{
int i=0;
int n[] = new int[size];
Scanner keyboard = new Scanner(System.in);
System.out.println("Enter the integers : ");
while(i<size)
{
n[i] = keyboard.nextInt();
i++;
}
System.out.println("Enter the sum : ");
sum=keyboard.nextInt();
for(int k=0;k<size;k++)
{
for(int j=0;j<size;j++)
{
if(n[k]+n[j]==sum && n[k] != n[j])
System.out.println(n[k] + " + " + n[j] + "=" + sum);
}
}
}
There are some issues with this code:
1. This will fail if there are some integers which are repeated. For instance if the numbers are 1 2 3 3 4 and the sum is 6 it will not find 3,3
2. It will also repeat some numbers ..for instance in the earlier example it will say 2+ 4 as well as 4 + 2
3. The time complexity is more as compared to a hashtable.
If we ignore the time complexity the first two issues can be fixed by making the following changes:
for(int k=0;k<size;k++)
{
for(int j=k+1;j<size;j++)
{
if(n[k]+n[j]==sum )
System.out.println(n[k] + " + " + n[j] + "=" + sum);
}
}
public static void main(String[] args) {
ArrayList<Integer> a= new ArrayList<Integer>();
a.add(0);
a.add(2);
a.add(4);
a.add(6);
a.add(8);
a.add(10);
a.add(12);
System.out.println("display list "+a);
int s=10;
for(int i=0;i<a.size();i++)
{
int diff=s-a.get(i);
if(a.contains(diff))
{
System.out.println(a.get(i)+" + "+diff);
}
}
}
gives duplicates though
display list [0, 2, 4, 6, 8, 10, 12]
0 + 10
2 + 8
4 + 6
6 + 4
8 + 2
10 + 0
Time O(nlogn) space => O(1)
private static void PrintPairs(int[] input, int p)
{
Quicksort(input, 0, input.Length - 1);
int startIndex = 0;
int endIndex = input.Length - 1;
while (startIndex < endIndex)
{
int sum = input[startIndex] + input[endIndex];
if (sum == p)
{
Console.WriteLine("input[{0}] = {1} + input[{2}] = {3}", startIndex, input[startIndex], endIndex, input[endIndex]);
startIndex++;
}
else if (sum < p)
{
startIndex++;
}
else if (sum > p)
{
endIndex--;
}
}
}
private static void Quicksort(int[] inputs, int left, int right)
{
int i = left, j = right;
int pivot = inputs[(left + right) / 2];
while (i <= j)
{
while (inputs[i] < pivot)
{
i++;
}
while (inputs[j] > pivot)
{
j--;
}
if (i <= j)
{
int tmp = inputs[i];
inputs[i] = inputs[j];
inputs[j] = tmp;
i++;
j--;
}
}
if (left < j)
{
Quicksort(inputs, left, j);
}
if (i < right)
{
Quicksort(inputs, i, right);
}
}
Assume given numbers are sorted.Then create a temp array obtained by substracting elements from the array but in reverse fashion.Then check the 2 sorted arrays.Eg:10 12 15 18 20 and sum is 33 then temp array is 13 15 18 21 23.Then check 10 and 13.10<13 then move to 12.12<13.then 14<13(no)so 14 and 15.so on O(n)
Sort the given list of numbers in O(nlogn), and then pick each element, find k = sum-ele, and do a binary search for finding 'k',
if there exists such a value 'k' , it means it is the required pair which sums to 'sum'.
Time complexity :: O(nlogn)
public class SumElement
{
public static void main(String[] args) {
SumElement _obj = new SumElement();
int[] M = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 , 13, 14 ,15, 0, 16, -1, 20, 17, -5, -13, -23, 19, -4};
//Qick Sort;
int pivote = _obj.partition(M, 0, M.length -1);
// prints all pair of elements having sum 15
_obj.findSumElement(M, 15);
}
private int partition(int[] a, int min, int max) {
if (min > max)
return 0;
int p = min;
for (int i = min + 1; i <= max; i++ ) {
if (a[i] < a[p]) {
swap(a, p, p + 1);
if (i != p+1)
swap(a, p, i);
p = p+ 1;
}
}
partition(a, min, p -1);
partition(a, p+1, max);
return p;
}
private void swap( int[] a, int f, int s) {
if (f < a.length && s <a.length) {
int t = a[f];
a[f] = a[s];
a[s] = t;
}
}
private void findSumElement(int[] a, int s)
{
int l = 0;
int r = a.length -1;
while (l < r) {
int sum = a[l] + a[r];
if (sum == s) {
System.out.println("sum = ("+a[l] + " + "+a[r]+") = "+s);
l++;
r--;
} else if (sum > s){
r--;
} else {
l++;
}
}
}
}
Python: if somebody finds better way please let me know:
#!/usr/bin/python
def recurseWrapper(array):
for i in range(len(array)):
temp = array[:]
id=temp[i]
temp.pop(i)
recurse(temp,id)
def recurse(array,id):
if (len(array) == 0):
return
if ( id + array[0] == 6 ):
print "%i + %i = 6" % (id,array[0])
array.pop(0)
recurse(array,id)
if __name__ == "__main__":
numbers = [1,2,3,3,4,5]
recurseWrapper(numbers)
1 + 5 = 6
2 + 4 = 6
3 + 3 = 6
3 + 3 = 6
4 + 2 = 6
5 + 1 = 6
public void checkSum(List<Integer>, list, int s){
int resultQty = 0;
for(int i = 0; i < list.length(); i++){
for(int j = 0; j < list.length(); j++){
if(list.get(i) + list.get(j) == s)
resultQty++;
system.out.printl(list.get(i) + "+" + list.get(j) + "=" + s);
}
}
if(resultQty == 0)
system.out.println("No result found.");
}
// complexity is O(nlogn)
List<Integer> nums = Arrays.asList(4,3,5,1,2,7,-1,-2,10,12);
Collections.sort(nums);
int sum = 8;
int min = nums.get(0);
// terminate early
if (min > sum) {
return;
}
// initially reduce our list
int possibleMax = sum - min;
int maxIdx = Collections.binarySearch(nums, possibleMax);
// NB subList won't copy array, it's just a convenient 'view'
if (maxIdx > 0) {
nums = nums.subList(0, maxIdx + 1);
} else {
nums = nums.subList(0, -maxIdx - 1);
}
for (int i = 0; i < nums.size(); i++) {
Integer n = nums.get(i);
// assume current as first number
int remainder = sum - n;
// filter out candidates (which are right subarray)
List<Integer> candidates = nums.subList(i + 1, nums.size());
// find remainder
int idx = Collections.binarySearch(candidates, remainder);
if (idx >= 0) {
//print result twice
Integer n1 = nums.get(i + idx + 1);
System.out.printf("%d + %d = %d%n", n, n1, sum);
System.out.printf("%d + %d = %d%n", n1, n, sum);
}
}
Can be solved using dynamic programmin as a variation of the knapsack problem.
The value and weight of the items of the knapsack are set to the integer values, i.e. values[]={1,2,3,4,5}, weights[]={1,2,3,4,5}, the maximum weight in the knapsack is set to the target value. Complexity: O(n*W)
main()
{
int arr[10]={1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int i,k;
int j=sizeof(arr)/sizeof(int);
k = j;
int sum;
cin >>sum;
while(i<k)
{
while(j>i)
{
if(sum == arr[i]+arr[j] )
{
cout << "pair" << arr[i] <<" "<< arr[j]<<endl ;
cout << "pair" << arr[j] <<" "<< arr[i]<<endl ;
i++;
j--;
}
else
j--;
}
j=k;
i++;
}
}
#include <stdio.h>
void merge(int a[],int low,int high);
void mergesort(int a[],int low,int high);
int binarysearch(int a[],int i,int j,int key);
int main(int argc, char const *argv[])
{
int *a,i=0,key,left,right;
a=(int *)malloc(sizeof(int)*10);
printf("data\n");
a[i]=rand()%10;
for ( i = 1; i < 10; ++i)
{
a[i]=a[i-1]+(rand()%20);
}
for ( i = 0; i < 10; ++i)
{
printf("%d ",a[i] );
}
printf("\n");
printf("key\n");
scanf("%d",&key);
mergesort(a,0,9);
i=binarysearch(a,0,9,key/2);
if(i<=0||i==9)
{
printf("no elements\n");
return 0;
}
left=i-1;
right=i;
while(left>=0&&right<=9)
{
if(a[left]+a[right]>key)
{
left--;
}
else if(a[left]+a[right]<key)
{
right++;
}
else
{
printf("%d %d\n",a[left],a[right] );
if(left<=0 && right>=9) break;
if(left>0) left--;
else if(right<9) right++;
}
}
return 0;
}
int binarysearch(int a[],int i,int j,int key)
{
if(i>j) return j;
int mid=(i+j)/2;
if(a[mid]==key)
{
return mid;
}
else if(mid+1<=j && a[mid]<key && a[mid+1]>key)
{
return mid;
}
else if(a[mid]<key)
{
return binarysearch(a,mid+1,j,key);
}
else
{
if(mid-1>=0 && a[mid-1]<key && a[mid]>key)
{
return (mid-1);
}
else return binarysearch(a,i,mid-1,key);
}
}
void mergesort(int a[],int low,int high)
{
int m;
if(low<high)
{
m=(low+high)/2;
mergesort(a,low,m);
mergesort(a,m+1,high);
merge(a,low,high);
}
}
void merge(int a[],int low,int high)
{
if(low>=high) return;
int b[high-low+1],mid=(low+high)/2;
int i=low,j=mid+1,k=-1;
for(;i<=mid && j<=high;)
{
while(a[i]<a[j] && i<=mid && j<=high)
{
b[++k]=a[i];
i++;
}
while(a[i]>=a[j] && i<=mid && j<=high)
{
b[++k]=a[j];
j++;
}
}
for(;i<=mid;i++)
b[++k]=a[i];
for(;j<=high;j++)
b[++k]=a[j];
for (k=0, i = low; i <=high; ++i,++k)
{
a[i]=b[k];
}
}
int main(int argc, char **argv)
{
std::vector<int> array = { 1, 2, 3, 4, 5 };
int sum = 6;
for (auto i = 0; i < array.size(); ++i) {
for (auto j = i; j < array.size(); ++j) {
if (i == j) continue;
if ((array[i] + array[j]) == sum) {
std::cout << array[i] << " + " << array[j] << " = " << 6 << std::endl;
std::cout << array[j] << " + " << array[i] << " = " << 6 << std::endl;
}
}
}
return 0;
}
public static void printAllPairsSummedToN(int[] arr, int sum) {
TreeSet<Integer> set = new TreeSet<>();
for (int i : arr) {
if (i <= sum && !set.contains(sum - i))
set.add(i);
}
for (int i : set) {
System.out.println(String.format("%3d, %3d", i, sum - i));
}
}
1. Initially create a Hashtable or an Array( that acts like hash table) from the list . - O(n)
- foo February 07, 20132. For each element get the value s -a[i], look it up in hashtable. If it exists print a[i] + (s-a[i]) = s