16 ms·

Dynamic Programming for Technical Interviews

470 points by Aditya_Ramesh 8y ago

mlthoughts2018 8y ago
I never much enjoyed dynamic programming and I do think it’s a poor choice for timed interview questions, but I did become more interested in it when I realized there are patterns to the cache strategies that can be used to group problems. For example like the usual matrix raster fill approach for e.g. 0-1 knapsack, or sepatately using two cursors to fill the upper triangle of a matrix like for longest common subsequence and for optimal order of associative computation (like matrix multiplication).
tyingq 8y ago
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 https://news.ycombinator.com/item?id=19395862
- sanderjd 8y ago
  lol yep and I just made basically the same comment as well.
  - zestyping 8y ago
    Hey, nice timing. High five, everyone.
- Cyph0n 8y ago
  Based on my understanding, the key difference with DP is that you build the solution bottom up instead of top-down. For example, in case of computing the factorial of 10 recursively, you would start at fact(10) and move down to the base case, fact(1). With DP, you would start with fact(1) and compute succesive results based on computed ones, all the way up to fact(10). Following on from this, you usually build up the solution in an array, sequentially, instead of navigating down the tree of solutions and storing as you go (memoization).
  - alangpierce 8y ago
    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 term to refer to both.
    - chillee 8y ago
      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).
      - alangpierce 8y ago
        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.
        chillee 8y ago
        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.
- stale2002 8y ago
  Honestly? Yeah... It basically is. This is harder than it sounds though. DP problems tend to be solvable in only a couple lines of code, but the tough part is deciding what to recurve on, and what to memoize.
- jonahx 8y ago
  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%5Bsubdomains%5D%5B%5D=dynamic-programming https://www.hackerrank.com/domains/algorithms?filters%5Bsubd... (I have no affiliation with the site)
  - protomyth 8y ago
    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?
    - jonahx 8y ago
      I'd just try a couple of those problems and see how much practice you need.
- alangpierce 8y ago
  > So "DP" is just recursion with memoization? Sort of. "I know DP" doesn't just mean "I know what memoized recursion is". It means "I know how to take a problem, recognize that DP might help, frame it recursively with highly-overlapping subproblems, and use memoized recursion to implement an efficient algorithm for it". Especially in advanced cases, it take a lot of skill to look at a problem in just the right way that memoized recursion makes it computationally easy. For example, sometimes you might have a problem where the simple DP approach takes n^3 space, but with some trickery you can get it down to n^2.
  - tyingq 8y ago
    So, what about something relatively straightforward? Like Fibonacci. Is it "DP" if I recurse+cache?
    - alangpierce 8y ago
      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.
      - tyingq 8y ago
        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"?
        slavik81 8y ago
        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 https://en.wikipedia.org/wiki/Dynamic_programming#History
- reader5000 8y ago
  Recursion with memoization can still take exponential time whereas a DP solution is usually going to be quadratic or better.
  - chillee 8y ago
    That's not really true. There's plenty of DP solutions that are >cubic or exponential.
- mrburton 8y ago
  I think many people struggle with understanding "Dynamic Programming." Hopefully the following clears it up for you. Dynamic Programming can be done using Memoization (top-down; aka recursively) or Tabular method (bottom-up). So what's the difference? When you see top-down, it means to start from the root of the problem and recursively descend to the base case. As you pop up the stack, you will either calculate and store the result or look up the value in the cache. e.g., in the Fibonacci sequence, check to see if fib(4) was already calculated. No? Calculated and store it so the next time you come across this, you can use the result and not worry about processing fib(1), fib(2), fib(3), etc. When you see bottom-up, think about filling out a table from the upper left corner column by column then row by row. To speed performance, you'll look at prior values, the value in the column above vs. column to the left vs. or column diagonally to the left. I know this sounds a bit strange, but if you solve the following problems, you'll see a repeating pattern. Edit Distance 0/1 Knapsack Rod Cutting Longest Common Subsequence Longest Path in Matrix Coin Change I've been writing about this in detail. Eventually I'll publish my writing to help others. I solve ~20 problems using Memoization and the Tabular method. As I solve each problem, I compare the solutions with prior problems showing the pattern. What I want to do is help people spot "patterns" vs. memorizing algorithms that are very problem specific.
  - zestyping 8y ago
    Thanks for helping clear this up. It seems that many dynamic programming solutions can be arrived at by starting with a recursive formulation, adding memoization, and then optimizing the cache based on specialized knowledge of the problem. For example: 1. Q: How can you compute Fibonacci number f(n) recursively? A: f(n) = f(n-1) + f(n-2) 2. Q: How can you memoize the results of your recursive function(s) to dramatically reduce the number of calls? A: Make a cache keyed on n that stores f(n). 3. Q: Given specialized understanding of the problem, how can you minimize the size of the cache? A: Notice that you don't need to keep all O(n) slots; you only need to keep two ints. Can every dynamic programming solution be explained this way? Or is there a good example of a dynamic programming problem for which you really need to make a leap that can't be sensibly reached through this sequence of three questions?
