I have been looking at Dynamic Programming for interviews recently. I used to be decent in solving these problems back in the day, but even then it would take me couple of hours to come up with a solution that works. However, more I read on blind, Dynamic Programming is a norm now and you are expected to have a flawless solution in a 30-45 minute interview. Unless I have seen the problem or similar problem before or its stroke of luck, its not possible for me to come up with a flawless code in 45 minutes that too on a while board where I have to execute the logic in mind under stress. How do you prepare for this? I read few posts where people said its easy and its just recursion with memonization. I know that but then there are problems that need somethinking and building the table. It takes time to find the flawless recursive solution.( considering edge cases) TC: 160k
Just practice. As for ingraining the ideas in your head I found this post pretty helpful, at least as a starting point: https://reddit.com/r/cscareerquestions/comments/c6t7a0/_/esb5dq9/?context=1
Thanks!
Solving DP isn't reasoning or logic or practice or science. It's an ancient form of discovery. It's called revelation. U either just get it or u don't. Other option is to read the Bible.
That's the plan when I am done with the rat race.
Rats are above such races. Now they just drag pizza through stairs.
This won't always work, but one way would be to see if the problem can be solved recursively. Once you implement a recursive solution, see if you can memoize to prevent solving the same subproblem multiple times. And voila! Call it DP and be done with it. Again, this isn't applicable every time.
Yes I understand it and works mostly for simple problems. My point is even coming up with a recursive solution to hard problems takes some time. Then you have to find a way to save the sub problem solution in such a way you can build upon it as you expand your solution space. It can be eventually solved ... but it’s hard for me to at least go get yo a flawless execution in 20-45 minutes. I have worked in ASR in the past and we have been using dynamic programming to find solutions . It coding those solutions took way more than 45 minutes too using computer to validate if your sub problem is actually framed correctly.
http://jeffe.cs.illinois.edu/teaching/algorithms/ there is a free book that explains general approach well. Though I can find a top-down solution with memoization, but converting it to a bottom-up solution still takes a long.
Agree! It does and sometimes it comes naturally and sometimes it does not!
Honestly have noticed a lot of companies have stopped asking DP heavy questions recently (even the big ones). Backtracking, Map interface questions, trees, and interval questions have been fairly popular.
Trees. Trees everywhere
DP is not hard once you master it. To master it, simply solve many problems on LC. Regardless, I agree with the premise that they are stupid to ask in an interview setting. They are yet another way for Google to give its employees a fake sense of superiority when they interview people. As a consequence, all the rest of the industry which wants to be as cool as Google copycat this interview style and it's useless questions. I wouldn't invest too much time in it unless you covered all the rest of the material and have spare time. If for some reason you get an interviewer that asks you a DP question, simply remind yourself that he most likely suffers from erectile dysfunction Seeing you agonizing over the problem in the interview, is the only way he can reach an erection. Most likely after the interview he runs off to the rest room and masturbates.
Could not stop laughing! If I get a DP, not sure I can stop my laughter :-)
I agree. They kinda suck.
Don't you dare they are my favorite algorithms. (Though when you don't get them it sucks :/)
I used to love DP too when I had time and was young. It does give you kicks :-). In speech recognition it used to be absolute must. As an example the Stock selling problem for at most K transaction is hard one for me. It took me more than 30 minutes just to formulate the sub problem and create the table that I can extent as I increase my solution space. I also think I was lucky here because I brushed some classical DP before jumping in. However, if I would have seen this problem in an actual interview ... no way I would be able solve it, that too on a white board in 45 minutes. That worries me ...