Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Dynamic Programming for Technical Interviews

blogarithms.github.io

Post reply on HN
Print view View original

61–70 of 225 posts

Re: Dynamic Programming for Technical Interviews

#61

Post by alangpierce »

hn_throwaway_99 wrote: post #54
alangpierce wrote: post #17

> problems on DP are pretty standard in most product-company-based hiring challenges This is sad and a little surprising to me. I've always thought of DP problems as being obviously terrible interview questions, even among the different types of algo questions (which are already heavily criticized). Candidates who have learned DP in school usually find them really easy, and candidates who haven't usually don't even h…

For what it's worth, I use DP problems extensively for a main reason: in my experience I have found an extremely high correlation between folks who do well on DP problems and folks who are good overall engineers. I have never had a candidate that did very well on DP problems that didn't end up being an overall great programmer (though I certainly have had folks do well on DP problems who were deficient in other ways,…

I guess I'm more worried about false negatives (i.e. people doing poorly who would do well on the job) than false positives. I have worked with excellent coworkers who I think would likely do really poorly on DP questions because they didn't do contest programming or didn't happen to learn it in their education.

Recursion is a great thing to include in an interview (in moderation), no objections there. Many real-world situations are naturally recursive, and a good grasp of recursion helps build a strong intuition for many aspects of programming. DP (specifically designing recursion with overlapping subproblems) is a much more specific technique that I think isn't as beneficial for programming ability, though I certainly don't doubt that people who know DP well are often also good programmers.

Re: Dynamic Programming for Technical Interviews

#62

Post by jogjayr »

alangpierce wrote: post #17

> problems on DP are pretty standard in most product-company-based hiring challenges This is sad and a little surprising to me. I've always thought of DP problems as being obviously terrible interview questions, even among the different types of algo questions (which are already heavily criticized). Candidates who have learned DP in school usually find them really easy, and candidates who haven't usually don't even h…

> Candidates who have learned DP in school usually find them really easy, and candidates who haven't usually don't even have a chance at solving them

is directly related to

> DP comes up almost never in the real world

If you haven't studied DP at school, done competitive programming, or Leetcoded for interview prep you are not likely to have encountered it doing everyday work. And even naturally talented coders are going to struggle with unfamiliar types of problems.

Unfortunately, I don't see a way out of this. It's probably true that programmers who are good at solving DP problems are generally quite good, which is why DP problems get asked at interviews. It's a good signal for ability to learn difficult things, which is a desirable quality in employees. This means that good programmers who don't know DP are forced to learn it or accept that they won't clear some interviews. Absent some other way to clearly signal technical ability, I think DP problems are here to stay.

Re: Dynamic Programming for Technical Interviews

#63

Post by jhall1468 »

hn_throwaway_99 wrote: post #54
alangpierce wrote: post #17

> problems on DP are pretty standard in most product-company-based hiring challenges This is sad and a little surprising to me. I've always thought of DP problems as being obviously terrible interview questions, even among the different types of algo questions (which are already heavily criticized). Candidates who have learned DP in school usually find them really easy, and candidates who haven't usually don't even h…

For what it's worth, I use DP problems extensively for a main reason: in my experience I have found an extremely high correlation between folks who do well on DP problems and folks who are good overall engineers. I have never had a candidate that did very well on DP problems that didn't end up being an overall great programmer (though I certainly have had folks do well on DP problems who were deficient in other ways,…

> For some reason most people seem to be born without the part of the brain that understands pointers

Well, that's just false. Everyone can understand pointers given both time and interest. I realize Joel likes to think him and people like him are "special" and born with innate super powers, but we have overwhelming evidence that it isn't true.

I certainly wouldn't recommend hiring someone to write embedded systems that don't understand pointers, but if you are hiring a generalist, a good engineer can figure it out if it becomes a job requirement down the road.

These are the reasons literally everything Joel says should be taken with the biggest grain of salt you can find. He seems like a smart dude, but like a lot of smart dudes that are aware of their intelligence he highly overestimates (and overvalues) his particular opinions.

My advice: don't be like Joel and use anecdata to drive your theories on what constitutes a good interview. You're already writing exactly like he does, and that's not beneficial to you or to those you're interviewing.

Re: Dynamic Programming for Technical Interviews

#64

Post by bogomipz »

akhilcacharya wrote: post #52
chillee wrote: post #33

Earlier quoted context omitted.

I actually disagree. Of the problems that are commonly asked in programming interviews, DP is perhaps the one that tests "general problem solving" the best. Many other problems require problem-specific tricks/uncommon tricks. On the other hand, there's rarely a DP problem (that comes up in interviews) that relies on a problem-specific trick.

Highly disagree with this. There are pretty significant approach differences between 2D DP, 1D DP, Tree DP, string operations, etc. Determining what you optimize and cache (if you do top-down, which I prefer) is often problem-specific. The way the optimal solutions are laid out the differences between the most efficient fibonacci (O(1) space), "House Robber" independent set problem, and various problems on top of str…

I'm familiar with 1D and 2D but what are some examples of Tree DP besides the standard Fibonacci questions?

Re: Dynamic Programming for Technical Interviews

#65

Post by jogjayr »

elteto wrote: post #35
kccqzy wrote: post #28

Earlier quoted context omitted.

In contrast, I find that the ability to formulate a problem using DP coorelates with whether a person is able to think in a mathematical way. In many dynamic programming problems you need to first define a function P(i,j) or some such, and then define it recursively; when proving the correctness, you use induction. The ability to grasp this recursion and induction is correlated with the level of abstract mathematical…

Your two paragraphs are contradictory. If someone can learn to solve just DP problems by practicing in leetcode then DP is a useless metric or proxy of someone’s ability to reason mathematically. You should have said “the ability to solve DP problems is a good metric of the ability of a candidate to solve DP problems“. I would have agreed with you in that case :)

> If someone can learn to solve just DP problems by practicing in leetcode then DP is a useless metric or proxy of someone’s ability to reason mathematically.

I'm not a fan of DP but I don't follow this logic. Does practicing maths problems for an exam make the exam a useless metric of mathematical reasoning?

Re: Dynamic Programming for Technical Interviews

#66

Post by chillee »

akhilcacharya wrote: post #52
chillee wrote: post #33

Earlier quoted context omitted.

I actually disagree. Of the problems that are commonly asked in programming interviews, DP is perhaps the one that tests "general problem solving" the best. Many other problems require problem-specific tricks/uncommon tricks. On the other hand, there's rarely a DP problem (that comes up in interviews) that relies on a problem-specific trick.

Highly disagree with this. There are pretty significant approach differences between 2D DP, 1D DP, Tree DP, string operations, etc. Determining what you optimize and cache (if you do top-down, which I prefer) is often problem-specific. The way the optimal solutions are laid out the differences between the most efficient fibonacci (O(1) space), "House Robber" independent set problem, and various problems on top of str…

Disagree. The general concept is the same - "Where can you collapse states into one". Someone who understands DP well should find tree DP natural, and might even come up with it themselves without learning about it beforehand. I'm not sure what you mean by string operations - most string DP problems don't require special treatment.

I agree that there are significant approach differences. However, the high level approach of: 1. Find a DP state that allows you to collapse states. 2. Find DP state transitions 3. Solve the problem

is constant among problems. The most common complaint I've heard about interview problems is that they relied on some "trick" to solve - DP problems don't have these tricks.

Re: Dynamic Programming for Technical Interviews

#67

Post by chillee »

mayank wrote: post #50
chillee wrote: post #33

Earlier quoted context omitted.

I actually disagree. Of the problems that are commonly asked in programming interviews, DP is perhaps the one that tests "general problem solving" the best. Many other problems require problem-specific tricks/uncommon tricks. On the other hand, there's rarely a DP problem (that comes up in interviews) that relies on a problem-specific trick.

> On the other hand, there's rarely a DP problem (that comes up in interviews) that relies on a problem-specific trick. That's a pretty big parenthetical. DP problems as a class are full of clever tricks for elegant solutions that took decades of research. Any practical use of DP is almost certainly going to use problem-specific tricks as well. Which makes DP tricky, especially in interviews.

Yes, there's a ton of DP problems that require clever tricks. I've had to show these tricks to friends who believed that DP problems were too formulaic.

Could you give an example of DP problems that show up in interviews that require problem-specific tricks? I'm contrasting DP problems with other interview questions like: Find whether a linked list has a cycle in O(1) memory or implement a queue with 2 stacks.

Re: Dynamic Programming for Technical Interviews

#68

Post by matz1 »

sanderjd wrote: post #4

I have always felt that dynamic programming is only confusing because of the name. The concept of caching previously calculated values in order to save time by avoiding recalculation (at the cost of using more space) is intuitive. What am I missing?

I can relate, the name is so intimidating the first time I heard it.

Re: Dynamic Programming for Technical Interviews

#69

Post by matz1 »

alangpierce wrote: post #17

> problems on DP are pretty standard in most product-company-based hiring challenges This is sad and a little surprising to me. I've always thought of DP problems as being obviously terrible interview questions, even among the different types of algo questions (which are already heavily criticized). Candidates who have learned DP in school usually find them really easy, and candidates who haven't usually don't even h…

The good thing of these type of question is it can be practiced, and it's pretty much "standard". Once you comfortable with it you can essentially interview anywhere.

Re: Dynamic Programming for Technical Interviews

#70

Post by chillee »

bogomipz wrote: post #64
akhilcacharya wrote: post #52

Earlier quoted context omitted.

Highly disagree with this. There are pretty significant approach differences between 2D DP, 1D DP, Tree DP, string operations, etc. Determining what you optimize and cache (if you do top-down, which I prefer) is often problem-specific. The way the optimal solutions are laid out the differences between the most efficient fibonacci (O(1) space), "House Robber" independent set problem, and various problems on top of str…

I'm familiar with 1D and 2D but what are some examples of Tree DP besides the standard Fibonacci questions?

Fibonacci isn't considered Tree DP. One example of a tree DP problem is: Given a tree with N nodes, how many ways are there of coloring each node with black or white given that no two white nodes are adjacent.
Post reply on HN