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 Take-home Project rounds at Morgan Stanley.

What role is this question designed for?

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

Compute minimal cost to merge numbers | Morgan Stanley Coding Question

Quick Overview

Compute minimal cost to merge numbers evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Compute minimal cost to merge numbers

Company: Morgan Stanley

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Take-home Project

Given an array of positive integers, you may repeatedly perform the following operation until one number remains: choose any two numbers x and y, pay a cost of x + y, and insert x + y back into the array. Compute the minimal possible total cost. Describe the algorithm, prove why it is optimal, analyze time and space complexity, and implement it in C++. Discuss edge cases such as n = 1, duplicate values, and very large integers.

Quick Answer: Compute minimal cost to merge numbers evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Given an array of positive integers, you may repeatedly perform the following operation until exactly one number remains: choose any two numbers x and y, remove them, pay a cost of x + y, and insert the value x + y back into the array. Return the minimal possible total cost (the sum of all the per-operation costs). This is the classic optimal-merge / Huffman problem. The optimal strategy is greedy: always merge the two smallest available numbers. Use a min-heap so each step pops the two smallest values in O(log n). Intuitively, every original value contributes to the running cost once per merge it participates in, i.e. it is charged a number of times equal to its depth in the merge tree, so keeping small values deep (merging them earliest) minimizes the weighted sum. Edge cases: - An empty array or a single element requires no merges, so the cost is 0. - Duplicate values are handled naturally by the heap. - Sums can grow large; use 64-bit integers (Python is arbitrary-precision; Java/C++ use long/long long). Return 0 when the array has 0 or 1 elements.

Constraints

0 <= n (array length); return 0 when n <= 1.
Each element is a positive integer.
The accumulated total cost may exceed 32-bit range; use 64-bit integers in Java/C++.
Merges continue until exactly one number remains.

Examples

Input: ([4, 3, 2, 6],)

Expected Output: 29

Explanation: Merge 2+3=5 (cost 5), then 4+5=9 (cost 9), then 6+9=15 (cost 15). Total 5+9+15 = 29.

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

Expected Output: 19

Explanation: Merge 1+2=3 (cost 3), then 3+3=6 (cost 6), then 4+6=10 (cost 10). Total 3+6+10 = 19.

Input: ([20, 4, 8, 2],)

Expected Output: 54

Explanation: Merge 2+4=6 (cost 6), then 6+8=14 (cost 14), then 14+20=34 (cost 34). Total 6+14+34 = 54.

Input: ([5],)

Expected Output: 0

Explanation: A single element needs no merge, so the cost is 0.

Input: ([],)

Expected Output: 0

Explanation: An empty array needs no merge, so the cost is 0.

Input: ([7, 7],)

Expected Output: 14

Explanation: Only one merge possible: 7+7=14 (cost 14). Duplicates handled naturally.

Input: ([1, 1, 1, 1],)

Expected Output: 8

Explanation: Merge 1+1=2 (cost 2), 1+1=2 (cost 2), then 2+2=4 (cost 4). Total 2+2+4 = 8.

Input: ([1000000, 1000000, 1000000],)

Expected Output: 5000000

Explanation: Merge 1000000+1000000=2000000 (cost 2000000), then 2000000+1000000=3000000 (cost 3000000). Total 5000000 — large sums require 64-bit accumulation.

Hints

Think about how many times each original value gets added into the running cost — it equals its depth in the merge tree.
To minimize a weighted sum where weight = depth, keep the smallest values deepest: always combine the two smallest numbers first.
A min-heap (priority queue) lets you repeatedly extract the two smallest values in O(log n) and push their sum back.

Quick Overview