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