>"I'll show you how to do DP"
Hey it's the same 3 example problems that are in every textbook, GeeksforGeeks, Leetcode, etc.
Dynamic Programming for Technical Interviews
131–140 of 225 posts
Re: Dynamic Programming for Technical Interviews
#132> 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,…
Come on, pointers are easy. In a 45 min interview you could teach someone pointers and still leave time to solve the problem.
DP is much less easy to understand unless one has purposefully studied and solved a lot of DP problems.
I agree with a lot of comments here. Interviewing for DP only nets you people who have studied DP.
Re: Dynamic Programming for Technical Interviews
#133In 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'
Re: Dynamic Programming for Technical Interviews
#134> 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 not like DP is the only way to solve problems even designed for a DP solution. So an interviewee might have a general technique that applies for most problems but when faced with a DP problem their method takes more time. Now in an interview, taking more time is generally bad and this candidate would be judged lower. However, in real life scenarios, since DP problems are so rare, the interviewee's method might actually be faster.
Basically, giving any test question that is dependent on someone knowing something they could look up in a book is not as effective as testing how well someone reasons about an unknown type of problem.
Re: Dynamic Programming for Technical Interviews
#135This is a comment to demonstrate the differences between DP and memoized recursion to people in the sibling comments. When I was learning DP vs Memoization I thought Floyd-Washall algorithm to find shortest path length between all pairs of nodes in a graph is a good example of DP that wouldn't work the same way with memoization. In FW algorithm, because of the order of filling up the table and discarding old values o…
That is interesting but I still don't totally get how DP is different from simple memoization.
Your fib example can be expressed as corecursion, and in fact, its an example often used to explain it.
val fibsViaUnfold =
unfold((res0, res1)) { case (f0, f1) => Some((f0, (f1, f0 + f1))) }
fibsViaUnfold.take(7).toList shouldBe List(0, 1, 1, 2, 3, 5, 8)
Here is a python version from wikipedia
def nth_factorial(k):
n, f = 0, 1
while n Re: Dynamic Programming for Technical Interviews
#136Earlier quoted context omitted.
> 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 was in a team with a very talented competitive programmer guy. He came up with solutions for some pretty tough problems I couldn't wrap my head around. Fantastic programmer right? The other 99% except hardcore algorithmic optimizations, like structuring code, creating simple code, naming variables, splitting code into classes/functions and refactoring? No clue about any of that. All he produced was "read-only" and…
At my first company, there was this one file in the solution that we called DaVinci.cpp because it was over 20000 lines long and written by one developer who had long since retired. The thing is, the code was complex and worked so no one ever refactored it.
Re: Dynamic Programming for Technical Interviews
#137> 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,…
> 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.
That's the first day, surely? That's how I remember it. You're not going to wait with explaining pointers, right?
And I don't think anyone didn't get it, despite being Engineering students rather than CS students.
It just seems like a huge exaggeration to me.
Re: Dynamic Programming for Technical Interviews
#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 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.
Re: Dynamic Programming for Technical Interviews
#139Earlier 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,…
> 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 happening. Joel is a bit pompous, that's true, but there definitely are people who cannot understand pointers when taught in a normal CS course, and if 4 years of university didn't teach them pointers I don't think they'll get them while programming in the field.
As an aside, the fact that some people can't grok some things shouldn't be controversial. I myself can't understand lots of things and probably would never understand them in the way that people who grok them instantly do. People have different modes of thinking, and I do not doubt that there exist people who cannot grasp pointers and recursion in the same intuitive way that I do. That doesn't make them less smart in general, but it does mean they're a bad fit for e.g. a C programmer position.
Re: Dynamic Programming for Technical Interviews
#140Earlier quoted context omitted.
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…
> "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…
I think its a win win. They get to pick someone who is more suited to their needs (problem solving that needs some algorithms thinking) and you get to work at a place where things are more rote.