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.

- joe kidd September 26, 2013 | Flag Reply
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.

- mingjun September 26, 2013 | Flag Reply
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.

- Anonymous September 27, 2013 | Flag Reply
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.

- Anonymous September 27, 2013 | Flag Reply
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.

- Anonymous September 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Could your provide some code please?

- Anonymous October 02, 2013 | Flag Reply
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[0];

            //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;
        }

- Andy October 03, 2013 | Flag Reply
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.

- Anonymous October 13, 2013 | Flag
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].

- Anshul October 03, 2013 | Flag Reply
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[0]; // 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;
}

- Iuri Covalisin October 31, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- maverick March 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- maverick March 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- maverick March 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- maverick March 16, 2014 | Flag Reply
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;
 }

- wjian@yahoo-inc.com September 21, 2014 | Flag Reply
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;

- Anonymous November 16, 2014 | Flag Reply
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 .

- Anonymous November 16, 2014 | Flag Reply
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;
    }
  }
}

- ZY May 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Kaushik Lele October 30, 2016 | Flag Reply


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