Bloomberg·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jun 2026

Summary

Bloomberg SWE interview with a greedy/sorting problem about splitting people across two cities at minimum cost. Pretty classic algorithmic setup but the constraint of exactly n per city is what makes it interesting.

Questions Asked (1)

You have 2n people, each with a cost to fly to city A or city B. How do you split them so exactly n go to each city and the total flight cost is minimized?

Algorithms & Data Structures

Author's notes

My first instinct was brute force and i caught myself before saying it out loud, which was a small win.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Recognize this as a greedy problem: compute the cost difference (costA - costB) for each person, sort by this difference, and assign the n people with the smallest differences to city A and the rest to city B. Explain why this works by showing that any swap that keeps the counts balanced cannot reduce the total cost.

Pro tip: After presenting the greedy solution, mention that you can avoid a full sort by using a min-heap or quickselect to find the n smallest differences, which can be more efficient for large n. This shows you think about optimization beyond the basic approach.

1. Clarify the problem

Restate the problem to ensure understanding: we have 2n people, each with a cost to fly to A and a cost to fly to B, and we need exactly n people in each city while minimizing total cost.

2. Define the cost difference

For each person, compute the difference d_i = costA_i - costB_i. This represents the extra cost of sending person i to A instead of B.

3. Sort by difference

Sort the people in ascending order of d_i. The people with the smallest differences are those who are relatively cheaper to send to A (or less expensive to send to A compared to B).

4. Assign cities

Assign the first n people (smallest d_i) to city A and the remaining n people to city B. This ensures exactly n people per city and minimizes the total cost.

5. Prove optimality

Argue that any other assignment would require swapping at least one person from A with one from B, and such a swap would increase or keep the total cost the same because the person moved to A has a larger d_i than the person moved to B.

Key Points to Mention

Greedy algorithm: sort by cost difference and pick the n smallest for city A.
Proof of optimality via exchange argument: swapping any two people between cities cannot reduce total cost.
Time complexity: O(n log n) due to sorting, which is optimal for comparison-based sorting.
Alternative approach: use a min-heap or quickselect to find the n smallest differences in O(n) average time.
Edge cases: all differences equal, negative differences, large input sizes.
Space complexity: O(n) for storing differences and assignments.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.