Minimal number of buckets to hold X marbles while maintaining countability

[KingNothing]

You are the owner of a marble warehouse where you store marbles in buckets. You can fit any number of marbles in one bucket. Your job is to store X marbles in a minimal number of buckets. But, when a customer comes and asks for Y number of marbles, you must be able to hand over some buckets and give them the exact number, without adding/removing marbles from the buckets.

Essentially, minimize the number of buckets while maintaining countability.

I was asked this question in a job interview, and would like to hear your answers.

 

[pmsrw3]

The optimal answer depends a lot on the distribution of customer demands. But part of the answer, I guess, would be to have the number of marbles in each bucket be a power of two: i.e., buckets with 1 marble, 2 marbles, 4, 8, ... That would allow you to fill any order. Off hand I can't think of another strategy that uses fewer buckets while preserving total flexibility.

 

[KingNothing]

1 marble, 2 marbles, 4, 8, ... That would allow you to fill any order.

That's the answer I gave: populate the buckets with powers of two and put the remainder in one "overflow" bucket.

The customer may ask for any number of marbles, but they don't care how many buckets they get. You only care how many buckets you store.