Microsoft Interview Question
Software Engineer / DevelopersTeam: Global Foundation Services
Country: United States
Interview Type: In-Person
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.
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 .
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).
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.
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.
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).
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;
}
}
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;
}
}
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;
}
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.
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.
Are you serious? For a stream with numbers of infinite size, you will require a hashtable with infinite entries. Good luck with that.
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;
}
}
Let the given number is N.
- Thunder2020 January 09, 2012Pick 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.