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

171–180 of 225 posts

Re: Dynamic Programming for Technical Interviews

#171

Post by sanderjd »

akhilcacharya wrote: post #58
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?

Formulating the recursion and caching strategy is the difficult part and it is non-trivial to identify at times. For example, this is simple to explain in the abstract case but what about a concrete case like text justification or edit distance? The hardest part is getting to the recurrence relation, and then implementing it.

Does the term only apply to recursive solutions? Caching is often useful in iterative solutions as well; does that count?

I would pretty much never start an interview response with a recursive solution in an interview because I pretty much never end up with a recursive solution in my work. I have very rarely been asked to do something recursively having already done it iteratively.

Re: Dynamic Programming for Technical Interviews

#172

Post by sanderjd »

clickok wrote: post #9
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?

Richard Bellman coined the name, and according to legend it was because the phrase 'dynamic programming' was so anodyne that not even the most officious bureaucrat could object. In Bellman's own words[0]: "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 Secr…

Thank you for this story :)

He clearly had no idea he'd be burdening generations of programmers preparing for interviews.

Re: Dynamic Programming for Technical Interviews

#173

Post by zerocool2750 »

Aditya_Ramesh wrote: post #169
zerocool2750 wrote: post #133

In the knapsack example they say... > "No global variables should be modifed in the function" Am I wrong or does the author immediately go on to modify the global variable 'dp' p.s. @author typo in that sentence 'modifed'

Thanks for pointing out the typo! I'll fix that right away. And in regards to the "global variable", my variable 'dp' is my cache array. It's where I'm storing my precomputed results. If I don't modify it, it's not DP anymore, it's plain recursion. :) I guess I should've mentioned that the actual memoization table is an exception. Anyway, thanks for reading my article! :)

Totally makes sense I just think it's slightly confusing in that context. Anyway, awesome article I enjoyed the read!

Re: Dynamic Programming for Technical Interviews

#174

Post by [deleted] »

agbell wrote: post #135
imslavko wrote: post #32

This is a comment to demonstrate the differences between DP and memoized recursion to people in the sibling comments. When I was learning DP vs Memoization I thought Floyd-Washall algorithm to find shortest path length between all pairs of nodes in a graph is a good example of DP that wouldn't work the same way with memoization. In FW algorithm, because of the order of filling up the table and discarding old values o…

That is interesting but I still don't totally get how DP is different from simple memoization. Your fib example can be expressed as corecursion, and in fact, its an example often used to explain it. val fibsViaUnfold = unfold((res0, res1)) { case (f0, f1) => Some((f0, (f1, f0 + f1))) } fibsViaUnfold.take(7).toList shouldBe List(0, 1, 1, 2, 3, 5, 8) That's scala, but should work anywhere where we can produce a lazy st…

[deleted]

Re: Dynamic Programming for Technical Interviews

#175

Post by chillee »

bogomipz wrote: post #159
chillee wrote: post #70

Earlier quoted context omitted.

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.

Isn't that just the classic graph coloring problem though? A tree is just a type of graph.

Well, A. Not exactly because there's no restrictions on when you can color nodes black, and B. Graph coloring in general is NP-complete while this problem has an O(n) solution.

Re: Dynamic Programming for Technical Interviews

#176

Post by zodiac »

agbell wrote: post #135
imslavko wrote: post #32

This is a comment to demonstrate the differences between DP and memoized recursion to people in the sibling comments. When I was learning DP vs Memoization I thought Floyd-Washall algorithm to find shortest path length between all pairs of nodes in a graph is a good example of DP that wouldn't work the same way with memoization. In FW algorithm, because of the order of filling up the table and discarding old values o…

That is interesting but I still don't totally get how DP is different from simple memoization. Your fib example can be expressed as corecursion, and in fact, its an example often used to explain it. val fibsViaUnfold = unfold((res0, res1)) { case (f0, f1) => Some((f0, (f1, f0 + f1))) } fibsViaUnfold.take(7).toList shouldBe List(0, 1, 1, 2, 3, 5, 8) That's scala, but should work anywhere where we can produce a lazy st…

There's a "simple memoization" version of fibonacci that takes more space than `fibsViaUnfold`. I think the term "simple memoization" (and equivalents used in these comments) are a bit too imprecise to be useful.

Re: Dynamic Programming for Technical Interviews

#177

Post by akhilcacharya »

sanderjd wrote: post #171
akhilcacharya wrote: post #58

Earlier quoted context omitted.

Formulating the recursion and caching strategy is the difficult part and it is non-trivial to identify at times. For example, this is simple to explain in the abstract case but what about a concrete case like text justification or edit distance? The hardest part is getting to the recurrence relation, and then implementing it.

Does the term only apply to recursive solutions? Caching is often useful in iterative solutions as well; does that count? I would pretty much never start an interview response with a recursive solution in an interview because I pretty much never end up with a recursive solution in my work. I have very rarely been asked to do something recursively having already done it iteratively.

In a colloquial sense yes, DP includes both.

But to be precise, most people only consider the bottom-up approach to be actual Dynamic Programming.

Re: Dynamic Programming for Technical Interviews

#178

Post by asark »

JustSomeNobody wrote: post #132
hn_throwaway_99 wrote: post #54

Earlier quoted context omitted.

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

Come on, pointers are easy. In a 45 min interview you could teach someone pointers and still leave time to solve the problem. DP is much less easy to understand unless one has purposefully studied and solved a lot of DP problems. I agree with a lot of comments here. Interviewing for DP only nets you people who have studied DP.

There are several "hard" things in CS/software-development that I keep having to convince myself I do, in fact, understand, every time they come up in a discussion like this, because I find them really simple and wonder whether maybe I missed something. One's pointers. I don't get what's so hard about them. I mean I get why they might be tough the first time you're introduced to them but it's exactly the same kind of reasoning/structure that's used all over the place in programming, so if one can't understand pointers I'm not sure how one's programming at all, really.

Re: Dynamic Programming for Technical Interviews

#179

Post by PopeDotNinja »

wizzairflyer wrote: post #147
Jach wrote: post #105

Earlier quoted context omitted.

Talk is cheap, code is what matters. But maybe the interviewer wanted to save time not writing an incorrect solution if he believed your approach was wrong and you could talk yourself out of it? Did you get to step through how your solution would arrive at the number 14 given 2 eggs and 100 floors? And if you wrote it out, would it produce that number? (Personally I have no idea what you mean with the binary search a…

A funny trick is to ask this question but first give the candidate an infinite amount of eggs. Once he succeeds, ask the question with only 2 eggs. That might explain the binary search answer.

The approach would have been easier way for me to answer the question. I wrote something like that to guesstimate the number of git commits on GitHub a project I didn't have time to clone a few years back (I think it was Linux). Basically I started at page 1, then went to 2, 4, 8, 16, etc. When I hit a 404, I went back 50% of the way to the previous number (e.g. if it was page 1024, the previous was 512, then I went to 768). If 50% was a 404, go to back midpoint of lower range (e.g. midpoint of 512 and 768). It if was legit, go to midpoint of upper range (e.g. between 768 and 1024). Wash/rinse/repeat. It was a fun exercise to burn some time on a slow day. If someone actually wants to see the code, reply to this comment and I'll find it, or write it again.

Now I want to go back and study up on that dynamic programming stuff again! Yay inspiration!

Re: Dynamic Programming for Technical Interviews

#180

Post by zeroonetwothree »

chillee wrote: post #70
bogomipz wrote: post #64

Earlier quoted context omitted.

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.

That just has a straightforward recursive solution. I’m not even sure where the DP comes in beyond that.
Post reply on HN