5 ms·

The knapsack problem is the canonical dynamic programming problem. Any decent combinatorics class should touch on these concepts at some point.

by pushrax 12y ago

tptacek 12y ago
And that makes it a good interview question because...
- pushrax 12y ago
  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.
  - kasey_junk 12y ago
    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.
    - pushrax 12y ago
      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.
      - deleted 12y ago
        [deleted]
      - kasey_junk 12y ago
        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.
  - tptacek 12y ago
    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.
- mturmon 12y ago
  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.
  - tptacek 12y ago
    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.

The knapsack problem is the canonical dynamic programming problem. Any decent combinatorics class should touch on these concepts at some point.

by pushrax 12y ago

The knapsack problem is the canonical dynamic programming problem. Any decent combinatorics class should touch on these concepts at some point.

tptacek 12y ago

And that makes it a good interview question because...

pushrax 12y ago
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.
- kasey_junk 12y ago
  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.
  - pushrax 12y ago
    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.
    - deleted 12y ago
      [deleted]
    - kasey_junk 12y ago
      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.
- tptacek 12y ago
  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.
mturmon 12y ago
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.
- tptacek 12y ago
  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.