Microsoft Interview Question Software Engineer in Tests
Your solution is O(n) in space and in time also.
If the interviewer wants a O(1) in space, I think the best algo is O(n logn) = sort array, and then have two pointers - one at the 0 and one at n - and compare the current sum with k and then increase or decrease one pointer.
i was asked the same question in my interview with Amazon. I gave a hash based algorithm and the interviewer was fine with it. The solution is not O(n) space complexity. It is infact O(SUM) because you insert or retrieve elements that are less than SUM. if SUM >max(n) then space complexity is O(n).
@chennavarri... suppose you have this array: -1, -2, -3, and the next n numbers (negatives).
What is the complexity? O(-n^2)?
If you are using an hash, you will use in the worst case n different "cells". Therefore, the solution with hash is O(n) in space.
In the sorting method, complexity is O(n^2):
First pointer points to the 0th element and you advance the second pointer from the 1st to the nth element until sum of 0th and ith element exceeds the desired sum or the end of list is reached.
When exceeded, you need to advance the first pointer to the 1st element but while doing this, you also need to set the second pointer to the 2nd element, you cannot just keep the second pointer where it is. So it becomes O(n^2)..
If it is going to be O(n^2), why do we need to sort it? Can't we find the pairs without sorting, in O(n^2)?
1. Sort the array, say in ascending order.
2. Have two references: one to the beginning(left) of the sorted array and one at the end(right).
3. while right > left
3.0 Check if the two add up to the sum.
3.1 If yes, return them.
3.2 Else if their sum is < required sum, increment left.
3.3 else decrement right.
4. If we get out of the above loop, there are no two numbers that add up to sum.
This runs in O(nlogn + n/2) ~ O(nlogn), depending on the sorting method that is used.
Store the array into a hashmap.
Traverse the array again, and for each element Arr[i], check whether Sum - A[i] exists in the hashmap.
Since, hashmap has constant put/get times, this gives a linear solution in the size of the array.
--Chander
Let 'k' be sum. Read the array and start updating in hashtable. for each update check if k-a[i] is available in hash table, if not then update else print the sol.
- Anonymous October 09, 2010This will be in O(n).