Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Dynamic Programming for Technical Interviews

blogarithms.github.io

Post reply on HN
Print view View original

181–190 of 225 posts

Re: Dynamic Programming for Technical Interviews

#181

Post by reader5000 »

baobabKoodaa wrote: post #145
deepGem wrote: post #75

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…

DP is a general problem solving approach. It's about recognizing which parts of a naive solution have repetition which can be eliminated to improve the time complexity of the solution. Another poster aptly described it as finding states which can be collapsed into one. However you want to think about it, - DP is a general problem solving approach - DP is not limited to any particular implementation detail (like my pa…

In "Algorithms" [Dasgupta, Papamdimitriou, Vazirani] they state that the memoization (e.g. querying a hash table) can have significant overhead leading to a large constant factor in the big O analysis. On the other hand, the bottom up approach using a table solves all the possible subproblems including ones that are not needed and ones that the recursive approach would avoid. So from a big O perspective the recursive top-down and the table bottom-up approaches are the same but there can be significant constant factor differences.

Re: Dynamic Programming for Technical Interviews

#182

Post by pwaivers »

vardhanw wrote: post #143

In the first problem illustrated, I wanted to also get the list of coins. I made this attempt, but this hardly seems elegant. Any comments to make it better? n=10 denom = [1,3,4] dp = [-1 for i in range(n+1)] dpl = [[] for i in range(n+1)] def f(n): if dp[n]!= -1: return dp[n] ans = 10**10 if n =0: new = f(n-i)+1 if new

To be more elegant, you can remove the "dp" array. If you want to keep track of the full list, then you only need to keep track of "dpl". Here is code that I wrote and it works:

  n = 10
  denom = [1, 3, 4]
  dpl = [[] for i in range(n+1)]
  def f(n):
      if dpl[n]:
          return dpl[n]
  
      if n = 0:
              new = f(n-i) + [i]  # append i to the end of the array
              if len(new)

Re: Dynamic Programming for Technical Interviews

#183

Post by tracer4201 »

hn_throwaway_99 wrote: post #54
alangpierce wrote: post #17

> 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…

