Epic Systems Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Written Test
I assume that we are only interested in integral solutions ?
otherwise, even if area A is an integer, there is infinite no of solutions.
so for integer solutions, it should be smth like:
- compute factorization of A into pairwise coprime irreducible factors
- for each possible combination of two factors give 4 possible solutions (resp. when the first point is at one of the 4 corners of a rectange)
could be quite boring to implement this..
public class RectPerm {
public static void ouputVertices(int x1, int y1, int l, int b){
System.out.println("("+(x1+l)+","+y1+"),"+"("+(x1)+","+(y1+b)+"),"+"("+(x1+l)+","+(y1+b)+")" );
// System.out.println("("+(x1-l)+","+y1+"),"+"("+(x1)+","+(y1+b)+"),"+"("+(x1-l)+","+(y1+b)+")" );
// System.out.println("("+(x1+l)+","+y1+"),"+"("+(x1)+","+(y1-b)+"),"+"("+(x1+l)+","+(y1-b)+")" );
// System.out.println("("+(x1+l)+","+y1+"),"+"("+(x1)+","+(y1+b)+"),"+"("+(x1+l)+","+(y1+b)+")" );
}
public static void printVertices(int x1, int y1, int area){
Double d = Math.sqrt(area);
int high = d.intValue();
for(int i = 1; i <= high; i++) {
int length, breadth;
if ( area % i == 0){
length = i;
breadth = area/i;
ouputVertices(x1, y1, length, breadth);
ouputVertices(x1, y1, -1*length, breadth);
ouputVertices(x1, y1, length, -1*breadth);
ouputVertices(x1, y1, -1*length, -1*breadth);
}
}
}
public static void main(String[] args) {
printVertices(0,0,1);
printVertices(1,2,1);
}
}
To eliminate repetitions, the three lines:
ouputVertices(x1, y1, -1*length, breadth);
ouputVertices(x1, y1, length, -1*breadth);
ouputVertices(x1, y1, -1*length, -1*breadth);
Should be replaced with:
ouputVertices(x1, y1, breadth, length);
With this change, the above code will give unique solutions for rectangles where length != breadth. For case of square, use a filter for unique values of solutions. Filter can be like an if else statement in printVertices() method like this:
if(length == breadth) {
ouputVertices(x1, y1, length, breadth);
} else {
ouputVertices(x1, y1, length, breadth);
ouputVertices(x1, y1, breadth, length);
}
I liked the solution in time complexity as sqrt(area).
java function which does this. just copy paste and execute
void factorizeAndFindOtherCoordintes(int area, int x, int y){
for(int i=1; i<=area; i++){
for(int j=area; j>= 1; j--){
if(i*j == area){
System.out.println("("+x+","+y+")");
System.out.println("("+x+","+(y+j)+")");
System.out.println("("+(x+i)+","+y+")");
System.out.println("("+(x+i)+","+(y+j)+")");
System.out.println("-----------------");
System.out.println("("+x+","+y+")");
System.out.println("("+x+","+(y+j)+")");
System.out.println("("+(x-i)+","+y+")");
System.out.println("("+(x-i)+","+(y+j)+")");
System.out.println("-----------------");
System.out.println("("+x+","+y+")");
System.out.println("("+x+","+(y-j)+")");
System.out.println("("+(x-i)+","+y+")");
System.out.println("("+(x-i)+","+(y-j)+")");
System.out.println("-----------------");
System.out.println("("+x+","+y+")");
System.out.println("("+x+","+(y-j)+")");
System.out.println("("+(x+i)+","+y+")");
System.out.println("("+(x+i)+","+(y-j)+")");
System.out.println("-----------------");
}
}
}
}
public class RectPermu1 {
public void print_all_rect(int x, int y, int len, int wid){
int Ysign,Xsign;
for(int i=1; i<=4;i++){
Xsign = (i==1 || i==4)? 1:-1;
Ysign = (i==1 || i==2)? 1:-1;
System.out.print("("+ x + "," + y + ") ");
System.out.print("("+ (x+Xsign*len) + "," + y + ") ");
System.out.print("("+ (x+Xsign*len) + "," + (y+Ysign*wid) + ") ");
System.out.print("("+ x + "," + (y+Ysign*wid) + ") ");
System.out.println();
}
System.out.println();
}
public void print_all_permu(int area, int x, int y){
for(int len=1; len<=Math.sqrt(area);len++){
if(area%len==0){
int wid = area/len;
print_all_rect(x,y,len,wid);
if(len!=wid) print_all_rect(x,y,wid,len);
}
}
}
public static void main(String[] args) {
RectPermu1 obj = new RectPermu1();
int area = 1;
obj.print_all_permu(area,1,1);
}
}
java function which does this:-
void factorizeAndFindOtherCoordintes(int area, int x, int y){
for(int i=1; i<=area; i++){
for(int j=area; j>= 1; j--){
if(i*j == area){
System.out.println("("+x+","+y+")");
System.out.println("("+x+","+(y+j)+")");
System.out.println("("+(x+i)+","+y+")");
System.out.println("("+(x+i)+","+(y+j)+")");
System.out.println("-----------------");
System.out.println("("+x+","+y+")");
System.out.println("("+x+","+(y+j)+")");
System.out.println("("+(x-i)+","+y+")");
System.out.println("("+(x-i)+","+(y+j)+")");
System.out.println("-----------------");
System.out.println("("+x+","+y+")");
System.out.println("("+x+","+(y-j)+")");
System.out.println("("+(x-i)+","+y+")");
System.out.println("("+(x-i)+","+(y-j)+")");
System.out.println("-----------------");
System.out.println("("+x+","+y+")");
System.out.println("("+x+","+(y-j)+")");
System.out.println("("+(x+i)+","+y+")");
System.out.println("("+(x+i)+","+(y-j)+")");
System.out.println("-----------------");
}
}
}
}
i think there will be total 8 different sets for the other 3 points. correct me if i am wrong.
but i have assumed that we are computing only for integral points.
Why would there be 8? It could be less, could be more, depending on the area. For Eg, if the area is 25 and the point is (0,0), the possible diagonally opposite points are (1,25) (5,5) (25,1). If the area is 64 (1,64) (2,32) (4,16) (8,8) (16,4) (32,2) (64,1). once you know the two diagonally opposite points in a rectangle its easy to figure out the other two points.
Simple Java solution:
public static double[][] findCorner(double[][] initPoint, double area){
double[][] corners = new double[12][2];
double diameter = Math.sqrt(area);
int count = 0;
for (double i=-1; i<2; i+=2){ // left / right
for (double j=-1; j<2; j+=2){ // up / down
corners[count+0][0] = initPoint[0][0] + i*diameter;
corners[count+0][1] = initPoint[0][1];
corners[count+1][0] = initPoint[0][0];
corners[count+1][1] = initPoint[0][1] + j*diameter;
corners[count+2][0] = initPoint[0][0] + i*diameter;
corners[count+2][1] = initPoint[0][1] + j*diameter;
count += 3;
}
}
return corners;
}
HI can you explain your code because diameter doesn't make any sense. Are you considering a circle circumcising rectangle?
#include <iostream>
#include <vector>
using namespace std;
int main() {
int x,y;
int area;
vector<int> myvector1;
vector<int> myvector2;
cout<<"Enter Area: ";
cin>>area;
cout<<"Enter X and Y coordinates: ";
cin>>x>>y;
//Find factors for area
for(int i=1;i<=area;i++) {
if(area%i == 0) {
cout<<i<<" ";
myvector1.push_back(i);
}
}
for(int i=0,j = myvector1.size()-1;i<j;i++,j--) {
cout<<"Combination "<<": (";
cout<<myvector1[i] - x<<","<<x<<") ";
cout<<"("<<y<<","<<myvector1[j] - y<<") ";
cout<<"("<<myvector1[i] - x<<","<<myvector1[j] - y<<")\n";
cout<<"Combination "<<": (";
cout<<x - myvector1[i]<<","<<x<<") ";
cout<<"("<<y<<","<<myvector1[j] - y<<") ";
cout<<"("<<x - myvector1[i]<<","<<myvector1[j] - y<<")\n";
cout<<"Combination "<<": (";
cout<<x - myvector1[i]<<","<<x<<") ";
cout<<"("<<y<<","<<y - myvector1[j]<<") ";
cout<<"("<<x - myvector1[i]<<","<<y - myvector1[j]<<")\n";
cout<<"Combination "<<": (";
cout<<myvector1[i] - x<<","<<x<<") ";
cout<<"("<<y<<","<<y - myvector1[j]<<") ";
cout<<"("<<myvector1[i] - x<<","<<y - myvector1[j]<<")\n";
}
return 0;
}
This is a working code in C++:
#include<cstdio>
#include<iostream>
#include<string>
using namespace std;
int main()
{
int x, y, d1, d2;
cin>>x;
cin>>y;
cin>>d1;
cin>>d2;
cout<<(x+d1)<<" "<<y<<endl;
cout<<(x)<<" "<<(y+d2)<<endl;
cout<<(x+d1)<<" "<<(y+d2)<<endl;
cout<<"---------"<<endl;
cout<<(x-d1)<<" "<<y<<endl;
cout<<(x)<<" "<<(y+d2)<<endl;
cout<<(x-d1)<<" "<<(y+d2)<<endl;
cout<<"---------"<<endl;
cout<<(x-d1)<<" "<<y<<endl;
cout<<(x-d1)<<" "<<(y-d2)<<endl;
cout<<(x)<<" "<<(y-d2)<<endl;
cout<<"---------"<<endl;
cout<<(x+d1)<<" "<<y<<endl;
cout<<(x+d1)<<" "<<(y-d2)<<endl;
cout<<(x)<<" "<<(y-d2)<<endl;
cout<<"---------"<<endl;
if (d1!=d2)
{
cout<<(x+d2)<<" "<<y<<endl;
cout<<(x)<<" "<<(y+d1)<<endl;
cout<<(x+d2)<<" "<<(y+d1)<<endl;
cout<<"---------"<<endl;
cout<<(x-d2)<<" "<<y<<endl;
cout<<(x)<<" "<<(y+d1)<<endl;
cout<<(x-d2)<<" "<<(y+d1)<<endl;
cout<<"---------"<<endl;
cout<<(x-d2)<<" "<<y<<endl;
cout<<(x-d2)<<" "<<(y-d1)<<endl;
cout<<(x)<<" "<<(y-d1)<<endl;
cout<<"---------"<<endl;
cout<<(x+d2)<<" "<<y<<endl;
cout<<(x+d2)<<" "<<(y-d1)<<endl;
cout<<(x)<<" "<<(y-d1)<<endl;
}
return 0;
}
Suppose the point is x1,y1 = (2,1) and area is 10
- max August 29, 2012Lets assume we shift the origin to the given point x1,y1 = (2,1)
then we need to find all pairs of x,y such that product x*y = 10
so the possible integral pair are (1,10) and (2,5)
For each (x,y) pair there are 8 possible combinations of three other points.
So for (2,5) we have
1. (2,5) (2,0) (0,5) // we have assumed origin as first point
2. (-2,5) (-2,0) (0,5)
3. (2,-5) (2,0) (0,-5)
4. (-2,-5) (-2,0) (0,-5)
5. (5,2) (5,0) (0,2)
6. (-5,2) (-5,0) (0,2)
7. (5,-2) (5,0) (0,-2)
8. (-5,-2) (-5,0) (0,-2)
Now shifting origin back to given point x1,y1 = (2,1)
by adding (x+2, y+1) to each 8 combinations above
(this can be done in the above step itself)
Similarly for there are 8 combinations for pair (1,10)
So the main problem here is to find set of pairs of factor of given area and there are 8 possible combinations of three other points of the rectangle