Live data from Hacker News

Dynamic Programming for Technical Interviews

blogarithms.github.io

161–170 of 225 posts

Re: Dynamic Programming for Technical Interviews

#161
post #148
post #144

Earlier quoted context omitted.

Do you think that "I'll put my nice hat on and guide you to the solution, if I feel like it" is an optimal way to measure "problem solving that needs some algorithms thinking"?

Well, of course one can be a dick about it, but nothing in the parent post indicated that he was. May be you had a bad experience in the past and projecting it on the author of the comment. I tend to / try to assume good faith. Picking up loosely specified directions and filling up the gaps is indeed an important skill to have. If I had the time to describe the solution in the minutest detail to a co-worker, I would…

A whiteboard DP puzzle is totally different from any real-world engineering situation of “picking up loosely specified directions and filling up the gaps.”

No point in arguing this further. These tests are fundamentally just a performative power trip masquerading as objective measurement — the perfect storm of software engineer bias.

Re: Dynamic Programming for Technical Interviews

#162

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

I don't know what version of the problem you solved, but generally you are limited by the number of eggs you are allowed to use. Say you have a hundred floors and 1 egg, binary search would drop an egg from the 50th floor, have it break (assuming the key floor was <50), and then promptly fail.

Re: Dynamic Programming for Technical Interviews

#163
post #161
post #148

Earlier quoted context omitted.

Well, of course one can be a dick about it, but nothing in the parent post indicated that he was. May be you had a bad experience in the past and projecting it on the author of the comment. I tend to / try to assume good faith. Picking up loosely specified directions and filling up the gaps is indeed an important skill to have. If I had the time to describe the solution in the minutest detail to a co-worker, I would…

A whiteboard DP puzzle is totally different from any real-world engineering situation of “picking up loosely specified directions and filling up the gaps.” No point in arguing this further. These tests are fundamentally just a performative power trip masquerading as objective measurement — the perfect storm of software engineer bias.

I think you are projecting your own biases here. OP said "DP question", there is no mention of a 'puzzle' anywhere. As I said in another comment of mine on this page, I have had to use DP in each of my last three years in real projects. If i were to hire someone for help with these, I would definitely be looking for comfort with DP styled thinking in a candidate. In order to do so I do have to simplify and abstract out the problem statement.

Re: Dynamic Programming for Technical Interviews

#164
post #138

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

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.

Re: Dynamic Programming for Technical Interviews

#165
post #74
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.

My last interview was structured like this. Remote. Able to work on it outside of work hours (so no missed office days). Tracked a shared repo. Was paid a retainer up front for n hours worked on the task at an agreed-upon hourly rate.

Needless to say it was a great experience.

I've also had interviews in the past where the interviewer didn't have the correct answer to a question they asked me, and just got confused when I tried to explain my answer more fully. In the end they said I was incorrect, due to their incorrect answer (that they must have taken down from another source). I didn't get that job. Probably for the best.

There are also some people who just shouldn't be interviewing others. They just don't have the emotional intelligence to manage the situation.

Re: Dynamic Programming for Technical Interviews

#166

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

Your reference to Joel and how you rely so much on your intuition tells me that you tend to have "I'm better than other" type of feeling just because you understand DP. This is the exact toxic I would want to avoid in the workplace. Same with Joel's reference, I'm shocked that he thinks understanding pointers is not a skill (may be I should interview him on pointer arithmetic and see just how good he is). My experience has been that these interviewers who say they are so good in DP, pointers, recursion and throw this aura of 'false negative' and know it all show true colors after the interview. They make wrong decisions on when to optimize, are clueless about scale and distributed systems, can't write complex sql, just don't know how to turn on little knobs to solve the problem so write huge unnecessary code. All this is probably because they never thought more than DP/recursion (which I would avoid at any cost in my code base).

Re: Dynamic Programming for Technical Interviews

#167
post #138

Earlier quoted context omitted.

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

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

Appreciate this more nuanced take. I think 'software engineering" job and "CS job" arent quite complementary. I do disagree that 'optimal' is often unimportant. It does matters a great deal when it matters, especially if that is the core of the project.

Dont know how much I can talk about the problems. One of them was definitely a string related problem but not about string diffing. The other two were on optimizing cost over all possible partitioning of a set (different kinds of sets in the different projects) -- hence my embarrassment at not having noted the same structure in the two different problems right away. It was one of those moments, "Wait a minute. I am doing this wrong. The sets are different but in an abstract sense I am doing the same thing in the other project over a different set".

Without DP it would have been very hard to come close to the optimal solution by local explorations unless one got lucky and started of by looking around a promising place in the search space.

I am sure DP can be put to some use when trying to optimize the placing of VMs on hosts. If done well the savings in dollars can easily hit 6 figures or more. These are real problems with real money at stake.

Re: Dynamic Programming for Technical Interviews

#168
post #131

>"I'll show you how to do DP" Hey it's the same 3 example problems that are in every textbook, GeeksforGeeks, Leetcode, etc.

Thanks for taking the time to read my post. :) Like I mentioned, this article only lays the groundwork. The next article I intend to write on is DP+Strings (for example, finding the longest substring of a string which is a subsequence of another, etc)

I'm starting with classical problems and I'll soon diverge into non-classical problems, as I've mentioned in my article too.

In any case, hope my other articles on my blog added more value to you in comparison!

Re: Dynamic Programming for Technical Interviews

#169

In the knapsack example they say... > "No global variables should be modifed in the function" Am I wrong or does the author immediately go on to modify the global variable 'dp' p.s. @author typo in that sentence 'modifed'

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! :)

Re: Dynamic Programming for Technical Interviews

#170
post #139

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…

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

Have you thought about may be you don't understand pointers and just think you do ? May be you should not start teaching and explaining about pointers before you understand it well. If you can't pin-point why your students don't understand and just say they won't understand at all (may be weak math background or something else), then I'm sorry you lack the knowledge to teach or use pointers.

Post reply on HN