Epic Systems Interview Question for Software Engineer / Developers


Country: United States
Interview Type: Written Test




Comment hidden because of low score. Click to expand.
3
of 5 vote

Suppose the point is x1,y1 = (2,1) and area is 10
Lets 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

- max August 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 votes

Can I ask a question? What if the point is (0, 0) , and Area is 2?

I think based on your algorithm, the results should be
(0,1), (1,2), (2, 0),
(1,0), (0,2), (2, 1),
etc.

But should (1,1) ,( -1, -1), (0,2) be a valid pair ?

- wxliuyizhe October 15, 2014 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

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..

- Anonymous January 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What about a rectangle with area of 25. For the case with width of 5 and height of 5, the other three points could be (-3, 4), (4, 3), (1, 7) with the first point at the origin. The edge of the rectangle is not aligned with any axis.

- Anonymous December 21, 2014 | Flag
Comment hidden because of low score. Click to expand.
2
of 4 vote

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);
	}

}

- rh February 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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).

- oli January 07, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Also, uncomment those three lines in method ouputVertices().

- oli January 07, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Is this restricted to integer rectangle dimensions? Otherwise, there's an infinite number of possibilities.

- eugene.yarovoi January 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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("-----------------");
}
}
}
}

- Anonymous January 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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);
	}
}

- thepraveen0207 October 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Also what about rotations? each permutation can be rotated in 360 degrees

- Anonymous January 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

They said that it is a rectangle and area is 1 it means
length = 2, breadth = 1/2
length = 3, breadth = 1/3
length = 4, breadth = 1/4
If they are not integers we will have infinite no. of combinations.

- Nani January 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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("-----------------");
				}
			}
		}
	}

- Anonymous January 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- atul February 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

- bdeesh February 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
	}

- Suz February 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

HI can you explain your code because diameter doesn't make any sense. Are you considering a circle circumcising rectangle?

- Madhur May 10, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hello can you explain your code a little bit more as it doesnt make sense what you mean by diameter. BY diameter do you mean its a circle around a rectangle? and then calculating all points? if so how did you calculate the diameter as just square root of area?

- madhur.eng May 10, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;
}

- XXX April 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

u r only considering rectangles parallel to coordinate axes. their could be other rectangles also possible

- thinker August 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Meraj Ahmed November 09, 2013 | Flag Reply


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