Bloomberg LP Interview Question for Software Engineers


Country: United States
Interview Type: Written Test




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

My Approach

1. find the difference value i.e) cost to NY - cost to SF [200, -60, 50, 250]
2. choose the top 50 lowest values and assign to NY location [2rd, 3rd person]
3. Rest 50 candidates to SF location [1st and 4th person]

1. use 2D array to store index as key and difference as value
2. use priority queue to get top 50 lowest value from the array

- Popeye September 22, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

No sorting or priority queue is required. It is cheaper to just find a median in the difference value array using a selection algorithm like quick-select (linear time on average) and assign 50 people with values <= than the median to NY.

- adr September 23, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

genius!!

- Sourab.reddy2k14 November 27, 2018 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is how I'd solve it
1 sort the list with the min value of the two
2 add the NY cost if NY is min or sf cost if sf is min only until either of the counts become 50
3 on any one count (NY/SF) reaches 50 add the rest of the list to the other

public class MinSumBt2 {
    public static void main(String[] args) {
        ArrayList<CostPair> list = new ArrayList<>();
        
        try (Scanner in = new Scanner(new FileReader("inputMinSum"))) {
            while (in.hasNext()) {
                list.add(new CostPair(in.nextInt(), in.nextInt()));
            }
        }
        catch (FileNotFoundException e) {
            e.printStackTrace();
        }
        list.sort(CostPair::compareTo);
        System.out.println(list);
        int sum = 0;
        int countNY = 0;
        int countSF = 0;
        for (CostPair tmp : list) {
            if (countNY < 50 && countSF < 50) {
                if (tmp.isNYMin) {
                    sum += tmp.toNY;
                    countNY++;
                }
                else {
                    sum += tmp.toSF;
                    countSF++;
                }
            }
            else if (countNY < 50) {
                sum += tmp.toNY;
                countNY++;
            }
            else {
                sum += tmp.toSF;
                countSF++;
            }
        }
        System.out.println(sum);
    }
    
    static class CostPair implements Comparable<CostPair> {
        int toNY;
        int toSF;
        boolean isNYMin;
        
        CostPair(int toNY, int toSF) {
            this.toNY = toNY;
            this.toSF = toSF;
            isNYMin = toNY < toSF;
        }
        
        private int min() {
            return (toNY < toSF) ? toNY : toSF;
        }
        
        private int max() {
            return (toNY < toSF) ? toSF : toNY;
        }
        
        @Override
        public int compareTo(CostPair c) {
            if (min() == c.min())
                return c.max() - max();
            return min() - c.min();
        }
        
        @Override
        public String toString() {
            return "[" + toNY + "," + toSF + "]";
        }
    }
}

- PeyarTheriyaa September 22, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The idea is to sort the list of candidates based on the result of diff() method.
The top 50 go to NY, bottom 50 go to SF.

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class FlightScheduler {

    static class CostData {
        private final int id; // person id
        private final int toNy;
        private final int toSf;

        public CostData(int id, final int toNy,
                final int toSf) {
            this.id = id;
            this.toNy = toNy;
            this.toSf = toSf;
        }

        int diff() {
            return this.toNy - this.toSf;
        }

    }

    private static final int NUMBER_OF_PARTICIPANTS = 100;

    static CostData create(int id) {
        return new CostData(id, random(), random());
    }

    private static void evaluateAndPrint(
            List<CostData> data) {
        int sumToNy = 0;
        int sumToSf = 0;
        for (int i = 0; i < data.size(); i++) {
            CostData c = data.get(i);
            System.out.println(String.format(
                    "%6d [%6d, %6d]  diff=%6d", c.id,
                    c.toNy, c.toSf, c.diff()));
            if (i < data.size() / 2) {
                sumToNy += c.toNy;
            } else {
                sumToSf += c.toSf;
            }
        }
        System.out.println("----------------------");
        System.out.println(String.format(
                "       [%6d, %6d] total=%6d", sumToNy,
                sumToSf, sumToNy + sumToSf));
        System.out.println("----------------------");
    }

    public static void main(String[] args) {
        List<CostData> input = new ArrayList<CostData>();
        for (int i = 0; i < NUMBER_OF_PARTICIPANTS; i++) {
            input.add(create(i));
        }
        // Evaluate and print the input
        evaluateAndPrint(input);
        // Evaluate and print cost saving
        Collections.sort(input, new Comparator<CostData>() {

            @Override
            public int compare(CostData o1, CostData o2) {
                return (int) (o1.diff() - o2.diff());
            }
        });
        evaluateAndPrint(input);
    }

    static int random() {
        return (int) (Math.random() * 1000);
    }

}

- radobenc September 22, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.Comparator;
	import java.util.Iterator;
	import java.util.PriorityQueue;
	
	public class FindCheapFlights {
		public static void main(String args[]) {
			int[][] flightCharges = new int[3][2];
			flightCharges [0][0] = 500;
			flightCharges [0][1] = 600;
			flightCharges [1][0] = 300;
			flightCharges [1][1] = 400;
			flightCharges [2][0] = 700;
			flightCharges [2][1] = 900;
			findCheapFlights(flightCharges);
			
		}
	
		private static void findCheapFlights(int[][] flightCharges) {
			int countA = 0;
			int countB = 0;
			PriorityQueue<Integer> pq = new PriorityQueue<Integer>(4, (Comparator<? super Integer>) new CheapFLightComparator());
			
			for(int i = 0;i<3;i++)
			{	
				int cheapFlight = flightCharges[i][0] - flightCharges[i][1];
				if(cheapFlight<0 && countA<50)
				{
					pq.add(flightCharges[i][0]);
					System.out.println(flightCharges[i][0]+" is cheap");
					countA++;
				}
				else {
					pq.add(flightCharges[i][1]);
					System.out.println(flightCharges[i][1]+" is cheap");
					countB++;
				}				
			}
			for(Integer in : pq)
			{
				System.out.println(in);
			}
			
		}
	
	}
	 class CheapFLightComparator implements Comparator<Integer>{	
		@Override
		public int compare(Integer o1, Integer o2) {
			
				if(o1<o2)
				{
				return -1;
				}
				return 1;			
		}
	}

