Bloomberg LP Interview Question
Country: United States
Let's start from one dimensional points. In order for a pair of points to have an integer mid-point, both points should either be odd or even. Given a set of n odd (or even) points, there are nC2 pairs that have an integer mid-point. Time complexity is O(n) time for counting the number of odd/even points.
Scaling up to two-dimensional case: do the above operation for the x-axis; divide the given set into set_even and set_odd. For each set, do the same operation as above. Time complexity is O(2n) = O(n).
For N-dimensional case: the time complexity is also O(n).
1. Create a data structure called Pair {int x, y;} and assume that the input array comes in this format.
2. Initialize four variables of Type Pair to null. These four represent the four cases {Pair(evenX, evenY), Pair(evenX, oddY), Pair(oddX, evenY), Pair(oddX, oddY)}
3. Now start iterating over the input array of pairs. If you encounter a pair of a particular type from the four possible types listed above, set the respective Pair variable with those values.
4. There are 8 cases to consider here:
a1. while setting Pair(evenX, evenY), we discover that it was null - set it to current (X,Y)
a2. while setting Pair(evenX, evenY), we discover that it was not null - return this variable and current Pair(X,Y) as a solution
a3 & a4. same as a1 and a2, except for pairs of type Pair(oddX, oddY)
a5. while setting Pair(oddX, evenY), we discover that Pair(evenX, oddY) was null - set it to current(X,Y)
a6. while setting Pair(oddX, evenY), we discover that Pair(evenX, oddY) was not null - return this variable and current Pair(X, Y) as solution
a7 & a8. same as a5 and a6 but with "oddX" and "evenY" replaced by "evenX" and "oddY" and vice versa respectively.
This would be an O(n):O(1) solution in time:space.
Sorry for the partial answer. There is probably an extra step:
5. return error "no such occurrence of pairs found"
If this is N dimensional, then naturally the above approach breaks. It would then become O(2^n):O(2^n) in time:space. You can maybe then iterate over the input array, and compute the values for the midpoint for each of the N dimensions, for every M^2 combination of points. This would thus be a O(NM^2):O(N) solution in time:space.
Here is my idea.
It's pretty clear, that pair of numbers has integer mid-value, if sum of these digits is even.
There are two good ways for us: both of numbers are even or both of numbers are odd.
Now we can associate each point to bit vector. F.e. (3,4,5,6) = (3%2,4%2,5%2,6%2) =(1,0,1,0) (binary system) = 10 (decimal system)
Now we should group each point by it's decimal representation, we may use dictionary for example.
class Point
{
public List<int> Dots { get; set; }
public override string ToString()
{
return String.Format("({0})",String.Join(",",Dots));
}
}
class Program
{
public static void FindPairs(List<Point> points)
{
var pairs = new Dictionary<int, List<Point>>();
foreach (var point in points)
{
var val = 0;
var temp = 1;
point.Dots.ForEach(dot =>
{
if (dot%2 == 1)
{
val += temp;
}
temp *= 2;
});
if (pairs.ContainsKey(val))
pairs[val].Add(point);
else
pairs.Add(val , new List<Point>{point});
}
foreach (var pair in pairs.Where(pair => pair.Value.Count > 1))
{
foreach (var point in pair.Value)
{
Console.WriteLine(point.ToString());
}
Console.WriteLine();
}
}
}
If by "mid-point", you mean a point exactly in the middle, then all you need to check is whether (x1 + x2) % 2 == 0 and (y1 + y2) % 2 == 0. For "N" dimensions, it will be O(N) to determine whether or not this happens.
If mid-point is "some" point on the line segment connecting the two given points. It will be quite harder to determine. If X = [x1, x2, ..., xN] and y = [y1, y2, ..., yN], then you can do this in O(D N) where D = min(abs(xi - yi)). I don't know if faster is possible:
Here is the code for the second case:
def midPoint(point_a, point_b):
d = 10000000;
N = len(point_a)
index = -1
for n in range(0, len(point_a)):
diff = point_a[n] - point_b[n]
if diff < 0:
diff = -diff
if diff < d:
d = diff
index = n
DX = point_b[index] - point_a[index]
for inc in range(1, d):
didnt_work = False
for i in range(0, N):
if i == index:
continue
dy = point_b[i] - point_b[i]
dx = inc
if ((dy * dx) % DX):
didnt_work = True
break
if not didnt_work:
point_c = point_a
for n in range(0, N):
point_c[n] = (point_b[n] - point_a[n]) * inc / DX + point_c[n]
print point_c
if __name__ == '__main__':
line = raw_input("Point A (blank space separated. RET after last.): ")
x = line.split(" ")
line = raw_input("Point B (blank space separated.RET after last.): ")
y = line.split(" ")
if len(x) != len(y):
print "Points have different dimensions. Exit -1"
exit(-1)
point_a = []
point_b = []
for n in range(0, len(x)):
point_a.append(int(x[n]))
point_b.append(int(y[n]))
midPoint(point_a, point_b)
Test:
Point A (blank space separated. RET after last.): 4 9 13 2 -5 12
Point B (blank space separated.RET after last.): 9 19 28 22 20 2
[5, 11, 16, 6, 0, 10]
[6, 14, 20, 12, 8, 6]
[7, 17, 24, 18, 15, 3]
[8, 18, 27, 21, 19, 2]
public class pairofPoints {
public static void main(String[] args) {
int[] pair1 = {1,1};
int[] pair2 = {3,3};
float x=0,y=0;
x = ((float)pair1[0] + (float)pair2[0])/2;
y = ((float)pair1[1] + (float)pair2[1])/2;
if((Math.floor(x) == Math.ceil(x)) && (Math.floor(y) == Math.ceil(y))){
System.out.println("Have Integer Mid Point");
}
else
System.out.println("Dont Have Integer Mid Point");
}
}
If the definition of mid point is exact "integer" value for the average of the point values, here is a solution for the n-dimension point. Though it does compare only two points.
public static class PointND {
public int[] arr;
public PointND() {}
}
public static void midPoints() {
int [] data1 = {2,2,8,5,9};
int [] data2 = {8,4,4,7,11};
PointND p1 = new PointND();
p1.arr = data1;
PointND p2 = new PointND();
p2.arr = data2;
boolean midPFound = true;
if ( p1.arr.length == p2.arr.length ) {
int [] midPoint = new int[p1.arr.length];
for ( int i = 0 ; i < p1.arr.length; ++i ) {
double mid = ( (double)p1.arr[i] + (double)p2.arr[i] )/2;
if ( mid == (p1.arr[i] + p2.arr[i])/2 ) {
midPoint[i] = (int)mid;
} else {
System.out.println("No Mid point found.");
midPFound = false;
break;
}
}
if (midPFound) {
System.out.println("Mid point is: " );
for ( int a : midPoint ) {
System.out.print(a + " ");
}
System.out.print("\n");
}
} else {
System.out.println("Unequal dimensions of points.");
}
}
No one has pointed out yet that you need examine at most 5 points, no matter how long the input list is. Two points have an integer midpoint if the X values are either both even or both odd, and ditto for the Y values. There are 4 different permutations of even-odd for both X and Y, and therefore if you examine 4 points and haven't found a match, you have exhausted all the possibilities and the 5th point must match one of them.
For N dimensions, the worst-case number to examine would be 2^N+1.
This is actually obvious, and yes, people here are clueless to miss such an easy one...
// C++
//
// Background:
// Given a set of integer dots (like (1,5)).
// How can you find a pair that has an integer mid-point?
// For example,
// (1,1) and (3,3) have an integer mid-point of (2,2)
// (1,1) and (3,2) do not have an integer mid-point (2, 1.5)
//
// Problem:
// In given array of points, count all
// pairs of points which have an integer mid-point;
//
// Ex: a[0] = Point(1,1),
// a[1] = Point(1,3),
// a[2] = Point(3,3),
// a[3] = Point(2,2),
// a[4] = Point(3,2)
//
// Pairs with integer mid-point:
// a[0] and a[1] : mid point(1,2)
// a[0] and a[2] : mid point(2,2)
// a[1] and a[2] : mid point(2,3)
// So count = 3
//
//-------------------------
// Solution
//
// algorithm complexity: O(n)
// space complexity: O(2^d)
// where d = dots dimensional count
//
// author: przemek urbanski
#include <iostream>
#include <vector>
#include <math.h>
//-----------------------------------------
using namespace std;
//-----------------------------------------
typedef pair<int,int> Point;
typedef vector<Point> Vec;
int combination(int n);
//-----------------------------------------
int solution(const Vec& v)
{
unsigned int pair[2][2] = {{0},{0}};
for (unsigned int i=0; i<v.size(); i++)
{
int a= v[i].first % 2;
int b =v[i].second % 2;
pair[a][b]++;
}
int total = 0;
for (int i=0; i<2; i++)
for (int j=0; j<2; j++)
{
total += combination( pair[i][j] );
// cout << "point: " << i <<":" << j ;
// cout << ", count: "<< pair[i][j] ;
// cout << ", sum: " << combination( pair[i][j] );
// cout << ", total: " << total << endl;
}
return total;
}
//-----------------------------------------
int combination(int n)
{
return ( pow(n,2) - n ) / 2;
}
//----------------------------------------------
int main()
{
Vec v;
v = { Point(1,1),
Point(1,3),
Point(3,3),
Point(2,2),
Point(3,2)};
cout << solution(v) << endl;
}
//----------------------------------------------
As explained above for 2D, you have to examine atmost 5 points and for N-dimension, at most 2^N+1.
Algo to find the actual point:
For 2-D, sum of x-axis co-ordinates and y-co-ordinates should be even.
Consider a binary representation with 0 denoting even and 1 for odd. So a point can have 4 values 00,01,10,11 corresponding to both (x,y) even, (x even, y odd), (x odd, y even) and (1,1) will be both odd.
Traverse the set and as you see each point, assign a value(0,1,2 or 3) to the co-ordinate. When you find a point which also the same value, you found a matching point.
For n-dimension, instead of 00 to 11, you would have 0...0 (n zeroes) to 1...1 (n ones). i.e integer values 0 to 2^N-1. With a similar approach, you have to find if 2 points have the same value.
As explained above for 2D, you have to examine atmost 5 points and for N-dimension, at most 2^N+1.
Algo to find the actual point:
For 2-D, sum of x-axis co-ordinates and y-co-ordinates should be even.
Consider a binary representation with 0 denoting even and 1 for odd. So a point can have 4 values 00,01,10,11 corresponding to both (x,y) even, (x even, y odd), (x odd, y even) and (1,1) will be both odd.
Traverse the set and as you see each point, assign a value(0,1,2 or 3) to the co-ordinate. When you find a point which also the same value, you found a matching point.
For n-dimension, instead of 00 to 11, you would have 0...0 (n zeroes) to 1...1 (n ones). i.e integer values 0 to 2^N-1. With a similar approach, you have to find if 2 points have the same value.
As explained above for 2D, you have to examine atmost 5 points and for N-dimension, at most 2^N+1.
Algo to find the actual point:
For 2-D, sum of x-axis co-ordinates and y-co-ordinates should be even.
Consider a binary representation with 0 denoting even and 1 for odd. So a point can have 4 values 00,01,10,11 corresponding to both (x,y) even, (x even, y odd), (x odd, y even) and (1,1) will be both odd.
Traverse the set and as you see each point, assign a value(0,1,2 or 3) to the co-ordinate. When you find a point which also the same value, you found a matching point.
For n-dimension, instead of 00 to 11, you would have 0...0 (n zeroes) to 1...1 (n ones). i.e integer values 0 to 2^N-1. With a similar approach, you have to find if 2 points have the same value.
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
ArrayList<int[]> list = new ArrayList<int[]>();
list.add( new int[]{4,5} );
list.add( new int[]{9,9} );
list.add( new int[]{1,2} );
findPairWithMidpoint(list);
}
public static boolean isEven(int x){return x%2==0?true:false;}
public static void findPairWithMidpoint(ArrayList<int[]> list)
{
int[] pair = list.get(0);
int j = 0, len = list.size();
for(int i=1; i<len; i++)
{
int[] pair2 = list.get(i);
int x1,x2,y1,y2;
x1 = isEven(pair[0])?0:1;
y1 = isEven(pair[1])?0:1;
x2 = isEven(pair2[0])?0:1;
y2 = isEven(pair2[1])?0:1;
if((((x1^x2)!=1)&&((y1^y2)!=1)))
{
System.out.println("("+pair[0]+","+pair[1]+")");
System.out.println("("+pair2[0]+","+pair2[1]+")");
return;
}
else if(i == len-1)
{
if(++j<len-1)
{
pair = list.get(j);
i = j;
}
else
{
System.out.println("NONE");
return;
}
}
}
System.out.println("NONE");
return;
}
}
Given a list of points each of 2-d, here is the code:
- shekhar2010us March 11, 2014