5 ms·

For those of you planning on interviewing... Having done interviews for a large tech firm, dynamic programming questions are a favorite for weeding out candida

For those of you planning on interviewing... 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.

nilkn 12y ago
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.
- JoeAltmaier 12y ago
  And yet, I can count on one finger the number of recursive algorithms I have ever, ever used in 20 years of programming.
  - kajecounterhack 12y ago
    That's interesting, YMMV cuz I've been full-time for a little over a year and I've already written (at least) three. Particularly tree and graph manipulations can be very common tasks depending on your job description.
  - kasey_junk 12y ago
    And I'm sure you can find people who have programmed extensively for the last 20 years and have not needed to deal with pointers directly.
    - nilkn 12y ago
      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.
      - kasey_junk 12y ago
        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.
        nilkn 12y ago
        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.
        kasey_junk 12y ago
        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.

nilkn 12y ago

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.

JoeAltmaier 12y ago
And yet, I can count on one finger the number of recursive algorithms I have ever, ever used in 20 years of programming.
- kajecounterhack 12y ago
  That's interesting, YMMV cuz I've been full-time for a little over a year and I've already written (at least) three. Particularly tree and graph manipulations can be very common tasks depending on your job description.
- kasey_junk 12y ago
  And I'm sure you can find people who have programmed extensively for the last 20 years and have not needed to deal with pointers directly.
  - nilkn 12y ago
    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.
    - kasey_junk 12y ago
      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.
      - nilkn 12y ago
        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.
        kasey_junk 12y ago
        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.