- vowelless 8y ago
  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.pdf http://web.mit.edu/15.053/www/AppliedMathematicalProgramming...
zestyping 8y ago
Is dynamic programming the same as memoized recursion, or does it include techniques beyond that?
- sn41 8y ago
  It is basically memoized recursion. However, that does not mean that it is easy. To find out the optimal substructure - that is, building the solution to the problem from the optimal solution of its subproblem decomposition - is where the actual difficulty of the technique lies. Exercises from a standard algorithm textbook like Kleinberg and Tardos should give enough practice in solving these problems. Not all of them are straightforward.
- gowld 8y ago
  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.
- ufo 8y ago
  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.
sanderjd 8y ago
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?
- sgkzr 8y ago
  Not really much. The only difference is that DP could have smaller cache size if calculation order is planned. And I agree with you that it's only confusing because of the name.
- clickok 8y ago
  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 Secretary of Defense, and he actually had a pathological fear and hatred of the word, research. I’m not using the term lightly; I’m using it precisely. His face would suffuse, he would turn red, and he would get violent if people used the term, research, in his presence. You can imagine how he felt, then, about the term, mathematical. The RAND Corporation was employed by the Air Force, and the Air Force had Wilson as its boss, essentially. Hence, I felt I had to do something to shield Wilson and the Air Force from the fact that I was really doing mathematics inside the RAND Corporation. 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.’ I wanted to get across the idea that this was dynamic, this was multistage, this was time-varying—I thought, let’s kill two birds with one stone. Let’s take a word that has an absolutely precise meaning, namely dynamic, in the classical physical sense. It also has a very interesting property as an adjective, and that is 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. So I used it as an umbrella for my activities." ----- 0. From http://arcanesentiment.blogspot.com/2010/04/why-dynamic-programming.html http://arcanesentiment.blogspot.com/2010/04/why-dynamic-prog...
petermcneeley 8y ago
The knapsack problem here is of particular interest since despite the optimization problem being NP-hard the solution can in fact be found in O(n * W). This feels similar to how the theoretical best comparison sort is O( n log n) but radix can do this in O( n).
- mesarvagya 8y ago
  Knapsack still is a NP-Hard Problem. Even though DP solution looks linear, it has pseudo-polynomial time complexity[1][2] [1]https://en.wikipedia.org/wiki/Knapsack_problem#Computational_complexity https://en.wikipedia.org/wiki/Knapsack_problem#Computational... [2] https://stackoverflow.com/questions/4538581/why-is-the-knapsack-problem-pseudo-polynomial https://stackoverflow.com/questions/4538581/why-is-the-knaps...
alangpierce 8y ago
> 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 have a chance at solving them, so really they just test whether the person has learned DP, rather than other algo problems where you can at least try to claim that it's a proxy for "general problem solving ability". And DP comes up almost never in the real world (and when it does come up, you're often still better off taking a heuristic/inexact approach), so testing if the candidate knows DP is also almost completely useless. If you're an interviewer at a company that asks DP questions, please reconsider. There are almost certainly alternatives that are more fair and higher-signal.
- rfrey 8y ago
  >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.
  - chillee 8y ago
    I really doubt it. The type of reasoning needed for dynamic programming interview problems is barely connected to DP in reinforcement learning.
  - throwawaymath 8y ago
    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.
    - gaogao 8y ago
      At the FANG I'm at, DP is now heavily discouraged with a note that it was once a very common interview topic.
adamnemecek 8y ago
I’ve found this blog post to be the best of the bunch http://blog.ezyang.com/2010/11/dp-zoo-tour/ http://blog.ezyang.com/2010/11/dp-zoo-tour/
- ctchocula 8y ago
  This way of illustrating categories of DP problems seems really intuitive to me. Thanks for sharing.
aboutruby 8y ago
Only company I know of asking for "Dynamic Programming" is LinkedIn, is there any others?
- thewarrior 8y ago
  Google ?
candeira 8y ago
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-programming-versus-memoization.html https://blog.racket-lang.org/2012/08/dynamic-programming-ver...
- chillee 8y ago
  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.
  - rifung 8y ago
    > 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 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"
    - chillee 8y ago
      Yeah, you're right. The subproblems must overlap.
  - candeira 8y ago
    I understand that DP requires turning a recursive, top-down algorithm into an iterative one by yes, reusing the overlap in the subsolutions. And Krishamurthi's definition is the clearer I've seen that doesn't include "memoized recursion" as a subset of Dynamic Programming.
mesarvagya 8y ago
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.
- akhilcacharya 8y ago
  This is all well and good for fibonacci but it feels like the difficulty of the problem becomes exponentially greater when you start running into more complicated optimization strategies. Text justification is an example: [0] http://courses.csail.mit.edu/6.006/fall09/lecture_notes/lecture20.pdf http://courses.csail.mit.edu/6.006/fall09/lecture_notes/lect...
