Microsoft Interview Question Interns
Country: India
Interview Type: Phone Interview
Couple of issues to consider:
1. Your estimation of N is equal to the maximum value of the ball picked in K attempts. I am not sure if this is the optimal estimate in both the cases.
2. The probability calculations = P(ball with N value is picked in K attempts):
with replacement: P = [1-(1-1/N)^K]
without replacement: P = [K/N]
as K->N and for large N, P~(1-e^-1) ~ 0.632 (with replacement)
as K->N and for any N, P=1 (without replacement) as one would expect.
You take the maximum number from the picked ones, subtract 1, and divide by K = the average gap between elements.
Then simply add this gap to the found maximal one and that's your answer:
vector<int> a = {2,1,6,9,7,10};
int max = 0;
for (int x : a) {
if (max < x)
max = x;
}
cout << max + round((float)(max-1)/a.size()) << endl;
This looks wrong answer. Actually you dont have access to whole array based on which you are calculating max. You can consider question as following class
class Bag
{
private:
vector<int> Balls;
int size;
public:
Bag()
{
int size = random(); // generate some random integer
for(int i=0; i<size; i++)
Balls.push_back(i+1);
}
vector<int> GetKWithReplacement(int k)
{
vector<int> temp = new vector<int>(k);
for(int i =0; i<k ;i++)
{
int idx = random() % size;
temp.push_back(Balls[idx]);
}
return temp;
}
vector<int> GetKWithoutReplacement(int k)
{
vector<int> temp = new vector<int>(k);
int len = size;
for(int i =0; i<k ;i++)
{
int idx = random() % len;
temp.push_back(Balls[idx]);
Ball.removeat(idx);
len--;
}
return temp;
}
int ActualSize()
{
return size;
}
}
Now using above methods i.e. GetKWithoutReplacement() or GetKWithReplacement()
You have to calculate your guess which you can match with method ActualSize() from above class
I thought of taking the average of K picks then multiplying by 2 to get the total count estimate. My thought was this average would give a close approximation of the actual average. This average would be only half of the value we are looking for so multiplying by 2 will give us the total count
Code below:
public int getNumberOfBallsEtimate(int[] bag, int k){
//error checking here...
int val = 0;
for(int i = 0; i < k: i++){
val += getPickFromBag(bag);
}
int average = val/k; //is currently the aver
int countEstimate = average/2;
return countEstimate;
}
All, please give feed back on this approach
I still like my approach above but yours makes sense too!
A couple of notes:
- It won't work if you pick the same ball multiple times
- Change the average/2 to average*2 as you have it in your explanation ;)
That was the exactly the answer I gave (for the case where balls are picked without replacement)
(N+1)/2 ~ (a1+a2+.....ak)/k
Assume that we are going to declare N as the maximum value of the ball we see during the pick up times.
- monica_shankar May 21, 2015so we pick up k times and let the value of balls during the pick up be m1,m2,m3....mk
Without replacement:
The probability of drawing the N'ed value ball at first pick is 1/N
The probability of drawing the N'ed value ball at second pick is 1/(N-1)
The probability of drawing the N'ed value ball at third pick is 1/(N-2)
.... The probability of drawing the N'ed value ball at Kth pick is 1/(N-K)
As probability of one try does not affect the other, we use addition priciple
so with the value 1/N+1/(N-1).............1/(N-K) we can say that the maximum value of ball we pick would be the value N
With replacement:
The probability of picking the N'ed value ball at first try=1/N
The probability of picking the N'ed value ball at second try=1/N
.... The probability of picking the N'ed value ball at third try=1/N
so with probability of k/N, we can state that the maximum ball we pick would be the value N.
correct me if i am wrong somewhere, thanks!!!