How should I practice Minimum Stick Connection Cost?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Navan onsite interview problems in FastPrep.

Is Minimum Stick Connection Cost associated with Navan?

FastPrep tags this as a Navan onsite interview coding practice problem when the problem catalog has that company and stage context.

Minimum Stick Connection Cost

Navan● MediumFULLTIMEONSITE INTERVIEW

Learn

Problem statement

You are given an integer array sticks, where each element is the length of a stick.

You may connect any two sticks with lengths x and y. The new stick has length x + y, and the cost of this operation is also x + y.

Return the minimum total cost required to connect all sticks into one stick.

Interview follow-up

The interviewer also asked what to do when the input cannot fit in memory. Discuss an external-memory implementation of the minimum-cost merge process. The judged function here uses the supplied in-memory array.

Function

minimumStickConnectionCost(sticks: int[]) → int

Examples

Example 1

sticks = [2, 4, 3]return = 14

Connect 2 and 3 for cost 5, then connect 5 and 4 for cost 9. The total cost is 14.

Example 2

sticks = [1, 8, 3, 5]return = 30

One optimal sequence is 1 + 3 = 4, then 4 + 5 = 9, then 8 + 9 = 17, for total cost 4 + 9 + 17 = 30.

Constraints

1 <= sticks.length <= 10^4
1 <= sticks[i] <= 10^4