This is poorly written. I was hoping hacker news would have better scrutiny on articles.
Dynamic Programming for Technical Interviews
201–210 of 225 posts
Re: Dynamic Programming for Technical Interviews
#202Earlier 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've seen a few interviews in my time. On the order of 5k of them) Sorry, your "5k" doesn't pass the smell test, unless you can give some convincing reason why 20 years of one interview per day would be believable. So, I'm calling BS. You just seem bitter about interviews that you don't like and are trying to con people into giving your opinion more weight than that of others. Besides, if other companies are doing…
If you interview at a traditional tech company, you go through 5-8 interviews in a day. If somebody were to review, say, around 4 of these packets every week, they see about 20-30 interviews every week. That's ~1000-1500 a year. The 5K mark comes faster than you think.
And if you work at a company that size, changing the interview process is a bit more work than "oh, we just won't do that".
Not everybody works at a small startup.
Re: Dynamic Programming for Technical Interviews
#203Earlier 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've seen a few interviews in my time. On the order of 5k of them) That's actually pretty cool. May I ask how? > Because "knows DP" is pretty much the only bit of information you get Yes if the candidate meets with only one interviewer or if every interviewer asks only DP. I hope most companies don't interview that way - that would truly be a broken interview process. Obviously you ask about other stuff in the othe…
See another comment above for explanation how I got to that count. (In essence: reviewing lots of interviews)
> Do you have some examples of how this might be done?
I do :)
We did it at a previous company. We brought in several candidates at the same time, declared them a team, and gave them a half-finished video game (since it was a games company). With the goal of turning it into a better game by the end of the day. We also embedded one employee with that team for the whole day, and other reviewers would drift in and out, observe how people worked together.
The key components there: * Some groundwork is already done, you pick up an existing project. (Also tests a really important skill - reading and understanding code) * You work in a team - more output, and tests for your ability to work in a team. * You have a source of experience that can answer all your questions around tooling and libraries, and you can lean on them to get some of the hairier stuff done. (Also tests if you're willing to let go of the desire to show off to instead make things happen for the team)
And yes, we'd hire the whole "team" of around three people if they were all good, and we'd pass on everybody if they were all bad, and everything in between.
It worked pretty well, gave really good results, and both interviewers and interviewees enjoyed the process. It's also something you can't really learn by rote in advance, because you do what you'd be doing every day anyways.
Re: Dynamic Programming for Technical Interviews
#204Earlier 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…
> 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 associa…
Thankfully not 2.5 work years. See above for explanation. Probably around 0.5 work years, smeared over almost a decade.
And no, not an actual business problem, a constructed problem. But in the same domain. (See other comment above)
Re: Dynamic Programming for Technical Interviews
#205> 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 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…
> ... the correct answer.
The?
We're talking about programming, so I am rather stumped by that word.
But I suppose if your goal is to select only candidates that you can drive towards a particular solution, then "the" might be appropriate.
Re: Dynamic Programming for Technical Interviews
#206Earlier quoted context omitted.
That just has a straightforward recursive solution. I’m not even sure where the DP comes in beyond that.
What's your straightforward recursive solution? It might be what's considered Tree DP. If you want a harder problem I can give an example too :^)
Might you have some good resources you could share then on DP strategies and problem solving? Cheers.
Re: Dynamic Programming for Technical Interviews
#207So, in all of these examples, the author basically makes a set of all possible solution into a tree (where moving from ancestor to child is that tree correlates to making a possible decision) and then recursively traverses this tree to find the best option?
Re: Dynamic Programming for Technical Interviews
#208Earlier quoted context omitted.
What's your straightforward recursive solution? It might be what's considered Tree DP. If you want a harder problem I can give an example too :^)
Might you have some good resources you could share then on DP strategies and problem solving? Cheers.
I did make some slides here for my university's ICPC seminar: http://www.cs.cornell.edu/courses/cs5199/2019sp/
https://docs.google.com/presentation/d/1c1YUdhXOCLSVhH6Jn4TB...
It's partially targeted for competitive programming, though, so be warned that things like Tree DP/subset DP/convex hull optimization will likely not show up in interview questions (although they are pretty cool!)
Re: Dynamic Programming for Technical Interviews
#209Earlier quoted context omitted.
> [...] 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. […
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 c…
Thanks. (I have now looked up the correct way to quote).
Re: Dynamic Programming for Technical Interviews
#210Earlier quoted context omitted.
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. Any work in any kind of scale setting has to implicitly deal with this. You might not realize it immediately, but if you are dealing with a network of 100k+ nodes, or some database with 10M+ entries, or anything of that sort, there is a huge difference betwe…
> Any work in any kind of scale setting has to implicitly deal with this.
Obviously. And most experienced engineers know this. But a lot of us never deal with n > 10k or so. I've worked a lot in embedded, and even when n is large, it's usually just moving around a payload. Even when I've dealt with n>>10k, say writing a network server, I've rarely been concerned with complexity. I focus on doing the minimum amount of work possible. It's basically the same thing, without the academic formalism. The main rule of engineering seems to be "don't do stupid things()."
- except when it doesn't matter.