imslavko 8y ago
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
- hvidgaard 8y ago
  DP is a mathematically term describing certain problems. It does not state that you need to save all solutions to sub problems. If you do have a DP problem, the fastest way to solve it is with recursion and memoization as needed because of the properties of the problem.
  - imslavko 8y ago
    I am not arguing with this. In my comment my intend was to show that the distinction between the memoized top-down approach and bottom-up (the approach that is usually taught as DP in a classroom) is significant in some memory optimizations.
- agbell 8y ago
  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 stream of values. Here is a python version from wikipedia def nth_factorial(k): n, f = 0, 1 while n < k: n, f = n + 1, f * (n + 1) yield f Is DP a techique to arrive at the corecursive solution?
akhilcacharya 8y ago
The problem with DP problems (for me) is there seem to be a really large set of unique DP problems and coin change, knapsack, and grid DP problems like number of paths are only a small subset of them. What's more is that the rest of the problems can't be easily based on the approaches used for these...there might be dozens of problem classes to understand!
- ralusek 8y ago
  That might be the only dynamic thing about the otherwise terribly-named set of problems.
ram_rar 8y ago
After spending a lot of time interviewing candidates. I have pretty much come to the conclusion that DP problems dont give good signals about candidates problem solving skills. In my experience, less 5% of candidates can genuinely crack problems using DP. Most of them either give me memorized solution or just plain give up. If you are interviewing for a regular CRUD job aka web application. There are soo many other problems which can give much more refined signal about candidates skill. Please for love of God, dont ask DP. Unless you actually use it at work.
neilwilson 8y ago
Thirty years after it was first highlighted, we still don’t ask a juggler to actually juggle before hiring them. Admittedly we have moved on from simply talking about the balls to getting them to arrange the balls in a particular order. Still not juggling though. (For those that don’t get the reference. It’s a chapter in Peopleware)
tomerbd 8y ago
Hi, can you point the github source project of this blog? thanks.
fahimulhaq 8y ago
If you are looking for a good resource to prepare for Dynamic Programming for Technical Interviews, look at Grokking the Dynamic Programming Patterns for Coding Interviews (https://www.educative.io/collection/5668639101419520/5633779737559040 https://www.educative.io/collection/5668639101419520/5633779...) Disclaimer: I'm the co-founder of educative.io but NOT the author of this course.
jparkie 8y ago
I agree with other's opinions that asking a Dynamic Programming question is a weak signal for a candidate's competencies in general software development work like frontend, backend, mobile applications, and the like. However, I would like to counter a common opinion that eventually follows in similar threads and some of my social circles: "Algorithms is an undergraduate course in which students learn specialized solutions to esoteric math problems, all of which they ultimately forget when they spend real time working in the industry, so the knowledge shouldn't be relevant in an interview." It is fair that if you don't exercise what you learned, you will gradually forget it, but I believe its still important for a candidate to cherish algorithm design and analysis because I consider it a great toolbox of the trade. For all the concepts and the techniques I learned from my undergraduate course in data structures and algorithms, I utilized them as the basis of my Software Engineering Toolbox. What is my Software Engineering Toolbox? It is a collection of algorithm design concepts and techniques that I can employ anytime I am faced with a novel problem or a problem whose standard Stack Overflow solutions are inadequate. The Software Engineering Toolbox contains the following: Arrays, Linked List, Stack, Queue, Hash Table, Binary Search Tree, Priority Queue, Set, Trie, Sorting, Binary Search, Divide-and-Conquer, Backtracking, Dynamic Programming, Range Query Trees, Graph Algorithms, Bit Mask Optimizations, Square Root Bucket Optimizations, and Multiple Pointer Optimizations. First, I rarely implement my own data structures from scratch; all the programming languages that I use provide great standard libraries. Yet, I always remind myself the use of these data structures, because you would be surprised with the amount of people you can meet who tries to answer a problem that boils down to a set membership with a HashMap<Integer, Boolean> when they can just use a HashSet<Integer> or with the amount of people who manually treat an Array as a Stack or a Queue when those data structures are readily available. Second, I rarely implement my own sort or search functions from scratch; again, all the programming languages that I use provide great optimized functions. I treat Sorting and Binary Search as techniques that lend themselves to optimizing the locality of a data set such that you can easily answer basic statistics, find the bucket for a token in a ring, or merge data sets. These are simple techniques developers should readily know to exist when optimizing their code. Third, why do I have Divide-and-Conquer and Backtracking in my toolbox? I believe that no matter what problem you face, you should be able to bruteforce it. You can't always tell someone that you can't implement something because you didn't find a Stack Overflow answer or you didn't deduce a collage of standard library functions or third-party libraries to solve your problem. Using these techniques, you can at least arrive at a pretty weak solution which is still a solution. To actually address Divide-and-Conquer and Backtracking in relation to bruteforcing, these techniques allow you to easily traverse through a search space to filter for a certain combination or permutation of items that satisfy a customer's constraints. Furthermore, Backtracking is a relatively easy to medium difficulty technique that is the basis for a lot of the Graph Algorithms people keep balking at! Fourth, Dynamic Programming. To be honest, I rarely utilize it, but I appreciate it because the common subproblem types of 1D, 2D, Range, and Sub-Trees taught me how to order subproblems successively to solve other problems, which applies beyond DP. I discourage people from trying to pattern match Dynamic Programming problems and solutions, and I encourage them to truly digest CLRS and understand its 4 rules for Dynamic Programming to consider possible dependencies and structures for various combinations and permutations of the problem parameters to identify what the optimal substructure really is. Finally, the remaining things in my toolbox are included in my toolbox because they are useful in my work experience with real-time network anomaly detection and streaming analytics. For example, topological sorting distributed tracing events into a rooted tree that I encode into a bit vector using a left-child right sibling binary tree. Not everyone will do this, but with my toolbox I never worry much about facing new frontiers of problems or being tasked to create libraries and tools for myself and others to use instead of being at whims of someone else on the Internet. Overall, I hope people can look back at their courses in algorithm design and analysis and say, "Yeah, the problems and the solutions were really weird, but the techniques hidden away within them are actually GENERALIZABLE and are a fundamental basis to build new things and solve complex problems!" Nonetheless, I don't want anyone who is weak in algorithms design and analysis to feel discourage. Play to your own strengths whatever they maybe, or you can always strengthen them; it's never too late. Finally, my Software Engineering Toolbox has way more stuff like actual "engineering" stuff like automatic formatters, linters, fuzzers, automation, tests, mocks, coverage, "Infrastructure as Code", and blah blah blah. :") I would like to close by saying that a good engineer knows the right tools for the job. :)
js4ever 8y ago
DP is clearly more related to maths than programming. If you are looking for a mathematician it make sense... But if you are looking for a good real world developer it's completely wrong!
fukbezos 8y ago
I simply won't work for a company that makes me take a test to interview. My experience speaks for itself
bjs250 8y ago
>"I'll show you how to do DP" Hey it's the same 3 example problems that are in every textbook, GeeksforGeeks, Leetcode, etc.
- Aditya_Ramesh 8y ago
  Thanks for taking the time to read my post. :) Like I mentioned, this article only lays the groundwork. The next article I intend to write on is DP+Strings (for example, finding the longest substring of a string which is a subsequence of another, etc) I'm starting with classical problems and I'll soon diverge into non-classical problems, as I've mentioned in my article too. In any case, hope my other articles on my blog added more value to you in comparison!
  - bjs250 8y ago
    Yeah, I was being snarky up above, but will definitely look forward to the future articles.
