Quick Overview

Evaluates algorithmic skills in cost-optimization, greedy reasoning and sorting-based assignment while requiring correct handling of constraints and edge cases. Commonly asked in the Coding & Algorithms domain to test a candidate’s ability to design and implement a concrete, implementation-level algorithm and reason about correctness and complexity.

Minimize travel cost with two cities

Company: Bloomberg

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Technical Screen

You are scheduling candidates to attend an onsite interview. Each candidate i can fly to New York for cost c1[i] or to San Francisco for cost c2[i]. Constraint: You must send exactly ceil(n/2) candidates to New York, and the remaining candidates to San Francisco. Task: Compute the minimum possible total travel cost. Additionally, write a few unit-style test cases that validate your solution (including edge cases such as n=1 and odd n).

Quick Answer: Evaluates algorithmic skills in cost-optimization, greedy reasoning and sorting-based assignment while requiring correct handling of constraints and edge cases. Commonly asked in the Coding & Algorithms domain to test a candidate’s ability to design and implement a concrete, implementation-level algorithm and reason about correctness and complexity.

You are scheduling candidates for an onsite interview. For each candidate i, flying them to New York costs c1[i], and flying them to San Francisco costs c2[i]. You must send exactly ceil(n / 2) candidates to New York, where n is the total number of candidates, and send the remaining candidates to San Francisco. Return the minimum possible total travel cost.

Constraints

  • 1 <= n == len(c1) == len(c2) <= 200000
  • 0 <= c1[i], c2[i] <= 10^9

Examples

Input: ([30], [5])

Expected Output: 30

Explanation: There is only one candidate, and ceil(1/2) = 1, so that candidate must go to New York even though San Francisco is cheaper.

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

Expected Output: 110

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

Hints

  1. Try first assuming that everyone goes to San Francisco. Then ask: what is the extra cost or savings if a candidate is switched to New York?
  2. For candidate i, that switch changes the total by c1[i] - c2[i]. Which candidates should be chosen for New York?

Loading coding console...