I was asked this on a recent programming interview. As a recent college graduate, I'm not sure this is a fair question to ask under that context given the complexity of the problem. Nice article though.
It's one of those stupid questions where you either have seen it before and use memorization to pull it up or you flounder because you can't come up with a new algorithm on the spot.
Maybe unintentional (and not saying if this is good or bad) but it is a little self-selecting: by asking you can tell "Ok so candidate x has had this kind of educational background and at least has heard of the name which might correlate with traits y or z"
or knows about space-time complexity and why dynamic programming is important when dealing with problems such as this that might involve large data sets...
There seems to be a connotation that asking a question "just to see if the candidate has seen the problem before" is bad, for some reason (apologies if this connotation wasn't there).
This is actually a very important thing to look for in an interview. While it might not be "fair" in the sense that not all smart people can effectively answer it, it's absolutely effective to sort out who has a good grasp of algorithms (and memoization in particular). There are too many smart people out there to interview just for that; you've got to look for existing knowledge too.
There are definitely times in your hiring process when you want to bias towards people with existing knowledge. The problem with this particular question is that it doesn't imply any in depth knowledge of dynamic programming. It is literally something you can see in a survey of algorithms course.
So by asking this question, I suspect you are biasing towards people who have recently taken a survey of algorithms course. I'm having a hard time envisioning the hiring situation where I'd want that bias.
It's a good interview question for the same reason any question is: it allows you to see how the interviewee thinks and approaches a problem (if they haven't seen it before). If they have seen it before, you can see how well they can externalize their knowledge.
Not all questions are good interview questions. For any question you ask, you need to know A) why are you asking it? B) what does it bias your hiring pipeline towards/against? C) what is a good answer to the question? D) how would a perspective employee come to that answer? and most importantly E) given limited resources available to hiring, are there better questions I could be asking.
This is a question that is trivial to answer if you remember basic dynamic programming examples. It is nearly impossible to come up with the "right" answer without it. I'm trying very hard to understand what sort of hiring situation would be interested to know if someone understood basic dynamic programming (without knowing more advanced topics) or could suss it out on their own.
For sure, it's definitely not the ideal interview problem. My intended argument was just that it's not an unfair interview problem.
As an aside, I don't think it's that unlikely to come up with a dynamic programming solution without prior knowledge of the general problem class. It's a pretty intuitive idea.
Really? I'd think the intuitive solution is the greedy solution to the problem, which is incorrect.
Now we have to ask ourselves a few things A) which of us is correct about which is more intuitive and B) does being intuitively good at the knapsack problem imply anything about being intuitive at dynamic programming and C) does being intuitively good at dynamic programming or the knapsack problem have any correlation between good hires.
People say this about every kind of bad interview question. It's actually hard to come up with any interview question you can't say it about. So, you'll need a better reason.
It's funny, at this point in my career I'd value a person who said,
"This feels like a dynamic programming/max-flow-min-cut/linear programming problem. I'd formalize it, look it up in a textbook, like Chvatal, or on Wikipedia, and find the precise problem class. Then I'd look for an appropriate code. Or, maybe go back to the problem origin and see if the actual problem maps in to one of the more general classes I just looked up."
Perhaps much more realistic an answer than some poking around on the whiteboard by someone who may have studied this in school anyway. Having a feeling for problems that should already be well-studied/solved can be more valuable than bumbling on to the solution after a few minutes.
There is a way to turn knapsack algorithms into a good candidate qualifier --- if solving knapsack problems is related in some reasonably direct way to the role you're hiring for --- just create a work-sample test based on solving knapsack problems. Allow the candidate to work on the problem on their own time in their own home or office or whatever.
There. Now, instead of asking for CS theory from candidates in the most hostile imaginable setting (that's what a job interview is: hostile) and telling yourself a cute little story about how you're determining how candidates handle interesting problems that require them to consult the literature: you actually allow the candidate to demonstrate how they would do that.
I think it's a fair question in that it's taught in most algos classes and they don't usually ask it outright, they ask for some variation and want to see that you can handle the task of at least recognizing the problem, and then (hopefully) translating. Or at least getting close.
Also there are a couple of ways to approach this, I think it really helps elucidate how a person tackles a tricky problem upfront (does the person try to write the recurrence out first? does the person do the exponential recursive solution and then memoize? does the person visualize this like a graph, a table, or something else?)
Off the top of my head I look at it as a graph 2 coloring problem. The graph starts out with 1 node per item and zero edges. If we think two items will be in the same set (either in the knapsack or out) we merge the nodes and their weight and value combine into the new node. We draw edges between two nodes if their combined weights exceed the knapsack capacity. When we recurse out of our merge choice, we also draw an edge between the two nodes that composed the merge. Our recursion depth ends at a clique.
This still can easily be worse than n^2 if your weight is significantly higher than your number of objects. Aka max weight of 10,000 and 1,000 objects.
Edit: Note, n^2 is generally far better than 2^n so it's still useful even if it's slow.
My example would be 1000 objects * 10,000 weights = 10,000,000 options. Which is much better than 2^(1000) ~= 10^300 for calculating every possibility, but still worse than n^2.
For it to be worse you would need say 10 objects and 10,000 for max weight. so 2^n = 1024 vs n * k = 10 * 10,000 = 100,000
Does this actually answer the stated problem of "deciding the subset of items to pack"?
Looking at the solution table I can see that there are two possible solutions, and I can see a max value of 6. But I can't see how v[4,3] implies packing objects 1 and 3.
Author here -- great point! I've updated the problem statement to make it more clear :) In this case, the article is simply asking "what is the highest value that you can achieve"
Thanks for the feedback! :)
You can read the chart backwards to get an answer.
Check 2 vs 3 @4lb. That's constant so 3 is not in there.
Check 1 vs 2 @4lb. It changes so ob2 is in there. Now 3 weighs 2lb so look at 4lb - 2lb(ob3) = 2lb max weight.
Check 0 vs 1@2lb. That's increasing so object 1 is in there 2lb - 1lb (ob1) = 1lb max.
Check 0 @1lb that's greater than zero so object 0 is also in there.
Thus, the solution is objects 0,1,2 but not 3.
PS: Note, this only finds one solution there might be several. You can quickly find them with this chart but it's somewhat more complex. You would be looking for places where the max value does not change from the previous row, but the max value in the same row - the object weight = the max value - the object value.
Having done interviews for a large tech firm, dynamic programming questions are a favorite for weeding out candidates. Anecdotally, it correlates rather well with problem solving skills.
Years ago, Joel Spolsky wrote that it was critical for any interview to at least touch on pointers/references and recursion. I think at many major tech companies dynamic programming is included in that bag as well.
I'd be pretty impressed if someone had programmed extensively for two decades and yet had never dealt with references of some kind. It doesn't have to explicitly be pointers in C.
The above referenced Joel On Software article is called "The Perils of JavaSchools" and does in fact make an explicit difference between references and C style pointers.
I, however, explicitly mentioned references in both my posts. I was referring to a general idea, not a specific article. I've also personally interviewed at Fog Creek in Manhattan and was asked reference-based questions that I was allowed to answer in Java rather than C.
Regardless, if you want to reference that specific article, and only that article, I can do that as well. It happens to refute your very own point:
"Now, I freely admit that programming with pointers is not needed in 90% of the code written today, and in fact, it's downright dangerous in production code. OK. That's fine. And functional programming is just not used much in practice. Agreed.
[...]
But beyond the prima-facie importance of pointers and recursion, their real value is that building big systems requires the kind of mental flexibility you get from learning about them, and the mental aptitude you need to avoid being weeded out of the courses in which they are taught. Pointers and recursion require a certain ability to reason, to think in abstractions, and, most importantly, to view a problem at several levels of abstraction simultaneously. And thus, the ability to understand pointers and recursion is directly correlated with the ability to be a great programmer."
Finally, you tacitly assumed you knew which article I had in mind, and you were wrong, not that it matters since I wasn't actually trying to reference a specific article. I was referring to The Guerrilla Guide to Interviewing. He offers example questions like "reverse a linked list" or "detect loops in a tree structure" -- concepts and problems which are clearly not relegated only to C.
If you think that quote refutes my point then I clearly need to clarify what my point was.
1) Joel believes that pointers and recursion are concepts that require a way of thinking about higher order abstractions that correlates well with being a good programming hire. So it would make sense if we agreed with him to ask questions about pointers & recursion in interviews, even if we don't believe that pointers or recursion are used often in the settings we are hiring for.
2) Many people have built long careers without using recursion, but that doesn't refute the premise because it doesn't speak to the higher order abstractions assumption. Further, in the modern world recursion is no more or less likely to be used than pointers (which would be shocking at one point in the industry) as pointers also are not common.
3) The central assumption Joel basis his argument on is that pointers and recursion are interesting because reasoning well about them requires a higher level of abstraction. That higher level of abstraction simply does not exist with Java style references. So asking about references, while maybe useful in other contexts, doesn't have the benefits Joel is arguing for in the same way as pointers.
4) To relate this back to the article, A) is understanding dynamic programming indicative of some central mental type that will correlate with a good programmer? B) Does asking questions about the Knapsack problem suss out that understanding. I suspect, but can't prove that the answers are A) not like pointer/recursion understand and B) absolutely not.
This is a "false" solution, in the sense that you can create a large number of scenarios where just taking the most value/weight efficient item, regardless of the relationship between the items, will result in a non-optimal solution.
e.g. 2 Silver coins worth 4 and weighs 2. 1 Gold coin worth 5 and weighs 3. Silver slightly more efficient, but if your bag size is 5, the obvious solution is 1 gold + 1 silver coin worth 9, where as your "algorithm" would give 2 silver coins weighing 8, worth 8.
For example: If you have 10[s] (units of space) in your knapsack, and you have 3 items in front of you the first with two with 5[s] and 4[v] (units of value) each, and the third with 6[s] and 7[v], the best solution would be to take the first two, even though they have a lower [s]/[v] ratio, because you will end up with 1[v] more.
That's the greedy(and obvious) solution, which is optimal for the fractional version of the problem, not in the case of the 0/1 problem, mentioned in the article.
If you want a really challenging problem, look into the multiple knapsack problem.
This was part of an assignment for a Coursera Discrete Optimization course created by The University of Melbourne. It's a great course and I recommend it to anybody who wants to hone their understanding of dynamic programming and solving computationally expensive problems.
I took this course as well. Really interesting. And a really cool way to submit programming assignments and get instant feedback if you "passed" or not. Some years since I was in school, this might be the de-facto way of doing it now.
48 comments
[ 2.7 ms ] story [ 93.2 ms ] threadI honestly felt that this class was the most useful and relevant out of all CS classes I took as an undergraduate student.
Dynamic programming is very useful, and this problem is a classic. It's asked quite a bit in interviews.
This is actually a very important thing to look for in an interview. While it might not be "fair" in the sense that not all smart people can effectively answer it, it's absolutely effective to sort out who has a good grasp of algorithms (and memoization in particular). There are too many smart people out there to interview just for that; you've got to look for existing knowledge too.
So by asking this question, I suspect you are biasing towards people who have recently taken a survey of algorithms course. I'm having a hard time envisioning the hiring situation where I'd want that bias.
This is a question that is trivial to answer if you remember basic dynamic programming examples. It is nearly impossible to come up with the "right" answer without it. I'm trying very hard to understand what sort of hiring situation would be interested to know if someone understood basic dynamic programming (without knowing more advanced topics) or could suss it out on their own.
As an aside, I don't think it's that unlikely to come up with a dynamic programming solution without prior knowledge of the general problem class. It's a pretty intuitive idea.
Now we have to ask ourselves a few things A) which of us is correct about which is more intuitive and B) does being intuitively good at the knapsack problem imply anything about being intuitive at dynamic programming and C) does being intuitively good at dynamic programming or the knapsack problem have any correlation between good hires.
"This feels like a dynamic programming/max-flow-min-cut/linear programming problem. I'd formalize it, look it up in a textbook, like Chvatal, or on Wikipedia, and find the precise problem class. Then I'd look for an appropriate code. Or, maybe go back to the problem origin and see if the actual problem maps in to one of the more general classes I just looked up."
Perhaps much more realistic an answer than some poking around on the whiteboard by someone who may have studied this in school anyway. Having a feeling for problems that should already be well-studied/solved can be more valuable than bumbling on to the solution after a few minutes.
There. Now, instead of asking for CS theory from candidates in the most hostile imaginable setting (that's what a job interview is: hostile) and telling yourself a cute little story about how you're determining how candidates handle interesting problems that require them to consult the literature: you actually allow the candidate to demonstrate how they would do that.
Also there are a couple of ways to approach this, I think it really helps elucidate how a person tackles a tricky problem upfront (does the person try to write the recurrence out first? does the person do the exponential recursive solution and then memoize? does the person visualize this like a graph, a table, or something else?)
Edit: Note, n^2 is generally far better than 2^n so it's still useful even if it's slow.
For it to be worse you would need say 10 objects and 10,000 for max weight. so 2^n = 1024 vs n * k = 10 * 10,000 = 100,000
Looking at the solution table I can see that there are two possible solutions, and I can see a max value of 6. But I can't see how v[4,3] implies packing objects 1 and 3.
Check 2 vs 3 @4lb. That's constant so 3 is not in there.
Check 1 vs 2 @4lb. It changes so ob2 is in there. Now 3 weighs 2lb so look at 4lb - 2lb(ob3) = 2lb max weight.
Check 0 vs 1@2lb. That's increasing so object 1 is in there 2lb - 1lb (ob1) = 1lb max.
Check 0 @1lb that's greater than zero so object 0 is also in there.
Thus, the solution is objects 0,1,2 but not 3.
PS: Note, this only finds one solution there might be several. You can quickly find them with this chart but it's somewhat more complex. You would be looking for places where the max value does not change from the previous row, but the max value in the same row - the object weight = the max value - the object value.
Having done interviews for a large tech firm, dynamic programming questions are a favorite for weeding out candidates. Anecdotally, it correlates rather well with problem solving skills.
Particularly tree and graph manipulations can be very common tasks depending on your job description.
Regardless, if you want to reference that specific article, and only that article, I can do that as well. It happens to refute your very own point:
"Now, I freely admit that programming with pointers is not needed in 90% of the code written today, and in fact, it's downright dangerous in production code. OK. That's fine. And functional programming is just not used much in practice. Agreed.
[...]
But beyond the prima-facie importance of pointers and recursion, their real value is that building big systems requires the kind of mental flexibility you get from learning about them, and the mental aptitude you need to avoid being weeded out of the courses in which they are taught. Pointers and recursion require a certain ability to reason, to think in abstractions, and, most importantly, to view a problem at several levels of abstraction simultaneously. And thus, the ability to understand pointers and recursion is directly correlated with the ability to be a great programmer."
Finally, you tacitly assumed you knew which article I had in mind, and you were wrong, not that it matters since I wasn't actually trying to reference a specific article. I was referring to The Guerrilla Guide to Interviewing. He offers example questions like "reverse a linked list" or "detect loops in a tree structure" -- concepts and problems which are clearly not relegated only to C.
1) Joel believes that pointers and recursion are concepts that require a way of thinking about higher order abstractions that correlates well with being a good programming hire. So it would make sense if we agreed with him to ask questions about pointers & recursion in interviews, even if we don't believe that pointers or recursion are used often in the settings we are hiring for. 2) Many people have built long careers without using recursion, but that doesn't refute the premise because it doesn't speak to the higher order abstractions assumption. Further, in the modern world recursion is no more or less likely to be used than pointers (which would be shocking at one point in the industry) as pointers also are not common. 3) The central assumption Joel basis his argument on is that pointers and recursion are interesting because reasoning well about them requires a higher level of abstraction. That higher level of abstraction simply does not exist with Java style references. So asking about references, while maybe useful in other contexts, doesn't have the benefits Joel is arguing for in the same way as pointers. 4) To relate this back to the article, A) is understanding dynamic programming indicative of some central mental type that will correlate with a good programmer? B) Does asking questions about the Knapsack problem suss out that understanding. I suspect, but can't prove that the answers are A) not like pointer/recursion understand and B) absolutely not.
Without reading, I already knew the solution.
To solve it in your head: sort items by most value/weight efficient to least efficient.
Then take as much as you can until you're full.
(in a game like elder scrolls oblivion, that means jewelry first, and silver vases last)
-----
edit: I am mistaken, as some of the below comments accurately pointed out.
e.g. 2 Silver coins worth 4 and weighs 2. 1 Gold coin worth 5 and weighs 3. Silver slightly more efficient, but if your bag size is 5, the obvious solution is 1 gold + 1 silver coin worth 9, where as your "algorithm" would give 2 silver coins weighing 8, worth 8.
For example: If you have 10[s] (units of space) in your knapsack, and you have 3 items in front of you the first with two with 5[s] and 4[v] (units of value) each, and the third with 6[s] and 7[v], the best solution would be to take the first two, even though they have a lower [s]/[v] ratio, because you will end up with 1[v] more.
If you want a really challenging problem, look into the multiple knapsack problem.