The Cake Thief (Practice Interview Question)

You only have 3 free questions left (including this one).

But it doesn't have to end here! Sign up for the 7-day coding interview crash course and you'll get a free Interview Cake problem every week.

You're in!

You are a renowned thief who has recently switched from stealing precious metals to stealing cakes because of the insane profit margins. You end up hitting the jackpot, breaking into the world's largest privately owned stock of cakes—the vault of the Queen of England.

While Queen Elizabeth has a limited number of types of cake, she has an unlimited supply of each type.

Each type of cake has a weight and a value, stored in a CakeType structure:

  typedef struct CakeType {
    unsigned int weight;
    unsigned int value;
} CakeType;

For example:

  // weighs 7 kilograms and has a value of 160 shillings
CakeType cakeType = {7, 160};

// weighs 3 kilograms and has a value of 90 shillings
CakeType cakeType = {3, 90};

You brought a duffel bag that can hold limited weight, and you want to make off with the most valuable haul possible.

Write a function maxDuffelBagValue() that takes an array of cake type structures and a weight capacity, and returns the maximum monetary value the duffel bag can hold.

For example:

  const CakeType cakeTypes[3] = {
    {7, 160},
    {3, 90},
    {2, 15}
};

const size_t cakeTypesLength = sizeof(cakeTypes)/sizeof(cakeTypes[0]);

unsigned int capacity = 20;

maxDuffelBagValue(cakeTypes, cakeTypesLength, capacity);
// returns 555 (6 of the middle type of cake and 1 of the last type of cake)

Weights and values may be any non-negative integer. Yes, it's weird to think about cakes that weigh nothing or duffel bags that can't hold anything. But we're not just super mastermind criminals—we're also meticulous about keeping our algorithms flexible and comprehensive.

Gotchas

Does your function work if the duffel bag's weight capacity is 0 kg?

Does your function work if any of the cakes weigh 0 kg? Think about a cake whose weight and value are both 0.

We can do this in $O(n*k)$ time and $O(k)$ space, where $n$ is the number of types of cakes and $k$ is the duffel bag's capacity!

Breakdown

Start your free trial!

Where do I enter my password?

Actually, we don't support password-based login. Never have. Just the OAuth methods above. Why?

It's easy and quick. No "reset password" flow. No password to forget.
It lets us avoid storing passwords that hackers could access and use to try to log into our users' email or bank accounts.
It makes it harder for one person to share a paid Interview Cake account with multiple people.

Solution

Start your free trial!

Where do I enter my password?

Actually, we don't support password-based login. Never have. Just the OAuth methods above. Why?

It's easy and quick. No "reset password" flow. No password to forget.
It lets us avoid storing passwords that hackers could access and use to try to log into our users' email or bank accounts.
It makes it harder for one person to share a paid Interview Cake account with multiple people.

Complexity

$O(n*k)$ time, and $O(k)$ space, where $n$ is number of types of cake and $k$ is the capacity of the duffel bag. We loop through each cake ( $n$ cakes) for every capacity ( $k$ capacities), so our runtime is $O(n*k)$ , and maintaining the array of $k+1$ capacities gives us the $O(k)$ space.

Congratulations! Because of dynamic programming, you have successfully stolen the Queen's cakes and made it big.

Keep in mind: in some cases, it might not be worth using our optimal dynamic programming solution. It's a pretty slow algorithm—without any context (not knowing how many cake types we have, what our weight capacity is, or just how they compare) it's easy to see $O(n*k)$ growing out of control quickly if $n$ or $k$ is large.

If we cared about time, like if there was an alarm in the vault and we had to move quickly, it might be worth using a faster algorithm that gives us a good answer, even if it's not always the optimal answer. Some of our first ideas in the breakdown were to look at cake values or value/weight ratios. Those algorithms would probably be faster, taking $O(n\lg{n})$ time (we'd have to start by sorting the input).

Sometimes an efficient, good answer might be more practical than an inefficient, optimal answer.

Bonus

We know the max value we can carry, but which cakes should we take, and how many? Try adjusting your answer to return this information as well.
What if we check to see if all the cake weights have a common denominator? Can we improve our algorithm?
A cake that's both heavier and worth less than another cake would never be in the optimal solution. This idea is called dominance relations. Can you apply this idea to save some time? Hint: dominance relations can apply to sets of cakes, not just individual cakes.
What if we had a structure for every individual cake instead of types of cakes? So now there's not an unlimited supply of a type of cake—there's exactly one of each. This is a similar but harder problem, known as the 0/1 Knapsack problem.

What We Learned

Start your free trial!

Where do I enter my password?

Actually, we don't support password-based login. Never have. Just the OAuth methods above. Why?

It's easy and quick. No "reset password" flow. No password to forget.
It lets us avoid storing passwords that hackers could access and use to try to log into our users' email or bank accounts.
It makes it harder for one person to share a paid Interview Cake account with multiple people.

Do you have an answer?

Show answer

I have an answer Tell me more

Ready for more?

Check out our full course

You only have 3 free questions left (including this one).

Gotchas

Breakdown

Start your free trial!

Solution

Start your free trial!

Complexity

Bonus

What We Learned

Start your free trial!

Ready for more?

Programming interview questions by company:

Programming interview questions by topic: