It'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.
Solving dynamic programming interview problems
111–120 of 176 posts
Re: Solving dynamic programming interview problems
#112Being 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.
Re: Solving dynamic programming interview problems
#113Speaking 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…
When I interviewed at $BigCompany, I really enjoyed the whiteboard programming problems I got.
But I noticed that 2/3 of them ended up with recursive solutions. Meanwhile, I spend less than 1% of my real professional programming time writing recursive code, and it's a bit silly that so much focus is on such relatively obscure technique.
Re: Solving dynamic programming interview problems
#114Speaking 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…
When I interviewed at $BigCompany, I really enjoyed the whiteboard programming problems I got. But I noticed that 2/3 of them ended up with recursive solutions. Meanwhile, I spend less than 1% of my real professional programming time writing recursive code, and it's a bit silly that so much focus is on such relatively obscure technique.
I think it's a mistake to think of whiteboard problems as attempting to recreate a real work environment. They are a proxy for the kind of quality you are looking for that can be "measured" within the alotted time.
They can show that the person is prepared (they studied), generally knowledgable (they remember obscure stuff), or just clever (they come up with interesting approaches to the problem).
I'm not surprised you see both excessively simple (make sure they aren't ridiculously unqualified) and excessively obscure problems, since the first one essentially tests your reflexes and the second one tries to determine if you learned your job "by rote"
Re: Solving dynamic programming interview problems
#115Great 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.
Re: Solving dynamic programming interview problems
#116Speaking 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).
There are problems that have clearer solutions when expressed as recursive. There are problems that have clearer solutions when expressed as iterative.
Having both tools in your toolbox and knowing when to use each is part and parcel of developing yourself as a craftsman or craftswomen programmer.
In addition, being able to know when to use memoing in producing your solution is another tool to be put in your toolbox.
Yes, every recursive function has an iterative solution, but the iterative solution can be far more complex. The best example of this is that lovely little function - Ackermann-Peter function. The recursive version is just a few lines long. The iterative version is quite a few pages long.
There are specific schemas in which the recursive form should be rewritten as an iterative solution. You can find these detailed in such old gems of books like "Algorithms + Data Structures = Programs".
Re: Solving dynamic programming interview problems
#117Earlier quoted context omitted.
Then why does NASA consider it unsafe for mission critical code? How about unknown potential stack size? How about factoring a large number with recursion? Everything recursive can be transformed to iterative and yea sometimes it’s not as sexy but neither is a helmet https://www.reddit.com/r/programming/comments/3dnsh1/nasas_t...
> Then why does NASA consider it unsafe for mission critical code? They also proscribe unbounded iterations (point 2). In any case, NASA’s guidelines for mission-critical code are not necessarily good guidelines for general software engineering, given the constraints involved. It’s also worth noting that recursive solutions are probably more amenable to static analysis and automated theorem proving. > How about unkno…
> Then why does NASA consider it unsafe for mission critical code?
More like they're using an old Fortran 77 environment which doesn't support recursive functions.
Re: Solving dynamic programming interview problems
#118Earlier quoted context omitted.
I mean if you label all your variables i,j, and k and use minimal formatting or bracketing then I see your point it is harder to read. Whats complicated about an iteration. If it works properly after the first one chances are it will continue to work for the millionth one. If you see problems, its because something is modifying it between runs, but that wasn't a fault of the iterative strategy, it was the fault of a…
> Whats complicated about an iteration What’s complicated about a recursion? > If you see problems, its because something is modifying it between runs, but that wasn't a fault of the iterative strategy, it was the fault of a bad programmer. > Conversely, you must always make sure the stopping condition and all base cases are met during recursion. You seem to be applying a double standard here. > Forget one corner bas…
> > Whats complicated about an iteration
> What’s complicated about a recursion?
Especially as iteration is just a special case of recursion :)
Re: Solving dynamic programming interview problems
#119I'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 cand…
Also, it depends on the interviewer. I have been on both sides of the table and I can tell that as an interviewer you need to convey these type of questions very clearly. A interview is typically 45 minutes in most companies, where about 5-10 minutes are wasted in introduction etc. You have about 35 minutes and if you waste 15-20 minutes explaining a problem to the candidate and in the end leave the candidate with 15…
> where about 5-10 minutes are wasted in introduction etc.
That tells me a lot of concerning things about the organization. If you're considering that it's "wasted time." You're missing out on a lot of important information there.
Re: Solving dynamic programming interview problems
#120In 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 loc…
Any 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.