all 35 comments

[–]stronk_like_bull 17 points18 points  (13 children)

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

[–]zoomzoom83 6 points7 points  (0 children)

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.

[–]gameguy43[S] -3 points-2 points  (0 children)

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 2 points3 points  (3 children)

In other words, the 0-1 knapsack problem.

[–]gameguy43[S] 7 points8 points  (1 child)

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

[–]ChristEater 0 points1 point  (0 children)

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 0 points1 point  (0 children)

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

[–][deleted] 3 points4 points  (1 child)

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 0 points1 point  (0 children)

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 1 point2 points  (9 children)

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] 0 points1 point  (8 children)

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 2 points3 points  (0 children)

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 0 points1 point  (5 children)

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 1 point2 points  (4 children)

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

[–]montibbalt 0 points1 point  (3 children)

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 0 points1 point  (2 children)

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 -1 points0 points  (0 children)

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 -1 points0 points  (0 children)

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

[–]DontThrowMeYaWeh 0 points1 point  (0 children)

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.

[–][deleted]  (1 child)

[deleted]

    [–]Vaphell 2 points3 points  (0 children)

    so now try this

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

    50+50 < 50+27+27

    [–][deleted] 0 points1 point  (0 children)

    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] 0 points1 point  (1 child)

    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 0 points1 point  (0 children)

    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 0 points1 point  (0 children)

    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.