Find maximum cable length by cutting
Company: Bloomberg
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
You are given N cables with integer lengths and a target K. Cut the cables into pieces of equal integer length L to produce at least K pieces; maximize L. If impossible, return 0. Describe an algorithm using binary search on the answer and analyze its complexity. Follow up: support non-integer lengths with precision 1e-3.
Quick Answer: This question evaluates a candidate's proficiency in algorithm design, particularly applying binary search over a monotonic answer space and managing integer versus floating-point precision when maximizing piece length.
Given cable lengths and target piece count k, return the maximum integer piece length that can produce at least k pieces.
Constraints
- Inputs are provided as Python literals matching the function signature.
- Return a deterministic exact-match result.
Examples
Input: ([802, 743, 457, 539], 11)
Expected Output: 200
Explanation: Classic cable cutting.
Input: ([5, 5], 20)
Expected Output: 0
Explanation: Impossible target.
Input: ([], 1)
Expected Output: 0
Explanation: No cables.
Hints
- Choose a representation that makes the core operation simple.
- Handle empty and boundary inputs before the main algorithm.