Microsoft Interview Question for Software Engineer / Developers


Team: Global Foundation Services
Country: United States
Interview Type: In-Person




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

Let the given number is N.
Pick a number from linked list. say Y.
In the BST insert N-X. If N-X already exists then your answer is X, N-X. else pick next element from list.

- Thunder2020 January 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Agree !! .. Correct Logic

- Rohit Srivastava January 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

we scan one no at a time and if the no is greater than the given no then we discard it and if its less than the given no then it could be one of the two nos so we insert it in a bst. Now while inserting in the bst (when we compare with other nos) we will add the no with the nos already in the bst and if the sum equals the given no then we get the two nos(the no we are inserting and the no in the bst).
so we can do it in O(log n) avg time in inserting in bst. or O(n) in worst case if all the inputs are in sorted order.

- raja roy January 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

i didn't get how this solution works .for example 3->7->1.and given sum lets say 8.
insert 3: 3
insert 7: 3
\
7
insert 1: 3
/ \
1 7
we will never come across sum 8 while inserting .

- gladiator January 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

How can you do it in O(log n)? and worst case is O(nlog n) for sure. Every time you check the number you insert and search from a binary search tree having complexity of search O(log n). you would have searched n times if you found the second number at index n. so O(nlog n).

- godzilaa January 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

true the complexity is O(N log N)
and.. instead of storing the numbers, we can store,
(x-a[i])
where x is given, and a[i] is current element, when a new element comes, a[j], just search for a[j], if not found insert.

- mrb January 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Correct man .. this seems to be good login !!

- Rohit Srivastava January 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

check the sum-number (which is currently found) in BST .if we find it then leave it and print both value else insert in BST.do same thing till 1st pair is not getting.

- Anonymous January 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

How about storing each sum-x[i] in a hashmap and when we go through the array, we can search for the number in the hash table?

That way the search will be worst case: O(n * HashComputationTime) since search in hashmap is O(1).

- hello world January 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

for(int element : array)
{
if(sumMap.containsKey(element))
{
System.out.println(element + " " + sumMap.get(element) - element);
}
else
{
sumMap.put(sum- element, element);
}
}

- hello world January 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

we can make a hash value for different number into the range [0, 2^32-1], and in high probability we will find the answer.
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <bitset>

using namespace std;

bitset<(unsigned int)(0xffffffff)> table;
void getsum(unsigned int sum, int &a, int &b)
{
unsigned int number;

while(scanf("%u", &number)!=EOF)
{
if (table[sum -number] ==1)
{
a =sum -number;
b =value;
return;
}
table[number] =1;
}
}

- Anonymous January 10, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

we can make a hash value for different number into the range [0, 2^32-1], and in high probability we will find the answer.
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <bitset>

using namespace std;

bitset<(unsigned int)(0xffffffff)> table;
void getsum(unsigned int sum, int &a, int &b)
{
unsigned int number;

while(scanf("%u", &number)!=EOF)
{
if (table[sum -number] ==1)
{
a =sum -number;
b =value;
return;
}
table[number] =1;
}
}

- bo hou January 10, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If bitset set to 2^32 size doesn't works (As is the case with my compiler), we can use short array and get the arr_index, bit_index:

//
//  main.cpp
//  InfiniteStream_SumPair
//
//  Created by Srikant Aggarwal on 11/01/12.
//  Copyright 2012 NSIT. All rights reserved.
//

#include <iostream>
#include <math.h>

using namespace std;

int get_num()
{
    int n;
    cin >> n;
    return n;
}

int main (int argc, const char * argv[])
{
    int sum;
    cin >> sum;
    
    //assuming the duplicate number range is b/w 0 to 2^32
    const int length = 2^28;
    static short bit_array[length];
    
    while(true)
    {
        int n = get_num();
                
        int arr_index = n/8;
        int bit_index = n%8;
        
        int temp = 1 << bit_index;
                
        if(bit_array[arr_index] & temp)
        {
            cout << sum - n << " " << n << endl;
            return 0;
        }
        else
        {
            n = sum - n;
            arr_index = n/8;
            bit_index = n%8;
            
            temp = 1 << bit_index;
            
            bit_array[arr_index] =  bit_array[arr_index] | temp;
        }
    }
    
    return 0;
}

- Srikant Aggarwal January 11, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

Is the simpliest solution just to check every new element for the sum with the previous ones, until the sum be the right one?

let say, necessary sum = 5.

Add the first element: 1

Add the next one: 3
check: 1+3 != 5

Add the next one: 8
check: 1+8 != 5 
check: 3+8 != 5

Add next one: 2
check: 1+2 != 5
check: 3+2 == 5

Bingo! Our elements are : 1st and 4th.

- sergey.a.kabanov January 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Use a Hashmap:

while scan through the numbers, for every number (y) that is smaller than the given number (intG), check if the hashmap has the key value already, if yes, the first number is found. If not, insert into the hashmap: key = intG - y, value = y.

- Anonymous January 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Are you serious? For a stream with numbers of infinite size, you will require a hashtable with infinite entries. Good luck with that.

- Anonymous January 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

we can construct hashmap and size would be equal to given sum. it would be some finite number.if number are +ve then it would be easy.

- bharat January 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Brute force approach:
int n1 = head.data
int n2 = head.next.data
head = head.next.next;
while(head!=null){
   if(n1+n2 == givenSum){
      a[0] = n1;
      a[1] = n2;
      return a;
    }
    else{
      head = head.next;
      n1 = head.data;
      n2 = head.next.data;
    }
}

- AmzFAILFacebookFailMSFTFail January 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This will find the numbers only if they are next to each other in the list.

if list is 1->2->3->4 and n=4 it will not work.

- Anonymous January 11, 2012 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More