zerocool2750 8y ago
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'
- Aditya_Ramesh 8y ago
  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! :)
  - zerocool2750 8y ago
    Totally makes sense I just think it's slightly confusing in that context. Anyway, awesome article I enjoyed the read!
    - Aditya_Ramesh 8y ago
      Thank you! I'll make sure to go over some non-classical problems in my next article on DP to add more value :)
vardhanw 8y ago
In the first problem illustrated, I wanted to also get the list of coins. I made this attempt, but this hardly seems elegant. Any comments to make it better? n=10 denom = [1,3,4] dp = [-1 for i in range(n+1)] dpl = [[] for i in range(n+1)] def f(n): if dp[n]!= -1: return dp[n] ans = 10**10 if n<=0: return 0 mini=n for i in denom: if (n-i)>=0: new = f(n-i)+1 if new <= ans: mini=i ans = new dpl[n].append(mini) if mini!=n: dpl[n] = [item for sublist in [dpl[n], dpl[n-mini]] for item in sublist] dp[n]=ans return ans if __name__ == "__main__": ans = f(n) print(ans, dpl)
- pwaivers 8y ago
  To be more elegant, you can remove the "dp" array. If you want to keep track of the full list, then you only need to keep track of "dpl". Here is code that I wrote and it works: n = 10 denom = [1, 3, 4] dpl = [[] for i in range(n+1)] def f(n): if dpl[n]: return dpl[n] if n <= 0: return [] ans = list(range(n)) # this is the max size possible for i in denom: if n-i >= 0: new = f(n-i) + [i] # append i to the end of the array if len(new) <= len(ans): ans = new dpl[n] = ans return ans if __name__ == "__main__": sol = f(n) print(sol)
