31 ms·
A systematic approach like this or others (Gayle Laakmann Macdowell’s BUD) seem to reduce the risk of underperforming, but I haven’t had success with it. Instea
by reyg 9y ago
A systematic approach like this or others (Gayle Laakmann Macdowell’s BUD) seem to reduce the risk of underperforming, but I haven’t had success with it. Instead, problem identification has been most helpful to me.
The approaches for solving Dynamic Programming problems are different than those that require a fundamental data structure (like a heap). Recognizing the heart of the problem is harder, probably what the interviewer is really testing for, and in my opinion differentiates oneself better than following a step by step guide.
- suyash 9y agoCare to elaborate how do you go about problem identification?
- reyg 9y agoHm, here is an example: // 1. Explore the possibility of a recurrence relation. If the problem can be solved as a function of sub problems, then candidate techniques are DP, backtracking, greedy, and divide/conquer // 1a. Explore DP. If it’s DP, then optimal solutions of its subproblems are all that’s necessary. Confirm that subproblems are repeated so that I can reason for memoization and later leave room for a bottom up implementation. // 1b. Explore backtracking. If it’s a backtracking problem, then I should be able to test for the viability of a partial solution quickly. ...and so on
- abhirag 9y agoI think your example can be simplified :) Recursion + memoization provides most of the benefits of dynamic programming, including usually the same running time and well backtracking is recursion so the strategy can very well be -- Explore the possibility of a recurrence relation, if the possibility exists, try recursion :D
- thaumasiotes 9y agoSolve problems. Hopefully, after solving a problem several times, you'll be able to recognize it.
- dvirsky 9y agoThis. I tanked an interview once because the problem was phrased in a way that it wasn't apparent to me that it's basically a graph. Once I realised that it was also clear why a simple BFS would solve that problem. Sadly this happened just as the interview was over. I think I sort of blacked out because I couldn't identify the underlying problem, and my mind "unlocked" the moment that the stress of the interview ended. Which reminds me - another important thing is not to get stressed if the solution is not apparent immediately.