Bloomberg LP Interview Question Software Engineers
Country: United States
Interview Type: Written Test
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.
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 + "]";
}
}
}
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);
}
}
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;
}
}
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;
}
}
}
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.
//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];
}
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
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]]
My Approach
- Popeye September 22, 20181. 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