Google Interview Question
Software EngineersCountry: United States
Interview Type: In-Person
@sheva: it's correct, assume areas is one for all
- Probability to pick 1st is 1
- Next iteration, probability to pick 2nd is 0.5, so 0.5 for 1st and 0.5 for 2nd. 1st and 2nd have same probability (uniform)
- Next iteration, probability to pick 3rd is 1/3, so 1st and 2nd together is 2/3, 3 rd is 1/3, still uniform
...
it's an elegant algorithm for such cases, it's a similar one that is used when shuffling a deck of cards
@sheva
It is correct what you wrote about the probability of picking one of the rectangles. However, they are the probabilities "at the time" that you pick that specific rectangle. What we have to calculate are the probabilities of each rectangle being selected after iterating all rectangles.
For example, suppose the Rectangle0 has been selected. Then the rest of rectangles must not be selected (otherwise, variable 'selected' will be overwritten). So the prob. of rect0 being selected is as follows:
(A0 / A0) * (1 - A1 / (A0+A1)) * .... * (1 - A(n-1) / (A0 + A1 + ... + A(n-1))
= (A0 / (A0 + A1 + ... + A(n-1))
which is uniform prob. over all rectangles.
+) I believe it's an extension of reservoir sampling
I think the answer is correct, all rectangles are non overlapped that means that if you choose uniformly between all the rectangles you are not choosing uniformly between the all the possible points. For example what happens if the first rectangle is the smallest one but you choose uniformly between all the rectangles? The points of this rectangle will appear repeated more often as there a less available and the choosing frequency is the same as for the rest of the rectangles. I guess it is a matter of how you interpret the question but the given answer is the most complex one.
Also Java is not my most used language so I can be mistaken, please correct me if that is the case :). The probabilities are like this isn't??
Probability of rectangle 0 is: 1 - prob of choosing r1 - .... - prob of choosing rn
Probability of rectangle 1 is: area1 / (area0 + area1) - prob of choosing r2 - ... - prob of choosing rn
Probabilty of rectangle n is: areaN / (area0 + area1 + ... areaN)
Cheers :)
@tnutty2k8 if you used the area instead of the length it would work (the length is just for one dimension) but then you would have the problem to convert from the point to the rectangle and that is exactly what the algorithm is doing. It adds all the areas and choose one rectangle randomly.
@aonecoding Could you please clarify for the above follow up question:
According to ur soln:
The probability of picking a point from Rectangle0 => (area0-1) / area0 [can't pick 0 as total = 0]
The probability of picking a point from Rectangle1 => area1 / (area0 + area1)
The probability of picking a point from Rectangle2 => area2 / (area0 + area1 + area2)
The probability of picking a point from RectangleN => areaN / (area0 + area1 + ... areaN)
So isn't it non-uniform ?
Looking for interview experience sharing and coaching?
Visit aonecode.com for private lessons by FB, Google and Uber engineers
Our ONE TO ONE class offers
SYSTEM DESIGN Courses (highly recommended for candidates for FLAG & U)
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algos & Clean Coding),
latest interview questions sorted by companies,
mock interviews.
Our students got hired from G, U, FB, Amazon, LinkedIn and other top tier companies after weeks of training.
Feel free to email us aonecoding@gmail.com with any questions. Thanks!
Solution to follow-up: Randomly select a rectangle based on the areas as the weights (larger weights leads to higher probability). Then randomly find a point from the chosen rectangle.
- aonecoding August 03, 2017