Bloomberg LP Interview Question
Software Engineer InternsCountry: United States
Interview Type: In-Person
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));
}
}
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)
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
?
I am assuming input is SET and SET contains unique elements.
Nitin : You are correct Integer Overflow condition can come.
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
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.
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
?
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};
}
/*
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();
}
}
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;
}
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));
}
}
}
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);
}
}
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);
}
}
}
Key : SET contains unique elements.
- Krishna K Tiwari March 20, 2013Case : 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.