13 ms·
Solving dynamic programming interview problems
- morazow 8y agoI did watch live where Nikola solves this problem, https://www.youtube.com/watch?v=kKhnYLpME3w https://www.youtube.com/watch?v=kKhnYLpME3w. It covered most of requirements of dynamic programming. For me the interesting part was coming up with algorithmic complexity (Big-O) of the solution.
- lainga 8y ago6 points and already hugged to death...? <h1>Error establishing a database connection</h1>
- jjaredsimpson 8y agohttp://webcache.googleusercontent.com/search?q=cache:bP5uFme-168J:blog.refdash.com/dynamic-programming-tutorial-example/+&cd=1&hl=en&ct=clnk&gl=us http://webcache.googleusercontent.com/search?q=cache:bP5uFme...
- otasevic 8y agoThanks for sharing the link while it was down. Appreciate it.
- pansinghkoder 8y agowith all due respect to author, here's why solving real problems > interview problems
- otasevic 8y agoI agree. This blog is hosted separately from our servers so I went for a quick deployment of WP on google cloud. Learning: do not use google cloud VM micro instance, apparently it cannot support even moderate traffic.
- pansinghkoder 8y agoDouble thumbs up for fixing this!
- otasevic 8y agoHey everyone, sorry for this. It should be back up: http://blog.refdash.com/dynamic-programming-tutorial-example/ http://blog.refdash.com/dynamic-programming-tutorial-example...
- gridspy 8y agoSeems like the site needs to memoize the page rendering operation ;)
- 2bitencryption 8y agoI 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.
- lalwanivikas 8y agoWoah! What was the problem? Maybe then we can say if he was right or not.
- fizixer 8y agoFor me it was a bit the other way around. I solved the problem in a brute force way and on interviewer's asking, was flopping to come up with a better algorithm. Then he mentioned that I should consider DP. Unfortunately my DP was really bad so I knew right then I'm going to flop. And flop I did. For me the two weakest points are DP, and coming up with the right O() estimate for an algorithm that I just created on the whiteboard, and am looking at it for the first time in my life. Would love advice on how to get good at both.
- moufestaphio 8y agoFor DP? Practice a couple on like HackerRank, CodeFights etc. It starts to make sense after you do a few. For Big O notation? Just think about how many times you're iterating through things (in the worst possible case). e.g. Got two nested for loops each going to N.. we're going to loop N on the outer loop, so and each iteration of the inner loop we go through N times? that's N x N so O(N^2).. (easy example obviously).
- hinkley 8y agoI 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.
- lalwanivikas 8y agoI really wanted to try out your service couple of weeks ago, but turns out you are only in US. Any plans of opening it for Europe?
- otasevic 8y agoYes, currently it is only available for people searching for jobs in the US. I would say the answer is yes long-term, but probably not over the next few months.
- hyperation 8y agoIs it just me or the Big O algebra at the end doesn't seem right?
- danbruc 8y agoWhat 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 allows stopping decreases from left to right but I did not actually think it through, it is just my intuition that you would gain another square root.
- danbruc 8y agoBeing 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.
- otasevic 8y agothanks for this comment. I realized that I skipped a few steps in the explanation, so I am updating it now. But essentially you see that the equation is S^2 - S - 2L < 0 from that, you can solve that the roots of the function are: (1) 1/2 + sqrt(2L) and (2) 1/2 - sqrt(2L) That means that (S-1/2-sqrt(2L)) * (S-1/2+sqrt(2L)) < 0 The second term is always positive, which means that we need to make the first term negative in order for the inequality to hold. => S < 1/2 + sqrt(2L) which leads to O(sqrt(L)) when you let L approach infinity. Does this make sense?
- kizer 8y agoStep 1. ur problem graph better be a dag Step 2. ur sub problems better overlap Step 3. time to table dat dag Step 4. solve ur problems and build ur table graph the way a dag would : to-po-lo-gi-cal-ly
- sumitgt 8y agoNice way to put it!
- akhilcacharya 8y agoI think the DAG approach is a good one, but the problem is its not great for being applied generally. For me, it's difficult to think of something like the "House Robber" problem as a DAG.
- myWindoonn 8y ago(4) is what sets your approach apart from the OP. Solve the problem by searching through the graph, using standard graph search. The OP's "iterative" approaches are close, but they waste massive amounts of time by precomputing the entire table when they could search instead. Iteration with a stack is DFS; iteration with a FIFO queue is BFS; iteration with a priority queue is Dijkstra's if priorities are precise, or A* if priorities are admissible.
- nilkn 8y agoPotentially 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.
- yanslookup 8y agoDoes 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.
- sbov 8y agoThey 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.
- mikert5671 8y agofalse. I know hoards of engineers working on boring code at google
- sidlls 8y agoThat doesn't make it false.
- nilkn 8y agoWe 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.
- doublecorrect 8y ago
- mlevental 8y agowhy are there so many companies trying to "solve hiring". i get it's a big expense to make a bad hire but how are there like 10 different companies thinking they have an edge on 1. existing practices 2. each other
- otasevic 8y agoIt's not only a big expense. It is a stressful, biased and highly ineffective process. There is very little (if any) correlation between performance in interviews today and work performance. It's a hard problem that requires people to approach it seriously. And it is only getting worse with a high growth in number of people getting into tech. It's interesting to try to solve it.
- zawerf 8y agoIn 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/0000000000007765/dashboard/000000000003e0a8 https://codejam.withgoogle.com/2018/challenges/0000000000007...
- sannee 8y agoAnother cool Python DP hack is using @functools.lru_cache to perform the memoization (beware of the maxsize parameter though).
- dahart 8y agoYes 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.
- akshat_h 8y agoAny examples of code for this approach? From what I guess, you are implementing some kind of assembly like approach with explicit saving of stack frame, but I am having a hard time imagining it as being easier.
- Adverblessly 8y agoNot OP, but they probably mean something like the following toy problem (in C++): struct BinTree { long value; BinTree *left; BinTree *right; }; long long RecursiveDFSSum(BinTree *node) { if (NULL == node) { return 0; } return (long long)value + RecursiveDFSSum(node->left) + RecursiveDFSSum(node->right); } long long IterativeDFSSum(BinTree *tree) { std::vector<BinTree *> custom_stack; custom_stack.push_back(tree); long long value = 0; while (!custom_stack.empty()) { BinTree *node = *custom_stack.rbegin(); custom_stack.pop_back(); if (NULL != node) { value += node->value; custom_stack.push_back(node->left); custom_stack.push_back(node->right); } } return value; } Did not check this actually compiles etc. but you get the point. Both ways will give you the same solution in the same way, time complexity, space complexity etc. but the second one is not bound by max call stack size (only by max heap size). Additionally, the second one is slightly more space efficient, since the recursive solution requires saving an entire call frame into the stack (e.g. stack pointer, return address) whereas the iterative solution just stores one pointer per stack item.
- graycat 8y agoSo, 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!
- otasevic 8y agoGood point. Thanks for the comment. It's likely a bit on the optimistic side, but this focuses on DP problems typically encountered in interviews.
- graycat 8y agoDepends 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!
- hinkley 8y agoIf 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.
- btilly 8y agoSpeaking 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 8y 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 8y agoWhy are you assuming that the recursive solution is less clear?
- blackflame7000 8y agoExperience, tells me so. To be fair some items like Fibonacci numbers are probably equally as clear.
- deleted 8y ago[deleted]
- danmg 8y 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.
- Karishma1234 8y agoI have always found the word DP to be a bit confusing. DP problems are essentially recursion + caching. I do not even like the word "memoise".
- coastal-fiesta 8y agoIndeed, it sounds like someone is just saying "memorize" incorrectly.
- kolpa 8y agoThat's what happens when you "recurse".
- czinck 8y ago"Dynamic programming" was intentionally a super-vague but cool sounding term, it wasn't meant to be descriptive (unfortunately). https://en.wikipedia.org/wiki/Dynamic_programming#History https://en.wikipedia.org/wiki/Dynamic_programming#History
- scarface74 8y agoAnd most of the interviewers asking these questions just want someone who can help develop yet another software as a service CRUD app....
- mikec3010 8y agoExactly. I've been a C, C++, and java developer for the past 12 years and never used Big-O for anything other than a shibboleth to get past the door. A couple places practically used C++ itself as a gatekeeper: they want people who are smart enough to program in C++ and survive it's rigorous interview process, but their main product is filling out forms and routing documents through a document management system.
- scarface74 8y agoI did have to do one algorithm type interview in 1999, but the company was actually writing cross platform (Windows console, Unix, and MVS) C code where we had to implement everything from scratch, so it made sense. But unless you're Google, Facebook, Netflix, etc. where you have to solve problems at a scale that no one has had to solve before, most of the algorithm style questions are meaningless in your day to day work.
- xab9 8y agoYep. We need superman, but we are a bicycle repair shop. Only superman will do, that is the only thing we know for sure.
- toomanybeersies 8y agoIn another world, everyone is superman and we are looking for a bicycle repair man: https://www.youtube.com/watch?v=54CpPlCnM4I https://www.youtube.com/watch?v=54CpPlCnM4I
- xab9 8y agoHoped someone would get the monty python reference :D
- psychometry 8y agoI was excited for the article based on the title, but the example problem makes absolutely no sense to me.
- rsp1984 8y agoI've done a fair amount of interviews in my professional career, both as an engineer at Google as well as for my own startup. In an eng. interview you want to maximize information divided by time, i.e. you want to learn as much as possible about whether the candidate would be a good fit for the company and spend as little time as possible doing so (because you have other things to do -- such as interviewing more candidates). In my experience these kind of interview questions have a very poor information by time ratio. They are poor on information because they may give you an idea how well the candidate can do on puzzle questions but not so much how the candidate would do on actual real-world assignments. And they are especially poor on the denominator (time) because you are probably going to spend at least 1h with the candidate before you get past the obvious stuff. Also I guess about 70% of (pre-qualified) candidates would outright fail the question, so if you let this influence your hiring decision, given that the question is really quite "puzzly", you're inevitably going to miss out on a lot of talent (the kind that does well on actual work assignments).
- paxy 8y ago> Also I guess about 70% of (pre-qualified) candidates would outright fail the question This is probably right. Companies still use these questions, though, because they do a good job failing candidates who are not technical enough for the role. What you're essentially doing is filtering out bad candidates and selecting from good ones based on luck.
- hikarudo 8y agoIn other words, the companies are optmizing for precision, rather than recall, which makes sense.
- ghettoimp 8y agoI've done a lot of interviewing and participated in a lot of hiring decisions at a very large tech company. I think our process is guided far more by tradition than deliberate optimization for anything in particular. :)
- 8y ago
- dub 8y agoI have a fantasy. In the fantasy, an interview candidate says "this problem has an optimal substructure" or "this problem can be broken into overlapping subproblems" and then observes "reusing the results of overlapping subproblems to avoid re-computing them is sometimes called dynamic programming" At this point, balloons and confetti fall from the ceiling as Donald Knuth jumps out from under the table to hand the candidate an award for being the first known example of a candidate using "dynamic programming" correctly in a sentence.
- user5994461 8y agoOr just call it caching the intermediate solutions.
- mirceal 8y agoYou know you’ve made it when you have Knuth on standby under the table
- rajeshpant 8y agodoes knuth also come and kick the guy out, if he fails to solve it?
- chillee 8y agoI think the problem is easier viewed as just a standard graph traversal (although you can view graph traversals as DP...) https://ideone.com/rU5COm https://ideone.com/rU5COm
- bajsejohannes 8y agoA tiny correction in the following: if (position + adjustedSpeed in memo and adjustedSpeed in memo[position + adjustedSpeed] and adjustedSpeed in memo[position + adjustedSpeed]): The middle line is not needed.
- otasevic 8y agoThanks! Corrected it now to remove the duplicate line.
- curiousDog 8y agoUnpopular opinion, but the best way to prepare for DP problems is to solve the well known ones and memorize them and their recurrences. Only 2-3 companies like FB and Goog ask them (well they’re the only ones worth studying DP for anyway). Coming up with a recurrence on the spot is very hard. The edit-distance paper was an award winning ACM paper and expecting someone who has never seen that before to code it up (even the memorized one) is ridiculous.
- steelframe 8y agoThe best way to perform well in an interview is to have seen and worked on the problem at some point beforehand. When I got a job at Google (in a previous life), two of the questions in my interview loop were ones that I had seen in previous interviews. I kept my mouth shut about that and faked brilliance in the moment. That is, I pretended to be stumped for a second, then I created a narrative where I had a sequence of 2 or 3 "Ah-ha!" moments where I figured out how to refine my solution. I cued off the interviewer, waiting until they seemed just about to blurt out a hint, when I raised my hand and said, "WAIT! Maaaybe.... I can use a BFS instead of a DFS here and label the cells!" Then the interviewer would usually smile and nod in satisfaction. Finally, I "stumbled on" the "right answer" and slammed out the code that I had pretty much memorized up to that point. Make a stupid game, I'll play the stupid game, and have fun doing it. For the record, I kicked ass at Google (getting promoted twice) before moving on to greener pastures.
- bootsz 8y agoYep, 100% this. I recently finished a series of interviews after extensive preparation and had at least 3 sessions that went something like this. Practice enough problems and eventually you start seeing them crop up in real interviews. Doesn't say much for the usefulness of such an interviewing paradigm but that's a whole other conversation.
- braindongle 8y agoIt's a bad sign when a self-proclaimed authority lifts the definition of the topic from Wikipedia. Unless said authority wrote the Wikipedia entry, in which case I humbly apologize.
- netvarun 8y agoBeing able to solve dynamic programming problems may or may not get you a job but it certainly will get you a medal at high school programming/informatics Olympiads.
- grogers 8y agoGreat post about how to attack solving a problem using DP. But this is not a good interview question. It's a toy problem, not something you'll ever need to solve in real life. Maybe if you squint hard enough it's close to pathfinding algorithms, but be serious. I hate questions that aren't remotely relatable to something the candidate might experience. I get that interviews are short so you need tiny problems, but making them somewhat relevant will make comprehending the problem that much easier and give plenty of time for working on a solution. There's also not much depth to it. Either they can get a naive solution, get the DP solution, or just can't solve it. Maybe I'm just not creative enough but the only follow up I can think of is the typical 'how to test' and this isn't even a good question for that. For me as an interviewer, it is better to start with an easy problem, and then later on additional complexity. For example dealing with concurrency, how to generalize the solution for other cases, etc. These follow ups don't even usually need full code written out so you can get much deeper since it's faster. Whereas if you start from a hard/tricky problem and have to keep explaining it and hinting at how to solve it, both candidate and interviewer feel bad and you haven't learned much. Not that this is a particularly hard problem, it will fit within an interview slot if they are on top of things. But it's similar enough to questions I hate asking/getting (e.g. min of maxes of sliding windows) that I would definitely never ask it.
- triska 8y agoI often use the declarative programming language Prolog to solve dynamic programming tasks, because it is easy to type and helps you to declaratively express what a solution looks like. After you have expressed what must be the case in a solution, you can easily enable memoization on top of the existing code. For example, here is how you can use Prolog to solve the task from the article. The following Prolog predicate is true iff a given runway (represented as a list of "t" and "f" elements) is safe with a given speed: :- use_module(library(clpfd)). safe_runway(0, [t|_]). safe_runway(Speed0, Rs) :- Speed0 #> 0, Rs = [t|_], ( Speed = Speed0 ; Speed #= Speed0 - 1 ; Speed #= Speed0 + 1 ), length(Prefix, Speed), append(Prefix, Rest, Rs), safe_runway(Speed, Rest). Sample query and answer: ?- safe_runway(4, [t,f,t,t,t,f,t,t,f,t,t]). true . One interesting aspect of this solution is that we can generalize this query, and also use the same program to answer the question: Which speeds are actually safe for a given runway? For example: ?- safe_runway(Speed, [t,f,t,t,t,f,t,t,f,t,t]). Speed = 0 ; Speed = 2 ; etc. To enable memoization for this task, you only have to use your Prolog system's tabling mechanism. For example, in SWI-Prolog, you turn this into a dynamic programming solution by adding the directive :- table safe_runway/2. This makes the Prolog engine automatically remember and recall solutions it has already computed.
- mychael 8y agoAbove all else, Dynamic Programming is useful for making yourself feel like a superior programmer and writing blog posts about it. In 10+ years of working in this industry, I can't recall using it once outside of interviews.
- celim307 8y agoI just give them a real world issue/bug/feature and ask them how they would complete it. Obviously im looking for as best an answer they can give me without knowing my whole stack, but what's even better is if they ask questions about my stack. Shows they know how to do requirements gathering and if they ask the right questions.
- rikelmens 8y agoA blog post Peter Norvig commented. Nice.
- rajacombinator 8y agoWhat kind of companies ask dp problems in an interview? Seems pretty absurd.