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

Solving dynamic programming interview problems

blog.refdash.com

Post reply on HN
Print view View original

51–60 of 176 posts

Re: Solving dynamic programming interview problems

#51

Post by mikert5671 »

sbov wrote: post #22
yanslookup wrote: post #21

Earlier quoted context omitted.

Does the company you are at now pay developers the same as the companies that ask these types of questions? In my experience the companies asking these types of questions are picky because they can be.

They aren't picky because they can be. If that were true they wouldn't be complaining about the lack of qualified developers (pretty much every tech company I know of). Rather, they're picky because they (think they) need to be. Note that I'm not judging whether they are right or not.

false. I know hoards of engineers working on boring code at google

Re: Solving dynamic programming interview problems

#52

Post by alexandercrohde »

yanslookup wrote: post #21
nilkn wrote: post #17

Potentially interesting data point: the company I'm at right now has been pretty successful for over a decade and has, to my knowledge, never once asked a dynamic programming question in an interview for any candidate in that entire time. We've managed to hire a lot of great developers and have very rarely had any real issues.

Does the company you are at now pay developers the same as the companies that ask these types of questions? In my experience the companies asking these types of questions are picky because they can be.

I'd break that down like this:

Google-esque companies figure "Let's just ask these hard puzzles to filter by IQ, everything practical (e.g. databases) can be learned"

However, some companies tend not to see these specialized puzzles as an IQ test, but rather a memorization-based learned skill (learn these 10 algorithms and their performance metrics). To them, asking questions that represent day-to-day job challenges is a better predictor.

Re: Solving dynamic programming interview problems

#55

Post by blackflame7000 »

danmg wrote: post #44
blackflame7000 wrote: post #41

Earlier quoted context omitted.

Experience, tells me so. To be fair some items like Fibonacci numbers are probably equally as clear.

Divide an conquer type algorithms usually lend themselves to naive recursive solutions more often than not. DP usually requires you to find that solution and find some clever relationships that allow you to build up the final solution from the bottom up.

Sure there are some problems that lend themselves nicely I already said as much. But in general for an INTERVIEW problem, it as a poor skill to dwell on or even bother testing for since real-world coding is simply not done that way or God forbid what might happen when someone not as capable (but cheaper or younger) has to take over your code base.

Re: Solving dynamic programming interview problems

#56

Post by akhilcacharya »

kizer wrote: post #12

Step 1. ur problem graph better be a dag Step 2. ur sub problems better overlap Step 3. time to table dat dag Step 4. solve ur problems and build ur table graph the way a dag would : to-po-lo-gi-cal-ly

I think the DAG approach is a good one, but the problem is its not great for being applied generally. For me, it's difficult to think of something like the "House Robber" problem as a DAG.

Re: Solving dynamic programming interview problems

#57

Post by pansinghkoder »

otasevic wrote: post #7
pansinghkoder wrote: post #4

Earlier quoted context omitted.

with all due respect to author, here's why solving real problems > interview problems

I agree. This blog is hosted separately from our servers so I went for a quick deployment of WP on google cloud. Learning: do not use google cloud VM micro instance, apparently it cannot support even moderate traffic.

Double thumbs up for fixing this!

Re: Solving dynamic programming interview problems

#58

Post by akhilcacharya »

yanslookup wrote: post #49
nilkn wrote: post #24

Earlier quoted context omitted.

We pay very well for the area. We are not in Silicon Valley, but I know some of our salaries are higher than those of my friends who are at Google's MV campus.

Interesting. What industry if you don't want to name names? Total comp at Google for a "senior" (8-12 years experience) is $300k-$400k. Rare to hear about a non SV darling paying developers that much.

Don't want to speak for OP but it's highly possible he or she doesn't know how much Google-tier companies pay nowadays!

Re: Solving dynamic programming interview problems

#59

Post by extesy »

nilkn wrote: post #24
yanslookup wrote: post #21

Earlier quoted context omitted.

Does the company you are at now pay developers the same as the companies that ask these types of questions? In my experience the companies asking these types of questions are picky because they can be.

We pay very well for the area. We are not in Silicon Valley, but I know some of our salaries are higher than those of my friends who are at Google's MV campus.

Can you share your company name?

Re: Solving dynamic programming interview problems

#60

Post by jacquesm »

blackflame7000 wrote: post #37
btilly wrote: post #34

Speaking as someone who finds DP problems easy, I'd not figure it out from this approach. The way that I'd think about and tackle it in an interview is this: 1. Write a recursive solution. 2. Memoize. If you can solve it this way, then you have a DP problem. Of course this forces you into the top down (aka recursive) approach. But in an interview, "easier to reason about" is all that matters. Also the tradeoffs in se…

Is recursion really worth the loss of clarity? Almost always no. The more clever you are in your code, the less likely anyone will ever see it (or want to).

Recursion is usually clearer that iterative because it assigns names to the work being done. I find that much easier to read. Better yet: when you can state your cases separately. That's even more readable.
Post reply on HN