Bloomberg LP Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
O^2 solution for every pair of points, check if the 2 complementary points exist. To make the lookups faster build a x y map, and list of existing rectangles found
```
import hashlib
def hash(p1, p2):
if p2[0] > p1[0]:
p1, p2 = p2, p1
return hashlib.sha256(str(p1[0]) + "," + str(p1[1]) + "," + str(p2[0]) + "," + str(p2[1])).hexdigest()
def rect(points):
x_y_map = {}
y_x_map = {}
existing_rectangles = set([])
for point in points:
if point[0] not in x_y_map:
x_y_map[point[0]] = set([point[1]])
else:
x_y_map[point[0]].add(point[1])
count = 0
for point1 in points:
for point2 in points:
if point1 != point2 and point1[0] != point2[0] and point1[1] != point2[1]:
if point1[0] in x_y_map and point2[1] in x_y_map[point1[0]] and point2[0] in x_y_map and point1[1] in x_y_map[point2[0]]:
if hash(point1, point2) not in existing_rectangles and hash((point1[0], point2[1]), (point2[0], point1[1])) not in existing_rectangles:
existing_rectangles.add(hash(point1, point2))
print (point1, point2)
count += 1
print count
rect([(0,0), (1,0), (0,1), (1,1), (0,2), (2,2), (1,2)])
```
An idea: the condition that 4 points compose a rectangle is: take any 1 of the 4 as origin, the vectors from the origin to each of other 3 points, say v1, v2, v3, saistifies v1^2=v2^2+V3^2.(order 1,2,3 could be altered)
if the condition is correct, (may be not,still working on), the psedo code could be:
1.group all nodes in sets of 4. (no duplicating sets, i.e. "a b c d" considered the same set with "d a c b" ).
2. calculate the number of rectangles:
for each set
get 3 vectors
test if their magnitude satisfy the condition: biggest^2=medium^2+smallest^2
yes: number of rectangle +1
for loop end
public class NumberofRectangle {
public static void main(String[] args) {
Point[] points = new Point[8];
points[0] = new Point(0, 0);
points[1] = new Point(0, 1);
points[2] = new Point(0, 2);
points[3] = new Point(1, 0);
points[4] = new Point(1, 1);
points[5] = new Point(1, 2);
points[6] = new Point(2, 1);
points[7] = new Point(2, 2);
int num = getNumRectangles(points);
System.out.println("Number of Rectangles is : " + num);
}
private static int getNumRectangles(Point[] points) {
if (points.length < 4) {
return 0;
}
int numRectangles = 0;
for (int p1 = 0; p1 < points.length; p1++) {
for (int p2 = p1 + 1; p2 < points.length; p2++) {
for (int p3 = p2 + 1; p3 < points.length; p3++) {
for (int p4 = p3 + 1; p4 < points.length; p4++) {
if (points[p1].getX() == points[p2].getX() && points[p3].getX() == points[p4].getX()
&& points[p1].getY() == points[p3].getY() && points[p2].getY() == points[p4].getY()) {
numRectangles++;
System.out.println("Rectange with " + points[p1] + points[p2] + points[p3] + points[p4]);
}
}
}
}
}
return numRectangles;
}
static class Point {
private int x;
private int y;
Point(int x, int y) {
this.x = x;
this.y = y;
}
public int getX() {
return x;
}
public int getY() {
return y;
}
@Override
public String toString() {
return "Point [x=" + x + ", y=" + y + "]";
}
}
}
An approach to this problem can be to calculate the slope and the distance between every pair of points and store them in HashMap. Then
1. Select a pair from the hashmap
2. Go through the hashmap and look for pairs with the same distance and slope.
3. If found, search for 2 pairs of points with same slopes such that the new slope multiplied by the step1 slope is -1.
4. If found increment count
Though I think this approach would work, the running time would be O(n^4).
Do correct me if anything wrong.
O^2 solution, for each pair of points, check if the complementary points exist or not
and then count. Keep an x_y map for easy lookups, and a hsh value of rectangles for
duplicate prevention
import hashlib
X = 0
Y = 1
def hash(p1, p2):
if p2[X] > p1[X]:
p1, p2 = p2, p1
return hashlib.sha256(str(p1[X]) + "," + str(p1[Y]) + "," + str(p2[X]) + "," + str(p2[Y])).hexdigest()
def rect(points):
x_y_map = {}
y_x_map = {}
existing_rectangles = set([])
for point in points:
if point[X] not in x_y_map:
x_y_map[point[X]] = set([point[Y]])
else:
x_y_map[point[X]].add(point[Y])
count = 0
for point1 in points:
for point2 in points:
if point1 != point2 and point1[X] != point2[X] and point1[Y] != point2[Y]:
if point1[X] in x_y_map and point2[Y] in x_y_map[point1[X]] and point2[X] in x_y_map and point1[Y] in x_y_map[point2[X]]:
if hash(point1, point2) not in existing_rectangles and hash((point1[X], point2[Y]), (point2[X], point1[Y])) not in existing_rectangles:
existing_rectangles.add(hash(point1, point2))
print (point1, point2)
count += 1
print count
rect([(0,0), (1,0), (0,1), (1,1), (0,2), (2,2), (1,2)])
O^2 solution, for each pair of points, check if the complementary points exist or not
and then count. Keep an x_y map for easy lookups, and a hsh value of rectangles for
duplicate prevention
import hashlib
X = 0
Y = 1
def hash(p1, p2):
if p2[X] > p1[X]:
p1, p2 = p2, p1
return hashlib.sha256(str(p1[X]) + "," + str(p1[Y]) + "," + str(p2[X]) + "," + str(p2[Y])).hexdigest()
def rect(points):
x_y_map = {}
y_x_map = {}
existing_rectangles = set([])
for point in points:
if point[X] not in x_y_map:
x_y_map[point[X]] = set([point[Y]])
else:
x_y_map[point[X]].add(point[Y])
count = 0
for point1 in points:
for point2 in points:
if point1 != point2 and point1[X] != point2[X] and point1[Y] != point2[Y]:
if point1[X] in x_y_map and point2[Y] in x_y_map[point1[X]] and point2[X] in x_y_map and point1[Y] in x_y_map[point2[X]]:
if hash(point1, point2) not in existing_rectangles and hash((point1[X], point2[Y]), (point2[X], point1[Y])) not in existing_rectangles:
existing_rectangles.add(hash(point1, point2))
print (point1, point2)
count += 1
print count
rect([(0,0), (1,0), (0,1), (1,1), (0,2), (2,2), (1,2)])
O^2 solution, for each pair of points, check if the complementary points exist or not
and then count. Keep an x_y map for easy lookups, and a hsh value of rectangles for
duplicate prevention
import hashlib
X = 0
Y = 1
def hash(p1, p2):
if p2[X] > p1[X]:
p1, p2 = p2, p1
return hashlib.sha256(str(p1[X]) + "," + str(p1[Y]) + "," + str(p2[X]) + "," + str(p2[Y])).hexdigest()
def rect(points):
x_y_map = {}
y_x_map = {}
existing_rectangles = set([])
for point in points:
if point[X] not in x_y_map:
x_y_map[point[X]] = set([point[Y]])
else:
x_y_map[point[X]].add(point[Y])
count = 0
for point1 in points:
for point2 in points:
if point1 != point2 and point1[X] != point2[X] and point1[Y] != point2[Y]:
if point1[X] in x_y_map and point2[Y] in x_y_map[point1[X]] and point2[X] in x_y_map and point1[Y] in x_y_map[point2[X]]:
if hash(point1, point2) not in existing_rectangles and hash((point1[X], point2[Y]), (point2[X], point1[Y])) not in existing_rectangles:
existing_rectangles.add(hash(point1, point2))
print (point1, point2)
count += 1
print count
rect([(0,0), (1,0), (0,1), (1,1), (0,2), (2,2), (1,2)])
O^2 solution, for each pair of points, check if the complementary points exist or not
and then count. Keep an x_y map for easy lookups, and a hsh value of rectangles for
duplicate prevention
import hashlib
X = 0
Y = 1
def hash(p1, p2):
if p2[X] > p1[X]:
p1, p2 = p2, p1
return hashlib.sha256(str(p1[X]) + "," + str(p1[Y]) + "," + str(p2[X]) + "," + str(p2[Y])).hexdigest()
def rect(points):
x_y_map = {}
y_x_map = {}
existing_rectangles = set([])
for point in points:
if point[X] not in x_y_map:
x_y_map[point[X]] = set([point[Y]])
else:
x_y_map[point[X]].add(point[Y])
count = 0
for point1 in points:
for point2 in points:
if point1 != point2 and point1[X] != point2[X] and point1[Y] != point2[Y]:
if point1[X] in x_y_map and point2[Y] in x_y_map[point1[X]] and point2[X] in x_y_map and point1[Y] in x_y_map[point2[X]]:
if hash(point1, point2) not in existing_rectangles and hash((point1[X], point2[Y]), (point2[X], point1[Y])) not in existing_rectangles:
existing_rectangles.add(hash(point1, point2))
print (point1, point2)
count += 1
print count
rect([(0,0), (1,0), (0,1), (1,1), (0,2), (2,2), (1,2)])
Here's a simple solution (not super efficient but it works):
import itertools
import math
def distance(p0, p1):
return math.sqrt((p0[0] - p1[0])**2 + (p0[1] - p1[1])**2)
def collinear(p1,p2,p3):
return (p1[1] - p2[1]) * (p1[0] - p3[0]) != (p1[1] - p3[1]) * (p1[0] - p2[0])
def pythagorasCalc (array):
sides = sorted([distance(array[0],array[1]),distance(array[0],array[2]),distance(array[1],array[2])],reverse=True)
return abs(sides[0]**2 - (sides[1]**2+sides[2]**2))<0.0001 and (collinear(array[0],array[1],array[2]) )
A = [(0,0), (1,0), (0,1), (1,1), (0,2), (2,2), (1,2)]
# look for subsets of 4 (total of "7 choose 4" (=35 items) to froam possible squares
m = 4
L = set(itertools.combinations(A, m))
numOfSq = 0
for seq in L:
possibleSq = list(seq)
# check if the other 3 form a Pythagoras threesome
possibleTri = set(itertools.combinations(possibleSq, 3))
for idx,tri in enumerate(possibleTri):
if (pythagorasCalc(list(tri))) == False:
idx =- 1
break
if idx == 3:
numOfSq += 1
print "Squre:",possibleSq
print "Number of squares",numOfSq
public struct Point
{
public int X { get; set; }
public int Y { get; set; }
public Point(int x, int y)
{
X = x;
Y = y;
}
}
public static int RectanglesCount(List<Point> points)
{
Dictionary<int, HashSet<int>> dic = new Dictionary<int, HashSet<int>>();
foreach (var item in points)
{
if (dic.ContainsKey(item.Y))
dic[item.Y].Add(item.X);
else
dic.Add(item.Y, new HashSet<int>() { item.X });
}
int cnt = 0;
int[] ycoords = dic.Keys.OrderBy(i => i).ToArray();
for (int i = 0; i < ycoords.Length; i++)
{
for (int j = i+1; j < ycoords.Length; j++)
{
cnt += dic[i].Intersect(dic[j]).Count() / 2;
}
}
return cnt;
}
The complexity is o(n^2)
create dictionary where key is Y coordinate and values are Hashset of X coordinates.
public struct Point
{
public int X { get; set; }
public int Y { get; set; }
public Point(int x, int y)
{
X = x;
Y = y;
}
}
public static int RectanglesCount(List<Point> points)
{
Dictionary<int, HashSet<int>> dic = new Dictionary<int, HashSet<int>>();
foreach (var item in points)
{
if (dic.ContainsKey(item.Y))
dic[item.Y].Add(item.X);
else
dic.Add(item.Y, new HashSet<int>() { item.X });
}
int cnt = 0;
int[] ycoords = dic.Keys.OrderBy(i => i).ToArray();
for (int i = 0; i < ycoords.Length; i++)
{
for (int j = i+1; j < ycoords.Length; j++)
{
cnt += dic[i].Intersect(dic[j]).Count() / 2;
}
}
return cnt;
}
get all distinct x
for each pairs of x
get all possible y's for the two x => two list (list1), (list2)
(list) = intersection of (list1), (list2)
rectangles = x1,x2 and all pairs in (list)
e.g.
0,0
1,0
0,1
1,1
0,2
2,2
1,2
all x = {0 1 2}
case 1
x = 0,1
for x = 0 list for y - 0, 1, 2
for x = 1 list for y - 0, 1, 2
intersection - 0, 1, 2
rectangles: x1=0, x2=1, y1,y2 = 0,1 ; 1,2 ; 0,2 === 3 rectangles
case 2
x = 0,2
for x = 0 list for y - 0, 1, 2
for x = 2 list for y - 2
intersection - 2
rectangles: x1=0, x2=2, y1,y2 = none === 0 rectangles
case 3
x = 1,2
for x = 1 list for y - 0, 1, 2
for x = 2 list for y - 2
intersection - 2
rectangles: x1=1, x2=2, y1,y2 = none === 0 rectangles
total 3 rectangles
I hope this is right.
def find_rects(points):
rows = {}
for point in points:
p_row = point[0]
p_col = point[1]
if p_row not in rows:
rows[p_row] = []
for column in rows[p_row]:
for row, cols in rows.items():
if row == p_row:
continue
if column in cols and p_col in cols:
yield ((p_row, p_col), (p_row, column), (row, column), (row, p_col))
rows[point[0]].append(point[1])
Here's a C++ solution that works in O(n^2) time.
- Inputs are in the form for vector of pairs of points (x,y)
- All points are first stored in a hash map
- Now take one point(p1) from the list of points and look a point(p2) that can potentially be the diagonally opposite corner of a rectangle. It(p2) should have both coordinates different from the point in consideration(p1).
- Once we have a pair of diagonally opposite points(p1 & p2), we can look for other two points(p3 & p4) completing a rectangle by looking in the hashmap the points formed by combination of p1 & p2 coordinates.
int getRectangles(vector<pair<int,int>>& v){
if(v.size()<=3){
return 0;
}
int numOfRectangles=0;
map<pair<int,int>,bool> m;
for(int i=0;i<v.size();i++){
m[v[i]]=true;
}
for(int i=0;i<v.size();i++){
pair<int,int> p1=v[i];
for(int j=i+!;j<v.size();j++){
pair<int,int> p2=v[j];
if((get<0>(p1) != get<0>(p2)) && (get<0>(p1) != get<0>(p2))){
pair<int,int> p3(get<0>(p1),get<1>(p2));
pair<int,int> p4(get<0>(p2),get<1>(p1));
if(m[p3] && m[p4]){
numOfRectangles++;
}
}
}
}
return numOfRectangles;
}
Please do provide comments on the approach.
Here's a basic solution. Order( n^3 ) runtime. To improve algorithmic complexity the points should be indexed, possibly with a map/set combination.
struct point
{
point( int x, int y ) : x( x ), y( y ) { }
int x { 0 };
int y { 0 };
};
bool operator ==( const point & lhs, const point & rhs ) { return lhs.x == rhs.x && lhs.y == rhs.y; }
int no_of_rectangles( const std::vector<point> & vertices )
{
using namespace std;
int result = 0;
for ( auto anchor = vertices.begin( ); anchor != vertices.end( ); ++ anchor )
{
for ( auto opposite = anchor + 1; opposite != vertices.end( ); ++ opposite )
{
if ( ( anchor -> x != opposite -> x ) && ( anchor -> y != opposite -> y ) )
{
if (
find( vertices.begin( ), vertices.end( ), point( anchor -> x, opposite -> y ) ) != vertices.end( ) &&
find( vertices.begin( ), vertices.end( ), point( opposite -> x, anchor -> y ) ) != vertices.end( ) )
++ result;
}
}
}
return result / 2;
}
Here is O(n^3) solution. I loop through all the triplets of points, looking for only points that may form rectangle in clockwise order, meaning that we first hold the top_left point, then look for the top_right, then look for the bottom_right, finally look for the bottom_right, using math we deduce the position of the missing point and check if we have already this point given in the input points.
This may not give us duplicate rectangles because of the way we look for the rectangle in the set.
- mirak94 December 31, 2016typedef pair<double, double> dd; double oo = 10000000000000.0; struct Point{ double x,y; Point(double x, double y){ this->x = x; this->y = y; } }; Point* get_missing_point(Point* top_left, Point* top_right, Point* bottom_right, double m1, double m2){ // m1 is the slope of line (top_left <--> top_right) // m2 is the slope of line (top_left <--> bottom_left) double ck = bottom_right->y - m1 * bottom_right->x; double ci = top_left->y - m2 * top_left->x; double x_bottom_left = (ci-ck) / (m1-m2); double y_bottom_right = m1*x_bottom_left + ck; return new Point(x_bottom_left, y_bottom_right); } double get_slope(Point* p, Point* q){ double dy = p->y-q->y; double dx = p->x-q->x; if (dx == 0) { return oo; } return dy/dx; } bool is_perpendicular(double m1, double m2){ if(m1 == oo || m2 == oo){ return m1*m2 == 0.0; } return m1*m2 == -1.0; } double get_line_length(Point* p, Point* q){ return sqrt( pow(p->x - q->x, 2) + pow(p->y - q->y, 2)); } int count_rectangles(vector<Point*>& points){ unordered_set<dd> vis; for(Point* p : points){ vis.insert({p->x, p->y}); } int rec_cnt = 0; int n = (int)points.size(); for(int i=0; i<n; i++){ for(int j=0; j<n; j++){ if(points[j]->x <= points[i]->x){ continue; } double m1 = get_slope(points[i], points[j]); for(int k=0; k<n; k++){ if(points[k]->y >= points[j]->y){ continue; } double m2 = get_slope(points[j], points[k]); if(is_perpendicular(m1, m2)){ Point* missing_point = NULL; if(m2 == oo){ missing_point = new Point(points[k]->x-get_line_length(points[i], points[j]), points[k]->y); }else{ missing_point = get_missing_point(points[i], points[j], points[k], m1, m2); } if(vis.count({missing_point->x, missing_point->y})){ rec_cnt++; } } } } } return rec_cnt; }