Amazon Interview Question
Software Engineer / DevelopersHow do you resolve input array with dups?
Hashtable would bail out with dup keys.
You might have to add some special casing there.
You also have a problem with this input.
input: {1,2,3,4,5} , sum = 10.
this function will return 5,5 as the answer, where as the right answer is none.
sort the array (nlogn)
i=0, j=n-1 (j is set to last element of the array)
then use following algo ( O(n))
while i<j
if( (arr[i] + arr[j]) > val)
j--;
else if( (arr[i] + arr[j]) < val)
i++;
else
print arr[i], arr[j]
sort the array (nlogn)
i=0, j=n-1 (j is set to last element of the array)
then use following algo ( O(n))
while i<j
if( (arr[i] + arr[j]) > val)
j--;
else if( (arr[i] + arr[j]) < val)
i++;
else
print arr[i], arr[j]
This greedy algorithm is quite good.
This was my first thought, interviewer didn't like it much since its a nlogn. Shoot for fastest algo possible, which is O(n)
I love it when people answer specific questions with data structures. Clearly shows they don't know what they are talking about. I have 7 solutions off the top of my head.
1.) Red black tree
2.) AVL tree
3.) Fibonnaci heap
4.) DAG
5.) DFA
6.) Stack
7.) Linear programming
I think the point of discussing these questions is to get an idea of how other people would actually implement a solution. Supplying data structures and programming paradigms as answers does no good. It would be nice if you could provide an in depth explanation of the most efficient of your solutions.
Anonymous wrote:
--------
I love it when people answer specific questions with data structures. Clearly shows they don't know what they are talking about. I have 7 solutions off the top of my head.
1.) Red black tree
2.) AVL tree
3.) Fibonnaci heap
4.) DAG
5.) DFA
6.) Stack
7.) Linear programming
---------------
Idiot. What a silly thing to say. In fact you seem to quite adept at demonstrating your ignorance.
Just saying Hashtable is a perfectly reasonable answer.
Do you understand that people here are of their own will, sharing their time to help others out? So what if they don't include a complete solution, just a few keywords (in this case, hashtable) should be good enough for a determined person to come up with a solution for that.
1) Find the max, using a sort. nlog(n)
2) Populate a bit vector A[] with 1 for each integer in the array, 1 for those not in the array.
3) loop through the integer array, for each int i, if A[n-i]== 1. i and n-i are the two integers that add up to N.
There is no need to search in the 3rd step.
find min and max in O(n). then define a hash table with hashing function h(num)=num%d, where d=(max-min)/n.
now, for each element in an array search if the hash table contain a value (sum-num[i]) [i.e. search at the index h(sum-num[i])], if yes the present index and the number stored in hash table is the pair. If not, insert into hash table num[i].
Using this function, if we can assume that the numbers are uniformaly distributed, we can say that each bin will have one number on an avg. so the searching will be done in O(1). therefore total complexity is O(n).
---------
sort the array (nlogn)
i=0, j=n-1 (j is set to last element of the array)
then use following algo ( O(n))
while i<j
if( (arr[i] + arr[j]) > val)
j--;
else if( (arr[i] + arr[j]) < val)
i++;
else
print arr[i], arr[j]
This greedy algorithm is quite good.
-----------
This algo won't work. check it out.
void Find_Two_number(int a[],int size,int number)
{
int max = a[0];
int x = -1,y = -1;
for (int i = 0;i<size;i++)
{
if(a[i]>max)
{
max = a[i];
}
}
bool *b = new bool[max+1];
for (int i = 0;i<=max;i++)
{
b[i] = false;
}
for (int i = 0;i<size;i++)
{
b[a[i]] = true;
}
for (int i = 0;i<size/2;i++)
{
if(b[a[i]] == true)
{
if(b[number- a[i]] == true)
{
cout<< "X= "<< a[i]<<"; Y = "<< number-a[i]<<endl;
}
}
}
}
yes, it could be done in linear.. O(n).
public void PairsOfArraySumsUpToGivenInteger(int[] arr, int sum)
{
int i = 0, j = i + 1;
while (i < arr.Length)
{
if (arr[i] + arr[j] == sum)
{
Console.WriteLine(arr[i] + "," + arr[j]);
j++;
}
else
j++;
if (j >= arr.Length)
{
i++;
if (i < arr.Length - 1)
j = i + 1;
else
break;
}
}
The above algorithm can be solved using hashing, keep calculating the difference of the given number to each element in the array if the element is present in the array then, return true else insert the element into the hashset and when it is not true then, at the end of the operation return false.
Implemenatation:
#include<bits/stdc++.h>
using namespace std;
bool findsum(int arr[], int n, int x){
unordered_set<int> s;
for(int i = 0; i < n; i++){
int diff = x - arr[i];
if(s.find(diff) != s.end())
return true;
s.insert(arr[i]);
}
return false;
}
int main(){
int t, n, x;
cin>>t;
while(t--){
cin>>n>>x;
int arr[n];
for(int i = 0; i < n; i++)
cin>>arr[i];
if(findsum(arr, n, x) == 1)
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
//cout<<"Keep learning Keep growing"<<endl;
return 0;
}
could be done in On
- Omer February 07, 2009