This problem looks easy, and most candidates find the right idea within minutes. Then many of them implement it in a way that passes the examples and fails on half of all other inputs. Here's the problem, the trap, and a solution you can defend in an interview. You may also know it as "connect ropes with minimum cost" .
The Problem
A factory builds a product from N parts. Assembling two parts of sizes a and b takes a + b units of time and produces one new part of size a + b . Parts are assembled two at a time until only the final product is left.
Write a method that calculates the minimum total time to build the final product. The input consists of two arguments: numOfParts , the number of parts, and parts , a list of integers with the size of each part.
public class AssembleParts {
public static long minimumTime ( int numOfParts , List < Integer > parts ) { // implement your code here } }
Enter fullscreen mode
Exit fullscreen mode
Example: numOfParts = 4 , parts = [8, 4, 6, 12] .…