CareerCup

public class RandomSelectFromRectangle {
    class Rectangle {
        int x1, x2, y1, y2; //top left (x1, y1), bottom right (x2, y2)
    }

    class Point {
        int x, y;
        public Point(int a, int b) {
            x = a;
            y = b;
        }
    }

    final Random rand = new Random();

    //Round2
    public Point randomSelectFrom(Rectangle rectangle) {
        return new Point(rectangle.x1 + rand.nextInt(rectangle.x2 - rectangle.x1 + 1),
                        rectangle.y2 + rand.nextInt(rectangle.y1 - rectangle.y2 + 1));
    }

    //Round2 follow-up
    //first of all decide which rectangle yields the point (randomly select a rectangle based on area as the weight)
    //then apply randomSelectFrom(rectangle) on the selected rectangle
    public Point randomSelectFrom(Rectangle[] rectangles) {
        int selected = -1, total = 0;
        for(int i = 0; i < rectangles.length; i++) {
            int area = (rectangles[i].x2 - rectangles[i].x1) * (rectangles[i].y1 - rectangles[i].y2);
            if(rand.nextInt(total + area) >= total) {
                selected = i;
            }
            total += area;
        }
        return randomSelectFrom(rectangles[selected]);
    }
}

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.

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) + "]";
	}
    }
}