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

191–200 of 225 posts

Re: Dynamic Programming for Technical Interviews

#191

Post by JJMcJ »

deepGem wrote: post #75
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…

"and candidates who haven't usually don't even have a chance at solving them" I am one of those candidates, and I don't know why it is called Dynamic programming. To me a vey naive understanding of DP is this - it's just a simple cache mechanism to store intermediary results so that you don't have to recompute them and waste resources. In the real world we always think about and do such optimizations, be it I/O, disk…

Programming in the wide sense of any list of things to do.

Dynamic because it sounds nice.

Name was chosen because US Secretary of Defense at the time hated anything that smelled of research, so they found another name.

See https://en.wikipedia.org/wiki/Dynamic_programming#History

Remember, what most of on this board do is computer programming, or perhaps software programming.

The people who decide what songs to play on the radio. They are programmers also.

Re: Dynamic Programming for Technical Interviews

#192

Post by Aditya_Ramesh »

zerocool2750 wrote: post #173
Aditya_Ramesh wrote: post #169

Earlier quoted context omitted.

Thanks for pointing out the typo! I'll fix that right away. And in regards to the "global variable", my variable 'dp' is my cache array. It's where I'm storing my precomputed results. If I don't modify it, it's not DP anymore, it's plain recursion. :) I guess I should've mentioned that the actual memoization table is an exception. Anyway, thanks for reading my article! :)

Totally makes sense I just think it's slightly confusing in that context. Anyway, awesome article I enjoyed the read!

Thank you! I'll make sure to go over some non-classical problems in my next article on DP to add more value :)

Re: Dynamic Programming for Technical Interviews

#193

Post by wildmanx »

01100011 wrote: post #96
deepGem wrote: post #75

Earlier quoted context omitted.

"and candidates who haven't usually don't even have a chance at solving them" I am one of those candidates, and I don't know why it is called Dynamic programming. To me a vey naive understanding of DP is this - it's just a simple cache mechanism to store intermediary results so that you don't have to recompute them and waste resources. In the real world we always think about and do such optimizations, be it I/O, disk…

In my "real world" we normally don't care about things like big-O complexity. We worry about doing dumb things and not taking more time than we have available. I'm not saying big-O is useless or CS wizards are never helpful. It's just that you need one or two of them for a large team of normies, IME. I have a problem with this notion that knowledge of algorithms is required to be a good engineer though. Case in point…

> In my "real world" we normally don't care about things like big-O complexity. We worry about doing dumb things and not taking more time than we have available.

Any work in any kind of scale setting has to implicitly deal with this. You might not realize it immediately, but if you are dealing with a network of 100k+ nodes, or some database with 10M+ entries, or anything of that sort, there is a huge difference between doing something in O(N) or in O(N^2) or O(2^N). Just a nested loop where for each node you need to gather information from each other node is completely out of the question (quadratic vs. linear). Or where you try all combinations of something (exponential). Or where you look up something (linear search vs. logarithmic). I deal with such problems every day. And my job isn't anything special. You may call those "dumb things", but under the hood it's just asymptotic complexity, aka "big-O".

It could also be that your "real world" does not contain scale settings. But then please don't generalize; the industry is full of scale problems to be solved on a day-to-day basis.

Re: Dynamic Programming for Technical Interviews

#194

Post by baobabKoodaa »

eru wrote: post #158
baobabKoodaa wrote: post #149

Earlier quoted context omitted.

Try solving some difficult DP problems on CodeForces. You will find that an "understanding of recursion" is not enough to solve them.

No, no, it is an understanding of how to recurse just right. Not an understanding of the concept of recursion in general. Basically, recursion plus memoization is almost the same in terms of power and approach as dynamic programming.

No, it's not, and if you actually tried to solve one of the harder DP problems, this would become very obvious to you.

Here's one for you: https://codeforces.com/problemset/problem/1097/G

It's a dp problem, and you understand how to recurse just right, and you understand memoization, so you'll be able to solve it, right? Link your solution when you reply please.

Re: Dynamic Programming for Technical Interviews

#195

Post by wildmanx »

groby_b wrote: post #74
jogjayr wrote: post #62

Earlier quoted context omitted.

> Candidates who have learned DP in school usually find them really easy, and candidates who haven't usually don't even have a chance at solving them is directly related to > DP comes up almost never in the real world If you haven't studied DP at school, done competitive programming, or Leetcoded for interview prep you are not likely to have encountered it doing everyday work. And even naturally talented coders are g…

> It's probably true that programmers who are good at solving DP problems are generally quite good, which is why DP problems get asked at interviews. Yeah, no. (Source: I've seen a few interviews in my time. On the order of 5k of them) DP problems are absolute shit at giving a signal, even if the candidate knows DP problems. Because "knows DP" is pretty much the only bit of information you get, with possibly a slight…

> I've seen a few interviews in my time. On the order of 5k of them)

Sorry, your "5k" doesn't pass the smell test, unless you can give some convincing reason why 20 years of one interview per day would be believable.

