You have a stream of bytes from which you can read one byte at a time. You only have enough space to store one byte. After processing those bytes, you have to return a random byte. Note: The probability of picking any one of those bytes should be equal.
When we get the first byte, it is simple. There is only one so we store it. When we get the second one, it has 1/2 probability of being picked and the one we have stored has a 1/2 probability of being picked (we can use any programming language’s built-in random function). After picking one, we replace the current stored byte with the one we picked. Now it gets interesting. When we get the third one, it has 1/3 probability of being picked and the one we have stored has a 2/3 probability of being picked. We pick one of the two bytes based on this probability. We can keep doing this forever.
When we get the nth byte, it has a 1/n probability of being picked and the byte we have stored has (n-1)/n probability of being picked.
The probability of a car passing a certain intersection in a 20 minute windows is 0.9. What is the probability of a car passing the intersection in a 5 minute window? (Assuming a constant probability throughout)
Probability of a car passing in a 20 minute window = 1 – (probability of no car passing in a 20 minute window)
Probability of a car passing in a 20 minute window = 1 – (1 – probability of a car passing in a 5 minute window)^4
0.9 = 1 – (1 – x)^4
(1 – x)^4 = 0.1
1 – x = 10^(-0.25)
x = 1 – 10^(-0.25) = 0.4377
Probability of a car passing in a 20 minute window = 1 – (1 – probability of a car passing in a 5 minute window)^4
0.9 = 1 – (1 – x)^4
(1 – x)^4 = 0.1
1 – x = 10^(-0.25)
x = 1 – 10^(-0.25) = 0.4377
How would you cut a rectangular cake into two equal pieces when a rectangular piece has already been cut out of it? The cut piece can be of any size and orientation. You are only allowed to make one straight cut
What if we make a straight cut such that it passes through the center of both the rectangles? Since the cut halves both the rectangles, the resulting two pieces are guaranteed to have equal area. Each piece has an area equal to half the original cake minus half the area of the missing rectangular piece.
Two old friends, Jack and Bill, meet after a long time.
Jack: Hey, how are you man?
Bill: Not bad, got married and I have three kids now.
Jack: That’s awesome. How old are they?
Bill: The product of their ages is 72 and the sum of their ages is the same as your birth date.
Jack: Cool… But I still don’t know.
Bill: My eldest kid just started taking piano lessons.
Jack: Oh now I get it.
Bill: Not bad, got married and I have three kids now.
Jack: That’s awesome. How old are they?
Bill: The product of their ages is 72 and the sum of their ages is the same as your birth date.
Jack: Cool… But I still don’t know.
Bill: My eldest kid just started taking piano lessons.
Jack: Oh now I get it.
How old are Bill’s kids?
The product of their ages is 72. So what are the possible choices?
2, 2, 18 – sum(2, 2, 18) = 22
2, 4, 9 – sum(2, 4, 9) = 15
2, 6, 6 – sum(2, 6, 6) = 14
2, 3, 12 – sum(2, 3, 12) = 17
3, 4, 6 – sum(3, 4, 6) = 13
3, 3, 8 – sum(3, 3, 8 ) = 14
1, 8, 9 – sum(1,8,9) = 18
1, 3, 24 – sum(1, 3, 24) = 28
1, 4, 18 – sum(1, 4, 18) = 23
1, 2, 36 – sum(1, 2, 36) = 39
1, 6, 12 – sum(1, 6, 12) = 19
2, 4, 9 – sum(2, 4, 9) = 15
2, 6, 6 – sum(2, 6, 6) = 14
2, 3, 12 – sum(2, 3, 12) = 17
3, 4, 6 – sum(3, 4, 6) = 13
3, 3, 8 – sum(3, 3, 8 ) = 14
1, 8, 9 – sum(1,8,9) = 18
1, 3, 24 – sum(1, 3, 24) = 28
1, 4, 18 – sum(1, 4, 18) = 23
1, 2, 36 – sum(1, 2, 36) = 39
1, 6, 12 – sum(1, 6, 12) = 19
The sum of their ages is the same as your birth date. That could be anything from 1 to 31 but the fact that Jack was unable to find out the ages, it means there are two or more combinations with the same sum. From the choices above, only two of them are possible now.
2, 6, 6 – sum(2, 6, 6) = 14
3, 3, 8 – sum(3, 3, 8 ) = 14
3, 3, 8 – sum(3, 3, 8 ) = 14
Since the eldest kid is taking piano lessons, we can eliminate combination 1 since there are two eldest ones. The answer is 3, 3 and 8.
Read full article from 10 Google Interview Puzzles » My Tech Interviews