albertzeyer 8y ago
Note that the memory requirements in the Coin Change solution is O(N), and that is not optimal. You should be able to get away with O(max(denom) - min(denom)) (you don't need to cache everything).
lowdest 8y ago
I spent 2-3 weeks going through all DP problems on leetcode after work. I got that Tetris-effect where I was starting to hallucinate/dream DP problems and solutions as I would fall asleep at night. I did this specifically for interviewing. As I've said before, these kind of interviews screen for unusual geniuses or people with the motivation to spend many hours studying, which are two types of acceptable hires.
JJMcJ 8y ago
Coin changing - my understanding is that if each denomination of coin is at least twice that of the next smaller, then greedy is optimal. Note to self - see if you can prove it. That is the case for current US coinage, 1, 5, 10, 25, 50, 100, cents.
sramij 8y ago
This is poorly written. I was hoping hacker news would have better scrutiny on articles.
golergka 8y ago
So, in all of these examples, the author basically makes a set of all possible solution into a tree (where moving from ancestor to child is that tree correlates to making a possible decision) and then recursively traverses this tree to find the best option?

470 points by Aditya_Ramesh 8y ago

mlthoughts2018 8y ago

I never much enjoyed dynamic programming and I do think it’s a poor choice for timed interview questions, but I did become more interested in it when I realized there are patterns to the cache strategies that can be used to group problems. For example like the usual matrix raster fill approach for e.g. 0-1 knapsack, or sepatately using two cursors to fill the upper triangle of a matrix like for longest common subsequence and for optimal order of associative computation (like matrix multiplication).

tyingq 8y ago

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 https://news.ycombinator.com/item?id=19395862

sanderjd 8y ago
lol yep and I just made basically the same comment as well.
- zestyping 8y ago
  Hey, nice timing. High five, everyone.
Cyph0n 8y ago
Based on my understanding, the key difference with DP is that you build the solution bottom up instead of top-down. For example, in case of computing the factorial of 10 recursively, you would start at fact(10) and move down to the base case, fact(1). With DP, you would start with fact(1) and compute succesive results based on computed ones, all the way up to fact(10). Following on from this, you usually build up the solution in an array, sequentially, instead of navigating down the tree of solutions and storing as you go (memoization).
- alangpierce 8y ago
  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 term to refer to both.
  - chillee 8y ago
    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).
    - alangpierce 8y ago
      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.
      - chillee 8y ago
        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.
stale2002 8y ago
Honestly? Yeah... It basically is. This is harder than it sounds though. DP problems tend to be solvable in only a couple lines of code, but the tough part is deciding what to recurve on, and what to memoize.
jonahx 8y ago
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%5Bsubdomains%5D%5B%5D=dynamic-programming https://www.hackerrank.com/domains/algorithms?filters%5Bsubd... (I have no affiliation with the site)
- protomyth 8y ago
  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?
  - jonahx 8y ago
    I'd just try a couple of those problems and see how much practice you need.
alangpierce 8y ago
> So "DP" is just recursion with memoization? Sort of. "I know DP" doesn't just mean "I know what memoized recursion is". It means "I know how to take a problem, recognize that DP might help, frame it recursively with highly-overlapping subproblems, and use memoized recursion to implement an efficient algorithm for it". Especially in advanced cases, it take a lot of skill to look at a problem in just the right way that memoized recursion makes it computationally easy. For example, sometimes you might have a problem where the simple DP approach takes n^3 space, but with some trickery you can get it down to n^2.
- tyingq 8y ago
  So, what about something relatively straightforward? Like Fibonacci. Is it "DP" if I recurse+cache?
  - alangpierce 8y ago
    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.
    - tyingq 8y ago
      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"?
      - slavik81 8y ago
        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 https://en.wikipedia.org/wiki/Dynamic_programming#History
reader5000 8y ago
Recursion with memoization can still take exponential time whereas a DP solution is usually going to be quadratic or better.
- chillee 8y ago
  That's not really true. There's plenty of DP solutions that are >cubic or exponential.
mrburton 8y ago
I think many people struggle with understanding "Dynamic Programming." Hopefully the following clears it up for you. Dynamic Programming can be done using Memoization (top-down; aka recursively) or Tabular method (bottom-up). So what's the difference? When you see top-down, it means to start from the root of the problem and recursively descend to the base case. As you pop up the stack, you will either calculate and store the result or look up the value in the cache. e.g., in the Fibonacci sequence, check to see if fib(4) was already calculated. No? Calculated and store it so the next time you come across this, you can use the result and not worry about processing fib(1), fib(2), fib(3), etc. When you see bottom-up, think about filling out a table from the upper left corner column by column then row by row. To speed performance, you'll look at prior values, the value in the column above vs. column to the left vs. or column diagonally to the left. I know this sounds a bit strange, but if you solve the following problems, you'll see a repeating pattern. Edit Distance 0/1 Knapsack Rod Cutting Longest Common Subsequence Longest Path in Matrix Coin Change I've been writing about this in detail. Eventually I'll publish my writing to help others. I solve ~20 problems using Memoization and the Tabular method. As I solve each problem, I compare the solutions with prior problems showing the pattern. What I want to do is help people spot "patterns" vs. memorizing algorithms that are very problem specific.
- zestyping 8y ago
  Thanks for helping clear this up. It seems that many dynamic programming solutions can be arrived at by starting with a recursive formulation, adding memoization, and then optimizing the cache based on specialized knowledge of the problem. For example: 1. Q: How can you compute Fibonacci number f(n) recursively? A: f(n) = f(n-1) + f(n-2) 2. Q: How can you memoize the results of your recursive function(s) to dramatically reduce the number of calls? A: Make a cache keyed on n that stores f(n). 3. Q: Given specialized understanding of the problem, how can you minimize the size of the cache? A: Notice that you don't need to keep all O(n) slots; you only need to keep two ints. Can every dynamic programming solution be explained this way? Or is there a good example of a dynamic programming problem for which you really need to make a leap that can't be sensibly reached through this sequence of three questions?
