## Highbridge Capital Interview Question for Java Developers

Country: United States
Interview Type: In-Person

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

When one number is missing:
find the sum of numbers from 1 to n using the formula... n(n+1)/2. Then the difference between the actual sum and the calculated sum is the missing number

when two numbers are missing:
like above, get equation for a+b=x -------- equation 1
now sum the square the numbers using n(n+1)(2n+1)/6 and then calculate actual value for numbers from 1 to n. Now the difference is in the form of equation a^2 + b ^2 = y ------ equation 2

From these two equations, you can solve for a and b.

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

nice method , when 2 numbers are missing.
But when n is large, (n*(n+1)/2) will be large and will cause integer overflow. So, we can solve the first case by using the XOR method. Similarly, is there a method to solve for the second case?

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

Please clarify which XOR method u referring to.

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

DreamCoder's solu for find 1 missing number is perfect.
For multiple missing numbers, you can use counting sort,which takes O(N) spaces.

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

@rkt, is there a method to solve for the second case?
we can solve using xor.

1. xor of all the elements array and natural number 1 to n+1
Lets say we will get value 1(bit notation 0001)
2. divide the whole elements(array and natural numbers 1 to n+1) into two groups based on 1st bit(since resulting number in step1 has 1st bit 1).
one group of numbers which has all the 1st bits is 1
second group of numbers which has all the 1st bits is 0.
3. apply xor on first group you will get one number
4. apply xor on second group you will get second number.

TC. - O(n+n+n) = O(n)
SC - O(1)

-Devendar

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

Yes, we can use count sort to find multiple missing numbers from 1 to n or 1 to n+1. for example we have number n = 10 and series 2,5,4,3,1,7,9,10 then if we count sort based or our knowledge that biggest number is 10 then we will get 1,2,3,4,5,7,9,10 hence missing numbers while traversing again will be 6 and 8. This way you can find multiple missing numbers as well instead of solving equations which for 1 missing number is fine.
To know how counting sort works in O(N) time you can watch this video

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

@Anonymous: I understood the count sorting algo but if you observe carefully, the algo has a bug while displaying the array content that might lead to crash as display goes beyond the array size (until 1024)if size is just 16 in that case!!! Instead I would suggest to use len itself for the outer for loop to counter this bug...

Please correct if i am wrong.
Thanks.

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

public static int find_miss_one_number(int[] test,int form,int to){
int result1=0;
for(int i=0;i!=test.length;i++){
result1+=test[i];
}
int result2=0;
for(int i=form;i!=to+1;i++){
result2+=i;
}
return result2-result1;
}
public static int[] find_miss_two_numbers(int[] test,int form,int to){
int result1=0;
int result2=0;
for(int i=0;i!=test.length;i++){
result1+=test[i];
result2+=test[i]*test[i];

}
int result3=0;
int result4=0;
for(int i=form;i!=to+1;i++){
result3+=i;
result4+=i*i;
}
int sub1=result3-result1;
int sub2=result4-result2;

//x+y=sub1;
//x^2+y^2=sub2;

int a=2;
int b=sub1*(-2);
int c=sub1*sub1-sub2;

int[] result=new int;
result=(b*(-1)-((int)Math.sqrt(b*b-4*a*c)))/(2*a);
result=(b*(-1)+((int)Math.sqrt(b*b-4*a*c)))/(2*a);

return result;
}

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

we can subtract previous from current
if value>1 break;
you will get the value directly
complexity=O(n)

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

This Question is so easy, the running time is O(nlogn). If you can't see the answer immediately, you are not ready for an interview. Thanks.

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.