Live data from Hacker News

Solving dynamic programming interview problems

blog.refdash.com

21–30 of 176 posts

Re: Solving dynamic programming interview problems

#21
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.

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.

Re: Solving dynamic programming interview problems

#22
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.

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.

They aren't picky because they can be. If that were true they wouldn't be complaining about the lack of qualified developers (pretty much every tech company I know of).

Rather, they're picky because they (think they) need to be.

Note that I'm not judging whether they are right or not.

Re: Solving dynamic programming interview problems

#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 memory usage to pass but the equivalent C or C++ solution didn't require any tweaks)

[1] https://codejam.withgoogle.com/2018/challenges/0000000000007...

Re: Solving dynamic programming interview problems

#24
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.

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.

Re: Solving dynamic programming interview problems

#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, New York, 1977.\ \

Dimitri P.\ Bertsekas, {\it Dynamic Programming: Deterministic and Stochastic Models,\/} ISBN 0-13-221581-0, Prentice-Hall, Englewood Cliffs, NJ, 1987.\ \

George L.\ Nemhauser, {\it Dynamic Programming,\/} ISBN 0-471-63150-7, John Wiley and Sons, New York, 1966.\ \

E.\ B.\ Dynkin and A.\ A.\ Yushkevich, {\it Controlled Markov Processes,\/} ISBN 0-387-90387-9, Springer-Verlag, Berlin, 1979.\ \

Dimitri P.\ Bertsekas and Steven E.\ Shreve, {\it Stochastic Optimal Control: The Discrete Time Case,\/} ISBN 0-12-093260-1, Academic Press, New York, 1978.\ \

Wendell H.\ Fleming and Raymond W.\ Rishel, {\it Deterministic and Stochastic Optimal Control,\/} ISBN 0-387-90155-8, Springer-Verlag, Berlin, 1979.\ \

some of my work, etc.

Dynamic programming has been and is a major interest of the Department of Operations Research and Financial Engineering (ORFE) at Princeton.

Uh, "any" seems a bit optimistic!

Re: Solving dynamic programming interview problems

#26
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.

That's awesome! I generally think that DP problems introduce more noise because they're relatively easy to prepare for. So you might easily miss a good engineer who is not prepared. I try to argue about that in the beginning of the blog.

However, they're a reality for many interview loops, so it's better to be prepared.

Btw, what are some things that your company tests for, if you don't mind sharing?

Re: Solving dynamic programming interview problems

#27

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 coming from were somehow personally my fault to he had fun letting me twist in the wind.

Personally, I think that given how small the industry is, one of the goals of the interview process should be not to make an enemy of the candidate. Candidates have friends, and sometimes candidates come back in a few years after they've gotten more experience or you're looking for different skills. None of this will matter to Google until they find themselves in a MS-style hiring crisis in another five years when they aren't cool anymore.

Re: Solving dynamic programming interview problems

#28
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.

Re: Solving dynamic programming interview problems

#29
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.

That's awesome! I generally think that DP problems introduce more noise because they're relatively easy to prepare for. So you might easily miss a good engineer who is not prepared. I try to argue about that in the beginning of the blog. However, they're a reality for many interview loops, so it's better to be prepared. Btw, what are some things that your company tests for, if you don't mind sharing?

[deleted]

Re: Solving dynamic programming interview problems

#30
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,…

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.

Post reply on HN