Goldman Sachs Interview Question for Financial Software Developers


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)

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

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

- Biru January 30, 2013 | Flag
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.

- pandu.vdp January 30, 2013 | Flag
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.

- eugene.yarovoi January 30, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

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

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?

- OTR August 06, 2013 | Flag
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 ""

- Anonymous February 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

how about a diamond with edge of equal length.

- Passerby_A February 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

can you give the example for this question

- Anonymous January 30, 2013 | Flag Reply
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

- johnny January 31, 2013 | Flag Reply
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.

- td.abinesh February 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- alex February 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- td.abinesh February 04, 2013 | Flag
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.

- Anonymous February 05, 2013 | Flag Reply
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

- Mayur February 14, 2013 | Flag Reply
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.

- Varun March 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Alex March 24, 2013 | Flag
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.

- chenlc626 March 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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[1]-ptr1[1]+ptr1[0], ptr1[0]-ptr2[0]+ptr1[1]);
        return  ptr;
def     antiClockRotate(ptr1,ptr2):
        ptr=(ptr1[1]-ptr2[1]+ptr1[0], ptr2[0]-ptr1[0]+ptr1[1]);
        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;

- chenlc626 March 25, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- chenlc626 March 25, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- alex March 31, 2013 | Flag
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.

- Vishwanath June 27, 2013 | Flag Reply
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.

- Aishwarya May 14, 2016 | 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