vowelless 8y ago
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.pdf http://web.mit.edu/15.053/www/AppliedMathematicalProgramming...

zestyping 8y ago

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

sn41 8y ago
It is basically memoized recursion. However, that does not mean that it is easy. To find out the optimal substructure - that is, building the solution to the problem from the optimal solution of its subproblem decomposition - is where the actual difficulty of the technique lies. Exercises from a standard algorithm textbook like Kleinberg and Tardos should give enough practice in solving these problems. Not all of them are straightforward.
gowld 8y ago
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.
ufo 8y ago
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.

sanderjd 8y ago

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?

sgkzr 8y ago
Not really much. The only difference is that DP could have smaller cache size if calculation order is planned. And I agree with you that it's only confusing because of the name.
clickok 8y ago
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 Secretary of Defense, and he actually had a pathological fear and hatred of the word, research. I’m not using the term lightly; I’m using it precisely. His face would suffuse, he would turn red, and he would get violent if people used the term, research, in his presence. You can imagine how he felt, then, about the term, mathematical. The RAND Corporation was employed by the Air Force, and the Air Force had Wilson as its boss, essentially. Hence, I felt I had to do something to shield Wilson and the Air Force from the fact that I was really doing mathematics inside the RAND Corporation. 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.’ I wanted to get across the idea that this was dynamic, this was multistage, this was time-varying—I thought, let’s kill two birds with one stone. Let’s take a word that has an absolutely precise meaning, namely dynamic, in the classical physical sense. It also has a very interesting property as an adjective, and that is 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. So I used it as an umbrella for my activities." ----- 0. From http://arcanesentiment.blogspot.com/2010/04/why-dynamic-programming.html http://arcanesentiment.blogspot.com/2010/04/why-dynamic-prog...

petermcneeley 8y ago

The knapsack problem here is of particular interest since despite the optimization problem being NP-hard the solution can in fact be found in O(n * W). This feels similar to how the theoretical best comparison sort is O( n log n) but radix can do this in O( n).

mesarvagya 8y ago
Knapsack still is a NP-Hard Problem. Even though DP solution looks linear, it has pseudo-polynomial time complexity[1][2] [1]https://en.wikipedia.org/wiki/Knapsack_problem#Computational_complexity https://en.wikipedia.org/wiki/Knapsack_problem#Computational... [2] https://stackoverflow.com/questions/4538581/why-is-the-knapsack-problem-pseudo-polynomial https://stackoverflow.com/questions/4538581/why-is-the-knaps...

alangpierce 8y ago

> 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 have a chance at solving them, so really they just test whether the person has learned DP, rather than other algo problems where you can at least try to claim that it's a proxy for "general problem solving ability". And DP comes up almost never in the real world (and when it does come up, you're often still better off taking a heuristic/inexact approach), so testing if the candidate knows DP is also almost completely useless. If you're an interviewer at a company that asks DP questions, please reconsider. There are almost certainly alternatives that are more fair and higher-signal.

rfrey 8y ago
>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.
- chillee 8y ago
  I really doubt it. The type of reasoning needed for dynamic programming interview problems is barely connected to DP in reinforcement learning.
- throwawaymath 8y ago
  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.
  - gaogao 8y ago
    At the FANG I'm at, DP is now heavily discouraged with a note that it was once a very common interview topic.

adamnemecek 8y ago

I’ve found this blog post to be the best of the bunch http://blog.ezyang.com/2010/11/dp-zoo-tour/ http://blog.ezyang.com/2010/11/dp-zoo-tour/

ctchocula 8y ago
This way of illustrating categories of DP problems seems really intuitive to me. Thanks for sharing.

aboutruby 8y ago

Only company I know of asking for "Dynamic Programming" is LinkedIn, is there any others?

thewarrior 8y ago
Google ?

candeira 8y ago

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-programming-versus-memoization.html https://blog.racket-lang.org/2012/08/dynamic-programming-ver...

chillee 8y ago
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.
- rifung 8y ago
  > 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 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"
  - chillee 8y ago
    Yeah, you're right. The subproblems must overlap.
- candeira 8y ago
  I understand that DP requires turning a recursive, top-down algorithm into an iterative one by yes, reusing the overlap in the subsolutions. And Krishamurthi's definition is the clearer I've seen that doesn't include "memoized recursion" as a subset of Dynamic Programming.

mesarvagya 8y ago

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.

akhilcacharya 8y ago
This is all well and good for fibonacci but it feels like the difficulty of the problem becomes exponentially greater when you start running into more complicated optimization strategies. Text justification is an example: [0] http://courses.csail.mit.edu/6.006/fall09/lecture_notes/lecture20.pdf http://courses.csail.mit.edu/6.006/fall09/lecture_notes/lect...

imslavko 8y ago

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

hvidgaard 8y ago
DP is a mathematically term describing certain problems. It does not state that you need to save all solutions to sub problems. If you do have a DP problem, the fastest way to solve it is with recursion and memoization as needed because of the properties of the problem.
- imslavko 8y ago
  I am not arguing with this. In my comment my intend was to show that the distinction between the memoized top-down approach and bottom-up (the approach that is usually taught as DP in a classroom) is significant in some memory optimizations.
