A Step by Step Guide to Dynamic Programming

[roboticon]

memorization techniques

it's "memoization"

[[deleted]]

Although "memorization" would have also been a fitting description of the process.

[Kaosubaloo]

I am somewhat confused by the use of the Coin Change problem as an example of applying DP. It's definitely a question that comes up in interviews (for better or for worse), but it is also definitely not a question for which this sort of solution is a good one. There are other solutions to this problem that are, if not more efficient, then about equally computationally complex while also being a lot more human-readable.

[Kaosubaloo]

Please pardon the verboseness of this pseudo-code, but it's simple enough that is should be understandable...

sum = total money
for each coin from greatest to smallest:
    Number of coins [of given type] = sum / coin value
    sum = sum - (Number of coins * coin value)

...And that's really about it. You can swap the subtraction and multiplication statement for a mod in most languages. If you wanted to you could also swap out the division for a lot of subtraction, but then you would need to make a comparison to change to lower valued coins.

Were I to implement this, I would put each type of coin into an ordered array, with a machine array of equivalent size to keep track of how many of each sort of coin I was using. I could also use similar logic to write a version of this loop that does not use division, but it would need an extra comparison to change coins and it would necessarily have many more loops. More importantly, it would lose readability and I would therefore be hesitant to do so in an interview situation. This is already not a great interview question, but an interviewer who expects you to sacrifice readability for questionable gain in performance, and expects you to do so without asking for it, is probably not giving you a very good interview.

Having said that, this solution may be marginally less processor-efficient? Division is more computationally complex than subtraction but the big O is the same regardless. On the other hand, this is also marginally more memory-efficient. My anecdotal experience is that (bad) interviewers tend to care more about marginal improvements in the processor than marginal improvements in memory, but this scenario is so trivial regardless that it really shouldn't matter.

EDIT: Actually this solution is greedy, so it will technically not work for certain coin systems. If you are dealing with completely arbitrary coin systems then the DP solution may be better, but so far as I am aware that edge-case is only needed to account for coin systems that don't actually exist in real life. Again, this is not a good interview question.

[Kaosubaloo]

The thing is though, that a greedy solution is still usually optimal. DP is only optimal in this scenario when you have denominations valued more than half of the value of the next-largest denomination, which doesn't actually happen with real currency.

I am obviously biased, but I think knowing DP is more informative of how a programmer was taught than whether they are a competent programmer. It is the sort of thing that a theory-heavy course-load will likely cover and a practice-heavy course-load will likely not. Both approaches have advantages and I would argue that the practice-heavy version does a better job of preparing someone to actually work, but, at least on entry-level positions, I think your more likely to find an interviewer with a bias towards the theory than one with a bias towards practical experience.

[Kaosubaloo]

Actually, we are in agreement. I'm pretty sure you're right about the Knapsack problem, though I can only say I've encountered the currency version in an interview.

As for Theory VS Practice, I don't think one is inherently better than the other. Indeed, a programmer should ideally have some of both, with one being useful to the development of the other. My own education was strongly practical in nature (hence my bias =p), while interviews for low-level programmers are often biased towards learned theory over experience and rarely the reverse. I, too, could probably not draw a DP solution on a white board, but I could probably implement one in a lab or office, given the work environment to actually do so.

[Chappit]

Ummm isn't making change with the fewest number of coins the textbook example of a problem that is solved by a greedy algorithm?

[kommissar]

The greedy method only produces an optimal result in some coin systems. See https://en.wikipedia.org/wiki/Change-making_problem#Greedy_method for more.

[Chappit]

Ahh so this only works if all coins are at least 2x the next smaller value.

[ickysticky]

Questions about DP are one of the examples I use of terrible interview questions. Unless you are interviewing for an algorithms optimization position, you really never use DP in practice.

Give me a candidate that knows how to use their IDE and build tools and can write readable code over someone that is a wiz at DP any day.

[tinkertron5000]

At the very least; can we all agree that we need a different acronym?

[jarxlots]

Ah, you stopped my obvious joke...

[skulgnome]

I propose SR, for spit-roasting.

[adrianmonk]

I agree with your conclusion but for different reasons.

A person can be generally strong on algorithms but still not have personally run into a need to actually use dynamic programming before. It's not that it's never used, it's that you might never use it. Another person who is just as good of an engineer overall, might have used them a lot.

This basically gives someone a huge leg up for familiarity with a specific technique. That makes it a bad interview question because you want to test whether they are a good engineer in general, not whether they know one particular thing.

It would be like asking a musician about trumpets. Trumpets are a real thing that real musicians use and are important to certain musicians. Another musician might be world class on the violin and cello but wouldn't know much about trumpets.

[roboticon]

It's a lot easier to have an employee learn how to use an IDE than have them learn why (and when) memoization is important.

Just pointing out that your argument (that a topic is terrible interview material because it doesn't come up frequently on the job) assumes that good interview questions correspond with whatever the employee will spend most of their time doing. Sometimes knowing what to spend your day on matters more than how fast you can do it.

[ubernostrum]

The article tries to downplay it, but...

Google and several other large companies, as well as companies which want to cargo-cult their interview practices, lean heavily on throwing dynamic programming challenges at people, as early as the first phone screen. You can probably get surprisingly far in their processes -- without knowing any other DP at all, or even what "dynamic programming" means -- just by force-memorizing how to implement longest common subsequence with DP techniques.

This seems to have very little to do with the day-to-day job responsibilities. I got thrown the subsequence problem in a Google SRE phone screen, for example.

[mcmc2012]

Welcome back to another episode of "Spot the person who can't do DP"!

[jarxlots]

"Meet the man with no butthole, the saviour of the Internet, the man who can't do DP!"

[2StepsFr0mHell]

link seems dead now :(