Goldman Sachs Interview Question
Financial Software DevelopersCountry: United States
Interview Type: Phone Interview
Use an auxiliary hashtable if space is not an issue to solve this problem. The keys of the hashtable would be the x-coordinates of the points and the values would be arraylists of integers holding the y-coordinates of the points.
Use a vertical sweep line and move it from the left of the plane to the right. When 2 or more points are encountered by the sweep line, calculate the difference between their y-coordinates and let it be d. Look up in the hashtable to see if the corresponding points at a horizontal distance 'd' exist previously. In other words, for 2 points on the sweep line with coordinates (x1,y1), (x1, y2), check in the hashtable if points exist with coordinates (x1-d, y1) & (x1-d, y2) exist (Here, d = |y1-y2|). If they exist, they form a square.
Finally add the newly encountered points to the hashtable and repeat the procedure until the vertical sweep line moves past the rightmost point(s).
I believe it is possible for a square to exist in a 2D plane where none of it's vertices share x or y. An example would be tilting a square {0,1}, {1,1}, {0,1}, {0,0} by 20 degrees. This square would not be found by your method as there would never be 2 points from it at the same time on your sweep line.
My Algo:
A Set of points S{p1(x,y),p2(x,y)....pn(x,y)} is given. (S is an array of object)
Compute LineSegment[i][j] = dij For all i and for all j, where i and j are points in S.
Compute LineSegment[i][j] = Root(pow((S[j].x - S[i].x),2) + pow( (S[j].y -S[i].y),2)) if i!=j and LineSegment[j][i] does not exist yet.
for each point in S, say i
Find a pair of equal line segments
if some Pair(LineSegment[i][k], LineSegment[i][l]) exist then,
if LineSegment([k][l] < (Root(pow(LineSegment[i][k],2) + pow(LineSegment[i][l],2))) - hypotenuse
discard k and l.
else
find any LineSegment[i][m] whose value is equal hypotenuse, If exist {i, k, l, m} form a square in 2D
Comments welcome!!
Precalculate all slopes between any 2 points - O(n^2)
Then within each list of points with the same slope see if 2 corresponding perpendicular lines exist.
import com.google.common.collect.Lists;
import com.google.common.collect.Maps;
import com.google.common.collect.Sets;
import java.util.List;
import java.util.Map;
import java.util.Set;
public class FindSquaresIn2D {
static class Point{
double x,y;
Point(double x, double y) {
this.x = x;
this.y = y;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof Point)) return false;
Point point = (Point) o;
if (Double.compare(point.x, x) != 0) return false;
if (Double.compare(point.y, y) != 0) return false;
return true;
}
@Override
public int hashCode() {
int result;
long temp;
temp = Double.doubleToLongBits(x);
result = (int) (temp ^ (temp >>> 32));
temp = Double.doubleToLongBits(y);
result = 31 * result + (int) (temp ^ (temp >>> 32));
return result;
}
@Override
public String toString() {
return "{" +x +"," + y +'}';
}
}
static class Line{
Point a,b;
Line(Point a, Point b) {
this.a = a;
this.b = b;
}
@Override
public String toString() {
return "{" + a +"|" + b +'}';
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Line that = (Line) o;
return (this.a.equals(that.a) && this.b.equals(that.b) ||
this.a.equals(that.b) && this.b.equals(that.a));
}
@Override
public int hashCode() {
return (int) (a.x*a.y+b.x*b.y);
}
}
static List<Point> all = Lists.newArrayList(
new Point(0,0),new Point(0,2),new Point(1,1),new Point(1,-1),
new Point(2,2),new Point(2,0),new Point(2,1),
new Point(1,2), new Point(1.1,2.7), new Point(-1,-1)
);
public static void main(String[] args) throws InterruptedException {
Map<Double,Set<Line>> m = Maps.newHashMap();
for (int i = 0; i < all.size()-1; i++) {
Point a = all.get(i);
for (int j = i+1; j < all.size(); j++) {
Point b = all.get(j);
if (a.equals(b)) continue ;
Double slope = checkForNegativeExtremes( (a.y - b.y) / (a.x - b.x) );
Set<Line> l = m.get(slope);
if (l==null){
m.put(slope, l = Sets.newHashSet());
}
l.add(new Line(a, b));
}
}
for(Double slope : Lists.newArrayList( m.keySet())){
Set<Line> lTmp = m.get(slope);
if (lTmp==null || lTmp.size()<=1) continue ;
Double slopePerpendicular = checkForNegativeExtremes(-1. / slope);
Set<Line> perpendiculars = m.remove(slopePerpendicular);
if (perpendiculars==null || perpendiculars.size()<=1) continue ;
List<Line> l = Lists.newArrayList(lTmp);
for (int i = 0; i < l.size()-1; i++) {
Line l1 = l.get(i);
for (int j = i+1; j < l.size(); j++) {
Line l2 = l.get(j);
if (perpendiculars.contains(new Line(l1.a,l2.a)) && perpendiculars.contains(new Line(l1.b,l2.b))
// just in case we got them crossed here try the other way too.
|| perpendiculars.contains(new Line(l1.a,l2.b)) && perpendiculars.contains(new Line(l1.b,l2.a))){
System.out.println(l1.a+" "+l1.b+" "+l2.a+" "+l2.b+" form a square");
}
}
}
}
Thread.sleep(1000);
System.exit(0);
}
private static Double checkForNegativeExtremes(Double slope) {
if (slope.isInfinite() || slope.equals(-0.0)){
slope = Math.abs(slope); // this handles horizontal and perpendicular lines, dont want to differential between 0. and -0.
}
return slope;
}
}
Output :
{0.0,0.0} {2.0,0.0} {0.0,2.0} {2.0,2.0} form a square
{1.0,1.0} {2.0,1.0} {2.0,2.0} {1.0,2.0} form a square
{0.0,0.0} {1.0,1.0} {1.0,-1.0} {2.0,0.0} form a square
import com.google.common.collect.Lists;
import com.google.common.collect.Maps;
import com.google.common.collect.Sets;
import java.util.List;
import java.util.Map;
import java.util.Set;
public class FindSquaresIn2D {
static class Point{
double x,y;
Point(double x, double y) {
this.x = x;
this.y = y;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof Point)) return false;
Point point = (Point) o;
if (Double.compare(point.x, x) != 0) return false;
if (Double.compare(point.y, y) != 0) return false;
return true;
}
@Override
public int hashCode() {
int result;
long temp;
temp = Double.doubleToLongBits(x);
result = (int) (temp ^ (temp >>> 32));
temp = Double.doubleToLongBits(y);
result = 31 * result + (int) (temp ^ (temp >>> 32));
return result;
}
@Override
public String toString() {
return "{" +x +"," + y +'}';
}
}
static class Line{
Point a,b;
Line(Point a, Point b) {
this.a = a;
this.b = b;
}
@Override
public String toString() {
return "{" + a +"|" + b +'}';
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Line that = (Line) o;
return (this.a.equals(that.a) && this.b.equals(that.b) ||
this.a.equals(that.b) && this.b.equals(that.a));
}
@Override
public int hashCode() {
return (int) (a.x*a.y+b.x*b.y);
}
}
static List<Point> all = Lists.newArrayList(
new Point(0,0),new Point(0,2),new Point(1,1),new Point(1,-1),
new Point(2,2),new Point(2,0),new Point(2,1),
new Point(1,2), new Point(1.1,2.7), new Point(-1,-1)
);
public static void main(String[] args) throws InterruptedException {
Map<Double,Set<Line>> m = Maps.newHashMap();
for (int i = 0; i < all.size()-1; i++) {
Point a = all.get(i);
for (int j = i+1; j < all.size(); j++) {
Point b = all.get(j);
if (a.equals(b)) continue ;
Double slope = checkForNegativeExtremes( (a.y - b.y) / (a.x - b.x) );
Set<Line> l = m.get(slope);
if (l==null){
m.put(slope, l = Sets.newHashSet());
}
l.add(new Line(a, b));
}
}
for(Double slope : Lists.newArrayList( m.keySet())){
Set<Line> lTmp = m.get(slope);
if (lTmp==null || lTmp.size()<=1) continue ;
Double slopePerpendicular = checkForNegativeExtremes(-1. / slope);
Set<Line> perpendiculars = m.remove(slopePerpendicular);
if (perpendiculars==null || perpendiculars.size()<=1) continue ;
List<Line> l = Lists.newArrayList(lTmp);
for (int i = 0; i < l.size()-1; i++) {
Line l1 = l.get(i);
for (int j = i+1; j < l.size(); j++) {
Line l2 = l.get(j);
if (perpendiculars.contains(new Line(l1.a,l2.a)) && perpendiculars.contains(new Line(l1.b,l2.b))
// just in case we got them crossed here try the other way too.
|| perpendiculars.contains(new Line(l1.a,l2.b)) && perpendiculars.contains(new Line(l1.b,l2.a))){
System.out.println(l1.a+" "+l1.b+" "+l2.a+" "+l2.b+" form a square");
}
}
}
}
Thread.sleep(1000);
System.exit(0);
}
private static Double checkForNegativeExtremes(Double slope) {
if (slope.isInfinite() || slope.equals(-0.0)){
slope = Math.abs(slope); // this handles horizontal and perpendicular lines, dont want to differential between 0. and -0.
}
return slope;
}
}
Output :
{0.0,0.0} {2.0,0.0} {0.0,2.0} {2.0,2.0} form a square
{1.0,1.0} {2.0,1.0} {2.0,2.0} {1.0,2.0} form a square
{0.0,0.0} {1.0,1.0} {1.0,-1.0} {2.0,0.0} form a square
I was asked exactly same question , from GS. My solution was that I will calculate distance between each pair of point, and store those distances in a hash-map with distance as key and values as set of points. Then i will pick each key from hash-map and key*root(2)and then analyze all those two set of points. I could not finish it. Could not finish it. :(
I was asked exactly same question , from GS. My solution was that I will calculate distance between each pair of point, and store those distances in a hash-map with distance as key and values as set of points. Then i will pick each key from hash-map and key*root(2)and then analyze all those two set of points. I could not finish it. Could not finish it. :(
Here is a more universal approach than described by Apostle, i.e. it doesn't assume that the square's sides are parallel to the axes. The complexity looks to be O(N^2).
- nmr_guy August 08, 20131) For quick check-up on the existence of points with given coordinates, store all points in HashMap<String, int>. Here point coordinates are turned into String key as x+","+y.
2) Iterate i from 0 to N-1 and j from i+1 to N, where N is the total number of points. For each pair of points it is easy to predict where to expect the other corners of the square. You basically calculate the vector perpendicular to the line between your current two points. This vector is (ax, ay) = (y2-y1, -(x2-x1)), where (x1, y1) is the i-th point and (x2, y2) is the j-th point. The predicted positions will be either (x1+ax, y1+ay) & (x2+ax, y2+ay) OR (x1-ax, y1-ay) & (x2-ax, y2-ay).
3) If each point of the predicted pair exists in the HashMap then you found a square! I kept track of the found squares using an ArrayList<String>, because you find the same squares with different sequence of corners multiple times. In this ArrayList I represented as a sorted sequence of point indexes, turned into a string.
Notes: a) It might be enough to consider only predicted points (x1+ax, y1+ay) & (x2+ax, y2+ay). It yielded the same results on my test set of points. However, I am not good enough to prove that it will generally work :)
b) I was working with ints for my point coordinates, which actually limits you a lot on what kind of square orientations you can have. Ideally you'd want to switch to floats. However, due to the large number of significant digits that you would typically end up with, you wouldn't be able to get the HashMap to work. So I think for it to work you'd need to round coordinates to a fixed number of decimal places before you put them into HashMap. And then you just have to hope that you have enough precision to detect all the squares :)