Goldman Sachs Interview Question
Financial Software DevelopersCountry: India
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).
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.
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.
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.
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 ""
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
[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.
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.
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.
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
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.
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.
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;
The time complexity: O(n2). Space is the O(n). No need for multiplex, but only a simple add/substract.
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.
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