7 ms·
Speaking as someone who finds DP problems easy, I'd not figure it out from this approach. The way that I'd think about and tackle it in an interview is this:
by btilly 9y ago
Speaking as someone who finds DP problems easy, I'd not figure it out from this approach. The way that I'd think about and tackle it in an interview is this:
1. Write a recursive solution.
2. Memoize.
If you can solve it this way, then you have a DP problem. Of course this forces you into the top down (aka recursive) approach. But in an interview, "easier to reason about" is all that matters.
Also the tradeoffs in section 5 has a mistake. Memory can and frequently does go either way. Top down can let you recognize which states you never need to think through. But a bottom up (aka iterative) approach can let you discard memory after finishing an iteration. The memory savings from that can be considerable.
- blackflame7000 9y agoIs recursion really worth the loss of clarity? Almost always no. The more clever you are in your code, the less likely anyone will ever see it (or want to).
- darzu 9y agoWhy are you assuming that the recursive solution is less clear?
- blackflame7000 9y agoExperience, tells me so. To be fair some items like Fibonacci numbers are probably equally as clear.
- deleted 9y ago[deleted]
- danmg 9y agoDivide an conquer type algorithms usually lend themselves to naive recursive solutions more often than not. DP usually requires you to find that solution and find some clever relationships that allow you to build up the final solution from the bottom up.
- blackflame7000 9y agoSure there are some problems that lend themselves nicely I already said as much. But in general for an INTERVIEW problem, it as a poor skill to dwell on or even bother testing for since real-world coding is simply not done that way or God forbid what might happen when someone not as capable (but cheaper or younger) has to take over your code base.
- danmg 9y agoWe're talking about ACM style search problems that are used for interviews, and not about iterating over an array recursively. For these, the recursive formulation is the naive and inefficient way of solving them.
- kolpa 9y agoIf you systematically analyze it, you don't need to be clever on a per-problem basis. Every recursive solution can me methodically converted to DP.
- danmg 9y agoYes, it's a form of pattern recognition. You can get very good at it and do it mechanically, just like solving integrals. You can spend a lot of time getting very good at them, or you can just use memorization/rsolve just like you can just use maple or evaluate them numerically for integrals.
- deleted 9y ago[deleted]
- deleted 9y ago[deleted]
- algo646464 9y agoAll dynamic programming algorithms are recursive. They are essentially a (constructive) proof by induction. For clarity, perhaps one can include a "proof of correctness" of the algorithm in the comments.
- jacquesm 9y agoRecursion is usually clearer that iterative because it assigns names to the work being done. I find that much easier to read. Better yet: when you can state your cases separately. That's even more readable.
- blackflame7000 9y agoI don't think you represent the average coder. I'm willing to bet most people if shown 10 recursive and 10 iterative solutions to the same problems would admit the iterative approach is more intuitive. Especially since with a for loop you can control the number of iterations which has a number of optimization benefits. Now if its just while loops vs recursive then there's not much of a difference, however that is not the case.
- deleted 9y ago[deleted]
- deleted 9y ago[deleted]
- FractalLP 9y agoAgreed. HackerNews has a greater than average amount of developers that use Haskell, F#, OCaml, Scheme, and other languages which heavily promote recursion. I'm not sure if I personally find iteration easier because I learned it first, it matches my brain better, or if it is indeed easier for most of the population.
- joefkelley 9y agoYou might be able to trace the execution of the iterative code more easily, but in my experience it is often much less clear why that produces the correct result and how that code was written in the first place. Take a look at the wikipedia page for computing Levenshtein distance: https://en.wikipedia.org/wiki/Levenshtein_distance#Computing_Levenshtein_distance https://en.wikipedia.org/wiki/Levenshtein_distance#Computing... The recursive version needs barely any explanation. But ask me to carry it out by hand and I'm sure I'll pretty quickly get lost. The iterative version needs a lot more explanation for why it is the way it is, but I also think I could carry it out on paper quite easily.
- Silfen 9y agoIt depends on the particulars of a problem, but structural recursion is often substantially clearer. One reason is that it enables more abstract reasoning about the behavior of an algorithm. You can reason like you would for an induction proof, instead of mentally executing steps in a loop (denotational vs. operational).
- oldandtired 9y agoThere are problems that have clearer solutions when expressed as recursive. There are problems that have clearer solutions when expressed as iterative. Having both tools in your toolbox and knowing when to use each is part and parcel of developing yourself as a craftsman or craftswomen programmer. In addition, being able to know when to use memoing in producing your solution is another tool to be put in your toolbox. Yes, every recursive function has an iterative solution, but the iterative solution can be far more complex. The best example of this is that lovely little function - Ackermann-Peter function. The recursive version is just a few lines long. The iterative version is quite a few pages long. There are specific schemas in which the recursive form should be rewritten as an iterative solution. You can find these detailed in such old gems of books like "Algorithms + Data Structures = Programs".
- dahart 9y agoAh, you beat me to it. I came to make the same suggestion. DP is fancy caching, but you have to think about the space of the solution to do it right. It's not just easier to cache the results and use the recursive solution, but the code is often smaller and clearer too. I spent some time understanding and coding up edit distance between trees DP-style, which is a fair bit trickier than edit distance between strings. At the end of the whole project, I wished I had simply memoized.
- bitL 9y agoSometimes DP problems are pretty complex in a convoluted way employing some weird tricks before you could see it the DP way; it's best to take some advanced DP problems from TopCoder or ICPC and dissect them in detail. Trivial DP problems are phased out of interviews already, unless looking for junior positions.
- BurningFrog 9y agoWhen I interviewed at $BigCompany, I really enjoyed the whiteboard programming problems I got. But I noticed that 2/3 of them ended up with recursive solutions. Meanwhile, I spend less than 1% of my real professional programming time writing recursive code, and it's a bit silly that so much focus is on such relatively obscure technique.
- x1798DE 9y agoI think it's a mistake to think of whiteboard problems as attempting to recreate a real work environment. They are a proxy for the kind of quality you are looking for that can be "measured" within the alotted time. They can show that the person is prepared (they studied), generally knowledgable (they remember obscure stuff), or just clever (they come up with interesting approaches to the problem). I'm not surprised you see both excessively simple (make sure they aren't ridiculously unqualified) and excessively obscure problems, since the first one essentially tests your reflexes and the second one tries to determine if you learned your job "by rote"
- irq11 9y agoThey’re used because “that’s what company X uses”. People are cargo culting each other, and making up post hoc rationalizations for their behavior. Unless you work for a major tech company where optimizing the false positive rate is your primary concern, using these problems is counterproductive.
- BurningFrog 8y agoYeah, it's philosophically valid that you'd want to measure certain critical things that are different from the everyday grind. But I think the simpler explanation is that these interviewers mostly had picked "cool" recursion problems. I did get the job, and seeing $BigCompany's hiring process from the inside didn't contradict this.
- samfisher83 9y agoYou can solve most recursive problems with a loop and a stack. That way you aren't making a bunch of function calls eating up memory.