Dynamic Programming for Technical Interviews • Hacker News Board

Re: Dynamic Programming for Technical Interviews

#71

Post by candeira » Fri, Mar 15, 2019, 5:23 AM UTC

chillee wrote: post #36

candeira wrote: post #27

Dynamic Programming and memoization are definitely related techniques, but they are emphatically _not_ the same. Memoization is a black-box approach that can be applied to a generic recursive top-down, depth-first algorithm. Dynamic Programming is about rewriting the recursive top-down algorithm in a bottom-up, breadth-first manner. Shriram Krishnamurthi explains it best: https://blog.racket-lang.org/2012/08/dynamic-…

This is one definition, but I don't think it's the common one. The more common definition is that dynamic programming refers to solving a complicated problem by breaking it up into simpler overlapping subproblems that can be solved independently. Solving it with recursion/memoization vs. bottom-up is merely an implementation detail, while DP refers to a class of algorithms. EDIT: Corrected definition of DP.

I understand that DP requires turning a recursive, top-down algorithm into an iterative one by yes, reusing the overlap in the subsolutions.

And Krishamurthi's definition is the clearer I've seen that doesn't include "memoized recursion" as a subset of Dynamic Programming.

Re: Dynamic Programming for Technical Interviews

#72

Post by ram_rar » Fri, Mar 15, 2019, 5:37 AM UTC

After spending a lot of time interviewing candidates. I have pretty much come to the conclusion that DP problems dont give good signals about candidates problem solving skills. In my experience, less 5% of candidates can genuinely crack problems using DP. Most of them either give me memorized solution or just plain give up.

If you are interviewing for a regular CRUD job aka web application. There are soo many other problems which can give much more refined signal about candidates skill. Please for love of God, dont ask DP. Unless you actually use it at work.

Re: Dynamic Programming for Technical Interviews

#73

Post by closeparen » Fri, Mar 15, 2019, 5:40 AM UTC

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.

It's incredibly surprising to me. Our interview problems call for things like DFS, tries, stacks, etc. I've never seen a candidate so comfortable with these much more basic topics that I could imagine them writing a DP algorithm (much less proving it correct - we never ask that) in 45 minutes.

We are taught to prefer problems with several independent hurdles, each of which can be reasonably thought through even if not familiar with an algorithms textbook. From my memories of algorithms class, DP problems usually had one very tough "aha moment" to crack. Not a good way for the candidate to show problem solving skill, just more of a binary "did they get it or not?"

Re: Dynamic Programming for Technical Interviews

#74

Post by groby_b » Fri, Mar 15, 2019, 5:46 AM UTC

jogjayr wrote: post #62

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…

> 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 seasoning of "doesn't write utterly horrible code".

The reason they're asked is the reason most interview questions are asked: The interviewer picked them up somewhere, is now familiar with them, and will ask it till the cows come home. (It also allows you to feel all smart and academic when asking it, but that's rarely if ever the main motivation)

Here's an entirely novel concept for evaluating if somebody can write code that solves actual problems. We could ask people to, IDK, write code that solves actual problems. They're there for a day. A good coder can solve some pretty interesting problems in a day.

I know, I know. Heresy. Who'd ever evaluate people by looking at how they do their actual work if you can instead recite shibboleths on a whiteboard?

(Yes, I'm bitter about the tech interview process)

Re: Dynamic Programming for Technical Interviews

#75

Post by deepGem » Fri, Mar 15, 2019, 5:52 AM UTC

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 access or db access. I would love to understand how DP is any different.

Re: Dynamic Programming for Technical Interviews

#76

Post by msla » Fri, Mar 15, 2019, 5:54 AM UTC

hn_throwaway_99 wrote: post #54

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

> 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, and you can say things like "Get me the thing in box number 23" or "Get me the thing in box number 42 and the three boxes after it, put those four things together into a number and then get the four things at that box number and the three boxes after it" and, while the second thing is involved, it's straightforwards and it is precisely the kind of double-indirected thinking Joel is talking about.

To get a bit deeper, you can use the old "Paging Game", also known as the story of the Thing King, to introduce virtual memory:

http://archive.michigan-terminal-system.org/documentation/th...

This is wrong in almost every specific detail when it comes to modern systems, as it dates from circa 1972-1974, but you only need to change a few numbers around and it's good enough in a lies-to-children sense. The only substantial change that would be required is if you want to mention ASLR.

And that's it. That's it until they actually get intimate with a specific hardware architecture and OS and learn very specific, rather ephemeral details. Pointers just aren't all that special.

Re: Dynamic Programming for Technical Interviews

#77

Post by hhmc » Fri, Mar 15, 2019, 5:54 AM UTC

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…

The etymology comes from the field of mathermatical optimization, not from programming as commonly understood today.

Re: Dynamic Programming for Technical Interviews

#78

Post by RJIb8RBYxzAMX9u » Fri, Mar 15, 2019, 5:57 AM UTC

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…

> [...] I don't know why it is called Dynamic programming.

In this context "programming" means "optimization"[0].

[0] https://en.wikipedia.org/wiki/Mathematical_optimization

Re: Dynamic Programming for Technical Interviews

#79

Post by PopeDotNinja » Fri, Mar 15, 2019, 6:00 AM UTC

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 don't know anything about dynamic programming in the manner that it is taught. I also don't get why it's even a thing (which is to say I haven't studied the topic, and haven't yet seen a need to do so).

Someone recently gave me the egg dropping problem in an interview. I had never seen it before, but the answer eas obvious, and I verbally stated the solution in under a minute. I asked the interviewer if I could out the Log N solution, which I believe was essentially a binary search on a logical list of length N using a bit of looping or recursion. He asked me to go through the process of explaining it, and I really didn't see the point. He knew the answer, and he knew the answer, and he asked me to implement the simplest solution first. To me, that was the solution I started, but that wasn't good enough. The interview went downhill from there.

I later googled the answer, saw people explaining some overly complex matrix-y shenanigans, and I tuned out.

Maybe I'm missing something?

Re: Dynamic Programming for Technical Interviews

#80

Post by brianberns » Fri, Mar 15, 2019, 6:04 AM UTC

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…

> Here's an entirely novel concept for evaluating if somebody can write code that solves actual problems. We could ask people to, IDK, write code that solves actual problems. They're there for a day. A good coder can solve some pretty interesting problems in a day.

You mean solve an actual business problem that the interviewing company has? The ramp-up time to be productive in any real business that I've been associated with is significantly greater than the time available in a single interview (usually an hour or so). This is why toy problems are used.

Another issue is that it's not really fair to ask an interviewee to solve your company's problems for free. In fact, without some sort of contract, the interviewee technically owns her own work, so even if she manages to solve a real problem, the company really shouldn't use it.

(BTW, 5K interviews at one hour per interview is 625 eight-hour workdays. Assuming 50 work weeks of five days each in a year, that's 2.5 work years devoted to nothing but interviewing in your career. Yes?)