## Problem You have an array of `n` positive integers. In one operation, pick any two elements, merge them into their sum, and pay a cost equal to that sum. Repeat until one element remains. Return the minimum total cost to merge all elements. ```python def min_merge_cost(nums: list[int]) -> int: ``` ## Example ``` nums = [4, 3, 2, 6] Optimal: merge 2+3=5 (cost 5), then 4+5=9 (cost 9), then 9+6=15 (cost 15) -> total 29 Alternate: merge 2+4=6 (cost 6), 3+6=9, 6+9=15 -> total 30 Output: 29 ``` This is equivalent to Huffman coding: always merge the two smallest elements using a min-heap. ## Follow-ups 1. Why does always merging the two smallest values minimize cost? Give an informal proof. 2. What is the time complexity and space complexity of the heap-based approach? 3. What changes if merging has a fixed overhead: cost = sum + constant `c` per merge? 4. How does this problem relate to constructing an optimal binary search tree or Huffman tree?

InterviewDB Question

Minimum Possible Cost - Greedy Merge Operations to Minimize Total Cost

Question Details

Problem You have an array of n positive integers. In one operation, pick any two elements, merge them into their sum, and pay a cost equal to that sum. Repeat until one element remains. Return the minimum total cost to merge all elements. Example Thi…

Full Details

🔒

Unlock full leaked content

Full insider details, leaked discussions, and candidate experiences.

Get Premium →

Topics

Coding Oa

More from Amazon

Reddit 175 k remote offer or 300 k in Bay Area Reddit Done with 3 rounds of On-site Amazon SDE 1 interview , but no communication after that. What to do? Reddit Nned direction for future prepration. Reddit Have an Amazon. SDE1 interview in 4 days, need tips Reddit After many years in the industry, I still struggle with textbook definitions in interviews

← All Amazon questions Amazon Software Engineer Questions → All Greedy Questions →