Adobe Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Written Test
No clue what the specific question is. Sounds like a specific arrangement of rectangles, but then there is "n" there too. Sounds like the points are discrete (well for a computer related question it would have to be).
In general:
If we have a set of rectangles (defined with two corner points), to find the area they puncture seems like a tough problem (for me at least) to code in 45 min. (since I have to derive an idea first).
I don't know any well known algorithm off the top of my head, but I know how someone would integrate such areas in math assuming first continuous variables:
1) Integrate the punctured area using Fubini's theorem (iterated integral).
-------------------------------------------------------------------------------------------------
So we either integrate moving left to right on x-axis (or alternatively, move on y-axis).
This reduces the problem to essentially summing up inner 1D integrals.
Something like:
Double Integral{over area}
={using Fubini's theorem, using to do integral over x on outside}
Integral{from leftmost x to rightmost} of Integral{ something we call G(x) }*deltax
G(x) is "sort of" the intersection area of the line at x with the region.
We just need to know the intersection of the vertical line at position x with all the rectangles (so this reduces to 1D union of intervals problem).
To convert this problem to the integer (discrete case), we get:
Area =
SUM(x from leftmost to rightmost) of G(x)*(1) , where deltax = 1
where G(x) refers to union of intervals that intersected the rectangles AT BOTH x-1 and x (because deltax = 1).
I think we can keep updating G(x) with a D.S. and keep adding and removing rectangles into question.
I am rambling but it all boils down to converting double iterated interval to the discrete case (on paper it will make sense).
2) Calculate 2D Double Integral with Green's Theorem
-------------------------------------------------------------------------
Another way to do a 2D double integral is to use Green's theorem instead of Fubini's theorem. To do this, we need to find the sort of "concave" hull of all the corners and intersection points of the rectangles. So basically, all the relevant points in your "punctured" area.
Then we can use green's theorem to go "around" the "relevant" points in the proper order and find the area (we have to do this for the multiple region case which are not necessarily simply connected).
I am not sure if anyone really uses Green's theorem for such problems, if not someone see if it's a slick way and write a paper on it.
No clue what the specific question is. Sounds like a specific arrangement of rectangles, but then there is "n" there too. Sounds like the points are discrete (well for a computer related question it would have to be).
In general:
If we have a set of rectangles (defined with two corner points), to find the area they puncture seems like a tough problem (for me at least) to code in 45 min. (since I have to derive an idea first).
I don't know any well known algorithm off the top of my head, but I know how someone would integrate such areas in math assuming first continuous variables:
1) Integrate the punctured area using Fubini's theorem (iterated integral).
-------------------------------------------------------------------------------------------------
So we either integrate moving left to right on x-axis (or alternatively, move on y-axis).
This reduces the problem to essentially summing up inner 1D integrals.
Something like:
Double Integral{over area}
={using Fubini's theorem, using to do integral over x on outside}
Integral{from leftmost x to rightmost} of Integral{ something we call G(x) }*deltax
G(x) is "sort of" the intersection area of the line at x with the region.
We just need to know the intersection of the vertical line at position x with all the rectangles (so this reduces to 1D union of intervals problem).
To convert this problem to the integer (discrete case), we get:
Area =
SUM(x from leftmost to rightmost) of G(x)*(1) , where deltax = 1
where G(x) refers to union of intervals that intersected the rectangles AT BOTH x-1 and x (because deltax = 1).
I think we can keep updating G(x) with a D.S. and keep adding and removing rectangles into question.
I am rambling but it all boils down to converting double iterated interval to the discrete case (on paper it will make sense).
2) Calculate 2D Double Integral with Green's Theorem
-------------------------------------------------------------------------
Another way to do a 2D double integral is to use Green's theorem instead of Fubini's theorem. To do this, we need to find the sort of "concave" hull of all the corners and intersection points of the rectangles. So basically, all the relevant points in your "punctured" area.
Then we can use green's theorem to go "around" the "relevant" points in the proper order and find the area (we have to do this for the multiple region case which are not necessarily simply connected).
I am not sure if anyone really uses Green's theorem for such problems, if not someone see if it's a slick way and write a paper on it.
It was asked in Amazon Ninja Coder 2013.
Please refrain from posting questions for ongoing competition.
Now the competition is over. I will answer this.
I used recursive approach to solve this.
First mark the matrix with barren land as 0 and holes as 1.
Then check recursively for holes using DFS.
Let me know if you guys want working code.
Huh? That's brute force obvious.
We should be able to use information just from the corners
For getting holes info, you need to look at each point. So the best solution is O(n^2). DFS will give O(n^2) only.
Any new approach is welcome.
Can you please elaborate more on the question? I am not sure an intersection of rectangle creates holes.
- Rage October 27, 2013