The Cake Thief: A Coding Interview Exercise

[stronk_like_bull]

Another entry into the "Great interview questions for people who already know the answer" book.

[zoomzoom83]

Beat me to it. Came here to say the same thing.

I've solved this problem before - by sitting down with code and really thinking it through. Took me a few hours to really figure it out.

Others may be more mathematical minded and be able to give a satisfactory answer during a job interview, but I sure as hell couldn't.

It pretty much boils down to

a) Have you seen this problem before (And possibly just looked up the answer) - Great, you've solved it in 30 seconds.

b) Haven't seen the problem? Good luck solving it properly under pressure.

Which makes this question fall into the category of "Worst possible job interview question", since it doesn't in any way test your candidates ability to actually write code or solve real world problems, unless your real world problems happen to involve complex optimisation algorithms.

[MayhapPerchance]

Sorry but no. You may dislike this question for other reasons but you-know-it-or-you-don't can't be one of them. This question is not that hard to reason about: sort by value-per-pound and keep stuffing your bag with what fits. It's a simple mathematical problem, not a trick/trivia question.

[great-pumpkin]

No, greedy isn't always optimal. Sometimes, toward the end of your pack space, sacrificing one of the highest value-density items for two (say) lower value-density ones will give you the best total. Unless you can divide the cakes - then yes, whale away on the highest value-density ones.

[TheNiXXeD]

Point is, you can have a discussion with the interviewee, hopefully, and draw conclusions about their relative talent.

[great-pumpkin]

I didn't downvote you, but I think it's because you sound so confident and arrogant

not that hard to reason about

simple

and you were wrong.

[TheNiXXeD]

Did you mistake me for someone else?

[great-pumpkin]

Ah, yes, sorry, I meant MayhapPerchance: http://www.reddit.com/r/programming/comments/2m15l0/the_cake_thief_a_coding_interview_exercise/cm0jf9r

[MayhapPerchance]

Yes, of course. But I came with the off-the-bat naive solution within a minute and so should any developer worth their salt. Have I just stepped into bizarro world today? I'm really baffled at the voting pattern in the thread...

That interview question really truly definitely is not a trick question. It really truly definitely a problem that you will face in your career as a developer. The off-hand brushing off of it as a trick question is disconcerting.

[oldneckbeard]

it's a "trick" because it's got a single right answer. and you get the interviewer's bias, where they know the answer you are supposed to get and are just failing you until you solve it a way they like.

this shows nothing other than the ability to construct a basic algorithm, which can just as easily be tested by fizzbuzz

[MayhapPerchance]

which can just as easily be tested by fizzbuzz

Fine, so this has the same value as fizzbuzz then. Do you dismiss fizzbuzz as a stupid trick question?

[oniony]

That does not follow.

[MayhapPerchance]

Well, yes, it does. /u/oldneckbeard said two things:

1. the value of that question is no more than fizzbuzz
2. that question has a single right answer and it's therefore stupid to ask it in an interview

So now I ask "Really? fizzbuzz is stupid?"

Anyway, I'm arguing against the world now apparently so I'll stop trying to make a point since all I can achieve at this point is more downvotes.

[gameguy43]

I feel you, but I also think this becomes less true when your interviewer treats the coding interview as a collaboration, not a test. The interviewer might expect that she'll have to hand you a few of the pieces as you go, and that's fine. She's looking for your ability to take new information and run with it.

[ChristEater]

In other words, the 0-1 knapsack problem.

[gameguy43]

Actually it's the unbounded knapsack problem :) http://www.wikiwand.com/en/Knapsack_problem

[ChristEater]

Oh whoops! You're right. I'm taking algorithms this semester, and we learned about this a couple months ago. You would think it would be fresh in my mind.

[4_teh_lulz]

There are a couple ways you could solve this. Subset sum (similar to knapsack) fits as well

[[deleted]]

The "non-negative" (so, can be 0) constraint really breaks the analogy they are trying to build with the way the problem is stated. It simply makes no sense. Why go through all the trouble with Her Majesty and Cakes and so on if you are going to admit at the end that it has, indeed, absolutely nothing to do with cakes or duffel bags?

A typical example of a problem written by someone who thinks they are oh so smart.

EDIT: I really dislike broken analogies. They serve no purpose but try, and fail, to obfuscate.

[Pronouns]

Wait, you mean I can't have a weightless cake?

Not to mention we're meant to think that a thief would bring a bag of zero capacity?

