## Bloomberg LP Interview Question for Software Engineer Interns

• 1
of 1 vote

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
4
of 6 vote

Key : SET contains unique elements.
Case : Only one number is missing.
Missing number = sum {1 to 10} - sum{set elements}
Case : Two numbers are missing assume them X and Y.
X+ Y = sum {1 to 10} - sum{set elements}
X*Y = mul (1 to 10 ) / mul (set elements)

Will post the code in few minutes.

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

``````package algo;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

public class MissingElement {

public static void TwoMissingElements(Set<Integer>numbers){
double x=0,y=0;
double p=0;
double q=1;
int sum1=55;
int sum2=0;
Iterator itr = numbers.iterator();
while(itr.hasNext()){
sum2 = sum2 + (int)itr.next();
}
p = sum1-sum2;

System.out.println("P "+p);
itr = numbers.iterator();
while(itr.hasNext()){
q = q * (int)itr.next();
}
q=3628800/q;
System.out.println("Q "+q);
double k = Math.pow(p, 2.0);
x = p + Math.pow(k-4*q, 0.5);
x=x/2;
y =p-x;
System.out.println("First Element :"+x+ "   Second Element :"+y);
}

public static int OneMissingElement(Set<Integer>numbers){
/*
* sum1 will represents sum of 1 to 10 that is fixed. n*(n+1)/2
* n=10 so sum1 = 55
*/
int sum1=55;
int sum2=0;
Iterator itr = numbers.iterator();
while(itr.hasNext()){
sum2 = sum2 + (int)itr.next();
}

return sum1-sum2;
}

public static void main(String args[]){
Set<Integer> numbers= new HashSet<Integer>();
for(int i=1;i<=10;i++){
if(i==4||i==6)
continue;
numbers.add(i);
}
MissingElement.TwoMissingElements(numbers);
//System.out.println(MissingElement.OneMissingElement(numbers));

}

}``````

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

In case of two missing numbers, you are taking product. I think it is wrong as it will produce wrong result if our final product goes out of bound of integers. (Integer Overflow)

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

Why are you assuming each number appears only once?

Why can't it be something like

``7,7,7,7,7,7,7,7,7,7,1,1,1,1,1,1,1,1,1,4,4,4,4,4,2,2,2,2,2,2,2``

?

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

I am assuming input is SET and SET contains unique elements.

Nitin : You are correct Integer Overflow condition can come.

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

Have fun solving trivial problems.

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

Use another boolean array[10] to record whether the number appear, when iterate the set(even has duplicate situtation), Then we can iterate the boolean array, if array[index] is false means that number does not in the set

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

Using the sum of the squares of the numbers instead of their product leads to solving a quadratic equation as well. It would be better for bigger arrays, since it does not grow as fast as the product, and there is less likelihood of the overflow.

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

For the First problem
Sum of { 1,2,.....,10} = 55
Add all the number in array and subtract it from 55 you will get the missing Number.

For the Second problem
Let the Two value a & b are missing
Int temp = product of all number in that array
a*b = 10 ! / temp
now you can easily guess the product of two number.

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

