1
$\begingroup$

I was asked this question in a phone interview recently and I bombed it completely. Zero clue how to approach it. I wasn't able to find any similar patterns on google-ing. Thought maybe folks here might be able to help?


Statement: Given m sticks with different lengths. Combine these sticks to form longer sticks with the same length. What’s the smallest possible length of these newly unified sticks?

Conditions:

  • Must use all sticks
  • m < 50
  • max length of single stick less than 20

Example:

Input: 5 2 1 5 2 1 5 2 1
Output: 6
(Process: 1+5, 1+5, 1+5, 2+2+2)

Input: 3 3 3 2 2 5
Output: 9
(Process: 3+3+3, 2+2+5)

Input: 1 2 3 4 5
Output: 5
(Process: 2+3, 1+4, 5)

Input: 1 3 4 5
Output: 13
(Process: 1+3+4+5)
$\endgroup$
  • 2
    $\begingroup$ Just wondering: what company asked you this question? I had interviews in companies like Amazon and Facebook, and their questions never were nearly that hard. When you fix the desired length, Bin packing problem, which is Strongly NP-complete, can be reduced to this problem. So, unless I'm missing something, you didn't have a hope to solve this problem efficiently. $\endgroup$ – Dmitry Aug 6 at 0:38
  • $\begingroup$ And while constraints are small, I don't see how to use them. When the number of bins (the number of groups) is small (e.g. 2,3), you can use dynamic programming. If it's large ($\ge 25$), there are also simple approaches. But for values in between (e.g. 10) I don't see what to do $\endgroup$ – Dmitry Aug 6 at 2:06
2
$\begingroup$

Pragmatic approach: If I were given this in an interview, I'd formulate it as an integer linear programming problem and let an off-the-shelf ILP solver look for a solution for me.

Theoretical approach: As Dmitry mentions, this problem is related to bin packing. (It's not identical because you require the bins to be full, whereas normal bin packing doesn't require that.) Wikipedia says that there is a pseudopolynomial time algorithm for bin packing when the bin size is fixed, so you might look up that algorithm and see if it can be modified to apply to your problem. You might also explore this paper:

Michel X. Goemans, Thomas Rothvoß. "Polynomiality for bin packing with a constant number of item types". SODA 2014.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.