Amazon Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
This seems to be O(n^3) algorithm.
For a given c, finding (a,b) pair such that a+b = -c would take n^2.
and in worst case, you need to try all possible c, i.e. and so
n* O(n^2) = O(n^3)
No finding a pair that sums to a specific value can be done in O(n) given the array is already sorted. Copy paste from another site.
If a+b = K, then return (a,b).
If a+b < K, then move a to the right one position.
If a+b > K, then move b to the left one position.
Above may not work in worst case..
e.g. -6, 0 , 1, 2, 4
answer is: -6, 2, 4
To start with -6, we need to find a pair with sum 6
and probably search pair pattern would be:
(0,1), (0,2), (0,4) -- not found
(1,2), (1,4) -- not found
(2,4) -- found
And this search doesn't seem to be O(n). In worst case it will be:
(n-1) + (n-2) + (n-3) + .... + 1 = O(n^2) times
At the beginning a is at the start of array, b is at the end of the array. Now reexecute the code and see for yourself. Again the array MUST be sorted.
This solution would be in O(n^2) only if we use a hash table.
To pick 2 numbers a,b from an array takes O(n^2) in itself.
we can search for c such that c = -(a+b). If we would have hashed all the values then we can lookup if the value -(a+b) exists in the hashtable ensuring overall running time of O(N^2).
For this approach, the array need not be sorted.
{ -6, -4, 0, 12, 13 } will fail for this integer list.
12+ -6 = 6
when i do a search for -6 in the hash table it would print -6, 12 for sum 6 which is false.
good observation, we need to keep track of the 12 and -6 position so that the -6 will not hit those two positions.
There can be one case also
a= -(b+c)
there can be one +ve element say 10 and there can be two negative no -6 and -4 so it will fail for this case as well
The above solution will work just fine. There is another approach as well.
You can also traverse the array and put everything into hash table. Once this is done try all the possible pair sums and check if negative of the sum exists in the hash table. This will be O(n^2) as well.
1. Sort the given array (say sorted array is a). O(n log n)
2. Create a n x n matrix (say sum) where sum[i][j] = a[i] + a[j]
This matrix is sum of all possible pairs in given array where sum value is sorted
left to right and top to bottom. O(n^2)
Here diagonal elements can be ignored and also upper and lower triangular are same,
We need only upper or lower, so we may calculate only upper triangular portion of the
matrix.
3. Now for each element c in the array, search for -c in the sum array as below:
a) start from sum[0][0]
b) if current element in sum is equal to -c, you got the answer (a[i] + a[j] + c = 0)
c) if current matrix element is less than -c, go right in the same row
d) if current matrix element is more than -c OR you reached at the end of the row
,go down in the same column
e) If you reached at the last element of matrix (bottom right) and -c not yet found,
-c is not in the matrix
Step 3 will take at most 2n search for any -c (if your search happens to be
right, down, right, down, right, ..........), so total O(n^2)
Overall complexity: O(n log n) + O(n^2) + O(n^2) = O(n^2)
why u need extra space it can be done without taking the extra space also in O(n^2).
its sure that either 2 positive numbers in 3 or two negative nos are there use this fact
1. sort the array.
2.check that a[0]>=0 then return not possible at all.
3. find the position "pos" such that from here positive numbers start in O(n) just traverse the array.
4. now --
a. take element from i=0 to pos-1 and search in positive part of the array for two numbers such that a+b=-1*c this can be done in O(n2). if found just print those numbers and return.
b.similar as step 4a now just take i=pos to n-1 and search two nuymbers in the negative part such that a+b=-1*c this again in O(n2) if find print the numbers and return
5 return
hope it works in all the cases
I believe step 4(a) will take (n^2) for each element search and searching is needed for each array element in worst case so it becomes O(n^3). My others two comments I gave already where I said the same.
If a pair of number (a,b) can be found such that a+b = -c for a given c in O(n) time, we are good.
But I don't see how can we find a pair in O(n).
If you don't mind, could you please explain if you have any thought on that (You may want to look at my other two comments 1st on top)
explanation of findinf two pairs such that a+b=c
suppose arr[1...n] is array which is sorted as first step is sorting ok
now take left=1 and right =n and keep looping till left <right
and check in loop:
while(left<right)
{
if(a[left]+a[right]==key)
{
//we got it
break;
}
else if(a[left]+a[right]<key)
{
left++;
}
else
{
right--;
}
}
i think now u got it
Wat about this guys .. This is my solution when the array is sorted . First of all I am hashing all the values into an hash array and then I am traversing the array
int value=0;
for(i=0;i<a.length();i++)
{
if(hash(value-(a[i]+a[i+1])))
break;-> We have found the value
else
continue;
}
When the array is not sorted the program would be, same as the first I am hashing the values into hash array
int value=0,number=0;
for(i=0;i<a.length();i++)
{
number=value-a[i];
for(j=0;j<a.length();j++)
if(j==i)
continue
else
{
if(hash(number-a[j]))
break;-> we have found the series
}
}
This is O(n^2) solution .. Let me know your comments guys
problems : a + b + c = 0 -> a + b = -c
- Anonymous January 20, 2012as we known : in sorted array, find a, b that a + b = M (M is const value ), the algorithm is very simple and its time complexity is o(n)
so, my algorithm is :
step1: sort the array . o(nlogn)
step2: for each value c in the array :
find a + b = -c
at last, the time complexity is o(nlogn + n * n) = o(n^2)