Dynamic Programming for Technical Interviews • Hacker News Board

Re: Dynamic Programming for Technical Interviews

#31

Post by mesarvagya » Fri, Mar 15, 2019, 3:07 AM UTC

One of the techniques as described in CLRS is to first find the subproblem graph.

Consider Fibonacci sequence: f(0) = 0; f(1) = 1; f(n) = f(n-1) + f(n-2)

If we solve it naively, complexity will be O(1.6^n).

Now we can solve it in DP using two ways:

1. Top Down: Instead of recursively computing the same subproblem, just store the value of this computation and look it up when needed. That's it.

2. Bottom Up: One cannot come up with bottom up representation directly, unless we identify its recursive pattern and subproblems. Once we have this recursive pattern, just plot a graph for some values and we can identify overlapping subproblem and its overall graph.

Constructing graph for fib(5), we can see solutions from fib(4) and fib(3) are needed. Therefore, we need to find fib(3) and fib(4) before even solving for fib(5). Once we identify this graph, we can do bottom up, where we solve base solution (trivial or first node in graph) and construct our solution based in it.

Therefore, easy approach is to solve it top-down. Once it is done, we can identify subproblem graph and construct bottom up solution.

Re: Dynamic Programming for Technical Interviews

#32

Post by imslavko » Fri, Mar 15, 2019, 3:08 AM UTC

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 on the go, we are able to run the algorithm only using O(n^2) memory, but if we were to run it in a memoized recursive fashion, I would guess you will have to do with O(n^3) memory.

Another example is when a recurrence in DP only depends on the previous row (if we are going row by row) and you can only keep around O(n) memory swapping two rows representing the current row and the previous one. In a recursive black-boxy memoization method you will have to do with a full O(n^2) memory usage.

Finally, there is a technique to do DP on a table using O(n) memory vs O(n^2) and recovering the optimal path by recursively splitting the table into halves and only storing O(1) rows at a time. This technique is more complicated to explain in an HN comment tho.

Update: forgot the simplest example: fibonacci numbers. In the top-down approach, you would memoize results based on the index of the fib number, so you would need an array of results caching O(n) values. But if you build it up bottom-up, you can get away with only using two variables: previous and current and the do something like:

    prev, cur = cur, prev + cur

Re: Dynamic Programming for Technical Interviews

#33

Post by chillee » Fri, Mar 15, 2019, 3:13 AM UTC

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.

Re: Dynamic Programming for Technical Interviews

#34

Post by gowld » Fri, Mar 15, 2019, 3:13 AM UTC

zestyping wrote: post #3

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

Consider Fibonacci. Memoized recursion uses O(n) memory, because you don't garbage-collect anything. Bottom-up dynamic programming is O(1) memory, because you only need to remember the largest 2 subvalues you've computed.

Re: Dynamic Programming for Technical Interviews

#35

Post by elteto » Fri, Mar 15, 2019, 3:15 AM UTC

kccqzy wrote: post #28

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…

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 :)

Re: Dynamic Programming for Technical Interviews

#36

Post by chillee » Fri, Mar 15, 2019, 3:15 AM UTC

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

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.

Re: Dynamic Programming for Technical Interviews

#37

Post by vowelless » Fri, Mar 15, 2019, 3:16 AM UTC

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

Dynamic Programming is a concept from control theory in which the goal is to optimize a specific type of equation. Here, "programming" doesn't mean the same word as in "computer programming". It's just a carry over word from the field of optimization and mathematical modeling [0].

Goal is to optimize some problem that can be framed as having the following properties: an optimal solution to the overall problem will result in optimal solutions for all "subproblems" and these "subproblems" are not all disjoint. If they are disjoint, then don't need to use DP, but you can use a simpler divide and conquer approach (example: you don't need DP to solve mergesort)

Such problems are everywhere. Lots of path planning, shortest path type problems are DP based (high level ex: shortest path from A to C going via B necessarily will imply that the path from A to B is the shortest and B to C is the shortest). In reinforcement learning, similar ideas are crucial. Relatedly, in game theory, these types of problems arise in the form of subgame perfect equilibriums.

Thinking graphically, I believe all DPs can be represented as directed acyclical (hyper)graphs. So, the optimal solution on this graph will mean that the subgraphs in the solution also have optimal solutions, and that these subgraphs overlap.

In computer science, the optimizations tend to work incrementally as a 'wavefront' from the smallest subgraph (usually some basecases, starting points) -- using the solution to the current subgraph in the larger subgraph, etc. Eventually, the wavefront covers the relevant parts of the graph. This is what people tend to call "bottom up".

[0] http://web.mit.edu/15.053/www/AppliedMathematicalProgramming...

Re: Dynamic Programming for Technical Interviews

#38

Post by smallnamespace » Fri, Mar 15, 2019, 3:29 AM UTC

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.

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.org/wiki/Signalling_theory

Also, if being able to learn completely arbitrary things is correlated with intelligence and correlated with job performance, then people who are willing to jump through that arbitrary hoop are telling you that 1) they think they're more capable (faster learners) than average 2) they're willing to put in the effort to prove it to you. Maybe you're not a getting a pure signal of mathematical ability, but some combination of drive + ability + learning fast, and you care about all three.

Re: Dynamic Programming for Technical Interviews

#39

Post by rifung » Fri, Mar 15, 2019, 3:30 AM UTC

chillee wrote: post #36

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

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 programming to be applicable: optimal substructure and overlapping sub-problems. If a problem can be solved by combining optimal solutions to non-overlapping sub-problems, the strategy is called "divide and conquer" instead"

Re: Dynamic Programming for Technical Interviews

#40

Post by throwawaymath » Fri, Mar 15, 2019, 3:37 AM UTC

rfrey wrote: post #23

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…

>This is sad and a little surprising to me. I think dynamic programming is in fashion because of the rise of reinforcement learning among the buzzword savvy.

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.