So, I'm calling BS. You just seem bitter about interviews that you don't like and are trying to con people into giving your opinion more weight than that of others.

Besides, if other companies are doing interviewing "wrong" as you think, then just do it "right" in yours and have a competitive edge by hiring all those brilliant coders that other companies are too stupid recognizing. That would be a reason for you to be joyful instead of bitter, no?

Re: Dynamic Programming for Technical Interviews

#196

Post by baobabKoodaa »

reader5000 wrote: post #181
baobabKoodaa wrote: post #145

Earlier quoted context omitted.

DP is a general problem solving approach. It's about recognizing which parts of a naive solution have repetition which can be eliminated to improve the time complexity of the solution. Another poster aptly described it as finding states which can be collapsed into one. However you want to think about it, - DP is a general problem solving approach - DP is not limited to any particular implementation detail (like my pa…

In "Algorithms" [Dasgupta, Papamdimitriou, Vazirani] they state that the memoization (e.g. querying a hash table) can have significant overhead leading to a large constant factor in the big O analysis. On the other hand, the bottom up approach using a table solves all the possible subproblems including ones that are not needed and ones that the recursive approach would avoid. So from a big O perspective the recursive…

This is true. However, both approaches are "dp" if we are talking about the equivalent solution implemented in these different ways.

Re: Dynamic Programming for Technical Interviews

#197

Post by reader5000 »

baobabKoodaa wrote: post #196
reader5000 wrote: post #181

Earlier quoted context omitted.

In "Algorithms" [Dasgupta, Papamdimitriou, Vazirani] they state that the memoization (e.g. querying a hash table) can have significant overhead leading to a large constant factor in the big O analysis. On the other hand, the bottom up approach using a table solves all the possible subproblems including ones that are not needed and ones that the recursive approach would avoid. So from a big O perspective the recursive…

This is true. However, both approaches are "dp" if we are talking about the equivalent solution implemented in these different ways.

Yeah I thought the recursion+memo wasn't actually "dp" until I looked it up. Recursion without the memo is not DP however since you hit exp running time/memory and the whole point of DP is to avoid this.

Re: Dynamic Programming for Technical Interviews

#198

Post by jahewson »

deepGem wrote: post #75
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…

"and candidates who haven't usually don't even have a chance at solving them" I am one of those candidates, and I don't know why it is called Dynamic programming. To me a vey naive understanding of DP is this - it's just a simple cache mechanism to store intermediary results so that you don't have to recompute them and waste resources. In the real world we always think about and do such optimizations, be it I/O, disk…

What makes dynamic programming special is that it exploits optimal substructure, where a problem can be broken down into smaller sub-problems, the solution to which must be part of the optimal solution to the larger problem.

While caching can be applied anywhere, dynamic programming can only be applied where optimal substructure is present. For example, finding the shortest path between all points in a graph. Likewise, finding the longest path doesn't have optimal substructure and so dynamic programming cannot be applied in that case.

Re: Dynamic Programming for Technical Interviews

#199

Post by jhall1468 »

Asooka wrote: post #139
jhall1468 wrote: post #63

Earlier quoted context omitted.

> For some reason most people seem to be born without the part of the brain that understands pointers Well, that's just false. Everyone can understand pointers given both time and interest. I realize Joel likes to think him and people like him are "special" and born with innate super powers, but we have overwhelming evidence that it isn't true. I certainly wouldn't recommend hiring someone to write embedded systems t…

> Well, that's just false. Everyone can understand pointers given both time and interest. I'd like to believe that's true, but I've spent quite a lot of time trying to explain pointers and recursion to people and either they get it right away or practically never. Sometimes they end up with some cargo-culted half-way understanding that lets them solve most problems but they still don't seem to understand what's happe…

It's not controversial that different topics are difficult for different people, but the idea of "innate" understanding is absurd. And the idea that code quality has a direct causal relationship to code quality is even more absurd. He certainly didn't qualify that statement to imply C programmers have lousy code when they don't understand pointers, but how many people that struggle with pointers want to jump on that ship anyway?

End of the day, learning its a personal thing, and some people struggle in some topics and not in others, but under no circumstances do I think there's an innate ability to understand pointers and some people are never going to have it. That just sounds like C programmers trying to pet their ego.

Re: Dynamic Programming for Technical Interviews

#200

Post by hn_throwaway_99 »

alangpierce wrote: post #61
hn_throwaway_99 wrote: post #54

Earlier quoted context omitted.

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

I guess I'm more worried about false negatives (i.e. people doing poorly who would do well on the job) than false positives. I have worked with excellent coworkers who I think would likely do really poorly on DP questions because they didn't do contest programming or didn't happen to learn it in their education. Recursion is a great thing to include in an interview (in moderation), no objections there. Many real-worl…

That article by Joel goes into detail, but I agree with him that false positives (hiring someone who turns out to be a dud) are MUCH MUCH worse than missing out on someone who is potentially good (especially the rarer case of someone who is potentially good but still did poor on the interview).
Post reply on HN