Bloomberg LP Interview Question for Software Engineer / Developers


Country: United States
Interview Type: Phone Interview




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

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)])
```

- Rejith January 02, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

typedef 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;
}

- mirak94 December 31, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- fanwei918 December 26, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String args[]){

int numberofPoints = 7;
int pointsinRectangle=4;
//we need to choose 4 points out of 7 points (nCr i.e 7C4 )

int numberofRectangles = 7*6*5*4*3*2*1/4*3*2*1 * (3*2*1)

}

- Puneet Goyal December 27, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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 + "]";
}
}
}

- Anonymous December 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Siddharth December 29, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Rejith January 02, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Rejith January 02, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Rejith January 02, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Rejith January 02, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Jed January 06, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
        }

- vh.vahan February 03, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
        }

- vh.vahan February 03, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Shekhar Agrawal February 05, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Danno February 08, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Shashank Sharma April 12, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- robertgbjones April 17, 2017 | 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