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

101–110 of 176 posts

Re: Solving dynamic programming interview problems

#101

Post by jacquesm »

blackflame7000 wrote: post #98
throwaway37585 wrote: post #94

Earlier quoted context omitted.

> Whats complicated about an iteration What’s complicated about a recursion? > If you see problems, its because something is modifying it between runs, but that wasn't a fault of the iterative strategy, it was the fault of a bad programmer. > Conversely, you must always make sure the stopping condition and all base cases are met during recursion. You seem to be applying a double standard here. > Forget one corner bas…

Then why does NASA consider it unsafe for mission critical code? How about unknown potential stack size? How about factoring a large number with recursion? Everything recursive can be transformed to iterative and yea sometimes it’s not as sexy but neither is a helmet https://www.reddit.com/r/programming/comments/3dnsh1/nasas_t...

That's a restriction on the environment which has absolutely nothing to do with how readable a certain piece of code is. In fact it argues the opposite: we force you to use a less readable version of your code because the elegant one may be easier to read but it may have negative consequences due to implementation details.

That's a really good trade-off for them but it does not necessarily help readability.

Re: Solving dynamic programming interview problems

#102

Post by mirceal »

dub wrote: post #84

I have a fantasy. In the fantasy, an interview candidate says "this problem has an optimal substructure" or "this problem can be broken into overlapping subproblems" and then observes "reusing the results of overlapping subproblems to avoid re-computing them is sometimes called dynamic programming" At this point, balloons and confetti fall from the ceiling as Donald Knuth jumps out from under the table to hand the ca…

You know you’ve made it when you have Knuth on standby under the table

Re: Solving dynamic programming interview problems

#103

Post by simtel20 »

akhilcacharya wrote: post #58
yanslookup wrote: post #49

Earlier quoted context omitted.

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!

And some boutique finance firms are made of money.

Re: Solving dynamic programming interview problems

#104

Post by rajeshpant »

rsp1984 wrote: post #79

I've done a fair amount of interviews in my professional career, both as an engineer at Google as well as for my own startup. In an eng. interview you want to maximize information divided by time, i.e. you want to learn as much as possible about whether the candidate would be a good fit for the company and spend as little time as possible doing so (because you have other things to do -- such as interviewing more cand…

Also, it depends on the interviewer. I have been on both sides of the table and I can tell that as an interviewer you need to convey these type of questions very clearly. A interview is typically 45 minutes in most companies, where about 5-10 minutes are wasted in introduction etc. You have about 35 minutes and if you waste 15-20 minutes explaining a problem to the candidate and in the end leave the candidate with 15-20 minutes to solve a dynamic programming question, then it is very unfair on your part.

Most companies in bay area have 3-4 whiteboard interview rounds and I have experienced at least 1 interview, at every place I interviewed(FANG and other top bay area tech companies), where the interviewer wasted enough time either explaining the problem.

As an interviewer, it is really important to keep the time aspect in mind and choose a problem which could be easily explained. The problem itself could be hard, but story based problems waste candidate's time and have little value in assessing the ability of the candidate.

PS: I interviewed at one of the tech companies(the one you all know and I won't name), and in one of the technical rounds, it took the interviewer 20 minutes explaining the problem. The problem basically boiled down to finding largest number at any time in a given sequence without sorting the array. The problem had a background story of some cell towers where each tower had a strength and blah blah. The interviewer was also had communication issues.

Re: Solving dynamic programming interview problems

#105

Post by rajeshpant »

dub wrote: post #84

I have a fantasy. In the fantasy, an interview candidate says "this problem has an optimal substructure" or "this problem can be broken into overlapping subproblems" and then observes "reusing the results of overlapping subproblems to avoid re-computing them is sometimes called dynamic programming" At this point, balloons and confetti fall from the ceiling as Donald Knuth jumps out from under the table to hand the ca…

does knuth also come and kick the guy out, if he fails to solve it?

Re: Solving dynamic programming interview problems

#106

Post by sumeno »

hinkley wrote: post #27
2bitencryption wrote: post #8

I recently had a programming interview where, at the whiteboard question, I said "this may be a dynamic programming question, let me see--" and the interviewer said "STOP! Stop, every time someone says that, they end up flopping and never getting anywhere. Don't go down that path, I'm telling you." I think it had more to do with the interviewer being a poor interviewer, however.

I got screwed like that on my Google interview. You should not be blamed for assuming, when talking to Google, that the O(n!) or O(n^2) solution is not even worth talking about. So I flopped around on O(n), O(nm) and O(nlogn) solutions after trying to whiteboard a recurrence relationship and giving up on O(1). Interviewer had already decided that somehow the crazy rules I related to him about the industry I was comin…

> You should not be blamed for assuming, when talking to Google, that the O(n!) or O(n^2) solution is not even worth talking about.

If the naive solution is O(n!) then describing an O(n^2) solution is perfectly acceptable.

Re: Solving dynamic programming interview problems

#107

Post by otasevic »

bajsejohannes wrote: post #93

A tiny correction in the following: if (position + adjustedSpeed in memo and adjustedSpeed in memo[position + adjustedSpeed] and adjustedSpeed in memo[position + adjustedSpeed]): The middle line is not needed.

Thanks! Corrected it now to remove the duplicate line.

Re: Solving dynamic programming interview problems

#108

Post by et-al »

akhilcacharya wrote: post #56
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.

Can someone explain what DAG stands for? Thanks.

Re: Solving dynamic programming interview problems

#109

Post by jensv »

et-al wrote: post #108
akhilcacharya wrote: post #56

Earlier quoted context omitted.

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.

Can someone explain what DAG stands for? Thanks.

https://en.wikipedia.org/wiki/Directed_acyclic_graph

Re: Solving dynamic programming interview problems

#110

Post by steelframe »

curiousDog wrote: post #96

Unpopular opinion, but the best way to prepare for DP problems is to solve the well known ones and memorize them and their recurrences. Only 2-3 companies like FB and Goog ask them (well they’re the only ones worth studying DP for anyway). Coming up with a recurrence on the spot is very hard. The edit-distance paper was an award winning ACM paper and expecting someone who has never seen that before to code it up (eve…

The best way to perform well in an interview is to have seen and worked on the problem at some point beforehand.

When I got a job at Google (in a previous life), two of the questions in my interview loop were ones that I had seen in previous interviews. I kept my mouth shut about that and faked brilliance in the moment. That is, I pretended to be stumped for a second, then I created a narrative where I had a sequence of 2 or 3 "Ah-ha!" moments where I figured out how to refine my solution.

I cued off the interviewer, waiting until they seemed just about to blurt out a hint, when I raised my hand and said, "WAIT! Maaaybe.... I can use a BFS instead of a DFS here and label the cells!" Then the interviewer would usually smile and nod in satisfaction.

Finally, I "stumbled on" the "right answer" and slammed out the code that I had pretty much memorized up to that point.

Make a stupid game, I'll play the stupid game, and have fun doing it.

For the record, I kicked ass at Google (getting promoted twice) before moving on to greener pastures.

Post reply on HN