Microsoft Interview Question for Senior Software Development Engineers

• -1
of 1 vote

Country: United States
Interview Type: Phone Interview

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

This will be O(n), but could be done in parallel by distributing the list of rectangles to multiple nodes.

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

Algo,

You need to check only 4 positions for this. Find nearest left, right, top and bottom edge of the rectangles who overlaps the point P. then calculate then minArea(left , right, top bottom) rectangle gives you the answer.

Algorithm will take constant time if you can find those edges in constant time else it slips to O(n) for finding part overtime.

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

There's no way to do this in less than O(n) given what you've said and no extra constraints.

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

hprem991,
Unclear from your algo is how would you conclude the nearest edges without visiting all the rectangles. If some rectangles aren't checked, how can we conclude none of those could be the answer?

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

In what aspect they wanted the optimization? Can we assume that there a lot of queries and we need to do some preprocessing, or we don't have space to store all rectangles, so we need some online algorithm? Could you clarify. I see that this is telephonic interview

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

I think we can do it in O(log n) using interval trees. Lets say the given point is (x,y). Lets say, the positions of lower-left (xL, yL) & upper-right (xH, yH) corners of each rectangle are given. We will create two interval trees. Each node of first interval tree (say treeX) will have pair (xL, xH) corresponding to each rectangle. Similarly, each node of second interval tree (say treeY) will have pair (yL, hH) corresponding to each rectangle. In first pass (which is O(log n)), we will use treeX to get all the rectangles for which (xL < x < xH). In second pass (which is also order O(log n)), we will use treeY to get the minimum rectangle that contains (x,y).

Comment hidden because of low score. Click to expand.
0
of 2 vote

Could anyone please elaborate what the question is asking?
Do we need to find the rectangle with the smallest area that contains a given point? Or we need to find the rectangle that contains a point and the area formed by one of four vertices of the rectangle and this point is minimal?

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

perhaps dynamic programming was intended?
If area and density are bounded, repeated rectangles are assumed and you can somewhat optimized (since there are "billions" of rectangles)

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

divide and conquer?
merge step would be to find intersecting rectangle of 2 min overlapping rectangles?

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