agbell 8y ago
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 stream of values. Here is a python version from wikipedia def nth_factorial(k): n, f = 0, 1 while n < k: n, f = n + 1, f * (n + 1) yield f Is DP a techique to arrive at the corecursive solution?

akhilcacharya 8y ago

The problem with DP problems (for me) is there seem to be a really large set of unique DP problems and coin change, knapsack, and grid DP problems like number of paths are only a small subset of them. What's more is that the rest of the problems can't be easily based on the approaches used for these...there might be dozens of problem classes to understand!

ralusek 8y ago
That might be the only dynamic thing about the otherwise terribly-named set of problems.

ram_rar 8y ago

After spending a lot of time interviewing candidates. I have pretty much come to the conclusion that DP problems dont give good signals about candidates problem solving skills. In my experience, less 5% of candidates can genuinely crack problems using DP. Most of them either give me memorized solution or just plain give up. If you are interviewing for a regular CRUD job aka web application. There are soo many other problems which can give much more refined signal about candidates skill. Please for love of God, dont ask DP. Unless you actually use it at work.

neilwilson 8y ago

Thirty years after it was first highlighted, we still don’t ask a juggler to actually juggle before hiring them. Admittedly we have moved on from simply talking about the balls to getting them to arrange the balls in a particular order. Still not juggling though. (For those that don’t get the reference. It’s a chapter in Peopleware)

tomerbd 8y ago

Hi, can you point the github source project of this blog? thanks.

fahimulhaq 8y ago

If you are looking for a good resource to prepare for Dynamic Programming for Technical Interviews, look at Grokking the Dynamic Programming Patterns for Coding Interviews (https://www.educative.io/collection/5668639101419520/5633779737559040 https://www.educative.io/collection/5668639101419520/5633779...) Disclaimer: I'm the co-founder of educative.io but NOT the author of this course.

jparkie 8y ago

I agree with other's opinions that asking a Dynamic Programming question is a weak signal for a candidate's competencies in general software development work like frontend, backend, mobile applications, and the like. However, I would like to counter a common opinion that eventually follows in similar threads and some of my social circles: "Algorithms is an undergraduate course in which students learn specialized solutions to esoteric math problems, all of which they ultimately forget when they spend real time working in the industry, so the knowledge shouldn't be relevant in an interview." It is fair that if you don't exercise what you learned, you will gradually forget it, but I believe its still important for a candidate to cherish algorithm design and analysis because I consider it a great toolbox of the trade. For all the concepts and the techniques I learned from my undergraduate course in data structures and algorithms, I utilized them as the basis of my Software Engineering Toolbox. What is my Software Engineering Toolbox? It is a collection of algorithm design concepts and techniques that I can employ anytime I am faced with a novel problem or a problem whose standard Stack Overflow solutions are inadequate. The Software Engineering Toolbox contains the following: Arrays, Linked List, Stack, Queue, Hash Table, Binary Search Tree, Priority Queue, Set, Trie, Sorting, Binary Search, Divide-and-Conquer, Backtracking, Dynamic Programming, Range Query Trees, Graph Algorithms, Bit Mask Optimizations, Square Root Bucket Optimizations, and Multiple Pointer Optimizations. First, I rarely implement my own data structures from scratch; all the programming languages that I use provide great standard libraries. Yet, I always remind myself the use of these data structures, because you would be surprised with the amount of people you can meet who tries to answer a problem that boils down to a set membership with a HashMap<Integer, Boolean> when they can just use a HashSet<Integer> or with the amount of people who manually treat an Array as a Stack or a Queue when those data structures are readily available. Second, I rarely implement my own sort or search functions from scratch; again, all the programming languages that I use provide great optimized functions. I treat Sorting and Binary Search as techniques that lend themselves to optimizing the locality of a data set such that you can easily answer basic statistics, find the bucket for a token in a ring, or merge data sets. These are simple techniques developers should readily know to exist when optimizing their code. Third, why do I have Divide-and-Conquer and Backtracking in my toolbox? I believe that no matter what problem you face, you should be able to bruteforce it. You can't always tell someone that you can't implement something because you didn't find a Stack Overflow answer or you didn't deduce a collage of standard library functions or third-party libraries to solve your problem. Using these techniques, you can at least arrive at a pretty weak solution which is still a solution. To actually address Divide-and-Conquer and Backtracking in relation to bruteforcing, these techniques allow you to easily traverse through a search space to filter for a certain combination or permutation of items that satisfy a customer's constraints. Furthermore, Backtracking is a relatively easy to medium difficulty technique that is the basis for a lot of the Graph Algorithms people keep balking at! Fourth, Dynamic Programming. To be honest, I rarely utilize it, but I appreciate it because the common subproblem types of 1D, 2D, Range, and Sub-Trees taught me how to order subproblems successively to solve other problems, which applies beyond DP. I discourage people from trying to pattern match Dynamic Programming problems and solutions, and I encourage them to truly digest CLRS and understand its 4 rules for Dynamic Programming to consider possible dependencies and structures for various combinations and permutations of the problem parameters to identify what the optimal substructure really is. Finally, the remaining things in my toolbox are included in my toolbox because they are useful in my work experience with real-time network anomaly detection and streaming analytics. For example, topological sorting distributed tracing events into a rooted tree that I encode into a bit vector using a left-child right sibling binary tree. Not everyone will do this, but with my toolbox I never worry much about facing new frontiers of problems or being tasked to create libraries and tools for myself and others to use instead of being at whims of someone else on the Internet. Overall, I hope people can look back at their courses in algorithm design and analysis and say, "Yeah, the problems and the solutions were really weird, but the techniques hidden away within them are actually GENERALIZABLE and are a fundamental basis to build new things and solve complex problems!" Nonetheless, I don't want anyone who is weak in algorithms design and analysis to feel discourage. Play to your own strengths whatever they maybe, or you can always strengthen them; it's never too late. Finally, my Software Engineering Toolbox has way more stuff like actual "engineering" stuff like automatic formatters, linters, fuzzers, automation, tests, mocks, coverage, "Infrastructure as Code", and blah blah blah. :") I would like to close by saying that a good engineer knows the right tools for the job. :)

js4ever 8y ago

DP is clearly more related to maths than programming. If you are looking for a mathematician it make sense... But if you are looking for a good real world developer it's completely wrong!

fukbezos 8y ago

I simply won't work for a company that makes me take a test to interview. My experience speaks for itself

bjs250 8y ago

>"I'll show you how to do DP" Hey it's the same 3 example problems that are in every textbook, GeeksforGeeks, Leetcode, etc.

Aditya_Ramesh 8y ago
Thanks for taking the time to read my post. :) Like I mentioned, this article only lays the groundwork. The next article I intend to write on is DP+Strings (for example, finding the longest substring of a string which is a subsequence of another, etc) I'm starting with classical problems and I'll soon diverge into non-classical problems, as I've mentioned in my article too. In any case, hope my other articles on my blog added more value to you in comparison!
- bjs250 8y ago
  Yeah, I was being snarky up above, but will definitely look forward to the future articles.

