Bloomberg LP Interview Question for Software Engineer Interns


Country: England
Interview Type: Phone Interview




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

c++, implementation, O(n)

int findMissingNumber(vector<int>& arr, int N) {
    int i;

    i = N;
    while (i--) {
        N ^= i ^ arr[i];
    }

    return N;
}

- kyduke October 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Yes it is working. Could you please explain what is happening? thanks.

- SIVA R October 29, 2015 | Flag
Comment hidden because of low score. Click to expand.
3
of 3 votes

Same number do XOR twice, result is 0.
Items are 0~N and index are 0~N.
Only missing number do XOR once.

Then result is missing number.

- kyduke October 29, 2015 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

We can calculate sum of arithmetic progression (from 0 to N) and subtract actual sum of input array. Difference is the missing number.

int expectedSum = N * (0 + N) / 2;
int actualSum = sum(array); // trivial
return expectedSum - actualSum;

- Iuri Sitinschi October 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 votes

For the above solution,I think you need to use BigInt library if you want to multiply.

- revanthpobala October 29, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

You don't have to calculate the actualSum. Just keep subtracting array elements one by one from expectedSum. This way overflow of int can be avoided

- sk November 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

EDIT: A = [0,1,2,3,4,9,5,7,6]

- nonameno October 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int findMissingNumber(int[] arr,int n){

        int result = n;
        
        for (int i = 0 ;i<arr.length ; i++) result^=arr[i]^--n;
        
        return result;

}

- goku0609 October 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//Implementation in java
public class MissingNumber{
int missingNumber;
int [] arr;
int n;

for (int i = 0; i < arr.length; i = i+1){
missingNumber = result % (arr[i] = arr[i] % (n-1));
System.out.println("The missing number is" +missingNumber);


}
}

- Navjot Virk October 31, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What is "n" here ?

- YoYo January 22, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

def print_missing(l):
    sumn = (1 + l[len(l)-1]) * l[len(l)-1] * (0.5)
    x  = 0
    for i in l:
        x += i
    return (sumn - x)

z = print_missing([0, 1, 2, 3, 4, 5, 7])
print(int(z))

- anish531213 November 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Everyone might be answering the question but no one has actually considered the magnitude of N being really large? Any suggestion to get it to at least O(logn)?

- Anonymous November 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It's impossible to get it to less than O(n) because we need to look at every element at least once.

If we were to ignore an element, then now you don't see 2 out of N elements, so how do you know which one is missing?

- Carlos November 15, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

The question is not clear:
- Is the length of the array = N?
- [0, 1,3,4,9, 5,7,6] - 2 is also missing! What is the value of N?
- Can the numbers we repeated?

The answer will vary based on the question.

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

I find it easy enough:

a = [1,2,3,4,6,7,8,9]
for n in range(min(a),max(a)):
    if a.count(n) == 0:
        print n, 'is missing'

- Enol January 30, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

XOR ing a number with itself gives 0. If we XOR all the nos. from 0 to N, and also XOR the result with the elements in the array, the duplicate values are nullified, only the one missing remains-

Code -

public static void main(String[] args){
    int[] arr = {0, 1, 3, 4, 9, 5, 7, 6, 2};
   	int N = 9;
    
    System.out.println(missingnumber(arr, N));
    
  }
  
  
  public static int missingnumber(int[] arr, int N){
  	
    int res = 0;
    int n = arr.length;
    
    for(int i = 0; i <= N; i++)
      res = res^i;
    
    for(int i = 0; i < n; i++)
      res = res^arr[i];
    
    return res;
    
  }

- sudip.innovates October 10, 2017 | 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