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.

- J. March 29, 2013 | Flag Reply
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.

- teli.vaibhav March 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- Expressions March 29, 2013 | Flag
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.

- J. March 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- venky March 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Could you please provide the code

- Prashanth April 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@J
Your reasoning is perfectly valid. Thanks

- Expressions April 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

really good.

- Shivam Maharshi April 03, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes
{{{ ((((((0 ^ 1) ^ 2) ^ 3) ^ 4) ^ 5) ^ 6) ^ 8 == 15 }} Why not 7? - Anonymous November 13, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

not 7, why?

- Anonymous November 13, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous November 13, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Viraj Shah January 27, 2015 | Flag
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 .

- Engineer1111 March 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

in your method, how to avoid overflow?

- Anonymous March 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- jay March 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- bobthrollop April 21, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous June 28, 2014 | Flag
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.

- siva.sai.2020 March 29, 2013 | Flag Reply
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

- Expressions March 29, 2013 | Flag Reply
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)

- jai March 29, 2013 | Flag Reply
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,...

- Prashanth April 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Expressions April 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- J. April 25, 2013 | Flag
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];
		}
	return total;
}

- nueman fernandez May 09, 2013 | Flag Reply
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;

- Amir June 09, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- J. June 09, 2013 | Flag
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 ???

- balani.kunal June 09, 2013 | Flag Reply
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)

- Addy June 11, 2013 | Flag Reply
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));		
	}

- karpagaganesh March 07, 2014 | Flag Reply
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..)

- jay March 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- showell30@yahoo.com March 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Oops, I missed that. Indeed.

- jay March 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- karinca March 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- jay March 29, 2013 | Flag


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