What I've learned from 100s of interviews with candidates at top tech companies

Re:What I've learned from 100s of interviews with candidates... by drenvuk on Wednesday May 24, 2017 @04:07PM (#14413027)

I have a question about the dynamic programming bit. These questions do not seem intuitive unless its one of the simple ones like, add or multiply the two previous values in the memo (fibonacci) or just check the min or max of the value and modify regarding that. Those patterns can sometimes be easy to spot.

The more difficult ones feel like you absolutely have to have seen the problem before because there is complex relationship between the sub problems that are used to solve by induction/bottom up. How is someone supposed to solve these? Throwing out tons of guesses at the start feels like it'll still end up with me getting shown out before lunch time.

Recursion and memoization is easy but dynamic programming doesn't really feel as natural. Ways to get better? Just do more?

[ Parent | on HN ]

Re:What I've learned from 100s of interviews with candidates... by sanjoy_das on Wednesday May 24, 2017 @04:44PM (#14413305)

> Recursion and memoization is easy but dynamic programming doesn't really feel as natural. Ways to get better? Just do more?

Once you have the recursive solution, the DP solution should be fairly easy. Draw out the recursion tree for an example (or do it more generally), convert it to a DAG by combining redundant nodes, and then do a topological sort. That topological sort is the order in which you need to solve the subproblems to get a DP solution.

[ Parent | on HN ]

Re:What I've learned from 100s of interviews with candidates... by samuraijack on Thursday May 25, 2017 @04:13PM (#14419798)

Thanks! That is quite intuitive.

[ Parent | on HN ]

Re:What I've learned from 100s of interviews with candidates... by gaylemcd on Wednesday May 24, 2017 @06:09PM (#14413866)

Basically, yes, do more.

If you want to flip a memoization problem into bottom-up dynamic programming: 1. Make sure you really understand the memoization approach 2. Look at the base cases. What are the very last things the recursive approach does? 3. Build up the next case from the base case. 4. Repeat

[ Parent | on HN ]