Amazon Interview Question Software Engineer / Developers
Country: Canada
Interview Type: Phone Interview
method 2 can be done in a single pass
before inserting each element a[i] in hash check whether k-a[i] is already in hash..if yes return true
@Amit. Very Good point. +1. You're right it can be done in the first pass. It's still O(n) time and O(n) space though.
@oozz--yes..but two benefits
1.single pass only
2.we don't need to store the freq(case 2.a.a in your algo is handled implicitly)
even if a[i]=k-a[i]..we first check if diff is present or not and den insert...so storing freq is not necessary
I know buddy, that's why I upvoted your comment. Good suggestion. I said complexity-wise it's the same, but definitely better implementation.
@oOZz--yessss :) btw,can you think of any solution for the same problem but here we don't want 2 elements whose sum equal to k,but whose sum is closest to k...any o(n) time complexity approach??
@Amit
To find the closest numbers, you can use the hashtable method itself with a slight modification to querying the hashtable.
>> before inserting each element a[i] in hash check whether k-a[i] +/- j, with 0 <= j <= c, for some constant c, is already in hash..if yes return true
You may want to maintain variables that keep track of the minimum difference seen far and the corresponding pair of numbers that have the min. difference.
c will always be a constant here, for if we let grow c to the order of n, say n/2, then (k - a[i]) will be of order n, which implies that the array elements are so sparse that their number tends to be a constant. In other words, you will have an O(n) solution, albeit with an appreciable constant.
@Amit I don't know how to do it in O(n).
@tatt'va, do you care to share the code? I am lost with "k-a[i] +/- j, with 0 <= j <= c". This statement seem to me that this algorithm will only work if the array elements are close in range.
I'm a little confused about the time complexity. If we are inserting and querying a hashMap for method 2, doesn't this mean the complexity becomes O(logn)? Is this complexity only dependent on the number of hits on the initial array?
All,
If you want to do it in a single pass.. you need to check for both k-a[i] and k+a[i]..!!
Only checking for k-a[i] wont work..!!
@oOZz great Algos
I am giving program for your first Algo.
void search(int A[],int n,int K) {
int i,j,temp;
Sort(A,n);
for(i=0,j=n-1;i<j;) {
temp = A[i] + A[j];
if(temp == K) {
printf("Elements found %d %d", i, j);
return;
}else if(temp < k)
i=i+1;
else
j=j-1;
}
return;
}
Even it works without Sort since we are checking all possibilities.
#include<stdio.h>
main()
{
int a[10],i,j,sum,count=0;
printf("enter the sum you want to check : \n");
scanf("%d",&sum);
printf("enter the element of array : \n");
for(i=0;i<10;i++)
scanf("%d",&a[i]);
for(i=0;i<10;i++)
{
for(j=0;j<10;j++)
{
if((i!=j) && (a[i] + a[j] == sum))
count++;
}
}
if(count>0)
printf("True\n");
else
printf("False\n");
}
if the array contains a range of numbers...(i......N) then we can do it in O(n) time as well space complexty otherwise we need to sort the array first and follow two index(start index and end index approch)
solution for array having a range of.....
#include<stdio.h>
#include<stdlib.h>
#define MAX 800
main()
{
int a[]={1,34,6,78,44,788,33,56,4,,456,600,304};
int size=12;
if(haspair(a,size,792))
printf("Has pair::");
else
printf("No pair::");
}
int haspair(int *a,int size,int x)
{
int i;
int B[MAX]={0};
for(i=0;i<size;i++)
{
if(x-a[i]>=0 &&B[x-a[i]==1)
{
return true;
}
else
B[a[i]]=1;
}
}
public boolean twoSumToK(int[] array, int k) {
for (int i = 0; i < array.length; i++) {
for (int j = i + 1; j < array.length; j++) {
if (array[i] + array[j] == k) { return true; }
}
}
return false;
}
#include <iostream>
#include <stdio.h>
using namespace std;
bool func(int arr[],int sum,int size);
void print_sum(int arr[],int sum,int size)
{
int count = 0;
for (int i = 0;i < size; i++)
{
for(int j = 0;j < (size - i - 1); j++)
{
int temp_size = arr[i] + arr[i + j + 1];
if(temp_size == sum)
printf("(%d) Sum Found [%d] + [%d] = [%d]\n",++count,arr[i],arr[i + j + 1],sum);
}
}
}
int main()
{
int arr[5] = {2,3,4,5,2};
int sum = 7;
int size = sizeof(arr)/sizeof(arr[0]);
bool result = func(arr,sum,size);
print_sum(arr,sum,size);
return 0;
}
bool func(int arr[],int sum,int size)
{
for (int i = 0;i < size; i++)
{
for(int j = 0;j < (size - i - 1); j++)
{
int temp_size = arr[i] + arr[i + j + 1];
if(temp_size == sum)
return true;
}
}
return false;
}
This question is asked before, so if you search you can find the implementations as well. You can do this in two different ways
- oOZz July 09, 2013Method 1
1. Sort the number array A => A'
2. Keep two pointers start and end. start points to the first element and end points to the last element
3. while start < end, add sum = A'[start] + A'[end]
3.a. if sum == k return true
3.b. if sum < k, start++
3.c. if sum > k, end--
4. return false at the end (no match found at this point)
This is O(n log n) time due to sorting, and O(1) time
Method 2
1. First pass, put all the elements in the hashtable. the key is the number, the value is the frequency of the number in the array
2. second pass, calculate diff = k - A[i] and check if the key is in the hashtable
2.a. if diff is in the hashtable
2.a.a. special case (if diff == A[i])
check if the frequency is >2, then return true, else continue
2.a.b. return true (diff exists in hashtable and diff != A[i])
3. return false at he end (no match found at this point)
O(n) time, and O(n) space