## Goldman Sachs Interview Question for Financial Software Developers

• 1
of 1 vote

Country: India

Comment hidden because of low score. Click to expand.
2
of 4 vote

You can store the distance between two points in HashMap as a list of points. key = distance. Once done just look through the same distance point and see if you can make a square its O(n^2)

Comment hidden because of low score. Click to expand.
0

Good solution. The hashMap - square check part is a bit tricky. Take 2 elements from the list of line segments, and then check if they can make a square (taking 2 line segments = 4 points).

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

I also gave this solution. But is this optimal?.

First of all building a hash map of all distance would take O(n^2) time. Later we need to traverse the list of points and check for square property, this one also takes some more time.

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

If there are many squares of the same size, there may be distances that have a lot of pairs of points associated with them. Let's say we have 1M squares of side 4. Then there are at least 4M entries under the key of 4. Now you have to match them up and associate the right ones together to form squares. You haven't said anything about how you will do this efficiently. It's quite possible that you had an algorithm in mind for that, but without describing it, this solution seems incomplete.

Comment hidden because of low score. Click to expand.
0

I think you can first retrieve two pairs of points with the same distance in the hashtable which contain four distinct points, say ab, cd and their distance is 1. then you just check whether distance of ac, ad, bc, bd are all 1/sqrt(2). so the worst case will be n(n-1)/2 if the values with key==1 has n pairs of points.

Comment hidden because of low score. Click to expand.
0

Analyzing set of points from hashmap whose key is d distance and sqrt(2)*distance should give the points of square. But sqrt(2) logic did not click when i was going through interview. Do you think interviewer would consider this solution?

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

I think this problem can be solved easily by creating a nxn matrix with matrix[i][j] and matrix[j][i] representing the distance between ith and jth point. From that matrix, we can easily find out the points forming a square.

From such a matrix:
1. Loop through each row
2. Find two entries having equal value
3. Scan down through the same two columns to see if same two values occur again in any other row.

``````import math

class point:
def __init__(self, x, y):
self.x = x
self.y = y
def __str__(self):
return '(' + str(self.x) + ',' + str(self.y) + ')'

def distance (p1, p2):

return  math.sqrt((p2.x - p1.x)**2 + (p2.y - p1.y)**2)

list = [ ]
list.append( point( 1, 1 ) )
list.append( point( 1, 2 ) )
list.append( point( 1, 3 ) )
list.append( point( 2, 1 ) )
list.append( point( 2, 2 ) )
list.append( point( 3, 1 ) )
list.append( point( 3, 3 ) )

matrix = [[0 for x in xrange(7)] for x in xrange(7)]

for i in range(0, len(list)):
for j in range(i+1, len(list)):
matrix[j][i] = matrix[i][j] = distance(list[i], list[j])

for i in range(0, len(list)):
for j in range(i+1, len(list)):
for k in range(j+1, len(list)):
if matrix[i][j] == matrix[i][k]:
for l in range(i+1, len(list)):
if matrix[i][j] == matrix[l][j] and matrix[l][j] == matrix[l][k]:
print list[i]
print list[j]
print list[k]
print list[l]
print ""``````

Comment hidden because of low score. Click to expand.
0

how about a diamond with edge of equal length.

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

can you give the example for this question

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

first ---- calculate the distances between every pair of points .
2------- take a point and see whether it has any two adjacent vertices which are at the same distance.
if (No)
then neglect that vertex as if it need to form a square it need atleast two vertices at same distance.
if (yes and multiple such kind of pairs exist like ab and ad are same distance and ac and ae are at same distance)
then take each pair say ab and ad , so we know b and d then check its distance if it is root(2) of ab or ad then
if(No)
then go to next pair ac and ae.
if (Yes)
so we know abd can be a part of square , so property of square is , if we know 3 vertices we can find 4th one easily in O(1).calculate and check it is there in given vertices if there then fine it is one of the square else leave it and do the same process again.

we can reduce the complexity by removing the checked ones , I mean when b is checked at vertex a then at vertex b no need of checking a again.

i think it will be O(n^3) . but not sure

Comment hidden because of low score. Click to expand.
0
of 2 vote

