2 ms·

You are correct in that. A few points though: - While DP might be rare, memoize is quite common alternative. Sticking a @functools.cache in Python for example.

by behdad 3y ago

You are correct in that. A few points though: - While DP might be rare, memoize is quite common alternative. Sticking a @functools.cache in Python for example. They are functionally equivalent in many cases, - I believe knowing their data-structures and algorithms is the difference between an okay programmer and a good one, - When interviewing entry-level software-engineers, there's not much else you can ask them except for what they learned in class, which is these kinds of questions.

lmarcos 3y ago
> I believe knowing their data-structures and algorithms is the difference between an okay programmer and a good one For me, the difference between and okay programmer and a good one is: how much Linux/Unix they know (processes, core system calls, networking, sockets, awk/sed/bash). Whether you are writing apis for ecommerce platforms or writing custom k8s providers, Linux knowledge is a must. Knowing how to implement a trie? I bet most of us have never been in that situation.
- bonzini 3y ago
  That depends on what kind of system you are developing. For example if you're writing APIs for e-commerce platforms you may need to know how to tune a container's CPU and memory limits but not the difference between cgroups v1 and v2. Likewise, there are jobs where being able to reason on complexity and data structures is important.
- stavros 3y ago
  We have developers writing APIs for e-commerce platforms that don't know a lick of Linux, thus proving it's possible to write code without knowing how to deploy it.
  - Dudeman112 3y ago
    But then how are you gonna have a one-person IT department if your developer doesn't know Linux?
- hardware2win 3y ago
  Ecommerce? Linux? Wtf?
adamwk 3y ago
Those are fair points and you also said you didn’t expect them to implement DP. I’m curious what your minimum expectations are for the candidate to solve. When I ask these questions it’s usually about the journey more than the destination (which I believe you mentioned in the beginning) but I’m guessing you’d at least expect the candidate to come up with the brute force solution.
dclowd9901 3y ago
I think the difference between a good front end developer and an ok one is how they understand about what goes on under the hood of React. Your broad strokes don’t account for the domain knowledge of a job. If all you’re doing is interviewing college grads, then I guess you have no choice, but this interview question sucks in just about any other context.
thaumasiotes 3y ago
> While DP might be rare, memoize is quite common alternative. Sticking a @functools.cache in Python for example. They are functionally equivalent in many cases They're not just functionally equivalent. They are the same thing. There are two things you need for a dynamic programming solution: 1. You remember the answer every time your function is called. ("Memoization".) 2. You structure your function calls so that they will ask for a lot of answers that have already been computed. What you don't want is: say you're computing the sums of contiguous subsections of an array. You've already figured out that indices [2:5] sum to 3 and indices [5:8] sum to 8. When you need the sum of indices [2:8], you need to make sure you get it by asking for sum(2,5)+sum(5,8), and not by asking for sum(2,6)+sum(6,8).
- dmurray 3y ago
  > They're not just functionally equivalent. They are the same thing. There are two things you need for a dynamic programming solution At a high level they are the same, but it makes sense to distinguish between the techniques based on whether you need random access to the already-computed data. For example, if you are computing the nth fibonacci number f(n), a DP solution needs only the state f(n-1) and f(n), but a typical memoized solution keeps around all the state f(1) through f(n-1). For tougher problems, you can't always convert between them trivially while keeping performance the same.
  - thaumasiotes 3y ago
    > if you are computing the nth fibonacci number f(n), a DP solution needs only the state f(n-1) and f(n), but a typical memoized solution keeps around all the state f(1) through f(n-1) That's all true, but is it comparing like with like? The "generic DP" solution to the problem is to allocate an array of n elements and fill it in from f(1) to f(n). That's the same amount of storage the "typical" memoized solution uses; cutting it down to an array of 2 elements plus an (implicit) offset between the part of the array that's in use and the full array seems to be an optimization on top of the DP solution. You could apply the same optimization to a memoized form of the solution. I certainly agree that you most likely wouldn't do that, but you could. What do we learn by comparing a tightly optimized DP solution against a "typical" memoized solution? Why do we give the DP solution credit for not using what it "doesn't need" while penalizing the memoized solution for what the programmer probably added unnecessarily?

