Microsoft Interview Question Software Engineer / Developers
Team: ERP solution
Country: United States
Interview Type: In-Person
he just said you have to return the index of both numbers... sorting would change these... please read the questions before posting solutions
i gave the solution first Using the HashMap...with O(N)..after that Interviewer said he will make it harder..and ask me to avoid usage of HashMap...Also here We have to return the INDEX not the number...I think sorting doesn't help here...isn't it ?
Did you get any other inputs from the interviewer? With the question as such, I can only think of O(n*n) solutions.
The general problem "given a set of integers and an integer s, does any non-empty subset sum to s?" is called "subset sum problem. It is a special case of the knapsack problem and it is NP-complete. There is a pseudo-polynomial solution based on dynamic programming, but it requires additional data structures.
If you can sort the array and return both numbers (not their index) it can be tone in O(n log n): sort the array, then take the first and the last number: if their sum is s, then you are done. If it is less than s, you have to move the left pointer one step to the right, if the sum is greater than s, you have to move the right pointer one step to the left. Repeat until you either find the correct couple of numbers or the pointers collide.
@S am: if the array is sorted, you can pick a number and do a binary search (O(log N)) to see if there's a matching number so that the two add to the right sum. Since there's N numbers you have to try, the running time would be O(N logN), which is still much better than the naive O(N^2).
@Anirudh: That's easy. Put all the integers into a hash map. As you read each integer, subtract it from the target value, and now you want to know if there's another integer in the array whose value is that difference. Check the hash map for this.
@gcardone: This has nothing to do with subset-sum. This is a much more restricted problem that deals with only 2 integers. Try every possible first integer, and do a binary search for the second integer. This still results in an O(N logN) algo.
@eugene.yarovoi if the array is sorted then can't we do it in O(N) using this approach:
left=0;
right=n-1;
while(left<right){
currSum=arr[left]+arr[right];
if(currSum==actualSum)
return (left,right);
else if (currSum<actualSum)
left+=1;
else
right-=1;
}
@eugene.yarovoi
Solution suggested by you is poor.
U mean to say first i will sort(nlogn) and then search using binary search for every single element(which is difference from target no.) so it is nlogn
The sol suggested by @gcardone is abs fine.
Sort=nlogn
plus using 2 pointers on each end which is O(n)
That's not how I understood it. I thought the problem was to return two integers in the array such that they sum to the target value. This is consistent with the remark about using a hash map...
@eugene.yarovoi: Initially the Question was to provide pair of numbers which sum to the target number...Once i gave the solution with HashMap, he said now Retrieve the Index of those 2 numbers...i did that as well with O(N)...But now...he said lets remove the HashMap from the picture...And i was required to use only an array !!
I understand your solution of Binary search to get 2 numbers and if array is sorted..but what about the index in that case ?? as my questions was to provide index and not the number !! please share your thoughts. Thanks !!
In question they have said that "return both the numbers" which means "we need to find the sum of 2 numbers which is equal to the target number"
no. sum of sequence equal to target and return the index of start and end of the sub sequence
Y ep, I was asked to return pair of number which sum to the number.....later he asked me to find the index of those t w o number...I did one mistake , I could have used binary search as a numbers were sorted.I could Have avoided usage o f h as hma p
If you are to find a sequence of elements in the array, then binary search alone would not do. Consider this example (this time with the array sorted):
2 4 5 6 7 9 10
target sum=27
sequence: 5 6 7 9
indices to return = 2 & 5
This algorithm will take O(n) time and O(1) space.
Initialize two variables i and j = 0, and CumulativeSum = 0.
Do
{
If CumulativeSum < TargetSum, increment i and CumulativeSum += arr[i].
If CumulativeSum > TargetSum, CumulativeSum -= arr[j] and increment j.
If CumulativeSum == TargetSum, return i and j.
}
(while j <= i and i < n);
As the ARR is sorted :
public static List<Limit> eqSum(int[] arr, int length, int reqSum) {
List<Limit> l = new ArrayList<Limit>();
for (int i = 0; i < length; i++) {
int sum = 0;
for (int j = i; j < length; j++) {
sum = sum + arr[j];
if (sum == reqSum) {
Limit l1 = new Limit(i, j);
l.add(l1);
}
if (sum > reqSum) {
break;
}
}
}
return l;
}
Use Kadane's algorithm. Will get it done in linear time with no extra space (Except for a few variables).
But you got to modify it a bit to suit your question.
If sorting is allowed, it can be done in O(n lg n)
- Anonymous October 25, 2011