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

41–50 of 225 posts

Re: Dynamic Programming for Technical Interviews

#41

Post by alangpierce »

chillee wrote: post #29
alangpierce wrote: post #12

Earlier quoted context omitted.

I've done a lot of programming contest stuff, and at least when speaking casually, I've always heard DP as referring to either the top-down approach or the bottom-up approach. They have their tradeoffs (though usually top-down is better because it's easier to implement), but they're both DP. It may be that you're technically not supposed to use the term "DP" for the top-down variant, but in practice people use the te…

I'd say that in competitive programming, bottom-up is actually preferred. Bottom up is faster, usually shorter to code, and allows certain kinds of optimizations you can't do with top down (sliding window, convex hull trick, etc). Top down frees you from needing to think about order of computation, and also allows a different set of optimizations from bottom up (divide & conquer).

TBH it's been a while since I've done these contests seriously, but I remember the "order of computation" problem to be hard to think about for less trivial cases (like with a 3-dimensional table). But maybe I worried about it too much.

And just for fun, while we're listing these things:

Another advantage to bottom-up that I've seen is that sometimes top-down causes your recursion to get so deep that you run out of space in your call stack. Another advantage to top-down is that you're only filling in the subset of the table that's needed for the specific problem you're solving. Certainly someone with a lot of experience should be able to do both.

Re: Dynamic Programming for Technical Interviews

#42

Post by chillee »

rifung wrote: post #39
chillee wrote: post #36

Earlier quoted context omitted.

This is one definition, but I don't think it's the common one. The more common definition is that dynamic programming refers to solving a complicated problem by breaking it up into simpler overlapping subproblems that can be solved independently. Solving it with recursion/memoization vs. bottom-up is merely an implementation detail, while DP refers to a class of algorithms. EDIT: Corrected definition of DP.

> The more common definition is that dynamic programming refers to solving a complicated problem by breaking it up into simpler subproblems that can be solved independently I dont think that's sufficient? I thought DP also implies you actually reuse the answers from subproblems. From https://en.m.wikipedia.org/wiki/Dynamic_programming "There are two key attributes that a problem must have in order for dynamic program…

Yeah, you're right. The subproblems must overlap.

Re: Dynamic Programming for Technical Interviews

#43

Post by slavik81 »

tyingq wrote: post #22
alangpierce wrote: post #20

Earlier quoted context omitted.

Yep, it's still certainly DP, in the same sense that 1 + 1 is addition, but understanding 1 + 1 doesn't necessarily mean that you've mastered addition.

Just trying to understand the concept/name. I'm clearly not the only one confused. Say I, at runtime, build a table of function pointers. Based on some attribute/test of the input that suggests a specific type of function is faster for that type of input. If it's faster, but not exponentially faster than a naive solution...is that "dynamic"?

The name "Dynamic Programming" was coined to be deliberately confusing by an early researcher in the field for the sake of maintaining research funding in a hostile environment [1]. Don't worry too much about the components of the name.

[1]: https://en.wikipedia.org/wiki/Dynamic_programming#History

Re: Dynamic Programming for Technical Interviews

#44

Post by chillee »

alangpierce wrote: post #41
chillee wrote: post #29

Earlier quoted context omitted.

I'd say that in competitive programming, bottom-up is actually preferred. Bottom up is faster, usually shorter to code, and allows certain kinds of optimizations you can't do with top down (sliding window, convex hull trick, etc). Top down frees you from needing to think about order of computation, and also allows a different set of optimizations from bottom up (divide & conquer).

TBH it's been a while since I've done these contests seriously, but I remember the "order of computation" problem to be hard to think about for less trivial cases (like with a 3-dimensional table). But maybe I worried about it too much. And just for fun, while we're listing these things: Another advantage to bottom-up that I've seen is that sometimes top-down causes your recursion to get so deep that you run out of s…

Some examples where order of computation isn't that trivial is when you're doing DP on trees or a DAG.

+1 to the "filling in a subset" part. Usually it's not too relevant because it's merely a constant factor change, but occasionally it'll be very important.

Re: Dynamic Programming for Technical Interviews

#45

Post by ufo »

zestyping wrote: post #3

Is dynamic programming the same as memoized recursion, or does it include techniques beyond that?

Pretty much. Although sometimes it is more natural to build up the solution "bottom up" instead of using memoization.

The tricky bit is figuring out what is the recurrence relation (recursion) for the problem you are trying to solve.

Re: Dynamic Programming for Technical Interviews

#46

Post by alangpierce »

tyingq wrote: post #22
alangpierce wrote: post #20

Earlier quoted context omitted.

Yep, it's still certainly DP, in the same sense that 1 + 1 is addition, but understanding 1 + 1 doesn't necessarily mean that you've mastered addition.

Just trying to understand the concept/name. I'm clearly not the only one confused. Say I, at runtime, build a table of function pointers. Based on some attribute/test of the input that suggests a specific type of function is faster for that type of input. If it's faster, but not exponentially faster than a naive solution...is that "dynamic"?

> is that "dynamic"?

Nope, DP is a bit more than "build a table" or "cache results". It's specifically about framing a problem recursively, and it needs to be the sort of recursion that has overlapping subproblems. For example, fib(8) and fib(7) will both call fib(6), which means that it's useful to cache fib(6). Some problems (like counting the number of nodes in a tree) are recursive but don't have overlapping recursion, so DP doesn't help with those.

(Sorry, I didn't mean my "addition" comment to sound condescending! I just meant that memoized recursive fibonacci is a simple example of DP, and the fact that it's (relatively) simple doesn't mean it's not DP.)

Re: Dynamic Programming for Technical Interviews

#47

Post by chillee »

reader5000 wrote: post #21
tyingq wrote: post #2

So "DP" is just recursion with memoization? Or an I missing another piece? Edit: apparently I'm not the only one thinking this: https://news.ycombinator.com/item?id=19395862

Recursion with memoization can still take exponential time whereas a DP solution is usually going to be quadratic or better.

That's not really true. There's plenty of DP solutions that are >cubic or exponential.

Re: Dynamic Programming for Technical Interviews

#48

Post by jonahx »

protomyth wrote: post #30
jonahx wrote: post #13

Earlier quoted context omitted.

1. Solutions are typically written bottom up 2. The meat of the problem is understanding how to formulate it such that this "recursion" is possible. Point two is often non-trivial so your "just" -- while technically correct -- isn't true in practice. If you solve a variety of medium and difficult DP problems, it will be clear why. Eg: https://www.hackerrank.com/domains/algorithms?filters%5Bsubd... (I have no affiliat…

So, I should review my Thinking Forth book before the interview to get my bottom-up practice, or am I totally missing what is going on?

I'd just try a couple of those problems and see how much practice you need.

Re: Dynamic Programming for Technical Interviews

#49

Post by tyingq »

alangpierce wrote: post #46
tyingq wrote: post #22

Earlier quoted context omitted.

Just trying to understand the concept/name. I'm clearly not the only one confused. Say I, at runtime, build a table of function pointers. Based on some attribute/test of the input that suggests a specific type of function is faster for that type of input. If it's faster, but not exponentially faster than a naive solution...is that "dynamic"?

> is that "dynamic"? Nope, DP is a bit more than "build a table" or "cache results". It's specifically about framing a problem recursively, and it needs to be the sort of recursion that has overlapping subproblems. For example, fib(8) and fib(7) will both call fib(6), which means that it's useful to cache fib(6). Some problems (like counting the number of nodes in a tree) are recursive but don't have overlapping recu…

Ahh, that "overlap" qualifier is helpful. I roughly get it now. Thanks!

The funny thing is that I'd much rather use something like this back and forth discussion in an interview. It tells me more than a coding test.

Re: Dynamic Programming for Technical Interviews

#50

Post by mayank »

chillee wrote: post #33
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 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.

Post reply on HN