zerocool2750 8y ago

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'

Aditya_Ramesh 8y ago
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! :)
- zerocool2750 8y ago
  Totally makes sense I just think it's slightly confusing in that context. Anyway, awesome article I enjoyed the read!
  - Aditya_Ramesh 8y ago
    Thank you! I'll make sure to go over some non-classical problems in my next article on DP to add more value :)

vardhanw 8y ago

In the first problem illustrated, I wanted to also get the list of coins. I made this attempt, but this hardly seems elegant. Any comments to make it better? n=10 denom = [1,3,4] dp = [-1 for i in range(n+1)] dpl = [[] for i in range(n+1)] def f(n): if dp[n]!= -1: return dp[n] ans = 10**10 if n<=0: return 0 mini=n for i in denom: if (n-i)>=0: new = f(n-i)+1 if new <= ans: mini=i ans = new dpl[n].append(mini) if mini!=n: dpl[n] = [item for sublist in [dpl[n], dpl[n-mini]] for item in sublist] dp[n]=ans return ans if __name__ == "__main__": ans = f(n) print(ans, dpl)

pwaivers 8y ago
To be more elegant, you can remove the "dp" array. If you want to keep track of the full list, then you only need to keep track of "dpl". Here is code that I wrote and it works: n = 10 denom = [1, 3, 4] dpl = [[] for i in range(n+1)] def f(n): if dpl[n]: return dpl[n] if n <= 0: return [] ans = list(range(n)) # this is the max size possible for i in denom: if n-i >= 0: new = f(n-i) + [i] # append i to the end of the array if len(new) <= len(ans): ans = new dpl[n] = ans return ans if __name__ == "__main__": sol = f(n) print(sol)

albertzeyer 8y ago

Note that the memory requirements in the Coin Change solution is O(N), and that is not optimal. You should be able to get away with O(max(denom) - min(denom)) (you don't need to cache everything).

lowdest 8y ago

I spent 2-3 weeks going through all DP problems on leetcode after work. I got that Tetris-effect where I was starting to hallucinate/dream DP problems and solutions as I would fall asleep at night. I did this specifically for interviewing. As I've said before, these kind of interviews screen for unusual geniuses or people with the motivation to spend many hours studying, which are two types of acceptable hires.

JJMcJ 8y ago

Coin changing - my understanding is that if each denomination of coin is at least twice that of the next smaller, then greedy is optimal. Note to self - see if you can prove it. That is the case for current US coinage, 1, 5, 10, 25, 50, 100, cents.

sramij 8y ago

This is poorly written. I was hoping hacker news would have better scrutiny on articles.

golergka 8y ago

So, in all of these examples, the author basically makes a set of all possible solution into a tree (where moving from ancestor to child is that tree correlates to making a possible decision) and then recursively traverses this tree to find the best option?