- TonyStark September 23, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Using the diff method does lower the code complexity

public class MinSumBt2 {
    public static void main(String[] args) {
        ArrayList<CostPair> list = new ArrayList<>();
        
        try (Scanner in = new Scanner(new FileReader("inputMinSum"))) {
            while (in.hasNext()) {
                list.add(new CostPair(in.nextInt(), in.nextInt()));
            }
        }
        catch (FileNotFoundException e) {
            e.printStackTrace();
        }
        list.sort(CostPair::compareTo);
        int sum = 0;
        for (int i = 0; i < 100; i++)
            sum += i < 50 ? list.get(i).toNY : list.get(i).toSF;
        System.out.println(sum);
    }
    
    private static class CostPair implements Comparable<CostPair> {
        int toNY;
        int toSF;
        int diff;
        
        CostPair(int toNY, int toSF) {
            this.toNY = toNY;
            this.toSF = toSF;
            diff = toSF - toNY;
        }
        
        @Override
        public int compareTo(CostPair o) {
            return diff - o.diff;
        }
    }
}

- PeyarTheriyaa September 24, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My Approach :

1. Copy the array into two arrays, say A and B.
2. Make a min Heap of A by the cost of moving the candidate to NY and a Min heap B by the cost of moving the candidate to SF.
3. Now compare the top of each min Heap A and B.
3 a. If the cost is same, take pop entry from both A and B and add the entry to the total cost
3 b. if the cost in A is less than that of B, pop the A top entry from both the min Heap A and B and add the entry to the total cost
3 c. if the cost of B is less that that of A, pop the B top entry from both the min Heap A and B and add the entry to the total cost.
4. if you remove a entry from A, increment conut_NY by 1 and count_SF by 1. When any one of them becomes 50, proceed by removing the rest elements from the other min Heap
5. When the count of both of them become 50, return the total cost.

- himanshukumar660 September 27, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//A DP solution - if you think that you can use any solution other than a DP one (aka - greedy) please prove that the greedy property exists.

int minCostToFly(const vector<pair<int,int> >&c){
    int size = c.size();

    if(size % 2){
        return INT_MAX;
    }

    vector<vector<int > > dp(size/2 + 1,vector<int>(size/2 + 1,INT_MAX));

    for(int sf = 0; sf <= size/2; ++sf){
        for(int ny = 0; ny <= size/2 ; ++ny){

            if(sf == 0 && ny == 0){
                dp[sf][ny] = 0;
                continue;
            }

            if(ny){
                dp[sf][ny] = min(dp[sf][ny],dp[sf][ny - 1] + c[sf + ny - 1].first);
            }

            if(sf){
                dp[sf][ny] = min(dp[sf][ny],dp[sf - 1][ny] + c[sf + ny - 1].second);
            }
        }
    }

    return dp[size/2][size/2];
}

- Guy September 28, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def minTravelCost(cost):
	scost = sorted(cost, key = lambda x: -(x[1] - x[0]))
	tot = 0
	mid = len(scost) // 2
	
	for i in range(mid):
		tot += scost[i][0]
	
	for i in range(mid + 1, len(scost)):
		tot += scost[i][1]
		
	if not len(scost) % 2:
		tot += scost[mid][1]
	else:
		tot += min(scost[mid][0], scost[mid][1])
	
	return tot

- Anon October 06, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def splitCands(*candidates):
    noof = len(candidates)
    assert noof%2 == 0, "We need even number of candidates, got " + str(noof)
    
    c=[*candidates]
    print(c)
    c.sort(key=lambda x: x[0]-x[1])
    print ("sorted")
    print(c)
    ny_part = c[:noof//2]
    sf_part = c[noof//2:]
    ny_sum = sum([c[0] for c in ny_part])
    sf_sum = sum([c[1] for c in sf_part])
    print("cost NY: %u\t %s"   % (ny_sum, ny_part))
    print("cost SF: %u\t %s\n" % (sf_sum, sf_part))
    
splitCands([100,50], [60,200])
splitCands([100,50], [200,50], [300,250], [400,150], [500,50], [100,850], [600,1200], [0,100])

Output:

[[100, 50], [60, 200]]
sorted
[[60, 200], [100, 50]]
cost NY: 60	 [[60, 200]]
cost SF: 50	 [[100, 50]]

[[100, 50], [200, 50], [300, 250], [400, 150], [500, 50], [100, 850], [600, 1200], [0, 100]]
sorted
[[100, 850], [600, 1200], [0, 100], [100, 50], [300, 250], [200, 50], [400, 150], [500, 50]]
cost NY: 800	 [[100, 850], [600, 1200], [0, 100], [100, 50]]
cost SF: 500	 [[300, 250], [200, 50], [400, 150], [500, 50]]

- Diana November 04, 2018 | 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