14 ms·

> 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 probl

> 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 have a chance at solving them, so really they just test whether the person has learned DP, rather than other algo problems where you can at least try to claim that it's a proxy for "general problem solving ability". And DP comes up almost never in the real world (and when it does come up, you're often still better off taking a heuristic/inexact approach), so testing if the candidate knows DP is also almost completely useless. If you're an interviewer at a company that asks DP questions, please reconsider. There are almost certainly alternatives that are more fair and higher-signal.

rfrey 8y ago
>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.
- chillee 8y ago
  I really doubt it. The type of reasoning needed for dynamic programming interview problems is barely connected to DP in reinforcement learning.
- throwawaymath 8y ago
  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.
  - gaogao 8y ago
    At the FANG I'm at, DP is now heavily discouraged with a note that it was once a very common interview topic.
    - YorkshireSeason 8y ago
      What are you encouraged to do with the problems of recursion that DP addresses, stack overflow and overlapping instances?
- mehrdadn 8y ago
  DP is most definitely not in fashion because of reinforcement learning. It's been pretty standard since long before the ML buzz.
kccqzy 8y ago
In contrast, I find that the ability to formulate a problem using DP coorelates with whether a person is able to think in a mathematical way. In many dynamic programming problems you need to first define a function P(i,j) or some such, and then define it recursively; when proving the correctness, you use induction. The ability to grasp this recursion and induction is correlated with the level of abstract mathematical thinking a candidate is capable of. That said, if a candidate goes to LeetCode or some other site to practice all the DP problems, then it's possible that the candidate can only solve DP problems without gaining other abilities.
- elteto 8y ago
  Your two paragraphs are contradictory. 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. You should have said “the ability to solve DP problems is a good metric of the ability of a candidate to solve DP problems“. I would have agreed with you in that case :)
  - smallnamespace 8y ago
    > 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.org/wiki/Signalling_theory https://en.wikipedia.org/wiki/Signalling_theory Also, if being able to learn completely arbitrary things is correlated with intelligence and correlated with job performance, then people who are willing to jump through that arbitrary hoop are telling you that 1) they think they're more capable (faster learners) than average 2) they're willing to put in the effort to prove it to you. Maybe you're not a getting a pure signal of mathematical ability, but some combination of drive + ability + learning fast, and you care about all three.
    - pmiller2 8y ago
chillee 8y ago
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.
- mayank 8y ago
  > On the other hand, there's rarely a DP problem (that comes up in interviews) that relies on a problem-specific trick. That's a pretty big parenthetical. DP problems as a class are full of clever tricks for elegant solutions that took decades of research. Any practical use of DP is almost certainly going to use problem-specific tricks as well. Which makes DP tricky, especially in interviews.
  - chillee 8y ago
    Yes, there's a ton of DP problems that require clever tricks. I've had to show these tricks to friends who believed that DP problems were too formulaic. Could you give an example of DP problems that show up in interviews that require problem-specific tricks? I'm contrasting DP problems with other interview questions like: Find whether a linked list has a cycle in O(1) memory or implement a queue with 2 stacks.
- akhilcacharya 8y ago
  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.
  - bogomipz 8y ago
    I'm familiar with 1D and 2D but what are some examples of Tree DP besides the standard Fibonacci questions?
hn_throwaway_99 8y ago
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-guide-to-interviewing-version-30/ 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."
- alangpierce 8y ago
  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-world situations are naturally recursive, and a good grasp of recursion helps build a strong intuition for many aspects of programming. DP (specifically designing recursion with overlapping subproblems) is a much more specific technique that I think isn't as beneficial for programming ability, though I certainly don't doubt that people who know DP well are often also good programmers.
mehrdadn 8y ago
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).
jogjayr 8y ago
> 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 going to struggle with unfamiliar types of problems. Unfortunately, I don't see a way out of this. 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. It's a good signal for ability to learn difficult things, which is a desirable quality in employees. This means that good programmers who don't know DP are forced to learn it or accept that they won't clear some interviews. Absent some other way to clearly signal technical ability, I think DP problems are here to stay.
- groby_b 8y ago
  > 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)
  - brianberns 8y ago
    > 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?)
matz1 8y ago
The good thing of these type of question is it can be practiced, and it's pretty much "standard". Once you comfortable with it you can essentially interview anywhere.
closeparen 8y ago
>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?"
deepGem 8y ago
"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.
- hhmc 8y ago
  The etymology comes from the field of mathermatical optimization, not from programming as commonly understood today.
