91–100 of 225 posts
Admittedly we have moved on from simply talking about the balls to getting them to arrange the balls in a particular order. Still not juggling though.
(For those that don’t get the reference. It’s a chapter in Peopleware)
Earlier quoted context omitted.
Your two paragraphs are contradictory. If someone can learn to solve just DP problems by practicing in leetcode then DP is a useless metric or proxy of someone’s ability to reason mathematically. You should have said “the ability to solve DP problems is a good metric of the ability of a candidate to solve DP problems“. I would have agreed with you in that case :)
> If someone can learn to solve just DP problems by practicing in leetcode then DP is a useless metric or proxy of someone’s ability to reason mathematically. I'm not a fan of DP but I don't follow this logic. Does practicing maths problems for an exam make the exam a useless metric of mathematical reasoning?
> problems on DP are pretty standard in most product-company-based hiring challenges This is sad and a little surprising to me. I've always thought of DP problems as being obviously terrible interview questions, even among the different types of algo questions (which are already heavily criticized). Candidates who have learned DP in school usually find them really easy, and candidates who haven't usually don't even h…
I don't want to work with such a person. They still got the job, because connections, but will 100% never be on my team.
Dynamic Programming and memoization are definitely related techniques, but they are emphatically _not_ the same. Memoization is a black-box approach that can be applied to a generic recursive top-down, depth-first algorithm. Dynamic Programming is about rewriting the recursive top-down algorithm in a bottom-up, breadth-first manner. Shriram Krishnamurthi explains it best: https://blog.racket-lang.org/2012/08/dynamic-…
> problems on DP are pretty standard in most product-company-based hiring challenges This is sad and a little surprising to me. I've always thought of DP problems as being obviously terrible interview questions, even among the different types of algo questions (which are already heavily criticized). Candidates who have learned DP in school usually find them really easy, and candidates who haven't usually don't even h…
"and candidates who haven't usually don't even have a chance at solving them" I am one of those candidates, and I don't know why it is called Dynamic programming. To me a vey naive understanding of DP is this - it's just a simple cache mechanism to store intermediary results so that you don't have to recompute them and waste resources. In the real world we always think about and do such optimizations, be it I/O, disk…
I have a problem with this notion that knowledge of algorithms is required to be a good engineer though. Case in point: Senior algorithm nerd on my project is going nuts over algorithmic complexity and delaying an early delivery to another team so they can begin using our new feature. In our case, n is fairly small no matter what, so 2n vs n^2 really doesn't matter to us. The code he's optimizing isn't even the long pole in the tent. It calls other routines which take 2/3 of the total time anyway. We could just deliver now and improve later when we have real world data on how people want to use our feature, but nope, we're wasting time on endless rewrites in search of perfection which may not matter if the other team can't deploy our stuff in time.
Grokking the Dynamic Programming Patterns for Coding Interviews (https://www.educative.io/collection/5668639101419520/5633779...)
Disclaimer: I'm the co-founder of educative.io but NOT the author of this course.
So "DP" is just recursion with memoization? Or an I missing another piece? Edit: apparently I'm not the only one thinking this: https://news.ycombinator.com/item?id=19395862
I think many people struggle with understanding "Dynamic Programming." Hopefully the following clears it up for you. Dynamic Programming can be done using Memoization (top-down; aka recursively) or Tabular method (bottom-up). So what's the difference? When you see top-down, it means to start from the root of the problem and recursively descend to the base case. As you pop up the stack, you will either calculate and s…
It seems that many dynamic programming solutions can be arrived at by starting with a recursive formulation, adding memoization, and then optimizing the cache based on specialized knowledge of the problem. For example:
1. Q: How can you compute Fibonacci number f(n) recursively? A: f(n) = f(n-1) + f(n-2)
2. Q: How can you memoize the results of your recursive function(s) to dramatically reduce the number of calls? A: Make a cache keyed on n that stores f(n).
3. Q: Given specialized understanding of the problem, how can you minimize the size of the cache? A: Notice that you don't need to keep all O(n) slots; you only need to keep two ints.
Can every dynamic programming solution be explained this way? Or is there a good example of a dynamic programming problem for which you really need to make a leap that can't be sensibly reached through this sequence of three questions?
Earlier quoted context omitted.
"and candidates who haven't usually don't even have a chance at solving them" I am one of those candidates, and I don't know why it is called Dynamic programming. To me a vey naive understanding of DP is this - it's just a simple cache mechanism to store intermediary results so that you don't have to recompute them and waste resources. In the real world we always think about and do such optimizations, be it I/O, disk…
> [...] I don't know why it is called Dynamic programming. According to Richard Bellman, who came up with the name: An interesting question is, Where did the name, dynamic programming, come from? The 1950s were not good years for mathematical research. We had a very interesting gentleman in Washington named Wilson. He was Secretary of Defense, and he actually had a pathological fear and hatred of the word research. […
According to Richard Bellman, who came up with the name:
An interesting question is, Where did the name, dynamic programming, come from?
The 1950s were not good years for mathematical research. We had a very interesting gentleman in Washington named Wilson. He was Secretary of Defense, and he actually had a pathological fear and hatred of the word research. [...] What title, what name, could I choose?
In the first place I was interested in planning, in decision making, in thinking. But planning, is not a good word for various reasons. I decided therefore to use the word "programming"
[...] it's impossible to use the word "dynamic" in a pejorative sense. Try thinking of some combination that will possibly give it a pejorative meaning. It's impossible.
Thus, I thought dynamic programming was a good name. It was something not even a Congressman could object to.
> problems on DP are pretty standard in most product-company-based hiring challenges This is sad and a little surprising to me. I've always thought of DP problems as being obviously terrible interview questions, even among the different types of algo questions (which are already heavily criticized). Candidates who have learned DP in school usually find them really easy, and candidates who haven't usually don't even h…
I asked a dp question in an interview. It was useful. Here's why. I know the solution, so I frequently guide the interviewee towards the correct answer and offer my help. Plus I put my nice guy hat on. I have seen a supposedly good candidate refuse my offers of help and then proceed to spaghetti code on the board a series of disjointed while loops that is obviously going to go nowhere. I don't want to work with such…
For my taste the brevity and content of your story indicates a lack of introspection. It seems to me that the only option you consider is that the interviewee gets all the blame.
The reason for my suspicion is that independent of what happened there you should at least be aware that the story is not suitable to be shared in this form, because readers here only get your (very short too) story. Sure, you will get agreement - from people who jump to quick conclusions without actually having a basis for it. You are not even trying to give sufficient and/or unbiased information. I know this is just a forum and casual conversation, but to compare with science, which has the same issue of communicating one's ideas to other people, the equivalent would be a paper that only publishes the authors conclusions.