How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Bloomberg.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Bloomberg during technical interviews.

Minimize Travel Assignment Cost | Bloomberg Coding Question

Quick Overview

This question evaluates algorithmic problem-solving in combinatorial optimization and dynamic programming, testing competency with cost-minimization, constraint handling (exact counts per destination), and trade-offs between greedy heuristics and DP formulations.

Minimize Travel Assignment Cost

Company: Bloomberg

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given `n` people who each need to travel to exactly one of two cities: San Francisco or New York. The input is an array `costs`, where `costs[i] = [sfCost, nyCost]` represents the cost of sending person `i` to San Francisco and New York, respectively. Assume `n` is even. 1. Compute the minimum total cost to send exactly `n / 2` people to San Francisco and exactly `n / 2` people to New York. 2. Follow-up: Generalize the solution so that exactly `k` people must be sent to San Francisco and the remaining `n - k` people must be sent to New York. 3. Implement a dynamic programming solution and include your own test cases. Example: ```text costs = [[10, 20], [30, 200], [400, 50], [30, 20]] ``` One optimal assignment is: - Send people 0 and 3 to San Francisco: cost `10 + 30` - Send people 1 and 2 to New York: cost `200 + 50` Total cost: `290` Return the minimum possible total cost.

Quick Answer: This question evaluates algorithmic problem-solving in combinatorial optimization and dynamic programming, testing competency with cost-minimization, constraint handling (exact counts per destination), and trade-offs between greedy heuristics and DP formulations.

Part 1: Minimum Cost with Equal City Quotas

You are given an array costs where costs[i] = [sfCost, nyCost] is the cost of sending person i to San Francisco or New York. The number of people n is even. Send exactly n / 2 people to San Francisco and exactly n / 2 people to New York. Return the minimum possible total cost.

Constraints

0 <= n <= 100000
n is even
costs[i].length == 2
0 <= costs[i][0], costs[i][1] <= 10000

Examples

Input: [[10, 20], [30, 200], [400, 50], [30, 20]]

Expected Output: 110

Explanation: Send people 0 and 1 to San Francisco and people 2 and 3 to New York: 10 + 30 + 50 + 20 = 110.

Input: []

Expected Output: 0

Explanation: No people means no travel cost.

Input: [[50, 10], [20, 100]]

Expected Output: 30

Explanation: Exactly one person must go to each city. Send person 1 to San Francisco for 20 and person 0 to New York for 10.

Input: [[5, 5], [5, 5], [5, 5], [5, 5]]

Expected Output: 20

Explanation: All assignments cost the same, so any valid 2-and-2 split gives total cost 20.

Hints

Imagine sending everyone to New York first. What is the extra cost or savings of switching one person to San Francisco?
Sort people by (sfCost - nyCost). The best people to send to San Francisco are those with the smallest differences.

Part 2: Minimum Cost with Exactly k People in San Francisco

You are given an array costs where costs[i] = [sfCost, nyCost] is the cost of sending person i to San Francisco or New York. You are also given an integer k. Send exactly k people to San Francisco and the remaining n - k people to New York. Return the minimum possible total cost.

Constraints

0 <= n <= 100000
0 <= k <= n
costs[i].length == 2
0 <= costs[i][0], costs[i][1] <= 10000

Examples

Input: ([[10, 20], [30, 200], [400, 50], [30, 20]], 1)

Expected Output: 120

Explanation: The best single person to send to San Francisco is person 1. Total = 30 + 20 + 50 + 20 = 120.

Input: ([[5, 9], [4, 7]], 0)

Expected Output: 16

Explanation: Nobody goes to San Francisco, so send both people to New York: 9 + 7 = 16.

Input: ([[5, 9], [4, 7]], 2)

Expected Output: 9

Explanation: Everyone goes to San Francisco: 5 + 4 = 9.

Input: ([[8, 4], [6, 10], [7, 5]], 2)

Expected Output: 17

Explanation: Send people 1 and 2 to San Francisco and person 0 to New York: 6 + 7 + 4 = 17.

Input: ([], 0)

Expected Output: 0

Explanation: Empty input with k = 0 has total cost 0.

Hints

Start by assuming everyone goes to New York. Then each switch to San Francisco changes the total by sfCost - nyCost.
You need exactly k switches, so choose the k smallest cost changes.

Part 3: Dynamic Programming Travel Assignment

Implement a dynamic programming solution for the travel assignment problem. You are given an array costs where costs[i] = [sfCost, nyCost] and an integer k. Send exactly k people to San Francisco and the remaining n - k people to New York. Return the minimum possible total cost. Solve this version using dynamic programming rather than sorting-based greediness.

Constraints

0 <= n <= 200
0 <= k <= n
costs[i].length == 2
0 <= costs[i][0], costs[i][1] <= 10000

Examples

Input: ([[10, 20], [30, 200], [400, 50], [30, 20]], 2)

Expected Output: 110

Explanation: A best assignment is people 0 and 1 to San Francisco, and people 2 and 3 to New York.

Input: ([[1, 100], [2, 3], [50, 4]], 0)

Expected Output: 107

Explanation: If k = 0, everyone must go to New York: 100 + 3 + 4 = 107.

Input: ([[1, 100], [2, 3], [50, 4]], 3)

Expected Output: 53

Explanation: If k = n, everyone must go to San Francisco: 1 + 2 + 50 = 53.

Input: ([], 0)

Expected Output: 0

Explanation: No people and k = 0 gives cost 0.

Input: ([[12, 30], [40, 20], [50, 50], [30, 60]], 2)

Expected Output: 112

Explanation: Send people 0 and 3 to San Francisco, and people 1 and 2 to New York: 12 + 30 + 20 + 50 = 112.

Hints

Let dp[i][j] be the minimum cost after considering the first i people with exactly j sent to San Francisco.
For each person, try sending them either to New York or to San Francisco and update the next DP state.

Quick Overview