For what it's worth, I use DP problems extensively for a main reason: in my experience I have found an extremely high correlation between folks who do well on DP problems and folks who are good overall engineers. I have never had a candidate that did very well on DP problems that didn't end up being an overall great programmer (though I certainly have had folks do well on DP problems who were deficient in other ways,…

I’m not seeing the connection here between DP problems or pointers indicating great engineers. I’ve worked with people who were great at programming problems but couldn’t actually solve real world problems without step by step guidance, folks who cannot communicate at all with the team or with product people, folks who have a terrible work ethic, etc. The ability to solve DP would be nothing but noise if we were to go back and time and hold these interviews differently... and to be honest, we almost always had at least some recursion or DP problem. All it really did was bias our hiring towards grads fresh from school.

Regarding understanding pointers... you may as well use the candidates understanding of object oriented programming or knowing how to test their code. Pointers seems like an arbitrary litmus test, and it comes off as you feel like understanding pointers make you special when it really doesn’t.

Re: Dynamic Programming for Technical Interviews

#184

Post by rafiki6 »

dahart wrote: post #157
01100011 wrote: post #96

Earlier quoted context omitted.

In my "real world" we normally don't care about things like big-O complexity. We worry about doing dumb things and not taking more time than we have available. I'm not saying big-O is useless or CS wizards are never helpful. It's just that you need one or two of them for a large team of normies, IME. I have a problem with this notion that knowledge of algorithms is required to be a good engineer though. Case in point…

> In my “real world” we normally don’t care about things like big-O complexity. We worry about doing dumb things and not taking more time than we have available. Big-O is just a formal word for how much time you’re going to take, a way to figure out if you’re likely to take more time than available. So, it sounds like you do care about it, you’re just saying it doesn’t matter if you’re formal about it? If your team’s…

> Big-O is just a formal word for how much time you’re going to take, a way to figure out if you’re likely to take more time than available

This is a common misunderstanding about big-O. It's not about how much time you're gonna take but it's actually a measure of how complexity affects time growth as the data grows.

"Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. "

From: https://en.wikipedia.org/wiki/Big_O_notation

I generally don't like wikipedia, but they got this one right.

Re: Dynamic Programming for Technical Interviews

#185

Post by UncleMeat »

reader5000 wrote: post #181
baobabKoodaa wrote: post #145

Earlier quoted context omitted.

DP is a general problem solving approach. It's about recognizing which parts of a naive solution have repetition which can be eliminated to improve the time complexity of the solution. Another poster aptly described it as finding states which can be collapsed into one. However you want to think about it, - DP is a general problem solving approach - DP is not limited to any particular implementation detail (like my pa…

In "Algorithms" [Dasgupta, Papamdimitriou, Vazirani] they state that the memoization (e.g. querying a hash table) can have significant overhead leading to a large constant factor in the big O analysis. On the other hand, the bottom up approach using a table solves all the possible subproblems including ones that are not needed and ones that the recursive approach would avoid. So from a big O perspective the recursive…

Then mention this in the interview. I ask an algorithms question that would likely be hated on HN but when candidates tell me the practical difference (API cleanliness, maintainability, performance, extensibility) between approaches that ultimately don't impact asymptotic runtime I love it.

Re: Dynamic Programming for Technical Interviews

#186

Post by lowdest »

I spent 2-3 weeks going through all DP problems on leetcode after work. I got that Tetris-effect where I was starting to hallucinate/dream DP problems and solutions as I would fall asleep at night.

I did this specifically for interviewing. As I've said before, these kind of interviews screen for unusual geniuses or people with the motivation to spend many hours studying, which are two types of acceptable hires.

Re: Dynamic Programming for Technical Interviews

#187

Post by rafiki6 »

rafiki6 wrote: post #184
dahart wrote: post #157

Earlier quoted context omitted.

> In my “real world” we normally don’t care about things like big-O complexity. We worry about doing dumb things and not taking more time than we have available. Big-O is just a formal word for how much time you’re going to take, a way to figure out if you’re likely to take more time than available. So, it sounds like you do care about it, you’re just saying it doesn’t matter if you’re formal about it? If your team’s…

> Big-O is just a formal word for how much time you’re going to take, a way to figure out if you’re likely to take more time than available This is a common misunderstanding about big-O. It's not about how much time you're gonna take but it's actually a measure of how complexity affects time growth as the data grows. "Big O notation is a mathematical notation that describes the limiting behavior of a function when th…

Not entirely sure why I am getting downvoted here. It's factually correct and relevant to the discussion. I'm starting to think someone is actively trying to downvote my comments.

Re: Dynamic Programming for Technical Interviews

#188

Post by ajbeach22 »

01100011 wrote: post #96
deepGem wrote: post #75

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…

In my "real world" we normally don't care about things like big-O complexity. We worry about doing dumb things and not taking more time than we have available. I'm not saying big-O is useless or CS wizards are never helpful. It's just that you need one or two of them for a large team of normies, IME. 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

This is me, but luckily where I work I have people who can keep me in check because we generally do design reviews before anything big is built.

However, I have been in situations at previous companies where big(o) was ignored to take short cuts up front, because the "data was small" and suddenly scaling to even just 100 users starts to break things because of poor design decisions when it gets into production.

I guess the lesson here is more the importance of design reviews. Also n^2 is HUGE even for small data if there is IO or api calls involved. Any public api you provide, that is n^2 is not a good idea because you never know who may end up using it for what.

Re: Dynamic Programming for Technical Interviews

#189

Post by JJMcJ »

Coin changing - my understanding is that if each denomination of coin is at least twice that of the next smaller, then greedy is optimal. Note to self - see if you can prove it.

That is the case for current US coinage, 1, 5, 10, 25, 50, 100, cents.

Re: Dynamic Programming for Technical Interviews

#190

Post by chillee »

zeroonetwothree wrote: post #180
chillee wrote: post #70

Earlier quoted context omitted.

Fibonacci isn't considered Tree DP. One example of a tree DP problem is: Given a tree with N nodes, how many ways are there of coloring each node with black or white given that no two white nodes are adjacent.

That just has a straightforward recursive solution. I’m not even sure where the DP comes in beyond that.

What's your straightforward recursive solution? It might be what's considered Tree DP. If you want a harder problem I can give an example too :^)
Post reply on HN