Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Dynamic Programming for Technical Interviews

blogarithms.github.io

Post reply on HN
Print view View original

51–60 of 225 posts

Re: Dynamic Programming for Technical Interviews

#51

Post by mesarvagya »

petermcneeley wrote: post #14

The knapsack problem here is of particular interest since despite the optimization problem being NP-hard the solution can in fact be found in O(n * W). This feels similar to how the theoretical best comparison sort is O( n log n) but radix can do this in O( n).

Knapsack still is a NP-Hard Problem. Even though DP solution looks linear, it has pseudo-polynomial time complexity[1][2]

[1]https://en.wikipedia.org/wiki/Knapsack_problem#Computational...

[2] https://stackoverflow.com/questions/4538581/why-is-the-knaps...

Re: Dynamic Programming for Technical Interviews

#52

Post by akhilcacharya »

chillee wrote: post #33
alangpierce wrote: post #17

> problems on DP are pretty standard in most product-company-based hiring challenges This is sad and a little surprising to me. I've always thought of DP problems as being obviously terrible interview questions, even among the different types of algo questions (which are already heavily criticized). Candidates who have learned DP in school usually find them really easy, and candidates who haven't usually don't even h…

I actually disagree. Of the problems that are commonly asked in programming interviews, DP is perhaps the one that tests "general problem solving" the best. Many other problems require problem-specific tricks/uncommon tricks. On the other hand, there's rarely a DP problem (that comes up in interviews) that relies on a problem-specific trick.

Highly disagree with this. There are pretty significant approach differences between 2D DP, 1D DP, Tree DP, string operations, etc. Determining what you optimize and cache (if you do top-down, which I prefer) is often problem-specific.

The way the optimal solutions are laid out the differences between the most efficient fibonacci (O(1) space), "House Robber" independent set problem, and various problems on top of string distance seem not to have much in common between them.

Re: Dynamic Programming for Technical Interviews

#53

Post by mehrdadn »

rfrey wrote: post #23
alangpierce wrote: post #17

> problems on DP are pretty standard in most product-company-based hiring challenges This is sad and a little surprising to me. I've always thought of DP problems as being obviously terrible interview questions, even among the different types of algo questions (which are already heavily criticized). Candidates who have learned DP in school usually find them really easy, and candidates who haven't usually don't even h…

>This is sad and a little surprising to me. I think dynamic programming is in fashion because of the rise of reinforcement learning among the buzzword savvy.

DP is most definitely not in fashion because of reinforcement learning. It's been pretty standard since long before the ML buzz.

Re: Dynamic Programming for Technical Interviews

#54

Post by hn_throwaway_99 »

alangpierce wrote: post #17

> problems on DP are pretty standard in most product-company-based hiring challenges This is sad and a little surprising to me. I've always thought of DP problems as being obviously terrible interview questions, even among the different types of algo questions (which are already heavily criticized). Candidates who have learned DP in school usually find them really easy, and candidates who haven't usually don't even h…

For what it's worth, I use DP problems extensively for a main reason: in my experience I have found an extremely high correlation between folks who do well on DP problems and folks who are good overall engineers.

I have never had a candidate that did very well on DP problems that didn't end up being an overall great programmer (though I certainly have had folks do well on DP problems who were deficient in other ways, e.g. communication, etc.), though I have had some 'false negatives' with candidates who did poorly on DP problems who still ended up being productive employees.

Also, I wouldn't use DP problems for some types of roles, but in general I find that the ability to think recursively is overall highly indicative of programming ability. I'm not the only one who thinks this way: https://www.joelonsoftware.com/2006/10/25/the-guerrilla-guid... . Joel is talking about pointers specifically in this quote but I think it equally applies to recursion:

