## Google Interview Question for Software Engineer / Developers

Country: United States
Interview Type: In-Person

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

Check Reservoir Sampling on wiki please. In this case k = 1.

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

simulate an array shuffle, with a virtual array(only save the length, and the 1st element).
When we scan to index n, the 1st element of the virtual array, would be any number in x0...xn with probability 1/n

the shuffle function works like,
when scan to xi, there are i+1 choices to insert it to the virtual array. randomInt(i+1)
if random number is 0, replace the 1st element.
else do nothing.

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

The reference to "an infinite stream of ..." implies that we cannot simply consider a uniform distribution as in the case of discrete random variables. In other words, we cannot assume 1/n as the probability assigned to each element. One thing we can do, however, is to check if the lower and the upper bound of these numbers are available. Then, we can use something like:

``(b-a)rnd() + a``

to find the next probability. Such a boundaries can be found on-the-fly i.e., as the numbers are arriving we can update the previous bounds, given the recently received value.

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

``````Divide the streams into partitions and each partition contains set of numbers.
Now, genRand() to the pick the partition and once the partition is picked, then again do genRand() now to pick the number.
Now, the prob (number) = 1/(n^2) .

We can even extend to more complex (distributed).
1. genRand() to pick a node
2. Each node has many partitions and now genRand() to pick a partition within a node
3. Now, once the partition is pick , genRand() to pick the number,
In this, prob(num) = 1/(SPN) where S = # of nodes , P = # of partitions with each node (assume same for all nodes) and N = # of elements in each partitions.``````

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

Divide the streams into partitions and each partition contains set of numbers.
Now, genRand() to the pick the partition and once the partition is picked, then again do genRand() now to pick the number.
Now, the prob (number) = 1/(n^2) .

We can even extend to more complex (distributed).
1. genRand() to pick a node
2. Each node has many partitions and now genRand() to pick a partition within a node
3. Now, once the partition is pick , genRand() to pick the number,
In this, prob(num) = 1/(SPN) where S = # of nodes , P = # of partitions with each node (assume same for all nodes) and N = # of elements in each partitions.

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

Could your provide some code please?

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

``````public int GetRandom()
{
var list = new List<int> { 5, 8, 9, 10, 12, 15, 20 };
var currentLocation = 0;
var randomNo = list;

//We don't count the list so it is as good an infinite stream
foreach (var item in list)
{
currentLocation += 1;
if (currentLocation == 1) continue;
//Return a no between 1 and the last item in the list. The probability for the new no to be picked get's less and less
//as we go through the list and all no has equal chance.
int newRandomLocation = new Random().Next(currentLocation) + 1;
randomNo = newRandomLocation == currentLocation ? item : randomNo;
}

return randomNo;
}``````

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

Could you explain your logic more? Confused about what is happening inside the loop.

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

Assuming that input is in form of an infinite array A.
Generate a random floating point number y between 0 and 1.
Let x = 1/y.
return A[x-1].

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

This is reservoir sampling where k == 0

``````int singleReservoirSampling(std::vector<int> &arr) {
int result = arr; // use single var instead of array as k == 0
for(int i = 1; i < arr.size(); ++i) {
int r = std::rand() % i;
if(r == 0) { // replacing r <= k with r == 0
result = arr[i]; // probability to be set is 1 to i
}
}
return result;
}``````

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

_//en.wikipedia.org/wiki/Reservoir_sampling

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

_//en.wikipedia.org/wiki/Reservoir_sampling

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

_//en.wikipedia.org/wiki/Reservoir_sampling

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

_//en.wikipedia.org/wiki/Reservoir_sampling

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

``````static int stream_sample(int* numbers)
{
int k = 0;
int selected = 0;
while (*numbers != 0)
{
++k;
if (rand() * k < 1)
{
selected = *numbers;
}
numbers++;
}
return selected;
}

static int stream_sample(int* numbers)
{
double cur = 1;
double selected = 0;
while (*numbers != 0)
{
double new_cur = rand();
if (new_cur < cur)
{
cur = new_cur;
selected = *numbers;
}
numbers++;
}
return selected;
}``````

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

``````while(next(element))
{
r = random(0,counter_value);
if(r == 0)
random = a[counter_value];
}
return random;``````

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

``````Analysis :

In the ith iteration we decide whether ith element should be the random element.
P(candidate = i) : 1/i

Probability that the ith element so chosen is the random element :
P(candidate=i)*P(it is never replaced)

In ith iteration : P(random element which is replaced) :  1/i
P(it is not replaced) : 1 - 1/i
P(pth element is random) :
P(chosen p) * P(never replaced random in p+1th iteration to final iteration )
= 1/p *  Product{i = p+1 to n} (1-i)/i   = 1/n .``````

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

``````int p = 0;
int count = 0;
public void read(int n){
count++;
if(count == 1){
p = n;
}else{
int index = random(1, count) // inclusive;
if(index == count){
p = n;
}
}
}``````

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

What probability are we talking about ? "Equal probability for each" means ??

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