- RJIb8RBYxzAMX9u 8y ago
  > [...] 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 https://en.wikipedia.org/wiki/Mathematical_optimization
- mafm 8y ago
  > [...] I don't know why it is called Dynamic programming. According to Richard Bellman, who came up with the name: An interesting question is, Where did the name, dynamic programming, come from? The 1950s were not good years for mathematical research. We had a very interesting gentleman in Washington named Wilson. He was Secretary of Defense, and he actually had a pathological fear and hatred of the word research. [...] What title, what name, could I choose? In the first place I was interested in planning, in decision making, in thinking. But planning, is not a good word for various reasons. I decided therefore to use the word "programming" [...] it's impossible to use the word "dynamic" in a pejorative sense. Try thinking of some combination that will possibly give it a pejorative meaning. It's impossible. Thus, I thought dynamic programming was a good name. It was something not even a Congressman could object to.
  - jonsen 8y ago
    Formatted for mobile: According to Richard Bellman, who came up with the name: An interesting question is, Where did the name, dynamic programming, come from? The 1950s were not good years for mathematical research. We had a very interesting gentleman in Washington named Wilson. He was Secretary of Defense, and he actually had a pathological fear and hatred of the word research. [...] What title, what name, could I choose? In the first place I was interested in planning, in decision making, in thinking. But planning, is not a good word for various reasons. I decided therefore to use the word "programming" [...] it's impossible to use the word "dynamic" in a pejorative sense. Try thinking of some combination that will possibly give it a pejorative meaning. It's impossible. Thus, I thought dynamic programming was a good name. It was something not even a Congressman could object to.
