## Microsoft Interview Question for Software Engineer / Developers

Team: ERP solution
Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
0
of 0 vote

If sorting is allowed, it can be done in O(n lg n)

Comment hidden because of low score. Click to expand.
0

he just said you have to return the index of both numbers... sorting would change these... please read the questions before posting solutions

Comment hidden because of low score. Click to expand.
0

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 ?

Comment hidden because of low score. Click to expand.
0

Did you get any other inputs from the interviewer? With the question as such, I can only think of O(n*n) solutions.

Comment hidden because of low score. Click to expand.
0

I agree! O(n*n) is the only solution I get.

Comment hidden because of low score. Click to expand.
0

What if the arr ay I s sorted ??? How will you get the index of both numbers ?

Comment hidden because of low score. Click to expand.
0

How did u do it O(N) using a HashMap

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

@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.

Comment hidden because of low score. Click to expand.
0

can any1 give me the algorithm to implement the above prob using HASH ?

Comment hidden because of low score. Click to expand.
0

@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;
}``````

Comment hidden because of low score. Click to expand.
0

@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)

Comment hidden because of low score. Click to expand.
0

Using the 2 pointers is better, agreed. I didn't bother because either way it's NlogN.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Can anyone explain me the problem definition with an example ?please

Comment hidden because of low score. Click to expand.
0

4 5 6 2 10 9 7
target sum=18
ans: 6 2 10

Comment hidden because of low score. Click to expand.
0

here return index of 6 and 10... i.e. 2 & 4

Comment hidden because of low score. Click to expand.
0

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...

Comment hidden because of low score. Click to expand.
0

@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 !!

Comment hidden because of low score. Click to expand.
0

As u said
4 5 6 2 10 9 7
target sum=18
ans: 6 2 10

but another ans is 7 6 5 or 9 5 4

then which pair is the ans..how will you decide that ?

Comment hidden because of low score. Click to expand.
0
of 0 vote

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"

Comment hidden because of low score. Click to expand.
0

no. sum of sequence equal to target and return the index of start and end of the sub sequence

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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);

Comment hidden because of low score. Click to expand.
0

hey but here you are taking a continuous subarray.If target sum is 28 then in that case this solution wont work

Comment hidden because of low score. Click to expand.
0
of 0 vote

I am wondering if this can be done using functors in C++

Comment hidden because of low score. Click to expand.
0

Hi Sameer,
Can you explain..how you can do this using functors.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}
if (sum > reqSum) {
break;
}
}
}
return l;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0

Can you explain properly instead of suggesting ?

Comment hidden because of low score. Click to expand.
0

in WIKI, Search for "Maximum subarray problem" . Its Straight forward

Comment hidden because of low score. Click to expand.
0
of 2 vote

(1) Do sorting (forget about the indexes) O(NlogN)
(2) Find the two numbers in O(N) (by using two pointers).
(3) Find the indexes of two numbers in the original array in O(N).

Comment hidden because of low score. Click to expand.
0
of 0 vote

Lets take x = 2 pow n where n = number of elements in the array. Then, we find out from 1 till x, where there are only two bits of the number set to 1. Then we take those indices , and find out those numbers which add up to the fixed number.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.