by behdad 3y ago

lmarcos 3y ago

> I believe knowing their data-structures and algorithms is the difference between an okay programmer and a good one For me, the difference between and okay programmer and a good one is: how much Linux/Unix they know (processes, core system calls, networking, sockets, awk/sed/bash). Whether you are writing apis for ecommerce platforms or writing custom k8s providers, Linux knowledge is a must. Knowing how to implement a trie? I bet most of us have never been in that situation.

bonzini 3y ago
That depends on what kind of system you are developing. For example if you're writing APIs for e-commerce platforms you may need to know how to tune a container's CPU and memory limits but not the difference between cgroups v1 and v2. Likewise, there are jobs where being able to reason on complexity and data structures is important.
stavros 3y ago
We have developers writing APIs for e-commerce platforms that don't know a lick of Linux, thus proving it's possible to write code without knowing how to deploy it.
- Dudeman112 3y ago
  But then how are you gonna have a one-person IT department if your developer doesn't know Linux?
hardware2win 3y ago
Ecommerce? Linux? Wtf?

adamwk 3y ago

Those are fair points and you also said you didn’t expect them to implement DP. I’m curious what your minimum expectations are for the candidate to solve. When I ask these questions it’s usually about the journey more than the destination (which I believe you mentioned in the beginning) but I’m guessing you’d at least expect the candidate to come up with the brute force solution.

dclowd9901 3y ago

I think the difference between a good front end developer and an ok one is how they understand about what goes on under the hood of React. Your broad strokes don’t account for the domain knowledge of a job. If all you’re doing is interviewing college grads, then I guess you have no choice, but this interview question sucks in just about any other context.

thaumasiotes 3y ago

> While DP might be rare, memoize is quite common alternative. Sticking a @functools.cache in Python for example. They are functionally equivalent in many cases They're not just functionally equivalent. They are the same thing. There are two things you need for a dynamic programming solution: 1. You remember the answer every time your function is called. ("Memoization".) 2. You structure your function calls so that they will ask for a lot of answers that have already been computed. What you don't want is: say you're computing the sums of contiguous subsections of an array. You've already figured out that indices [2:5] sum to 3 and indices [5:8] sum to 8. When you need the sum of indices [2:8], you need to make sure you get it by asking for sum(2,5)+sum(5,8), and not by asking for sum(2,6)+sum(6,8).

dmurray 3y ago
> They're not just functionally equivalent. They are the same thing. There are two things you need for a dynamic programming solution At a high level they are the same, but it makes sense to distinguish between the techniques based on whether you need random access to the already-computed data. For example, if you are computing the nth fibonacci number f(n), a DP solution needs only the state f(n-1) and f(n), but a typical memoized solution keeps around all the state f(1) through f(n-1). For tougher problems, you can't always convert between them trivially while keeping performance the same.
- thaumasiotes 3y ago
  > if you are computing the nth fibonacci number f(n), a DP solution needs only the state f(n-1) and f(n), but a typical memoized solution keeps around all the state f(1) through f(n-1) That's all true, but is it comparing like with like? The "generic DP" solution to the problem is to allocate an array of n elements and fill it in from f(1) to f(n). That's the same amount of storage the "typical" memoized solution uses; cutting it down to an array of 2 elements plus an (implicit) offset between the part of the array that's in use and the full array seems to be an optimization on top of the DP solution. You could apply the same optimization to a memoized form of the solution. I certainly agree that you most likely wouldn't do that, but you could. What do we learn by comparing a tightly optimized DP solution against a "typical" memoized solution? Why do we give the DP solution credit for not using what it "doesn't need" while penalizing the memoized solution for what the programmer probably added unnecessarily?