Google Interview Question
Software EngineersCountry: United States
Interview Type: In-Person
solution output:
```
$ javac RandomPointFromRectanglesUniformProb.java
$ java RandomPointFromRectanglesUniformProb
Rectangles (x1,y1,x2,y2):
[0,0,3,3]
[4,5,6,8]
Total area: 15
(0.6800052, 1.5723058) (inside of rectangle [0,0,3,3])
$ java RandomPointFromRectanglesUniformProb
Rectangles (x1,y1,x2,y2):
[0,0,3,3]
[4,5,6,8]
Total area: 15
(4.86407, 5.9339833) (inside of rectangle [4,5,6,8])
```
RandomPointFromRectanglesUniformProb.java
import java.util.List;
import java.util.ArrayList;
public class RandomPointFromRectanglesUniformProb {
public static void main(String args[]) {
List<Rectangle> rectangles = getNonOverlappingRectanglesForTest();
System.out.println("Rectangles (x1,y1,x2,y2):");
int totalArea = 0;
for (Rectangle rectangle : rectangles) {
System.out.println(rectangle.toString());
totalArea += rectangle.getArea();
}
System.out.println("\nTotal area: " + totalArea);
// could generate 1 random number and wrap it in x/y...
// but easier to read imho if we use 1 random number to pick which rectangle (weighted by area so it is uniform in space)
// and then use a method on the rectangle to get a random point in it
// chosen in an area proportionate way so overall we're sampling uniformly across the area of all rectangles
Rectangle randomRectangle = null;
float randomNumberUpToTotalArea = (float)(Math.random() * totalArea);
float totalAreaSoFar = 0;
for (Rectangle rectangle : rectangles) {
float area = (float)rectangle.getArea();
totalAreaSoFar += area;
if (randomNumberUpToTotalArea <= totalAreaSoFar) {
randomRectangle = rectangle;
break;
}
}
float randomX = randomRectangle.x + (float)(Math.random() * randomRectangle.width);
float randomY = randomRectangle.y + (float)(Math.random() * randomRectangle.height);
System.out.println("(" + randomX + ", " + randomY + ") (inside of rectangle " + randomRectangle.toString() + ")");
}
private static List<Rectangle> getNonOverlappingRectanglesForTest() {
List<Rectangle> rectangles = new ArrayList<Rectangle>();
// add rectangles. start with a couple hardcoded ones.
rectangles.add(new Rectangle(0, 0, 3, 3));
rectangles.add(new Rectangle(4, 5, 2, 3));
return rectangles;
}
private static class Rectangle {
int x;
int y;
int width;
int height;
public Rectangle(int x, int y, int width, int height) {
this.x = x;
this.y = y;
this.width = width;
this.height = height;
}
public int getArea() {
return width*height;
}
public String toString() {
return "[" + this.x + "," + this.y + "," + (this.x + this.width) + "," + (this.y + this.height) + "]";
}
}
}
Looking for interview experience sharing and coaching?
- acoding167 June 19, 2019Visit 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.