Why are the solutions (except Andre's) assuming each number appears only once (or missing numbers are filled so that there are exactly 10 numbers)?

Why can't it be something like

``7,7,7,7,7,7,7,7,7,7,1,1,1,1,1,1,1,1,1,4,4,4,4,4,2,2,2,2,2,2,2``

?

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

The definition of an unordered set: Unordered sets are containers that store unique elements in no particular order, and which allow for fast retrieval of individual elements based on their value.

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

Here's what I came up with before looking up the mathematical direction to solve this problem:

This solution isn't perfect as it requires a sanity check when doing the final XOR checks. But unordered set lookup has a constant average time complexity on average.
C++11 Solution:

``````pair<int, int> findMissingTwo(const unordered_set<int> &numbers)
{
/*
Note:
1) XOR all the elements, let the result of XOR be X1.
2) XOR all numbers from 1 to n, let XOR be X2.
3) XOR of X1 and X2 gives the missing number.
*/
auto it = numbers.begin();

int n = 1;        // Keep track of n.
int t1 = *it;     // Running Total.
int x1 = *(it++); // XOR all elements.
int x2 = n++;     // XOR 1 to n.
int missing = 0;  // Total missing

while (it != numbers.end())
{
t1 += *it;
x1 ^= *(it++);
x2 ^= n++;
}
// Two numbers missing from set, XOR with x2.
x2 ^= n++;
x2 ^= n;

// Sum of missing values = Known total - running total.
// Note: We do have a potential for overflow here.
missing = (n * (n + 1) / 2) - t1;

// XOR from 1 to N and see if X1^X2 is the missing number.
for (int cur_test = 1; cur_test <= n; cur_test++)
{
int x1_t = x1^cur_test;
int needed_value = missing - cur_test;
// if value isn't larger than n
// and value isn't itself
// and XOR of X1 and X2 gives the missing number
if (
needed_value <= n &&
needed_value != cur_test &&
needed_value == ((x1_t)^x2)
)
// Way to eleminate check?  Note, unordered_set lookup is very quick.
if (numbers.count(cur_test) || numbers.count(needed_value))
cout << "Bad Value Guessed (" << cur_test << "," << needed_value << ") Keep Looking..." << endl;
else
return {cur_test, (needed_value)};
}
// This should not hit, but need to return something.
return {-1,-1};
}``````

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

If you want the mathematical direction search for "Muthukrishnan Data Stream Algorithms" and look at puzzle 1.1.

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

``````/*
Question ID: 16171686

Given an unsorted set of numbers from 1 to 10 with one number missing .
How to find the missing number in the set without sorting.
How to find if two numbers are missing in the set?

Time Complexity: Linear -> O(n)
*/

public class sol16171686{

static int length;
static int[] a;
static int[] b = new int[10];

public static void traverse(){
for(int i = 0; i < length; i ++){
b[a[i] - 1] = a[i];
}
}

public static void check(){
for(int i = 0; i < 10; i ++){
if(b[i] == 0){
System.out.println("Missing Num: " + (i + 1));
}
}
}

public static void main(String[] args){
length = args.length;
a = new int[length];
for(int i = 0; i < length; i ++){
a[i] = Integer.parseInt(args[i]);
}
traverse();
check();
}
}``````

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

This is interesting, but I am wondering if the condition of not sorting the numbers is broken here. Certainly, what the traverse() is doing is a kind of sorting.

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

``````public static int[] missingNumbersFromSetBetween1And10(int[] setOfNumbers) {
int[] numbersBetween1And10 = new int[10];

int indexPosition;
for (int i = 0; i < setOfNumbers.length; i++) {
indexPosition = setOfNumbers[i] - 1;
numbersBetween1And10[indexPosition] = numbersBetween1And10[indexPosition] + 1;
}

int numberOfMissingItems = 0;
for (int i = 0; i < numbersBetween1And10.length; i++) {
if (numbersBetween1And10[i] == 0) {
numberOfMissingItems++;
}
}

int[] result = new int[numberOfMissingItems];
int resultPositon = 0;
for (int i = 0; i < numbersBetween1And10.length; i++) {
if (numbersBetween1And10[i] == 0) {
result[resultPositon] = i + 1;
resultPositon++;
}
}

return result;
}``````

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

I think this is the simplest way to get on the spot during an interview. for missing two elements.

``````#include <stdio.h>
int main ()
{
int a[] = {1,2,2,2,2,2,2,2,5,5,5,5,5,5,5};
int b[5] = {0,0,0,0,0};
int i = 0;
int j = 0;
for ( i = 0 ; i < (sizeof(a)/sizeof(int)); i++)
{
b[a[i] - 1] = b[a[i] -1] + 1;
}

for (i = 0; i < 5; i++)
{
if (b[i] == 0)
{
printf(" Missing : %d %d",b[i], (i+1));
}
}``````

}

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

yes it is :)
and will work for all i think. only size of array b will grow

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

The definition of an unordered set: Unordered sets are containers that store unique elements in no particular order, and which allow for fast retrieval of individual elements based on their value.

Key to the question is the values must be unique.

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

import java.util.*;
public class Missing_number {
public static void main(String args[])
{
int[] n=new int[9];
int sum=0,dif=0;
Scanner sc=new Scanner(System.in);
System.out.println("Enter the 9 elements:");
for(int i=0;i<9;i++)
n[i]=sc.nextInt();
for(int i=0;i<9;i++)
{
sum=sum+n[i];
}
dif=55-sum;
System.out.println("missing number is: "+dif);
}
}

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

``````public class findMissingElementV1 {

public static void main(String args[]) {
int[] a ={1,2,3,6};
int mainSum=0,i=0,sum=0;
for(i=0;i<7;i++){
mainSum += i;
}
for(i=0;i<a.length;i++){
sum =sum+ a[i];
}
int missingelement = mainSum-sum;
System.out.println(missingelement);
if(missingelement < 6){
System.out.println("Missing Element" +missingelement);
}
else{
int x=0,y=0,missProd=0;
mainSum =1;sum =1;
for(i=1;i<7;i++){
mainSum *= i;
}
for(i=1;i<a.length;i++){
sum =sum * a[i];
}
missProd = mainSum/sum;

System.out.println(missProd);

x = (int) (missingelement + Math.sqrt((missingelement*missingelement)-4*missProd));
x = x/2;
y = missingelement - x;
System.out.println("Missing Element "+x);
System.out.println("Missing Element "+y);
}
}

}``````

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