Bloomberg L.P.

## Interview Question

Senior Software Engineer Interview

-

# There will be a meeting at New York and San Francisco offices. We will have to fly the participants to either one of these two offices. Let's say each office can accommodate half of the participants. Our goal is to assign each participant to an office in a way that the total travel cost for the company is minimized. What is this minimal cost? SF NY A 500 700 B 200 600 C 400 500 D 600 200 Output : 1400 (A:500 + B:200 + C:500 +D: 200)

2

Can you give an high level solution which you arrived at the end? I am curious to know the solution 😊

Anonymous on

0

The solution was something like: Look for the candidates that have a bigger difference in cost first (in this case B and D since the difference for the price to each office are 400), choose the cheaper option for those. After one of the offices is full then just choose whatever spot is left.

Anonymous on

0

I would use a Min Heap for SF of size = no. of candidates / 2 . k = no. of candidates / 2 ; for(int i : SFcosts){ minHeap.offer(i); if(minHeap.size() > k){ minHeap.poll(); } } // so at the end we have half candiates with minimum cost for SF then remaining will go ti NY

Anonymous on

0

It is an optimization problem and hence I believe we can use dynamic programming. Let's say we have Minimum cost of place 2i-2 candidates then cost of placing 2i candidates is: MinCost(2i) = MinCost(2(i-1)) + Min(Cost(c1,l1) + Cost(c2, l2), Cost(c1,l2) + Cost(c2, l1)); c1 ,c2-> next two candidates. l1, l2 -> locations

Anonymous on

0

Here is what I ended up with (C#). The result is 1300 (it's better than the one provided in the question: B 200 D 200 A 500 C 400 class Program { static void Main(string[] args) { List arr = new List { new Pair("A",500,700), new Pair("B",200,600), new Pair("C",400,500), new Pair("D",600,200) }; while (arr.Count > 0) { Pair p = arr.OrderByDescending(x => x.GetDiff()).First(); Console.WriteLine(p.name + " " + p.GetMin().ToString()); arr.Remove(p); } Console.ReadKey(); } class Pair : IComparable { public Pair(string n, int p1, int p2) { name = n; priceNY = p1; priceSF = p2; } int priceNY; int priceSF; internal string name; internal int GetDiff() { return Math.Abs(priceSF - priceNY); } internal int GetMin() { return Math.Min(priceNY, priceSF); } public int CompareTo(object p) { Pair pr = p as Pair; if (pr != null) { return Convert.ToInt32(this.GetDiff() > pr.GetDiff()); } return 0; } } }

Timur on

0

It is an optimization problem. Intuition: let S1, S2 be the sets for city1 and city2. start assigning people to S1 and S2 based on which is lowest. then three cases, S1 = S2, S1 > S2 and vice versa. If S2 = S1 done. other cases: select member with min cost to city2 and push it to S2, repeat until S1 = S2. This is a greedy approach.

Krishna on

0

@Timur Your code actually violates the requirement that each office can only accomodate up to half of the candidates. In this case, you put 3 candidates (including B) into SF while only 1 in NY.

Anonymous on

0

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 if __name__ == '__main__': # Costs are in format of [(SF, NY)] print(minTravelCost([(500, 700), (200, 600), (400, 500), (600, 200)]))

Anonymous on

0

public class MinimumFlightCost { public static void main(String[] args) { List sf = new ArrayList(); List ny = new ArrayList(); sf.add(new Office(500, "A")); sf.add(new Office(200, "B")); sf.add(new Office(400, "C")); sf.add(new Office(600, "D")); ny.add(new Office(700, "A")); ny.add(new Office(600, "B")); ny.add(new Office(500, "C")); ny.add(new Office(200, "D")); List sfResult = new ArrayList(); List nyResult = new ArrayList(); Map cache = new HashMap(); List diff = new ArrayList(); for (int i = 0; i ofc.cost) return 1; return -1; } } }

GK on

0

You can sort the array in ascending order of the difference. Then for the first half pick the second index. Then pick the first index for second half

BlackDev on