Minimize the Total Cost of Merging Numbers
Company: PayPal
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
Overview: Minimize pairwise merge cost using a min-heap, with a greedy merge-tree proof, repeated contribution analysis, edge cases, and overflow considerations.
Read the full PayPal Software Engineer interview experience this question came from
Constraints
- numbers contains 0 through 2^31 - 1 entries.
- Each value and the exact minimum total cost are integers from 0 to 2^53 - 1, inclusive.
Examples
Input: ([4, 3, 2, 6],)
Expected Output: 29
Explanation: Merge 2 with 3, then 4 with the resulting 5, then 6 with the resulting 9. The costs are 5, 9, and 15.
Input: ([1, 8, 3, 5],)
Expected Output: 30
Explanation: The costs are 4, 9, and 17 when the smaller values merge first.
Hints
- Count how often an original value contributes to the cost if the group containing it is merged several times.