Do you get penalty for not solving any DP problem in bottom up approach, in Google onsite? How do you approach such problems? From brute force and then top down or directly to bottom up solution? Thanks!
Those are such POS interview questions. How many times have Googlers used that approach in their work?
Describe brute force, work on top down. Describe short comings of top down (usually stack overflow due to recursion or something similar), and describe trade offs against that with bottom up. Work on whatever is agreed upon after discussion. Not google specific, but I’ve found this method worked best in my phone screens with dp problems.
Does G ask DP problems? I’ve heard most companies don’t. Uber were not supposed to anymore. All 7 of my interviews at G, F, Amazon and Uber didn’t get any DP
Yup! You might be lucky then. ;)
DP is either easy or gotchya. And I don’t mean Memoization. I’d prefer DP problems
dont focus on bottom up dp, top down recursion with memoization is good enough, btw i interved 7 places, not sjngle dp or memoization problem
Why do people hate dp so much?
It’s a pain in the ass.
I would prefer to be asked DP rather than that one liner tricky array or math problems!
I would prefer DP rather than traveling salesman problem, KMP or some other crap
Yes, me too. It would be nightmare to get TSP problem. However, I liked KMP!!
I never understand why companies ask DP questions. I think it’s pure group think where companies do it, cause other companies are doing it. We will look back on this practice the same way we look at questions like “how many golf balls can you fit into a 747”
By the way, I love algorithmic problems and hope leetcode style interviews never go away. This isn’t a case of sour grapes, I just think it’s actually stupid.
Well, Amazon asks that in bar raiser interview.
Depends on the problem maybe? Do you have an example?
Palindrome partitioning.
I'd say be able to solve this with DFS/ backtracking. Then attempt DP when asked. You had this question in an interview?