Amazon Interview Question Software Engineer / Developers
0of 0 votesGiven 2 rectangles with top left and bottom right coordinates for each rectangle, return 1 if they have a common area otherwise return -1
Country: India
This will work only if the rectangles are axis aligned. If they aren't this will fail. For ex: consider rectangle1{(0,2) (5,0)} and rectangle2{(10,10),(-11,-9)}.
It wont work even for same axis aligned....It should be
if (x2 <= x3 || x4 <= x1 || y3 >= y2 || y1 >= y4) {
return -1;
}
return 1;
package amazon;
/*
* coordinate system:
* -<--------0----------------->X+
* |
* |
* |
* | +
* |
* |
* v
* Y+
*
* */
class Rectangle{
public int topleftX;
public int topleftY;
public int bottomrightX;
public int bottomrightY;
public Rectangle(int x1,int y1,int x2,int y2){
if(x2>x1&&y2>y1){
this.topleftX=x1;
this.topleftY=y1;
this.bottomrightX=x2;
this.bottomrightY=y2;
}
else{
System.out.println("err");
return;
}
}
}
public class Check_Two_Rectangle_Has_Common_Area {
public static int hasCommonArea(Rectangle o1,Rectangle o2){
int x1=o1.topleftX;
int y1=o1.topleftY;
int x2=o1.bottomrightX;
int y2=o1.bottomrightY;
int x3=o2.topleftX;
int y3=o2.topleftY;
int x4=o2.bottomrightX;
int y4=o2.bottomrightY;
if(y4<=y1){
return -1; //o2 above o1, totally
}
if(y3>=y2){
return -1; //o2 below o1, totally
}
if(x4<=x1){
return -1; //o2 left o1, totally
}
if(x3>=x2){
return -1; //o2 right o1, totally
}
return 1;
}
public static void main(String[] args) {
Rectangle o1=new Rectangle(0,0,1,1);
Rectangle o2=new Rectangle(2,2,10,10);
System.out.println(hasCommonArea(o1,o2));
}
}
#include <cstdio>
using namespace std ;
class rectangle {
public :
int x1;
int x2, y1, y2;
rectangle (int x_1, int y_1, int x_2, int y_2) {
x1 = x_1 ;
x2 = x_2 ;
y1 = y_1 ;
y2 = y_2 ;
}
};
int sharedArea (rectangle rec1, rectangle rec2) {
if (( rec1.x1 > rec2.x1 && rec1.x1 > rec2.x2 ) && ( rec1.x2 > rec2.x1 && rec1.x2 > rec2.x2 )) {
printf ( "\nNot matching rect1 is right of rect2" ) ;
return -1 ;
}
if (( rec1.x1 < rec2.x1 && rec1.x1 < rec2.x2 ) && ( rec1.x2 < rec2.x1 && rec1.x2 < rec2.x2 )) {
printf ( "\nNot matching rect1 is left of rect2" ) ;
return -1 ;
}
if ((rec1.y1 > rec2.y1 && rec1.y1 > rec2.y2 ) && ( rec1.y2 > rec2.y1 && rec1.y2 > rec2.y2 )) {
printf ( "\nNot matching rect1 is bottom of rect2" ) ;
return -1 ;
}
if ((rec1.y1 < rec2.y1 && rec1.y1 < rec2.y2 ) && ( rec1.y2 < rec2.y1 && rec1.y2 < rec2.y2 )) {
printf ( "\nNot matching rect1 is up of rect2" ) ;
return -1 ;
}
return 1 ;
}
int main () {
rectangle r1 (0,0,6,5) ;
rectangle r2 (5,4,8,-5) ;
if ( sharedArea (r1,r2) == 0 )
printf ( "\nNo shared area" ) ;
else printf ( "\nHas shared area" ) ;
return 0;
}
public static int isCommonArea(Rectangle rectOne,Rectangle rectTwo)
{
int x1 = rectOne.top_left_x;
int y1 = rectOne.top_left_y;
int x2 = rectOne.right_bottom_x;
int y2 = rectOne.right_bottom_y;
int x3 = rectTwo.top_left_x;
int y3 = rectTwo.top_left_y;
int x4 = rectTwo.right_bottom_x;
int y4 = rectTwo.right_bottom_y;
if(x1<x3 && x3<x2 && y1>y3 && y3>y2)
return 1;
if(x1<x3 && x3<x2 && y1>y4 && y4>y2)
return 1;
if(x1<x4 && x4<x2 && y1>y3 && y3>y2)
return 1;
if(x1<x4 && x4<x2 && y1>y4 && y4>y2)
return 1;
return -1;
}
For Full Code: ideone.com/yyE68
Even if this is correct (I haven't checked), it's way more complicated than it needs to be.
package practicepackage;
public class CheckSimilarAreasOfRectangles{
int x1;
int x2;
int x3;
int x4;
int y1;
int y2;
int y3;
int y4;
public void getCordinatesofFirstRectangle(int x1,int y1,int x2,int y2)
{
this.x1=x1;
this.y1=y1;
this.x2=x2;
this.y2=y2;
}
public void getCordinatesOfSecondRectangle(int x3,int y3,int x4,int y4)
{
this.x3=x3;
this.y3=y3;
this.x4=x4;
this.y4=y4;
}
public int calculateAreaOfRectangles()
{
int firstRectangleHeight=y2-y1;
if(firstRectangleHeight<0)
firstRectangleHeight*=-1;
int firstRectangleLength=x2-x1;
if(firstRectangleLength<0)
firstRectangleLength*=-1;
int areaFirstRectangle= firstRectangleHeight*firstRectangleLength;
int secondRectangleHeight=y3-y4;
if(secondRectangleHeight<0)
secondRectangleHeight*=-1;
int secondRectangleLength=x4-x3;
if(secondRectangleLength<0)
secondRectangleLength*=-1;
int areaSecondRectangle= secondRectangleHeight*secondRectangleLength;
if(areaFirstRectangle==areaSecondRectangle)
return 1;
else
return -1;
}
public static void main(String[] args)
{
CheckSimilarAreasOfRectangles sar= new CheckSimilarAreasOfRectangles();
sar.getCordinatesofFirstRectangle(5,5,8,2);
sar.getCordinatesOfSecondRectangle(13,10,16,7);
int equality = sar.calculateAreaOfRectangles();
System.out.println("The rectangles are equal in areas if 1 or are unequal if -1");
System.out.println("The equality number for areas of two rectangles is: "+ equality);
}
}
two rectangles are overlapped only if when projections to x and y axis are both overlapped. so in the non-rotate case, i.e. assume rect A[(xa0, ya0), (xa1, ya1)], B[(xb0, yb0), (xb1, yb1)] both aligned to the axis,
then
length_a = xa1 - xa0,
length_b = xb1 - xb0,
max_length_interval = max(abs(xb1 - xa0) , abs(xb0 - xa1)),
ditto for height; so they overlap
if (max_length_interval <= length_a + length_b) && (max_height_interval <= height_a + height_b)
Lets say (Rec = rectangular, L = Line)
Rec1 = (PintTop(X1t, Y1t), PointBottom(X1b, Y1b))
and
Rec2 = (PintTop(X2t, Y2t), PointBottom(X2b, Y2b))
L1x = (Pint(X1t, Y1t), Pint(X1b, Y1t))
L2x = (Pint(X2t, Y2t), Pint(X2b, Y2t))
L1y = (Pint(X1t, Y1t), Pint(X1t, Y1b))
L2y = (Pint(X2t, Y2t), Pint(X2t, Y2b))
so you simple check if lines intersect:
if (L1x intersect L2x && L1y intersect L2y)
return 1
else
return -1
Here is a Java method for checking if there is intersection:
private static boolean intersect (int a1, int b1, int a2, int b2) {
boolean result;
if (a1 > a2)
if (a1 > b2)
result = false;
else
result = true;
else
if (b1 >= a2)
result = true;
else
result = false;
return result;
}
1. Take mod of top left x and bottom right x for first rectangle. 2.take mod of top left y and bottom right y. 3.multiply ans of 1 and 2. Repeat the steps for rectangle. And compare area of both.
This wont work if the rectangles are rotated... it works only if the rectangles are aligned to the axis
Given how this question is phrased I would take it that the rectangles are axis-aligned
If they were aligned to the axis then this problem would be too easy. You could easily figure out the dimensions of the rectangle, then then it would just be child's play to find if boundaries were inside each other.
Actually, I take that back. I don't think it's possible to define a rectangle with 2 corner points and no reference axis.
return rec1.containsAnyCornerOf(rec2)|| rec2.containsAnyCornerOf(rec1)
PointToLineDistance(Point point,Line line)
If the diagonals of the two rectangles are equal then they would be of equal area. So just compare diagonal lengths.
Rec1 = {(x1, y1), (x2, y2)}
Rec2 = {(x3, y3), (x4, y4)}
- Jim on August 09, 2012 Edit | Flag Replyif (x2 <= x3 || x4 <= x1 || y3 <= y2 || y1 <= y4) { return -1; } return 1;