Are Dynamic Programming Interview Questions Valid?
I don’t understand why people ask DP questions in coding interviews. First, I don’t know a single person who can come up with DP solutions on their own without already knowing the answer from somewhere else or getting a hint. I’m sure there are some people who can invent DP solutions on their own, but that is probably a small minority. Second, I have never seen or needed a DP algorithm in production code. I’m not saying there are no practical applications for it. I’m just saying those are the rare cases and not the norm. So how are DP interview questions valid in assessing the coding skills of a candidate? Update: I am getting some hand-wavy, fictional answers like “DP is useful and everyone knows them”. Why don’t you back up your claims with real-life scenarios of production code instead of littering this post with your own interview practice mentality? I am NOT saying DP is useless. I am asking you about your OWN experience using it in the real world.
dp is considered as simple questions now. if people only ask me dp questions, i would thank them!
Dp is fine... What about segment trees and kmp?
Microsoft, you're mistaken. A lot of what you said absolutely incorrect. I've actually talked to people who were able to do dp solutions without any prior knowledge about dp. They also didn't know the fact that what they did is known as dp but they were able to come up with those solutions without having a prior exposure to dp.
I've never seen DP algorithms using arrays in production. However, I've written backtracking algs with memoization multiple times. And these are conceptually same as DP
The culture at google are very academic like. They live in their own bubble. So yes if you want a job from Google and companies that emulate them, then you need to study up.
@Op: people ask dp questions in interviews because they’re challenging and they want to weed out candidates who instead of learning dp, make posts on Blind asking why people ask dp questions in interviews.
Savage
Dp is just a fancy way of saying 'I used recursion with memoization'. Recursion is quite often used for processing structured data stored in a tree like fashion so yes it's used in production code.
Not in bottom up dp.
I've used recursion with memoization. In production, what matters is just recognizing that this technique can be applied. Unfortunately in interviews, what matters is spitting perfect code, which I agree, only folks who've memorized those kinds of solutions can come up with. Overall, I agree with you. What interviews should be looking for is insight. Someone solving a textbook problem in 30 mins is not the same as insightful problem solver. Solving those in 30 mins simply selects for people who've spent time practicing those problems.
“Solving those in 30 mins simply selects for people who've spent time practicing those problems.” What’s wrong with that? Being able to solve difficult dp problems means either a) the candidate is really smart or b) the candidate works hard and has put in a lot of time practicing and preparing for the interview. Either scenario is a win for the company.
a. Software engineering is not high speed puzzle solving b. Software engineering is not high speed puzzle solving a. Playing Sweet child of mine flawlessly is not the same as being an amazing guitarist b. Solving 500 calculus problems, getting a 6 pack abs, running a marathon is also working hard, none of which is useful in software engineering, just like rote puzzle solving on white board a. If I had to hire a basketball player for a team, should I hire the one who is similar to my other players or someone who compliments my team, filling in the gaps? b. If I had to hire a basketball player, should I hire one who worked hard at perfecting free throws at the expense of other team skills or someone who worked hard at shipping products out? Dude, get a grip. Folks who can solve leetcode are not by any measure smart or useful. It's a proxy and a pretty bad one at best, since it only avoids a supposed false negative. Doesn't even select for super stars
I agree with the point that if you know the dp question only then u can solve it
This is some pleb tier fake news. Real engineers can solve DP questions off the top of their head. If you've seen one of these questions, you should be able to solve all of them.
Yes DP is used in production code and yes many people come up with DP solutions without hints.