PopeDotNinja 8y ago
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?
- Jach 8y ago
  Talk is cheap, code is what matters. But maybe the interviewer wanted to save time not writing an incorrect solution if he believed your approach was wrong and you could talk yourself out of it? Did you get to step through how your solution would arrive at the number 14 given 2 eggs and 100 floors? And if you wrote it out, would it produce that number? (Personally I have no idea what you mean with the binary search approach, what is your logical list since doing it on the list of floors is wrong? But I've not thought about the egg dropping problem in a long time and have only seen the DP approach.) It might of course be that the interviewer only knew one way to solve it, any other way was therefore wrong. Or admitting they don't understand a demonstrated other way shows weakness, so is also wrong. I'd be perfectly happy to receive rejections from companies with those sort put in charge of interviewing.
  - wizzairflyer 8y ago
    A funny trick is to ask this question but first give the candidate an infinite amount of eggs. Once he succeeds, ask the question with only 2 eggs. That might explain the binary search answer.
dnautics 8y ago
I asked a dp question in an interview. It was useful. Here's why. I know the solution, so I frequently guide the interviewee towards the correct answer and offer my help. Plus I put my nice guy hat on. I have seen a supposedly good candidate refuse my offers of help and then proceed to spaghetti code on the board a series of disjointed while loops that is obviously going to go nowhere. I don't want to work with such a person. They still got the job, because connections, but will 100% never be on my team.
- nosianu 8y ago
  An alternative point of view is that you set them up with an unsuitable question in the first place. Also, the disadvantage of stories such as yours is that we only hear one side. How did your "help" look like? We don't know. For my taste the brevity and content of your story indicates a lack of introspection. It seems to me that the only option you consider is that the interviewee gets all the blame. The reason for my suspicion is that independent of what happened there you should at least be aware that the story is not suitable to be shared in this form, because readers here only get your (very short too) story. Sure, you will get agreement - from people who jump to quick conclusions without actually having a basis for it. You are not even trying to give sufficient and/or unbiased information. I know this is just a forum and casual conversation, but to compare with science, which has the same issue of communicating one's ideas to other people, the equivalent would be a paper that only publishes the authors conclusions.
- pavlov 8y ago
  > "I know the solution, so I frequently guide the interviewee towards the correct answer and offer my help. Plus I put my nice guy hat on." I wouldn't want to work with a person whose idea of a useful job interview is: "I'll pick an esoteric bullshit problem, put my nice guy hat on, and guide you towards the solution as I bask in your admiration of my largesse." It's like when self-declared "nice guys" approach women: when you have to make an explicit point about how nice you are being right now, you're probably doing something very wrong.
  - srean 8y ago
vishnugupta 8y ago
I interview regularly and I'm really keen to know if the person knows about time-space tradeoff. DP 'like' algorithms lend themselves well to evaluate this. Note that I say DP 'like' because I'm essentially looking for them to say memoization and implement it. And this doesn't really take a crazy DP optimization algorithm to evaluate this concept. And note that this time-space kind of tradeoff is something we indeed encounter regularly; e.g., caching (to avoid n/w call or computation), pre-computation etc., So the concept underlying DP is quite useful and it's premature to dismiss it as something that never comes up in the real world. That said, I understand that it's easy to push this and go down the path of more and more esoteric algorithms.
srean 8y ago
> And DP comes up almost never in the real world What a big load of rubbish and gratuitous generalization ! Just because it has not come up in your work or you may have passed opportunities to recognize its applicability at your work, does not qualify you in any way to make such a broad comment. DP has served me very well in each of the last three years in three different projects. In two of these projects I had joined the project midway. In every case the key was to recognize that DP applies where others had not and in doing so had left significant benefits on the table. In one case the 'others' was me myself. I had overlooked a potential application the first time. So much for "almost never in the real world" > candidates who haven't usually don't even have a chance at solving them The claim above sounds a lot like "If all the votes were counted then candidate B would have been elected". The whole point of an election is counting the votes. Is it such an unfair expectation that someone applying for a CS job ought to be familiar with one of its fundamental techniques ? If one is aiming for a commodity position, then perhaps yes.
- alangpierce 8y ago
  It does depend on the job, and I don't doubt that there exist jobs where DP in the interview process is reasonable, especially if it's a "CS job". I'm particularly talking about software engineering interviews, to be clear, not research positions or anything like that. Even in software engineering, I could imagine DP being important if the product relies heavily on high-quality string diffing, for example. I'm certainly interested to hear your real-world applications if you're able to share. I guess I have seen memoized DAG traversal come up, so in that sense I've seen DP, but it's not quite the same as "take this non-recursive-looking problem and make it recursive so you can memoize". Two situations come to mind when I think about DP being used in real-world applications (both just things I heard about): a talk I heard about how Google News compares news pages before and after the publisher makes an HTML change, and DNA sequence alignment problem. Both of them went like this: 1.) We want to find a perfect solution, but the search space is exponential size. 2.) Hey look, by using dynamic programming we can reduce the complexity to n^2 time and space. 3.) Wait, n^2 time/space is still too inefficient for many real-world use cases. Rather than trying to find a perfect solution, let's settle for a good enough solution by rethinking the approach and applying some heuristics. By putting some clever thought into it and sacrificing a little bit of quality, we can get something that takes O(n) time in practice. So I think an initial goal of looking through an exponential search space for an optimal solution (often what DP is solving) is often misguided anyway, since often "optimal" isn't actually so important.

rfrey 8y ago

>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.

chillee 8y ago
I really doubt it. The type of reasoning needed for dynamic programming interview problems is barely connected to DP in reinforcement learning.
throwawaymath 8y ago
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.
- gaogao 8y ago
  At the FANG I'm at, DP is now heavily discouraged with a note that it was once a very common interview topic.
  - YorkshireSeason 8y ago
    What are you encouraged to do with the problems of recursion that DP addresses, stack overflow and overlapping instances?
mehrdadn 8y ago
DP is most definitely not in fashion because of reinforcement learning. It's been pretty standard since long before the ML buzz.

kccqzy 8y ago

In contrast, I find that the ability to formulate a problem using DP coorelates with whether a person is able to think in a mathematical way. In many dynamic programming problems you need to first define a function P(i,j) or some such, and then define it recursively; when proving the correctness, you use induction. The ability to grasp this recursion and induction is correlated with the level of abstract mathematical thinking a candidate is capable of. That said, if a candidate goes to LeetCode or some other site to practice all the DP problems, then it's possible that the candidate can only solve DP problems without gaining other abilities.

elteto 8y ago
Your two paragraphs are contradictory. 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. You should have said “the ability to solve DP problems is a good metric of the ability of a candidate to solve DP problems“. I would have agreed with you in that case :)
- smallnamespace 8y ago
  > 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.org/wiki/Signalling_theory https://en.wikipedia.org/wiki/Signalling_theory Also, if being able to learn completely arbitrary things is correlated with intelligence and correlated with job performance, then people who are willing to jump through that arbitrary hoop are telling you that 1) they think they're more capable (faster learners) than average 2) they're willing to put in the effort to prove it to you. Maybe you're not a getting a pure signal of mathematical ability, but some combination of drive + ability + learning fast, and you care about all three.
  - pmiller2 8y ago

chillee 8y ago

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.

