41–50 of 176 posts
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).
Why are you assuming that the recursive solution is less clear?
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).
Earlier quoted context omitted.
Why are you assuming that the recursive solution is less clear?
Experience, tells me so. To be fair some items like Fibonacci numbers are probably equally as clear.
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 didn't get further along in that process because of that stupidity and have never even considered them as a place to work since, and I am an SRE/PE these days.
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).
For clarity, perhaps one can include a "proof of correctness" of the algorithm in the comments.
Earlier quoted context omitted.
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?
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.
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,…
If I had to guess, I'd wager that the Venn diagram of Dynamic Programming questions and interview questions is a narrow sliver. That is, unless you're being hazed, the sort of questions to show up in an interview might be at the shallow end of the pool.