## Bloomberg LP Interview Question for Financial Software Developers

Country: United States
Interview Type: Phone Interview

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

If we need to find one missing value from N successive numbers we can XOR all values that we have with each other and with numbers from 0 to N. And because:
a xor a = 0
a xor 0 = a
(a xor b) xor b = a
as a result we will have our missing number.
It has the same time complexity as the solution with finding sum but we won't get overflow.

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

This is a nice solution. To make it clearer, we can say that we XOR the index of each slot with the value in the slot of the array. Finally we XOR with 'n', the size of the array. The result would be the missing one.

Comment hidden because of low score. Click to expand.
0

In my profiling experiments I have found XOR and Integer taking same time.
A comparison of N(N+1)/2 and Sum(arr) will have total of N+1 operations.
N inividual XORs and then again XORing them N-1 times making total operations as 2*N-1.

Can you please point why doing XOR would be preferable?

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

To prevent overflow of integer if we have big numbers or too many numbers.

Comment hidden because of low score. Click to expand.
0

this is not so clear ......
please can any one elaborate the concept

Comment hidden because of low score. Click to expand.
0

Could you please provide the code

Comment hidden because of low score. Click to expand.
0

@J
Your reasoning is perfectly valid. Thanks

Comment hidden because of low score. Click to expand.
0

really good.

Comment hidden because of low score. Click to expand.
0
{{{ ((((((0 ^ 1) ^ 2) ^ 3) ^ 4) ^ 5) ^ 6) ^ 8 == 15 }} Why not 7?
Comment hidden because of low score. Click to expand.
0

``((((((0 ^ 1) ^ 2) ^ 3) ^ 4) ^ 5) ^ 6) ^ 8  == 15``

not 7, why?

Comment hidden because of low score. Click to expand.
0

NVM. You have to make the pairs first and then find the one that is missing

Comment hidden because of low score. Click to expand.
0

One condition for the above to work is that the value stored instead of the missing variable should be 0.

Comment hidden because of low score. Click to expand.
3
of 5 vote

Keep a variable sum and loop through the array - summing up all the elements: sum = sum + a[i] .

Missing number = (n*(n+1)/2) - sum

O(n) complexity .

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

in your method, how to avoid overflow?

Comment hidden because of low score. Click to expand.
0

Assert that N is at most the square root of the maximum integer we can store, I guess.

Comment hidden because of low score. Click to expand.
0

The answer will still be correct even if an overflow happens, since the integer values will simply wrap around and keep counting. In fact, even if (n*(n+1)/2) is a negative value because of overflow and sum is a large postive value, the subtraction of (n*(n+1)/2) - sum will "re-underflow" to the correct answer.

Comment hidden because of low score. Click to expand.
0

@bob: Depends on langauge/compiler. Overflows are undefined behavior in C++ for instance.

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

Let us say X = XOR sum of all elements from 0 to N
Y = XOR sum of given elements ( 0 to N , one number missed )

X xor Y vallue is the missed number.

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

In Python:

``````def findMissing(a,N):
sum=0
for x in a:
sum+=x

print (N*(N+1)/2)-sum``````

Test:

``findMissing([0,1,4,2],4)``

``3``

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

sum up all the given no and substract the total sum
no = n*(n+1)/2 - sum(array)

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

Every one has given solution , thinking in mind that array startes from 1 to N, but what happens if array start from may be 2,3,...

Comment hidden because of low score. Click to expand.
0

Not 1 to N but 0 to N. And the assumption is given in the question.

``How to find a missing value in an size N unsorted array (value from 0 to N but missing one of them).``

Comment hidden because of low score. Click to expand.
0

Nothing will change.
Both solutions (with XOR and sum of the arithmetic progression) will work.
But for sum-solution you will need to use a little bit different formula: N*(a1 + aN)/2
And for xor-solution you will need to xor with all numbers from a1 to aN (not from 0 to N).

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

``````int Missing_Term(int arr[], int num)
{
int total;
total = (n+1)*(n+2)/2;
for( int i = 0; i < num; i ++ )
{
total - = arr[i];
}
}``````

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

I am not a CS major. Can someone please tell me how this code is compared with others in terms of performace?

``````int temp[N+1];
for (int i=0;i<N;i++)
{
temp[arr[i]]=1;
}
While (temp[i]) {i--;}

return i;``````

Comment hidden because of low score. Click to expand.
0

Your solution has linear time complexity.
But it also has linear space complexity.

P.S. I don't think your code could be compiled because in case of non-constant N you need to allocate memory for your temp array dynamically. And if you allocate additional memory dynamically it will affect performance of your solution.

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

A sequel to this question is what if two numbers are missing ???

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

Given Array = A[n]
Auxialiary Array = B[n+1]
for(i=0;i<n+1;i++)
B[i]= -5; // Initialize B[n+1] with a negative numbers
for(i=0;i<n;i++)
{B[A[i]]= A[i];}
for(i=0;i<n+1;i++)
{if(B[i] == -5)
{return i; // i is the missing element
}
}

Complexity = O(n)

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

``````public class findMissingElement {

public static void main(String args[]){
// For sample input 0,5,2,3,1,4,6,10,8,9 where N is 10
int[] iparr = {0,5,2,3,1,4,6,10,8,9};
int sum = 0,s=0,max =0;
for (int i =0;i<iparr.length;i++)
if (iparr[i] >max)
max = iparr[i];
for (int i =0;i<=max;i++)
sum = sum + i;
for (int i =0;i<iparr.length;i++)
s = s + iparr[i];
System.out.println("Missing Element "+(sum-s));
}``````

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

Binary search. Suppose we have a list:

[1, 2, 3, 5, 6, 7, 8, 9] so length = 8

Divide the list into 2: [1, 2, 3, 5] and [6, 7, 8, 9], we know that the length is 8/2 = 4.

We can check to see which list is missing a number by checking 'first element' + length - 1 == 'last element', i.e. 6 + 4 - 1 = 9 but 1 + 4 - 1 == 4 != 5, so the left list contains the missing number.

Rinse an repeat, identify [3, 5] as having the missing element. Missing number is the average of the two.

Complexity: O(log n) (I think..)

Comment hidden because of low score. Click to expand.
0

The problem states that the array is unsorted, but this seems like a reasonable approach for the sorted case.

Comment hidden because of low score. Click to expand.
0

Oops, I missed that. Indeed.

Comment hidden because of low score. Click to expand.
0

Also array size is "N" and Numbers in array should not be higher than "N".

Comment hidden because of low score. Click to expand.
0

My aim was not to provide a totally sound solution, simply to do 95% of the work. The finer details are boring, it's obvious how my suggestion needs to be altered to make it fit that requirement.

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.

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