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)
Improve this question
$\endgroup$
2
  • 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$
    – user114966
    Aug 6, 2020 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$
    – user114966
    Aug 6, 2020 at 2:06

1 Answer 1

Reset to default
1
$\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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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