Akamai Interview Question
Software Engineer / DevelopersIn addition to the abv method, one can also use the hash table method if space is not a constrain.
Save all the elements in a hash table. For each value store a self bit so as to make sure 'sum - element ! = element itself'.
Chaining could be used for similar elements.
For each element search
Change self = 1
if('sum - element' is present in hash table && self ! = 1)
{print the two numbers.
return}
else {self = 0}
You can use merge sort to solve this question.
Steps are:
1- Sort the given array element using merge sort .
2- declare new array and subtract the given array elements from k and store in new array.
3- Sort the second array. remove the dulicate values from arrai and array2.
4- and then apply merge sort on array1 and array2 and save it to new array.
5- nw the elements that are repeated twice in an array3 are the numbers whose sum is k.
Complexity is O(nlgn)
I think this is the best algorithm....
1.Sort ascendancy, remove duplicates also in the process
2.Remove numbers which are >= k
3.Do steps 4 through 8 till i != j
4.Start with i = 0
5.Start with j = size - 1
6.If the sum is == k, display a[i]+a[j] = k, i++, j--
7.If the sum is < k, i++, go to step 5
8.If the sum is > k, j--, go to step 5
Can somebody calculate the complexity for this please? I don't know how to do...
step 1: sort the array //O(n.log(n))
//size=8
- shoonya.mohit May 02, 2010step 2:
i=0, j=7
if a[i]+a[j]==K //done
if a[i]+a[j] > K //j--
if a[i]+a[j] < K //i++
repeat step2, till it reaches mid point //O(n)