Given two list of lines, perpendicular to each other. Find the number of squares they form.
class Point {
int x;
int y;
Point(int x, int y) {
this.x = x;
this.y = y;
}
}
class Line {
Point start;
Point end;
Line(Point start, Point end) {
this.start = start;
this.end = end;
}
}
public int getNumberOfSquares(List<Line> lines, List<Line> perpendicularLines){
// todo: implement method
}
Example
Input:
Lines:
Line (start:Point (x:8, y:8), y:Point (x:18, y:8)) // K to S
Line (start:Point (x:1, y:6), y:Point (x:15, y:6)) // A to B
Line (start:Point (x:4, y:2), y:Point (x:20, y:2)) // C to D
Perpendicular Lines:
Line (start:Point (x:6, y:1), y:Point (x:6, y:9)) // F to E
Line (start:Point (x:8, y:1), y:Point (x:8, y:8)) // L to K
Line (start:Point (x:10, y:0), y:Point (x:10, y:9)) // H to G
Line (start:Point (x:14, y:1), y:Point (x:14, y:10)) // J to IOutput:
3
Expalination Visual representation:
Square 1: Intersecting points : M, N, O, P
Square 2: Intersecting points : N, Q, R, O
Square 3: Intersecting points : K, T, N, U
Other points:
I was able to brue force it and do it in O(N^4). However according to the interviewer there was a O(N^3) solution as well
Comments (6)