## Google Interview Question for SDE1s

• 0

Country: United States

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

the question will be, random with what distribution?
I assume with a uniform distribution: each point in the final region has the same probability to be chosen. For a single rectangle this is straight forward:

``````x = rectangle.left + random(rectangle.width);
y = rectangle.top + random(rectangle.height);``````

For multiple rectangles that don't overlap, we can say, we choose the rectangle proportionally to it's area and once the rectangle is chosen, pick a point in there.

``````long long are_sum = 0;
for(Rectangle& r : rectangles) {
area_sum += r.width * r.height;
if(random(area_sum) < r.width * r.height) {
x = rectangle.left + random(rectangle.width);
y = rectangle.top + random(rectangle.height);
}
}``````

But if they overlap it's tricky. The easiest way I can think of is to union the new rectangle with the existing area and only consider the rectangles that are not already covered and apply method 2.

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.

### 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.