mayank 8y ago
> On the other hand, there's rarely a DP problem (that comes up in interviews) that relies on a problem-specific trick. That's a pretty big parenthetical. DP problems as a class are full of clever tricks for elegant solutions that took decades of research. Any practical use of DP is almost certainly going to use problem-specific tricks as well. Which makes DP tricky, especially in interviews.
- chillee 8y ago
  Yes, there's a ton of DP problems that require clever tricks. I've had to show these tricks to friends who believed that DP problems were too formulaic. Could you give an example of DP problems that show up in interviews that require problem-specific tricks? I'm contrasting DP problems with other interview questions like: Find whether a linked list has a cycle in O(1) memory or implement a queue with 2 stacks.
akhilcacharya 8y ago
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.
- bogomipz 8y ago
  I'm familiar with 1D and 2D but what are some examples of Tree DP besides the standard Fibonacci questions?

hn_throwaway_99 8y ago

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-guide-to-interviewing-version-30/ 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."

alangpierce 8y ago
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-world situations are naturally recursive, and a good grasp of recursion helps build a strong intuition for many aspects of programming. DP (specifically designing recursion with overlapping subproblems) is a much more specific technique that I think isn't as beneficial for programming ability, though I certainly don't doubt that people who know DP well are often also good programmers.

mehrdadn 8y ago

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).

jogjayr 8y ago

> 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 going to struggle with unfamiliar types of problems. Unfortunately, I don't see a way out of this. 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. It's a good signal for ability to learn difficult things, which is a desirable quality in employees. This means that good programmers who don't know DP are forced to learn it or accept that they won't clear some interviews. Absent some other way to clearly signal technical ability, I think DP problems are here to stay.

groby_b 8y ago
> 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)
- brianberns 8y ago
  > 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?)

matz1 8y ago

The good thing of these type of question is it can be practiced, and it's pretty much "standard". Once you comfortable with it you can essentially interview anywhere.

closeparen 8y ago

>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?"

deepGem 8y ago

"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.

hhmc 8y ago
The etymology comes from the field of mathermatical optimization, not from programming as commonly understood today.
RJIb8RBYxzAMX9u 8y ago
> [...] 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 https://en.wikipedia.org/wiki/Mathematical_optimization
mafm 8y ago
> [...] I don't know why it is called Dynamic programming. According to Richard Bellman, who came up with the name: An interesting question is, Where did the name, dynamic programming, come from? The 1950s were not good years for mathematical research. We had a very interesting gentleman in Washington named Wilson. He was Secretary of Defense, and he actually had a pathological fear and hatred of the word research. [...] What title, what name, could I choose? In the first place I was interested in planning, in decision making, in thinking. But planning, is not a good word for various reasons. I decided therefore to use the word "programming" [...] it's impossible to use the word "dynamic" in a pejorative sense. Try thinking of some combination that will possibly give it a pejorative meaning. It's impossible. Thus, I thought dynamic programming was a good name. It was something not even a Congressman could object to.
- jonsen 8y ago
  Formatted for mobile: According to Richard Bellman, who came up with the name: An interesting question is, Where did the name, dynamic programming, come from? The 1950s were not good years for mathematical research. We had a very interesting gentleman in Washington named Wilson. He was Secretary of Defense, and he actually had a pathological fear and hatred of the word research. [...] What title, what name, could I choose? In the first place I was interested in planning, in decision making, in thinking. But planning, is not a good word for various reasons. I decided therefore to use the word "programming" [...] it's impossible to use the word "dynamic" in a pejorative sense. Try thinking of some combination that will possibly give it a pejorative meaning. It's impossible. Thus, I thought dynamic programming was a good name. It was something not even a Congressman could object to.

PopeDotNinja 8y ago

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?

