Bloomberg LP Interview Question for Software Engineer / Developers






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

Time O(n), space(1).

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

- coolbz February 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

- souravghosh.btbg March 10, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is an excellent solution. A little explanation would have made it even better. (I think/know USC is a good school)

- rayhan August 12, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

add 999,000 numbers and subtract that from sum_{1000,000) i

- phas October 28, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I meant, 999,999 numbers.

- phas October 28, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

missing numbers are more than one or just one?

- blueskin.neo November 20, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}

- Ram December 01, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@phas,
i think your method would work only if 1 number were missing..which is not the case here..

- veep December 13, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Anonymous December 13, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You're assuming they're sorted.

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

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.

- vin2502 December 13, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bubble sort + vin2502's
no need extra space

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

Although the solution bubble sort + vin2502 loop works and fulfills the condition imposed in the question, there is no harm in insisting on a more efficient sort like quick sort. For a million numbers, quick sort should be much much more efficient than bubble sort.

- Anonymous August 12, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

create new hastable.
populate with values from 1 to 1M -> O(N)
check condition hashtable.containsValue -> O(N)

- unradis January 16, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous August 12, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

XOR 1 - 1M first,
then XOR the array again,

The one left it the missing number

- Anonymous February 24, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Amazing solution.

- Anonymous July 25, 2011 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

What happens if multiple numbers are missing?

- Anonymous August 12, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use a bitmap of million million bits and. Traverse through the array and set the corresponding bit in the bit map. Traverse the but map. The bits with 0 value give the missing numbers.

- Anonymous March 10, 2011 | Flag Reply


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