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

111–120 of 225 posts

Re: Dynamic Programming for Technical Interviews

#111

Post by YorkshireSeason »

gaogao wrote: post #60
throwawaymath wrote: post #40

Earlier quoted context omitted.

To my recollection, dynamic programming problems were fasionable interview questions prior to the current wave of machine learning. That's to say I'm pretty sure they were being asked at Google/Facebook/etc around 2012 at least, likely earlier.

At the FANG I'm at, DP is now heavily discouraged with a note that it was once a very common interview topic.

What are you encouraged to do with the problems of recursion that DP addresses, stack overflow and overlapping instances?

Re: Dynamic Programming for Technical Interviews

#113

Post by albertzeyer »

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…

Yes, basically it is exactly that. (For why it is called like that, see other answers; but that's also somewhat irrelevant.)

But the main task is to identify how to iteratively / recursively solve the problem and what to cache (and then you should also be able to tell how efficient your solution is). This is the tricky bit. It doesn't matter if you call it DP or whatever. But it matters to be able to come up with efficient solutions for such problems. And this is what companies want to see.

Re: Dynamic Programming for Technical Interviews

#114

Post by matt-snider »

jonsen wrote: post #99
mafm wrote: post #81

Earlier quoted context omitted.

> [...] 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. […

Formatted for mobile: 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 c…

Thanks :-). This comes up so often! Is there a reason HN doesn't use a more mobile-friendly format for preformatted text?

Re: Dynamic Programming for Technical Interviews

#115

Post by pavlov »

dnautics wrote: post #94
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…

I asked a dp question in an interview. It was useful. Here's why. I know the solution, so I frequently guide the interviewee towards the correct answer and offer my help. Plus I put my nice guy hat on. I have seen a supposedly good candidate refuse my offers of help and then proceed to spaghetti code on the board a series of disjointed while loops that is obviously going to go nowhere. I don't want to work with such…

> "I know the solution, so I frequently guide the interviewee towards the correct answer and offer my help. Plus I put my nice guy hat on."

I wouldn't want to work with a person whose idea of a useful job interview is:

"I'll pick an esoteric bullshit problem, put my nice guy hat on, and guide you towards the solution as I bask in your admiration of my largesse."

It's like when self-declared "nice guys" approach women: when you have to make an explicit point about how nice you are being right now, you're probably doing something very wrong.

Re: Dynamic Programming for Technical Interviews

#116

Post by oblio »

mafm wrote: post #81
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…

> [...] 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. […

> 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.

Amusingly, Engine Charlie [1] was an engineer. You'd think an engineer understands the value of research :)

[1] https://en.wikipedia.org/wiki/Charles_Erwin_Wilson

Re: Dynamic Programming for Technical Interviews

#117

Post by roenxi »

candeira wrote: post #27

Dynamic Programming and memoization are definitely related techniques, but they are emphatically _not_ the same. Memoization is a black-box approach that can be applied to a generic recursive top-down, depth-first algorithm. Dynamic Programming is about rewriting the recursive top-down algorithm in a bottom-up, breadth-first manner. Shriram Krishnamurthi explains it best: https://blog.racket-lang.org/2012/08/dynamic-…

It is a good write up, but it underscores the mystery of how DP ever got named as a technique.

Memoization is a great general-purpose technique that covers pretty much all the obvious cases for DP to a reasonable standard. Its black-box nature allows for effective and well compartmentalised application.

DP is an extremely complicated and invasive technique that requires rewriting algorithms to optimise for space & time use.

It doesn't seem like the advantages of DP are enough to outweigh the neat design of memoisation. I'd rather see an interview question on implementing memoize in Python than writing a DP algorithm.

Re: Dynamic Programming for Technical Interviews

#118

Post by stan_rogers »

matt-snider wrote: post #114
jonsen wrote: post #99

Earlier quoted context omitted.

Formatted for mobile: 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 c…

Thanks :-). This comes up so often! Is there a reason HN doesn't use a more mobile-friendly format for preformatted text?

The feature is intended for code, note block quotes. Auto line wraps would be less than helpful.

Re: Dynamic Programming for Technical Interviews

#119

Post by [deleted] »

matt-snider wrote: post #114
jonsen wrote: post #99

Earlier quoted context omitted.

Formatted for mobile: 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 c…

Thanks :-). This comes up so often! Is there a reason HN doesn't use a more mobile-friendly format for preformatted text?

[deleted]

Re: Dynamic Programming for Technical Interviews

#120

Post by nosianu »

reallydontask wrote: post #109
solveit wrote: post #106

Earlier quoted context omitted.

> It would be good if the problem is unsolved and the interviewer him-/herself does not know the answer. I think one-use questions like this must be are bad. It makes it harder to compare candidates, which is what you really want in an interview.

you can also think about them another way, namely: How long it took somebody else in your team to solve the same problem Making allowances for interview conditions, namely high stress levels, etc ... Not perfect but an idea worth exploring. I speak as a former smug interviewer that while didn't ask DP questions, did have a set of favourite questions

> How long it took somebody else in your team to solve the same problem

I don't think that is useful. Variance is too great, even for a constant single person.

I think that anything that attempts to cast this issue as some objectifiable measurement problem is on the wrong track. Measurements work - on a statistical scale. Even then its hit or miss depending on how good the chosen values to be measured are. Just like public health issues. As soon as you try those approaches that work just fine on a large scale on individual problems you are toast. The results of those individual decisions can be measured using statistical methods, but don't try them on individuals.

Post reply on HN