"I’ve come to realize that understanding pointers in C is not a skill, it’s an aptitude. In first year computer science classes, there are always about 200 kids at the beginning of the semester, all of whom wrote complex adventure games in BASIC for their PCs when they were 4 years old. They are having a good ol’ time learning C or Pascal in college, until one day the professor introduces pointers, and suddenly, they don’t get it. They just don’t understand anything any more. 90% of the class goes off and becomes Political Science majors, then they tell their friends that there weren’t enough good looking members of the appropriate sex in their CompSci classes, that’s why they switched. For some reason most people seem to be born without the part of the brain that understands pointers. Pointers require a complex form of doubly-indirected thinking that some people just can’t do, and it’s pretty crucial to good programming. A lot of the “script jocks” who started programming by copying JavaScript snippets into their web pages and went on to learn Perl never learned about pointers, and they can never quite produce code of the quality you need."

Re: Dynamic Programming for Technical Interviews

#55

Post by akhilcacharya »

The problem with DP problems (for me) is there seem to be a really large set of unique DP problems and coin change, knapsack, and grid DP problems like number of paths are only a small subset of them. What's more is that the rest of the problems can't be easily based on the approaches used for these...there might be dozens of problem classes to understand!

Re: Dynamic Programming for Technical Interviews

#56

Post by akhilcacharya »

mesarvagya wrote: post #31

One of the techniques as described in CLRS is to first find the subproblem graph. Consider Fibonacci sequence: f(0) = 0; f(1) = 1; f(n) = f(n-1) + f(n-2) If we solve it naively, complexity will be O(1.6^n). Now we can solve it in DP using two ways: 1. Top Down: Instead of recursively computing the same subproblem, just store the value of this computation and look it up when needed. That's it. 2. Bottom Up: One cannot…

This is all well and good for fibonacci but it feels like the difficulty of the problem becomes exponentially greater when you start running into more complicated optimization strategies. Text justification is an example:

[0] http://courses.csail.mit.edu/6.006/fall09/lecture_notes/lect...

Re: Dynamic Programming for Technical Interviews

#57

Post by ralusek »

akhilcacharya wrote: post #55

The problem with DP problems (for me) is there seem to be a really large set of unique DP problems and coin change, knapsack, and grid DP problems like number of paths are only a small subset of them. What's more is that the rest of the problems can't be easily based on the approaches used for these...there might be dozens of problem classes to understand!

That might be the only dynamic thing about the otherwise terribly-named set of problems.

Re: Dynamic Programming for Technical Interviews

#58

Post by akhilcacharya »

sanderjd wrote: post #4

I have always felt that dynamic programming is only confusing because of the name. The concept of caching previously calculated values in order to save time by avoiding recalculation (at the cost of using more space) is intuitive. What am I missing?

Formulating the recursion and caching strategy is the difficult part and it is non-trivial to identify at times.

For example, this is simple to explain in the abstract case but what about a concrete case like text justification or edit distance?

The hardest part is getting to the recurrence relation, and then implementing it.

Re: Dynamic Programming for Technical Interviews

#59

Post by mehrdadn »

alangpierce wrote: post #17

> problems on DP are pretty standard in most product-company-based hiring challenges This is sad and a little surprising to me. I've always thought of DP problems as being obviously terrible interview questions, even among the different types of algo questions (which are already heavily criticized). Candidates who have learned DP in school usually find them really easy, and candidates who haven't usually don't even h…

DP questions are often pretty darn awesome. The solutions are so frequently elegant and really make you think hard about problems. When I fail them I learn so much... it's practically a win-win. I've been completely stumped by DP questions even after having done tough DP problems in multiple classes in school so I most definitely don't think those who've seen them in school find them really easy, unless for some silly reason you're asking exactly the same classical DP questions that everyone sees in school, like say Levenshtein distance. Even small twists can make the solution no longer be obvious, e.g. for edit distance consider an affine gap penalty (used in computational biology).

Re: Dynamic Programming for Technical Interviews

#60

Post by gaogao »

throwawaymath wrote: post #40
rfrey wrote: post #23

Earlier quoted context omitted.

>This is sad and a little surprising to me. I think dynamic programming is in fashion because of the rise of reinforcement learning among the buzzword savvy.

To my recollection, dynamic programming problems were fasionable interview questions prior to the current wave of machine learning. That's to say I'm pretty sure they were being asked at Google/Facebook/etc around 2012 at least, likely earlier.

At the FANG I'm at, DP is now heavily discouraged with a note that it was once a very common interview topic.
Post reply on HN