Jach 8y ago
Talk is cheap, code is what matters. But maybe the interviewer wanted to save time not writing an incorrect solution if he believed your approach was wrong and you could talk yourself out of it? Did you get to step through how your solution would arrive at the number 14 given 2 eggs and 100 floors? And if you wrote it out, would it produce that number? (Personally I have no idea what you mean with the binary search approach, what is your logical list since doing it on the list of floors is wrong? But I've not thought about the egg dropping problem in a long time and have only seen the DP approach.) It might of course be that the interviewer only knew one way to solve it, any other way was therefore wrong. Or admitting they don't understand a demonstrated other way shows weakness, so is also wrong. I'd be perfectly happy to receive rejections from companies with those sort put in charge of interviewing.
- wizzairflyer 8y ago
  A funny trick is to ask this question but first give the candidate an infinite amount of eggs. Once he succeeds, ask the question with only 2 eggs. That might explain the binary search answer.

dnautics 8y ago

I asked a dp question in an interview. It was useful. Here's why. I know the solution, so I frequently guide the interviewee towards the correct answer and offer my help. Plus I put my nice guy hat on. I have seen a supposedly good candidate refuse my offers of help and then proceed to spaghetti code on the board a series of disjointed while loops that is obviously going to go nowhere. I don't want to work with such a person. They still got the job, because connections, but will 100% never be on my team.

nosianu 8y ago
An alternative point of view is that you set them up with an unsuitable question in the first place. Also, the disadvantage of stories such as yours is that we only hear one side. How did your "help" look like? We don't know. For my taste the brevity and content of your story indicates a lack of introspection. It seems to me that the only option you consider is that the interviewee gets all the blame. The reason for my suspicion is that independent of what happened there you should at least be aware that the story is not suitable to be shared in this form, because readers here only get your (very short too) story. Sure, you will get agreement - from people who jump to quick conclusions without actually having a basis for it. You are not even trying to give sufficient and/or unbiased information. I know this is just a forum and casual conversation, but to compare with science, which has the same issue of communicating one's ideas to other people, the equivalent would be a paper that only publishes the authors conclusions.
pavlov 8y ago
> "I know the solution, so I frequently guide the interviewee towards the correct answer and offer my help. Plus I put my nice guy hat on." I wouldn't want to work with a person whose idea of a useful job interview is: "I'll pick an esoteric bullshit problem, put my nice guy hat on, and guide you towards the solution as I bask in your admiration of my largesse." It's like when self-declared "nice guys" approach women: when you have to make an explicit point about how nice you are being right now, you're probably doing something very wrong.
- srean 8y ago

vishnugupta 8y ago

I interview regularly and I'm really keen to know if the person knows about time-space tradeoff. DP 'like' algorithms lend themselves well to evaluate this. Note that I say DP 'like' because I'm essentially looking for them to say memoization and implement it. And this doesn't really take a crazy DP optimization algorithm to evaluate this concept. And note that this time-space kind of tradeoff is something we indeed encounter regularly; e.g., caching (to avoid n/w call or computation), pre-computation etc., So the concept underlying DP is quite useful and it's premature to dismiss it as something that never comes up in the real world. That said, I understand that it's easy to push this and go down the path of more and more esoteric algorithms.

srean 8y ago

> And DP comes up almost never in the real world What a big load of rubbish and gratuitous generalization ! Just because it has not come up in your work or you may have passed opportunities to recognize its applicability at your work, does not qualify you in any way to make such a broad comment. DP has served me very well in each of the last three years in three different projects. In two of these projects I had joined the project midway. In every case the key was to recognize that DP applies where others had not and in doing so had left significant benefits on the table. In one case the 'others' was me myself. I had overlooked a potential application the first time. So much for "almost never in the real world" > candidates who haven't usually don't even have a chance at solving them The claim above sounds a lot like "If all the votes were counted then candidate B would have been elected". The whole point of an election is counting the votes. Is it such an unfair expectation that someone applying for a CS job ought to be familiar with one of its fundamental techniques ? If one is aiming for a commodity position, then perhaps yes.

alangpierce 8y ago
It does depend on the job, and I don't doubt that there exist jobs where DP in the interview process is reasonable, especially if it's a "CS job". I'm particularly talking about software engineering interviews, to be clear, not research positions or anything like that. Even in software engineering, I could imagine DP being important if the product relies heavily on high-quality string diffing, for example. I'm certainly interested to hear your real-world applications if you're able to share. I guess I have seen memoized DAG traversal come up, so in that sense I've seen DP, but it's not quite the same as "take this non-recursive-looking problem and make it recursive so you can memoize". Two situations come to mind when I think about DP being used in real-world applications (both just things I heard about): a talk I heard about how Google News compares news pages before and after the publisher makes an HTML change, and DNA sequence alignment problem. Both of them went like this: 1.) We want to find a perfect solution, but the search space is exponential size. 2.) Hey look, by using dynamic programming we can reduce the complexity to n^2 time and space. 3.) Wait, n^2 time/space is still too inefficient for many real-world use cases. Rather than trying to find a perfect solution, let's settle for a good enough solution by rethinking the approach and applying some heuristics. By putting some clever thought into it and sacrificing a little bit of quality, we can get something that takes O(n) time in practice. So I think an initial goal of looking through an exponential search space for an optimal solution (often what DP is solving) is often misguided anyway, since often "optimal" isn't actually so important.