Goldman Sachs Interview Question for Financial Software Developers


Country: United States
Interview Type: Phone Interview




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

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

1) 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 :)

- nmr_guy August 08, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Murali Mohan August 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- schroeder.carl.j August 08, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Good point schroeder. You are right, my algo will not be able to detect such squares.

- Murali Mohan August 08, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Your algo. is (N^3). It can be made O(N^2). Instead of arrays in auxiliary hashtable use hashtables. This allows checking if the 2 points existence in constant time (but requires extra memory).

- leve August 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is an exhaustive search solution:
For each point p, find two other points x, y that are 1) of the same distance (d) from p, and 2) that are d*sqrt(2) apart. If these two points are found, look for a third point that is (1/2) * d * sqrt(2) from the midpoint of x and y.

- maximus_algorius August 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- MJ November 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

select any point a(x,y)
using three for loops we can compute all the possible squares

- Deric December 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- petko.ivanov September 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- mmmm November 01, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 3 vote

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

- aks August 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

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

- aks August 06, 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