Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Solving dynamic programming interview problems

blog.refdash.com

Post reply on HN
Print view View original

61–70 of 176 posts

Re: Solving dynamic programming interview problems

#61

Post by bitL »

dahart wrote: post #38
btilly wrote: post #34

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

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

Sometimes 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.

Re: Solving dynamic programming interview problems

#62

Post by blackflame7000 »

jacquesm wrote: post #60
blackflame7000 wrote: post #37

Earlier quoted context omitted.

Is 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).

Recursion 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.

I 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.

Re: Solving dynamic programming interview problems

#64

Post by danmg »

blackflame7000 wrote: post #55
danmg wrote: post #44

Earlier quoted context omitted.

Divide 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.

Sure 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.

We'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.

Re: Solving dynamic programming interview problems

#65

Post by coastal-fiesta »

nilkn wrote: post #24
yanslookup wrote: post #21

Earlier quoted context omitted.

Does the company you are at now pay developers the same as the companies that ask these types of questions? In my experience the companies asking these types of questions are picky because they can be.

We pay very well for the area. We are not in Silicon Valley, but I know some of our salaries are higher than those of my friends who are at Google's MV campus.

It's not terribly impressive to have a higher salary then a GOOG employee, but higher total compensation after stock and bonuses would be saying something.

Re: Solving dynamic programming interview problems

#66

Post by dahart »

zawerf wrote: post #23

In python you often need sys.setrecursionlimit for the recursive solutions since the default is really small. I found out the hard way in a recent Google CodeJam problem[1] that even that wasn't enough and sometimes you really do need the iterative solution to not time out. (I still believe that the limits for python for this problem was set too low since even the iterative solution required hand optimizing of the me…

Yes that, or code the recursive solution in a heap-allocated space rather than on the stack. It somehow seems easier, safer, and more explicit and controllable to me to adjust the code & data to use manual recursion with backtracking than try to adjust system stack limits. Often it consumes a lot less memory too, since you have more control over what your "stack frame" looks like; you don't have to store all your local variables for every step.

Re: Solving dynamic programming interview problems

#67

Post by danbruc »

danbruc wrote: post #18
hyperation wrote: post #11

Is it just me or the Big O algebra at the end doesn't seem right?

What do you think is wrong, I did not notice any really obvious mistake? Admittedly you would miss the improved bound unless you actually modified the implementation to abort further evaluation once you reach the maximum speed that still allows stopping, but I assume that is implied. I also guess one could even further improve the exponent to 1.25 by taking advantage of the fact that the maximum speed that still allo…

Being able to improve the exponent to 1.25 is probably wrong. After thinking about it more carefully I think you end up with a number of steps proportional to the generalized harmonic number of order -0.5 of L which seems to be Θ(n^1.5) but I am not really sure about that.

Re: Solving dynamic programming interview problems

#68

Post by Silfen »

blackflame7000 wrote: post #37
btilly wrote: post #34

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

Is 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).

It 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).

Re: Solving dynamic programming interview problems

#69

Post by ASinclair »

badlucklottery wrote: post #48
lalwanivikas wrote: post #35

Earlier quoted context omitted.

> You should not be blamed for assuming, when talking to Google, that the O(n!) or O(n^2) solution is not even worth talking about. So I flopped around on O(n), O(nm) and O(nlogn) solutions after trying to whiteboard a recurrence relationship and giving up on O(1). Did they say that they don't even want to listen to O(n^2) solution?

I'd be super surprised if they did. Google interviewers usually encourage you to spit out an easily-verifiable O(n^2) (or even worse!) solution as fast as possible. That way, if you get stuck and honestly can't finesse a faster solution, you can code that up and provide a code sample. People still try to fake their way through the process so being able to code up something close to a compilable function is a useful m…

Yep. This is how I conduct my interviews. I don't ask trick questions. Many of my candidates can quickly notice the simple solution but fail to write the solution in code.
Post reply on HN