Bloomberg LP Interview Question
Software Engineer / Developers// souravgh@usc.edu
// Wed 9 Mar 2011 2040
#include <stdio.h>
int main (void) {
int arr[50];
int indexInt = 0;
int locInt = 0;
for (indexInt = 0; indexInt < 50; indexInt++) {
arr[indexInt] = indexInt + 1;
}
arr[5 - 1] = 2;
arr[10 - 1] = 12;
arr[23 - 1] = 9;
arr[49 - 1] = 9;
for (indexInt = 0; indexInt < 50; indexInt++) {
locInt = arr[indexInt] < 1 ? -(arr[indexInt] + 1) : (arr[indexInt] - 1);
arr[locInt] = arr[locInt] > 0 ? -arr[locInt] : arr[locInt]; // Make it a -ve.
}
for (indexInt = 0; indexInt < 50; indexInt++) {
if (arr[indexInt] > 0) {
fprintf (stdout, "\t%d", indexInt + 1);
}
}
fprintf (stdout, "\n");
return 0;
}
O (n) time O (1) space. Of course this assumes that the 1 mil no.s are organized as an array similar to the 50 element array above, and that getting the value and setting the value at a particular index is O (1).
If sorted list, binary search. Takes make time to populate than to find the actual number.
=======================================
#include <iostream>
#include <vector>
using namespace std;
const unsigned long largestNum = 100000007;
unsigned long nstart=1;
unsigned long nend=largestNum;
unsigned long miss= 999999;
unsigned long middle = (nend-nstart)/2;
int main()
{
cout << "Start Populating. ...." << endl;
vector<unsigned long> vec;
// Populating 0 at first location so that
// don't have to bother about offset.
vec.push_back(0);
for( unsigned long j= nstart; j <= largestNum; ++j)
{
if( j == miss)
continue;
vec.push_back(j);
}
cout << "Start finding .... " << endl;
int count = 0;
while( (nend - nstart) > 1)
{
cout << "Count = " << ++count << endl;
if(middle == vec[middle])
{
nstart = middle;
middle = middle + (nend - nstart ) /2 ;
}
else
{
nend = middle;
middle = middle - (nend - nstart) /2 ;
}
}
if( middle == vec[middle])
{
cout << "Missing number is " << vec[middle]+1 << endl;
}
else
{
cout << "missing number is " << vec[middle]-1 << endl;
}
}
if all the numbers are stored in an array we can do this,
i=0;
if(arr[i+1]-arr[i] >1 )
{
//means some numbers are missing..
n = arr[i+1]-arr[i];
//so the missing numbers are arr[i]+1,arr[i]+2 ...upto n-1
}
ex. 102 - 95 =7. this means 6 numbers are missing..
missing numbers are 95+1,95+2...upto 95+6
so we do this for every 2 numbers starting from 1.
Space complexity is minimal since we r doin this using the array which is already present and not using any extras DS.
if all the numbers are stored in an array we can do this,
i=0;
if(arr[i+1]-arr[i] >1 )
{
//means some numbers are missing..
n = arr[i+1]-arr[i];
//so the missing numbers are arr[i]+1,arr[i]+2 ...upto n-1
}
ex. 102 - 95 =7. this means 6 numbers are missing..
missing numbers are 95+1,95+2...upto 95+6
so we do this for every 2 numbers starting from 1.
Space complexity is minimal since we r doin this using the array which is already present and not using any extras DS.
create new hastable.
populate with values from 1 to 1M -> O(N)
check condition hashtable.containsValue -> O(N)
You need to find a solution with **least possible space (complexity)**. A hash table will obviously need a storage of 1 million numbers (actually, a hash table will probably require 2 or 3 times more space). Hence, your solution probably isn't space efficient. Also, a simple for loop to find the missing number as described by vin2502 is much more efficient than using hashtable.containsValue. Because, first, it involves a function call and secondly, internally that function performs some operations (although constant), e.g., compute a hash of key (in this case an integer).
Time O(n), space(1).
- coolbz February 25, 2013Assume numbers are stored in an array of size 1M, loop through:
if a[i] == i or 0, move next, otherwise (if a[i] == a[a[i]], set a[i] =0 and move next, otherwise swap a[i] with a[a[i]])
By the end, every 0 positions are missing number.