## Bloomberg LP Interview Question for Software Engineers

• 0

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

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.

Comment hidden because of low score. Click to expand.
0

genius!!

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()) {
}
}
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 + "]";
}
}
}``````

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++) {
}
// 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);
}

}``````

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;
flightCharges  = 500;
flightCharges  = 600;
flightCharges  = 300;
flightCharges  = 400;
flightCharges  = 700;
flightCharges  = 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] - flightCharges[i];
if(cheapFlight<0 && countA<50)
{
System.out.println(flightCharges[i]+" is cheap");
countA++;
}
else {
System.out.println(flightCharges[i]+" 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;
}
}``````

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

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.

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

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

``````def minTravelCost(cost):
scost = sorted(cost, key = lambda x: -(x - x))
tot = 0
mid = len(scost) // 2

for i in range(mid):
tot += scost[i]

for i in range(mid + 1, len(scost)):
tot += scost[i]

if not len(scost) % 2:
tot += scost[mid]
else:
tot += min(scost[mid], scost[mid])

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-x)
print ("sorted")
print(c)
ny_part = c[:noof//2]
sf_part = c[noof//2:]
ny_sum = sum([c for c in ny_part])
sf_sum = sum([c 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]]``````

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.

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