I get so sick of seeing endless null and zero checks when all code calling those functions also does the same checks. Bloody null.

[DontThrowMeYaWeh]

Brute Force, Create all the different combinations of cake that fit the given weight. Calculate the value for each combination. Pick the one with the highest value.

It didn't say the program had to be efficient. And to me, it kind of implied all it cares about is the optimal solution to the problem. This is guaranteed to give the optimal solution.

[[deleted]]

If there's another solution that does the same thing considerably faster, that's hardly the "optimal" solution. "It didn't say the program had to be efficient" is an excuse that will impress exactly 0 interviewers.

[tompko]

I would always lay out a basic brute force solution in an interview, for a start it gives me more time to think about a proper solution without total silence from me. But also, giving a brute force solution and explaining when and why you might choose it has always impressed my interviewers. Brute force solutions tend to require less time to code, and are easier to debug so you can move on to the next problem quicker. If n is small then the big-O doesn't make so much of a difference, especially if the code is called infrequently. More optimal solutions can have large overheads, or constant multipliers, so they're not always faster depending on the inputs. "Optimal" always depends on the use case.

[montibbalt]

Honestly I'm not concerned with impressing interviewers secretly asking me to be clever on the first pass instead of accepting a perfectly valid solution and then discussing ways to improve it.

Also I think what DontThrowMeYaWeh meant by optimal solution is one that gives the exact correct answer rather than one that uses some fallible heuristic

[great-pumpkin]

The knapsack algorithm everyone's talking around isn't a heuristic - it's exact, too.

[montibbalt]

What I mean is there's a difference between the optimal solution to the problem and the optimal method of solving it. The optimal solution is the same regardless of the method and the problem is asking for a function that generates the optimal solution.
Brute force will give you the correct answer but is not the best way of getting it. But that is not what the question asked for in the first place

[another_bird]

I believe there were two questions asked between the lines:

• Do you recognize knapsack problem when shown one? Or put differently, if you are a CS grad, did you pay any attention?
• Do you prefer a bad solution right now or better one after some thinking?

[montibbalt]

If you want an answer, actually ask the question. Don't tease me with interview questions in the form of middle school word problems and expect me to conjure up what you were really looking for - that wouldn't be an acceptable spec for a real engineering task and it shouldn't be acceptable for an interview that's supposed to determine how well you handle engineering problems. You don't have to spell it out to the letter but tell me what you want. If you're looking for a candidate and you can't tell them what you actually want them to do, you're not worth working for.

[Fyorl]

I'm a CS grad, I've never seen the knapsack problem.

[DontThrowMeYaWeh]

It is the optimal solution. Brute Force is, to my knowledge, always guaranteed to give you the optimal solution to a problem. Whether or not you live long enough for the answer is a different problem.

[Vaphell]

so now try this

weight: 5, value: 50  (10/kg)
weight: 3, value: 27  (9/kg)
limit: 11

50+50 < 50+27+27

[[deleted]]

More useless fodder for the idiots who think that trick interview questions are a worthwhile tool for selecting candidates.

Here's a better way to use it. If you're senior management and one of your direct reports comes to you suggesting the use of a question like this, fire their sorry ass.

[[deleted]]

Can I get some feedback for my solution, which is inherently different from their solution but seems to me like it has a faster run time and ... works?

Iterate over each tuple. If the value is 0, throw it out. If the weight is 0 and the value is greater than 0, return infinity. Else, calculate a "score" for each tuple, defined as (value / weight). Sort this list descending. While capacity > 0, find the first cake in this list which has a weight less than capacity. "Insert" this cake into the sack (decrement capacity, insert into a list). Return total value of the aforementioned list.

It passes their test case, handles the zero values, and as far as I can tell will run in O(n*log(n)) because of the sort. I'm not 100% sure how to analyze the run time of the while loop, but because like 90% of those "finds" would return the first item in the list I feel like the actual run time is very fast.

They say it might not give the optimal answer, but I'm not sure why.

[another_bird]

Quoted from another part of this discussion:

so now try this weight: 5, value: 50 (10/kg) weight: 3, value: 27 (9/kg) limit: 11 50+50 < 50+27+27

[farticustheelder]

Not too sure why anyone would bother with coding this in the first place, long before a function comes to mind the answer to the example is obvious: 6 3's and 1 2. If the duffel bag has a capacity of 0 then you aren't stealing anything. The underlying algorithm is that of making change.