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

151–160 of 225 posts

Re: Dynamic Programming for Technical Interviews

#151

Post by throwawaymath »

Asooka wrote: post #141
msla wrote: post #76

Earlier quoted context omitted.

> For some reason most people seem to be born without the part of the brain that understands pointers. If you can understand P.O. box numbers, you can understand pointers. They're the same concept at the level of modern application programming, where the OS, MMU, and cache are comprehensively lying to your code to present the illusion of a completely flat address space. At that level, all a pointer is is a box number…

Yes, and then you have to make people understand that box [number 23] is itself in a box and 23 can change at any time. And you can ask for the thing in box [the thing in box [the thing in box [the number that was passed to this function]]]. It's a double and sometimes triple indirection and understanding that pointers and the things pointed to are the same kind of data is the hard part. It's numbers all the way down…

You're making a strong point here, which is that every real world analogy of pointers breaks down since everything is data. But I'm still not sold on the idea that pointers are intrinsically a "make it or break it" topic for people to learn.

In fact, I'm resistant to that sort of conclusion in general. I don't really think there are things that people of average intelligence can't learn, given enough time and pedagogy. And I say that as someone with a background in mathematics, which is one area most typically associated with people "not getting it."

If people don't learn pointers, it could be because they're not sufficiently motivated or don't have it presented to them the right way. It could be that the overuse of analogies does them a disservice, and they really just need to pick up a book. Whatever the case may be, I'd hesitate to say it can't be learned by any population of people.

Re: Dynamic Programming for Technical Interviews

#152

Post by baobabKoodaa »

jonfw wrote: post #142
collyw wrote: post #121

Earlier quoted context omitted.

If you really do need to know that stuff, you can read up on it when it's needed. Been programming professionally for over 15 years and have had to use this stuff once that i can remember. Knowing how to design and index a database well is way more useful.

To give the other side of the coin here- you at least need to know the basic logic behind it if you're going to be able to recognize when reading up on it might be needed. If you have never considered the benefits of caching certain computational results in a recursive algorithm, than you probably wouldn't be as quick to recognize when that technique would be useful.

Exactly. And also, even if you somehow recognized that "you need to use a DP solution here", it's not as easy as "read up on it" (like GP says). DP is not a trick that you can just learn once and then apply everywhere. It's not a npm package that you can install that solves your problem for you.

Re: Dynamic Programming for Technical Interviews

#153

Post by jghn »

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…

Speaking for myself, I was the person Joel described except that I didn't switch majors. The pointer wall first struck at the tail end of my HS years and then crushed me early on my Freshman year of college. It took me a couple of years but I finally wrapped my head around pointers. It could be that I really do fall into your half-way camp, but I don't think that's the case.

I was a terrible student more interested in playing games than doing any actual work, so that I'm sure was a large part in the problem being "years" instead of "months", but either way it was something I learned and not something I was just born with.

I do agree that for any person there will be things that they get right away and things that they'll never get. But I think those vary more than people realize.

Re: Dynamic Programming for Technical Interviews

#155

Post by jonfw »

pmiller2 wrote: post #88
smallnamespace wrote: post #38

Earlier quoted context omitted.

> If someone can learn to solve just DP problems by practicing in leetcode then DP is a useless metric or proxy of someone’s ability to reason mathematically. Metrics that can be gamed can still have a lot of signal in them because the cost of gaming the metric is higher than the benefit of gaming things. There's a branch of game theory/economics called signalling theory that's applicable here: https://en.wikipedia.o…

If the ability to learn completely arbitrary things is what they want to test, why not have them write an essay on the spot in Sanskrit?

It's not arbitrary, and it's not on the spot.

Dynamic programming asks them to either study or have abstract math skills. Both are good signs of competence.

Re: Dynamic Programming for Technical Interviews

#157

Post by dahart »

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.

Big-O is just a formal word for how much time you’re going to take, a way to figure out if you’re likely to take more time than available. So, it sounds like you do care about it, you’re just saying it doesn’t matter if you’re formal about it?

If your team’s n^2 worst case really is in the noise, then you’re absolutely right, the senior is prematurely optimizing.

But without more context, I have to assume there could be reasons your senior “nerd” might be right. Is there a noticeable difference to the user in run time with the largest n you can possibly have? Is the other team you’re delivering to going to call your n^2 routine from one of their own, one that has it’s own O(n) or O(n^2) outer loop?

I’d say big-O notation isn’t difficult, doesn’t take long to learn, doesn’t require school, and knowledge of it doesn’t make someone a wizard. It’s easy. It’s a low enough bar, that I do expect everyone on my team to feel comfortable looking at a function with loops and being able to tell whether something is O(n^2) or O(n^3).

The difficult cases are determining complexity of an architecture full of lots of interconnecting O(1..n) functions, when the complexity isn’t all in one place. I watch unnecessary O(n^3) algorithms get made even on teams of people who all know big-O.

Re: Dynamic Programming for Technical Interviews

#158

Post by eru »

baobabKoodaa wrote: post #149
deepGem wrote: post #84

Earlier quoted context omitted.

Absolutely, but I attribute the ability to decompose a problem into overlapping subproblems as an understanding of recursion, so I had implicitly assumed such an understanding.

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.

Re: Dynamic Programming for Technical Interviews

#159

Post by bogomipz »

chillee wrote: post #70
bogomipz wrote: post #64

Earlier quoted context omitted.

I'm familiar with 1D and 2D but what are some examples of Tree DP besides the standard Fibonacci questions?

Fibonacci isn't considered Tree DP. One example of a tree DP problem is: Given a tree with N nodes, how many ways are there of coloring each node with black or white given that no two white nodes are adjacent.

Isn't that just the classic graph coloring problem though? A tree is just a type of graph.

Re: Dynamic Programming for Technical Interviews

#160

Post by dahart »

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…

DP means you map the problem to a grid, and your cache connections are your neighbors on the grid.

Memoize (aka caching) was invented later than DP, and it’s easier and the same complexity. You don’t have to map your problem to a spatial layout.

One big difference is that DP often involves windowing your cache. While the problem might be on a 2d grid, the storage for your cache might be just two rows, and the algorithm will sweep down rows only once. So, a DP solution might be far less memory than a straightforward memoize, unless you’re doing work to clean up memoize as soon as it’s no longer needed.

Another big difference is that with DP you’re pre-allocating, while with memoize you’re typically using dynamic memory allocations by default. That obviously doesn’t have to be true, but makes a fairly naive DP solution faster than a fairly naive memoization.

Post reply on HN