Solving dynamic programming interview problems • Hacker News Board

Re: Solving dynamic programming interview problems

#31

Post by doublecorrect » Fri, May 18, 2018, 7:32 PM UTC

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.

A L4 (not "senior") Google engineer can easily make 300k+ total compensation in Pittsburgh or Boulder. I don't think your pay is going to be competitive, because you're neglecting the largest component (equity grants).

Re: Solving dynamic programming interview problems

#32

Post by sannee » Fri, May 18, 2018, 7:33 PM UTC

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…

Another cool Python DP hack is using @functools.lru_cache to perform the memoization (beware of the maxsize parameter though).

Re: Solving dynamic programming interview problems

#33

Post by [deleted] » Fri, May 18, 2018, 7:37 PM UTC

nilkn wrote: post #17

Potentially interesting data point: the company I'm at right now has been pretty successful for over a decade and has, to my knowledge, never once asked a dynamic programming question in an interview for any candidate in that entire time. We've managed to hire a lot of great developers and have very rarely had any real issues.

[deleted]

Re: Solving dynamic programming interview problems

#34

Post by btilly » Fri, May 18, 2018, 7:40 PM UTC

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.

Re: Solving dynamic programming interview problems

#35

Post by lalwanivikas » Fri, May 18, 2018, 7:44 PM UTC

hinkley wrote: post #27

2bitencryption wrote: post #8

I recently had a programming interview where, at the whiteboard question, I said "this may be a dynamic programming question, let me see--" and the interviewer said "STOP! Stop, every time someone says that, they end up flopping and never getting anywhere. Don't go down that path, I'm telling you." I think it had more to do with the interviewer being a poor interviewer, however.

I got screwed like that on my Google interview. 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). Interviewer had already decided that somehow the crazy rules I related to him about the industry I was comin…

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

Re: Solving dynamic programming interview problems

#36

Post by graycat » Fri, May 18, 2018, 7:44 PM UTC

otasevic wrote: post #28

graycat wrote: post #25

So, the OP has: > Dynamic Programming – 7 Steps to Solve any DP Interview Problem Here I see "any"!!! Dynamic programming is a huge field from work of R. Bellman, G. Nemhauser, R. Rockafellar, R. Wetts, D. Bertsekas, E. Dynkin, W. Fleming, S. Shreve, and more. E.g., there is, with TeX markup, Stuart E.\ Dreyfus and Averill M.\ Law, {\it The Art and Theory of Dynamic Programming,\/} ISBN 0-12-221860-4, Academic Press,…

Good point. Thanks for the comment. It's likely a bit on the optimistic side, but this focuses on DP problems typically encountered in interviews.

Depends on who is doing the interview!!!

Now, if I were doing an interview asking about dynamic programming, how about scenario aggregation, multi-variate spline approximations, neural net approximations, certainty equivalence with the Gaussian, non-inferior sets, measurable selection, etc.!!!!

One prof of mine wanted me to think about the role of potentials!

Re: Solving dynamic programming interview problems

#37

Post by blackflame7000 » Fri, May 18, 2018, 7:47 PM UTC

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

Re: Solving dynamic programming interview problems

#38

Post by dahart » Fri, May 18, 2018, 7:47 PM UTC

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. At the end of the whole project, I wished I had simply memoized.

Re: Solving dynamic programming interview problems

#39

Post by darzu » Fri, May 18, 2018, 7:52 PM UTC

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

Why are you assuming that the recursive solution is less clear?

Re: Solving dynamic programming interview problems

#40

Post by blackflame7000 » Fri, May 18, 2018, 7:53 PM UTC

hinkley wrote: post #27

2bitencryption wrote: post #8

I recently had a programming interview where, at the whiteboard question, I said "this may be a dynamic programming question, let me see--" and the interviewer said "STOP! Stop, every time someone says that, they end up flopping and never getting anywhere. Don't go down that path, I'm telling you." I think it had more to do with the interviewer being a poor interviewer, however.

I got screwed like that on my Google interview. 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). Interviewer had already decided that somehow the crazy rules I related to him about the industry I was comin…

I think most people will agree that Google doesn't have the best hiring strategy for minimizing false negatives during Interviews. Fortunately for them, they have the luxury of only needing to protect against false positives. Not getting hired at Google was the best thing that ever happened to my career. I ended up earning far more at a successful startup where I used the rejection as motivation.