Google Interview Question for Software Engineers


Country: United States
Interview Type: In-Person




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

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.

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

- aonecoding August 03, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 vote

@sheva: it's correct, assume areas is one for all
- Probability to pick 1st is 1
- Next iteration, probability to pick 2nd is 0.5, so 0.5 for 1st and 0.5 for 2nd. 1st and 2nd have same probability (uniform)
- Next iteration, probability to pick 3rd is 1/3, so 1st and 2nd together is 2/3, 3 rd is 1/3, still uniform
...
it's an elegant algorithm for such cases, it's a similar one that is used when shuffling a deck of cards

- Chris August 03, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

@sheva

It is correct what you wrote about the probability of picking one of the rectangles. However, they are the probabilities "at the time" that you pick that specific rectangle. What we have to calculate are the probabilities of each rectangle being selected after iterating all rectangles.

For example, suppose the Rectangle0 has been selected. Then the rest of rectangles must not be selected (otherwise, variable 'selected' will be overwritten). So the prob. of rect0 being selected is as follows:
(A0 / A0) * (1 - A1 / (A0+A1)) * .... * (1 - A(n-1) / (A0 + A1 + ... + A(n-1))
= (A0 / (A0 + A1 + ... + A(n-1))

which is uniform prob. over all rectangles.

+) I believe it's an extension of reservoir sampling

- BoogleBoogle August 04, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

I think the answer is correct, all rectangles are non overlapped that means that if you choose uniformly between all the rectangles you are not choosing uniformly between the all the possible points. For example what happens if the first rectangle is the smallest one but you choose uniformly between all the rectangles? The points of this rectangle will appear repeated more often as there a less available and the choosing frequency is the same as for the rest of the rectangles. I guess it is a matter of how you interpret the question but the given answer is the most complex one.

Also Java is not my most used language so I can be mistaken, please correct me if that is the case :). The probabilities are like this isn't??
Probability of rectangle 0 is: 1 - prob of choosing r1 - .... - prob of choosing rn
Probability of rectangle 1 is: area1 / (area0 + area1) - prob of choosing r2 - ... - prob of choosing rn
Probabilty of rectangle n is: areaN / (area0 + area1 + ... areaN)

Cheers :)

- Fernando August 03, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Forgive for a naive question but wouldn't generating a random index from range (0,rectangle.length] and using that as the selectedIndex work?

- tnutty2k8 August 03, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@tnutty2k8 if you used the area instead of the length it would work (the length is just for one dimension) but then you would have the problem to convert from the point to the rectangle and that is exactly what the algorithm is doing. It adds all the areas and choose one rectangle randomly.

- Fernando August 04, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

@aonecoding Could you please clarify for the above follow up question:

According to ur soln:

The probability of picking a point from Rectangle0 => (area0-1) / area0 [can't pick 0 as total = 0]
The probability of picking a point from Rectangle1 => area1 / (area0 + area1)
The probability of picking a point from Rectangle2 => area2 / (area0 + area1 + area2)
The probability of picking a point from RectangleN => areaN / (area0 + area1 + ... areaN)

So isn't it non-uniform ?

- sheva August 03, 2017 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More