Amazon Interview Question Software Engineer in Tests
Roy's solution assumes that the numbers are arranged in ascending order.
The question doesn't say anything about it.
No i don't assume that they would be in ascending order ... ...be the array in any order if you traverse through the array and check if the key (sum-a[i]) exists means their is a corresponding pair else put the value in hash... remember you don't have to worry in what order the hash is arranging it.. and the lookup is always O(1) .. Point to note i didn't say Array[sum - Array[i]] this would be a C/C++ implementation without any STL hash table. and it would require array to be sorted, but with hash table in JAVA or STL you won't need to sort it.
Anyways the interviewer told me the solution was rite at the end of the interview.
I'm just trying to learn stuff here. That's all.
The lookup is not O(1) rather O(n), for a hash table considering that collision is always possible. So, you'd spend essentially O(n2) time in solving the problem. Please correct me if I'm wrong.
Everyone is learning, why else anyone be here. Anyways my point was yes look up for N number in hasp is O(N) but for one lookup it's O(1) ... there can be collisions but that doesn't effect us. Ex if there are two 4's and the sum you require is 7 so 4+3 = 7 which 4 doesn't make any difference. The question doesn't say which 4 makes that pair. if in an array there were 10 number of 4's and one 3 still the answer has to be 4,3.
O(n^2) means u compared each element with every other element in the array but when you use hash table you are comparing only once every element ... one element of array compared to one element of hash. so the total number of comparison equals n ... which means O(n)... don't even bother thinking how hash table gets the key value in O(1)... until and unless u really want to.
I hope this clears your doubt.
Hi, I am not quite sure that i understand. Let me give it my understanding out of this.
We have a set of numbers {a1,a2,a3......an} and a number S = ai+aj
Lets have a hash table of size n elements
Start iterating from k= 1 to n,
1. Fill the hash table with two entries, S - ak and ak
2. If one collision found out of two insertion above, let say ak (WLOG) Declare ak and S-ak as two numbers in the array which constitute the sum.
Else continue
Help me know the pitfall of this.
just take two pointers,say p and q
- amd August 18, 2009p=0,q=n-1,count=0
while(p<q)
{
if(arr[p]+arr[q]==s)
{
p++;
q--;
count++;
}
if(arr[p]+arr[q]>s)
q--;
if(arr[p]+arr[q]<s)
p++;
}
cout<<count