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

81–90 of 225 posts

Re: Dynamic Programming for Technical Interviews

#81

Post by mafm »

deepGem wrote: post #75
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…

"and candidates who haven't usually don't even have a chance at solving them" I am one of those candidates, and I don't know why it is called Dynamic programming. To me a vey naive understanding of DP is this - it's just a simple cache mechanism to store intermediary results so that you don't have to recompute them and waste resources. In the real world we always think about and do such optimizations, be it I/O, disk…

> [...] I don't know why it is called Dynamic programming.

According to Richard Bellman, who came up with the name:

  An interesting question is, Where did the name, dynamic programming, come from?

  The 1950s were not good years for mathematical research. We had a very interesting gentleman in Washington
  named Wilson. He was Secretary of Defense, and he actually had a pathological fear and hatred of the 
  word research. [...] What title, what name, could I choose?
  
  In the first place I was interested in planning, in decision making, in thinking. But planning, is not a
  good word for various reasons. I decided therefore to use the word "programming"

  [...] it's impossible to use the word "dynamic" in a pejorative sense. Try thinking of some combination
  that will possibly give it a pejorative meaning. It's impossible.

  Thus, I thought dynamic programming was a good name. It was something not even a Congressman could object to.

Re: Dynamic Programming for Technical Interviews

#82

Post by tikhonj »

deepGem wrote: post #75
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…

"and candidates who haven't usually don't even have a chance at solving them" I am one of those candidates, and I don't know why it is called Dynamic programming. To me a vey naive understanding of DP is this - it's just a simple cache mechanism to store intermediary results so that you don't have to recompute them and waste resources. In the real world we always think about and do such optimizations, be it I/O, disk…

The tricky thing with dynamic programming is realizing that it fits—you have to understand how the problem you're solving decomposes into overlapping subproblems that are worth caching. Once you know what the subproblems are, implementing the algorithm is mostly a matter of getting some fiddly indexing logic right.

Take string edit distance for example: the key to the dynamic programming problem is seeing how the exponential blow up of possibilities actually has a rich overlapping structure that you can cache in a table. If you didn't know string edit distance was amenable to dynamic programming, you might not realize it at all even if you are constantly thinking about caching results. Once you see the structure, the algorithm becomes relatively straightforward.

Re: Dynamic Programming for Technical Interviews

#83

Post by jogjayr »

groby_b wrote: post #74
jogjayr wrote: post #62

Earlier quoted context omitted.

> 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 g…

