Bloomberg LP Interview Question


Country: United States




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

Given a list of points each of 2-d, here is the code:

public static void midPoints2D() {
    
    List<int[]> list = new ArrayList<int[]>();
    list.add( new int[]{4,5} );
    list.add( new int[]{8,9} );
    list.add( new int[]{1,2} );
    list.add( new int[]{4,6} );
    list.add( new int[]{3,8} );
    list.add( new int[]{8,4} );
    list.add( new int[]{9,2} );
    list.add( new int[]{8,5} );
    list.add( new int[]{8,1} );
    
    HashMap<String, List<int[]>> map = new HashMap<>();
    map.put("even-even", new ArrayList<int[]>() );
    map.put("even-odd", new ArrayList<int[]>() );
    map.put("odd-even", new ArrayList<int[]>() );
    map.put("odd-odd", new ArrayList<int[]>() );
    
    for ( int[] arr : list ) {
      if ( arr[0] % 2 == 0 && arr[1] % 2 == 0 ) {
        List<int[]> l = map.get("even-even");
        l.add(arr);
        map.put("even-even", l );
      } else if ( arr[0] % 2 == 0 && arr[1] % 2 != 0 ) {
        List<int[]> l = map.get("even-odd");
        l.add(arr);
        map.put("even-odd", l );
      } else if ( arr[0] % 2 != 0 && arr[1] % 2 == 0 ) {
        List<int[]> l = map.get("odd-even");
        l.add(arr);
        map.put("odd-even", l );
      } else {
        List<int[]> l = map.get("odd-odd");
        l.add(arr);
        map.put("odd-odd", l );
      }
    }
    System.out.println(map);
    // now values in all keys in the hashmap contains only those int[] which has midpoints
    for ( String key : map.keySet() ) {
      List<int[]> li = map.get(key);
      if ( li.size() > 1 ) {
        for (int i = 0 ; i < li.size(); ++i) {
          int [] arr1 = li.get(i);
          for (int j = i+1 ; j < li.size(); ++j) {
            int [] arr2 = li.get(j);
            System.out.print( "[" + arr1[0] + "," + arr1[1] + "] and " + "[" + arr2[0] + "," + arr2[1] + "] --> "  );
            System.out.print( "[" +  (arr1[0]+arr2[0])/2 + "," + (arr1[1]+arr2[1])/2  + "]\n" );
          }
        }
      }
    }
  }

- shekhar2010us March 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
4
of 6 vote

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

- mombasa February 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Killedsteel February 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

In this way, the time complexity should be O(5)=O(1), that means that you only need to check at most five pairs according to pigeonhole principle.

For N dimensional case, time complexity will be O(2^N), not matter how many elements are there.

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

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.

- Killedsteel February 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- GK February 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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]

- Ehsan February 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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");	

	}

}

- karpagaganesh March 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.");
    }
    
  }

- shekhar2010us March 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. use the mid point algorithm
2. check if mid point is a float

float x = (x1+x2)/2;
float y = (y1+y2)/2;

float check_x = x - (int)x;
float check_y = y - (int)y;

if(check_x != 0)
	return false;
else if (check_y != 0)
	return false;
else 
	return true;

- unknown March 31, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- bobthrollop April 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is brilliant. This means that the complexity is O(1), doesn't it?

- igorfactor June 28, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is actually obvious, and yes, people here are clueless to miss such an easy one...

- Anonymous June 28, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

No name-calling, please, especially since you didn't contribute anything.

- Anonymous June 28, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- PU May 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Web page badly escaped my code :)

To get it compiled remove char ; from line 56 and 57 (for loops), just before digit 2.

- PU May 10, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- im.code.warrior July 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- im.code.warrior July 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- im.code.warrior July 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- naomi.lijing@googlemail.com February 27, 2015 | 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