[Edit based on Alex's comment: The solution assumes that diagonal points of a square are enough to form squares. This does not work for the problem stated originally]
Maintain N series buckets and P series buckets.
N0 will contain all points(x,y) such that x-y=0
N1 will contain all points(x,y) such that x-y=1
Ni will contain all points(x,y) such that x-y=i

P0 will contain all points(x,y) such that x+y=0
P1 will contain all points(x,y) such that x+y=1
Pi will contain all points(x,y) such that x+y=i

For each bucket with size b, there are bC2(b choose 2) combinations of points that can combine to form a square.
Add these numbers for each bucket to get final number of squares possible.

O(n) time complexity. O(3n) space complexity as each point will be in both N and P buckets.

Comment hidden because of low score. Click to expand.
0

Consider the example:
(3,3), (4,4), (8,8),(9,9)
According to what you're sayin' there should be 4C2 squares, but I don't find even a single square formed by these points. Please explain to me where I am going wrong.

Comment hidden because of low score. Click to expand.
0

Oh, sorry, looks like I misinterpreted the question. I now wonder why I assumed diagonal points of a square are enough to form one. My solution works only for such scenarios. Sorry for the confusion.

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

Take a hashmap in which take N list one list having distance of one node to all other nodes,
Take an example first list for N1 node having distances of all other nodes then having list for N2 having just node of all other node except N1(N3 having node of every node except N2 and succesively now take N1-N2 distance from first list then check in N2 node list of same distance node to other node then if it close in N1 it form's squrae and check if before 3 iteration it forms graph it's not a square.

surely complexity is quite high.

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

We can solve this problem by taking combination ( nc4)
We are taking combination to avoid duplicate cordinates.
Lets store this cordinates in a list.
Example {a,b,c,d}--now from this points we can find 6 distances.
If 4 distances(lateral) are of equal size example |a-b|=|b-c|=|c-d|=|d-a|
and 2 distances (diagonal) are of equal size example |a-c|=|b-d| ... then we can say those cordinates form a sqare

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

I can think of the following:
Make an undirected graph of all the points.
When storing the edges, also include the length of the edge.
For each vertex, maintain a hashmap to save the edges based on distances.
This kind of data structure will greatly reduce the complexity.

Comment hidden because of low score. Click to expand.
0

Probably i don't get the task, but square is a rectangle which has 4 equal sides and 4 equal angles, so the test is fairly simple. it is to test for these two conditions, for each point

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

1> First you pick one pointer p1 from the list
2> Then you pick another pointer p2 from the rest of the list
3> using these two pointers as one side of the square to find out other possible two set of 2 pointers forming a square. If any of those pointer exists, store one solution.
4> Loop same logic through all of the pointer in the rest of the list
5> Then you remove P1 from the list, and start 1> again.
be noting:
1> There would be some repeat when searching, add some flag to avoid it.
2> You do not need to calculate the distance. You may need to perform vector rotate (p1-p2) rotate 90, or -90 to find 4 possible points.
3> A N Entry hash would be needed to check if the pointer is in the list.

Comment hidden because of low score. Click to expand.
0

Here is the python code:

``````origPtr=[(0,0), (1,0),(1,1), (0,1), (-1, -1), (-1,0), (-1,1), (0,-1), (1,-1), (3,6), (4, 9)];

foundSquare={};

origSet={};
for elem in origPtr:
origSet[elem]=None;
def     clockRotate(ptr1, ptr2):
ptr=(ptr2-ptr1+ptr1, ptr1-ptr2+ptr1);
return  ptr;
def     antiClockRotate(ptr1,ptr2):
ptr=(ptr1-ptr2+ptr1, ptr2-ptr1+ptr1);
return ptr;
def     orderPtr(ptr1, ptr2, ptr3,ptr4):
orderList=sorted([ptr1, ptr2, ptr3, ptr4]);
return tuple(orderList);
for index in range(len(origPtr)):
ptr1=origPtr[index];
for ptr2 in origPtr[index+1:]:
#left rotate:
ptr3=antiClockRotate(ptr2, ptr1);
ptr4=clockRotate(ptr1, ptr2);
if ptr3 in origSet.keys() and ptr4 in origSet.keys():
#print "found one clock square", ptr1, ptr2, ptr3, ptr4;
foundSquare[orderPtr(ptr1,ptr2,ptr3,ptr4)]=1;
#right rotate:
ptr3=clockRotate(ptr2, ptr1);
ptr4=antiClockRotate(ptr1, ptr2);
if ptr3 in origSet.keys() and ptr4 in origSet.keys():
#print "found one anti clock square", ptr1, ptr2, ptr3, ptr4;
foundSquare[orderPtr(ptr1,ptr2,ptr3,ptr4)]=1;

#print foundSquare;
for elem in foundSquare.keys():
print elem;``````

Comment hidden because of low score. Click to expand.
0

The time complexity: O(n2). Space is the O(n). No need for multiplex, but only a simple add/substract.

Comment hidden because of low score. Click to expand.
0

I don't think that the time complexity will be O(n2) since you can't find out the set of other pointers which form a square. How do you plan on finding it?

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

If points are (x1,y1) and (x2, y2), check
abs(x1-x2) equals abs (y1-y2).

if this matches, then those two points can make a square. do this for each combination ... O(n2). need to check if we can optimise the looping.

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

1.do a for loop check.
2. for each point, consider all the other points which are next to that point.
3.now, in each iteration we will have (x1,y1) and (x2,y2).
4. if y1==y2 means we can try to form square above or below these two points.
5. so calculate y3=x1-x2+y1(or y2) so the new points should be (x1,y3) and (x2,y3) which is to form the square above the line
5. calculate y4=x1-x2-y1(or y2), which will give (x1,y4) and (x2,y4) to form square below the line.
6.now check if you have all points to these two combinations.. that is( x1,y1 ),(x2,y2),(x1,y3),(x2,y3) or ( x1,y1 ),(x2,y2),(x1,y4),(x2,y4), if yes then store each combination as a key in hashmap.
7. for each iteration, check if the calculated combination is already there in hashmap, if not put else ignore.
8. at the end, we will have hashmap with keys as list of distinct points combination to form a square.
9. no of iteration would be n!. and space complexity to store in hashmap.

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.

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