> 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. Yeah, no. (Source: I've seen a few interviews in my time. On the order of 5k of them) DP problems are absolute shit at giving a signal, even if the candidate knows DP problems. Because "knows DP" is pretty much the only bit of information you get, with possibly a slight…

> I've seen a few interviews in my time. On the order of 5k of them)

That's actually pretty cool. May I ask how?

> Because "knows DP" is pretty much the only bit of information you get

Yes if the candidate meets with only one interviewer or if every interviewer asks only DP. I hope most companies don't interview that way - that would truly be a broken interview process. Obviously you ask about other stuff in the other interviews.

> The interviewer picked them up somewhere, is now familiar with them,

Lol, isn't that one reason every interview question is asked? I've never asked a question whose answer I wasn't familiar with. I know how you meant that though.

There are plenty of companies that don't do whiteboard problems or ask DP. Here's a few: https://github.com/poteto/hiring-without-whiteboards

> We could ask people to, IDK, write code that solves actual problems

It's pretty hard to get someone solving actual problems in a single day. Do you have some examples of how this might be done?

Re: Dynamic Programming for Technical Interviews

#84

Post by deepGem »

tikhonj wrote: post #82
deepGem wrote: post #75

Earlier quoted context omitted.

"and candidates who haven't usually don't even have a chance at solving them" I am one of those candidates, and I don't know why it is called Dynamic programming. To me a vey naive understanding of DP is this - it's just a simple cache mechanism to store intermediary results so that you don't have to recompute them and waste resources. In the real world we always think about and do such optimizations, be it I/O, disk…

The tricky thing with dynamic programming is realizing that it fits—you have to understand how the problem you're solving decomposes into overlapping subproblems that are worth caching. Once you know what the subproblems are, implementing the algorithm is mostly a matter of getting some fiddly indexing logic right. Take string edit distance for example: the key to the dynamic programming problem is seeing how the exp…

Absolutely, but I attribute the ability to decompose a problem into overlapping subproblems as an understanding of recursion, so I had implicitly assumed such an understanding.

Re: Dynamic Programming for Technical Interviews

#85

Post by burfog »

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,…

A good excuse for struggling with recursion is that the person is a kernel programmer. There, on a very limited stack, recursion is so dangerous that programmers develop a strong reflex to get rid of recursion. If you tell them to produce something recursive, at every line of code their mind will be screaming DANGER and trying to fix the problem.

Such people are better tested on problems involving cache lines, TLB entries, memory-mapped IO hardware, DMA, atomic instruction opcodes, and interrupts.

Re: Dynamic Programming for Technical Interviews

#86

Post by pmiller2 »

jogjayr wrote: post #83
groby_b wrote: post #74

Earlier quoted context omitted.

> 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. Yeah, no. (Source: I've seen a few interviews in my time. On the order of 5k of them) DP problems are absolute shit at giving a signal, even if the candidate knows DP problems. Because "knows DP" is pretty much the only bit of information you get, with possibly a slight…

> I've seen a few interviews in my time. On the order of 5k of them) That's actually pretty cool. May I ask how? > Because "knows DP" is pretty much the only bit of information you get Yes if the candidate meets with only one interviewer or if every interviewer asks only DP. I hope most companies don't interview that way - that would truly be a broken interview process. Obviously you ask about other stuff in the othe…

On a lot of companies’ interview loops, if one interviewer says “no hire,” it’s an overall “no hire.” If that person is asking DP, and you don’t know it, then you will fail the whole interview.

Re: Dynamic Programming for Technical Interviews

#87

Post by pmiller2 »

brianberns wrote: post #80
groby_b wrote: post #74

Earlier quoted context omitted.

> 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. Yeah, no. (Source: I've seen a few interviews in my time. On the order of 5k of them) DP problems are absolute shit at giving a signal, even if the candidate knows DP problems. Because "knows DP" is pretty much the only bit of information you get, with possibly a slight…

> Here's an entirely novel concept for evaluating if somebody can write code that solves actual problems. We could ask people to, IDK, write code that solves actual problems. They're there for a day. A good coder can solve some pretty interesting problems in a day. You mean solve an actual business problem that the interviewing company has? The ramp-up time to be productive in any real business that I've been associa…

Not an actual problem the company has, but a pared down version of a problem the company had.

Re: Dynamic Programming for Technical Interviews

#88

Post by pmiller2 »

smallnamespace wrote: post #38
elteto wrote: post #35

Earlier quoted context omitted.

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. Metrics that can be gamed can still have a lot of signal in them because the cost of gaming the metric is higher than the benefit of gaming things. There's a branch of game theory/economics called signalling theory that's applicable here: https://en.wikipedia.o…

If the ability to learn completely arbitrary things is what they want to test, why not have them write an essay on the spot in Sanskrit?

Re: Dynamic Programming for Technical Interviews

#89

Post by brianberns »

pmiller2 wrote: post #87
brianberns wrote: post #80

Earlier quoted context omitted.

> Here's an entirely novel concept for evaluating if somebody can write code that solves actual problems. We could ask people to, IDK, write code that solves actual problems. They're there for a day. A good coder can solve some pretty interesting problems in a day. You mean solve an actual business problem that the interviewing company has? The ramp-up time to be productive in any real business that I've been associa…

Not an actual problem the company has, but a pared down version of a problem the company had .

Easier said than done. You probably end up with something that's essentially a toy problem anyway.

Re: Dynamic Programming for Technical Interviews

#90

Post by smallnamespace »

pmiller2 wrote: post #88
smallnamespace wrote: post #38

Earlier quoted context omitted.

> 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. Metrics that can be gamed can still have a lot of signal in them because the cost of gaming the metric is higher than the benefit of gaming things. There's a branch of game theory/economics called signalling theory that's applicable here: https://en.wikipedia.o…

If the ability to learn completely arbitrary things is what they want to test, why not have them write an essay on the spot in Sanskrit?

Dynamic programming is far from completely arbitrary. But even if it were completely arbitrary, it would still serve a useful signaling function as long as people agreed on which hoops they're supposed to jump through.

A peacock's plumage serve little useful purpose except to show how fit he is; but that purpose is essential to the survival of the species.

Post reply on HN