5 ms·

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 compl

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.

tptacek 12y ago
Unless the role you're being interviewed for is "Algorithm Designer", this is a really stupid interview question.
- crazypyro 12y ago
  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.
gt565k 12y ago
Umm, the knapsack problem was covered extensively in my Design and Analysis of Algorithms class as part of the dynamic programming section. I 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.
- benihana 12y ago
  Seems like a great question to ask if you want to find out if a candidate has taken courses similar to you or has seen this problem before.
  - kajecounterhack 12y ago
    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"
  - gt565k 12y ago
    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...
  - norseboar 12y ago
    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.
    - kasey_junk 12y ago
      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.
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.
kajecounterhack 12y ago
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?)

tptacek 12y ago

Unless the role you're being interviewed for is "Algorithm Designer", this is a really stupid interview question.

crazypyro 12y ago
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.

gt565k 12y ago

Umm, the knapsack problem was covered extensively in my Design and Analysis of Algorithms class as part of the dynamic programming section. I 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.

benihana 12y ago
Seems like a great question to ask if you want to find out if a candidate has taken courses similar to you or has seen this problem before.
- kajecounterhack 12y ago
  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"
- gt565k 12y ago
  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...
- norseboar 12y ago
  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.
  - kasey_junk 12y ago
    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.

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.

kajecounterhack 12y ago

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?)