Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Dynamic Programming for Technical Interviews

blogarithms.github.io

Post reply on HN
Print view View original

121–130 of 225 posts

Re: Dynamic Programming for Technical Interviews

#121

Post by collyw »

01100011 wrote: post #96
deepGem wrote: post #75

Earlier quoted context omitted.

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

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…

If you really do need to know that stuff, you can read up on it when it's needed. Been programming professionally for over 15 years and have had to use this stuff once that i can remember. Knowing how to design and index a database well is way more useful.

Re: Dynamic Programming for Technical Interviews

#122

Post by vishnugupta »

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

Re: Dynamic Programming for Technical Interviews

#123

Post by jonsen »

stan_rogers wrote: post #118
matt-snider wrote: post #114

Earlier quoted context omitted.

Thanks :-). This comes up so often! Is there a reason HN doesn't use a more mobile-friendly format for preformatted text?

The feature is intended for code, note block quotes. Auto line wraps would be less than helpful.

Problem is when some text copied and pasted here incidentally starts paragraphs with two or more spaces. And maybe the the commenter does not know why it formats weirdly.

Re: Dynamic Programming for Technical Interviews

#125

Post by lawn »

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…

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 had many glaring problems.

It wasn't only during competitions either, he used the same style for assignments. Turns out he got shafted by the assistants and then he copied answers from another student (yes he got caught).

Re: Dynamic Programming for Technical Interviews

#126

Post by mlthoughts2018 »

I never much enjoyed dynamic programming and I do think it’s a poor choice for timed interview questions, but I did become more interested in it when I realized there are patterns to the cache strategies that can be used to group problems. For example like the usual matrix raster fill approach for e.g. 0-1 knapsack, or sepatately using two cursors to fill the upper triangle of a matrix like for longest common subsequence and for optimal order of associative computation (like matrix multiplication).

Re: Dynamic Programming for Technical Interviews

#128

Post by JustSomeNobody »

nosianu wrote: post #104
jogjayr wrote: post #83

Earlier quoted context omitted.

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

> It's pretty hard to get someone solving actual problems in a single day. Do you have some examples of how this might be done? Solve a small problem - of which millions can be found in issue trackers. Here is an example I just read on Github: Somebody reports that reading a JSON file results in a value that clearly is an integer being misidentified as "Not an integer". The source code is a parser written in C and th…

I think this would be great. It would give me, the interviewee, a chance to feel out how it is to work with the person interviewing me. Will they crap on every solution I propose? Or will we have some back and forth and find a solution that suits us both?

Also, you don't have the added stress of writing all the code from scratch, having to whiteboard recall boilerplate that a good IDE handles for you.

Re: Dynamic Programming for Technical Interviews

#129

Post by w8rbt »

01100011 wrote: post #96
deepGem wrote: post #75

Earlier quoted context omitted.

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

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…

When n is guaranteed to be very small it does not matter. Even an exponential solution would be fine in these cases. The 'algo nerd' on your team ought to know this.

Re: Dynamic Programming for Technical Interviews

#130

Post by JustSomeNobody »

reallydontask wrote: post #109
solveit wrote: post #106

Earlier quoted context omitted.

> It would be good if the problem is unsolved and the interviewer him-/herself does not know the answer. I think one-use questions like this must be are bad. It makes it harder to compare candidates, which is what you really want in an interview.

you can also think about them another way, namely: How long it took somebody else in your team to solve the same problem Making allowances for interview conditions, namely high stress levels, etc ... Not perfect but an idea worth exploring. I speak as a former smug interviewer that while didn't ask DP questions, did have a set of favourite questions

> How long it took somebody else in your team to solve the same problem

I don't think that is a good measure. I know many developers who want to solve everything fast because fast is productive in their eyes. The problem is they end up having a bug or three and spend some back and forth time with QA. So, now they didn't actually solve the problem fast and they wasted QAs time. I prefer to get a more holistic understanding of the code before fixing the issue and not get any bugs back from QA. In retro, when the QA tells the team how many bugs there were, I am proud when I'm not a part of that count.

Post reply on HN