Adobe Interview Question for Software Engineer / Developers


Country: India
Interview Type: Written Test




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

Can you please elaborate more on the question? I am not sure an intersection of rectangle creates holes.

- Rage October 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.

- Urik's twin Cookie Monster (dead now) October 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.

- Urik's twin Cookie Monster (dead now) October 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.

- Nitin Gupta October 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Huh? That's brute force obvious.

We should be able to use information just from the corners

- Urik's twin Cookie Monster (dead now) October 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Nitin Gupta October 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

"For getting holes info" doesn't describe any problem to me.
Time to bail on this thread.

- Urik's twin Cookie Monster (dead now) October 28, 2013 | Flag


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