Google Interview Question
Country: United States
Interview Type: Phone Interview
/*
Let the rectangles R_0, R_1,..R_L-1 have areas
A_0, A_1,..., A_L-1
Now find a random number between 0 and (A_L-1) -1
This will determine the rectangle inside of which our chosen point will reside
For example if the random number falls in range [A3..A4-1] then
the point is inside R3
Let the sides or R3 be a and b ( not equal )
Let a' = random number in range [ 0 and a-1]
Let b' = random number in range [ 0 and b-1]
The co-ordinates of the point we want are (a', b')
*/
lets assume we have rectangles R[0..n]
their areas are A[0..n]
S will have in index i the sum of all areas [0..i]. it has n+1 elements
S[0] = 0;
for (i=1; i<=n; i++) {
S[i] = S[i-1] + A[i-1];
}
p = random_uniform(S[n]); // pick a number between 0 & sum of all areas (excluding), i.e. number in range [0..S[n])
now find j such that S[j] < p < S[j+1]
that j is the index of the rectangle we pick, & it has the correct probability, represented by the range of that element from the total range
I am wondering whether those rectangles will be overlapping?
- tiandiao123 September 15, 2017