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

141–150 of 225 posts

Re: Dynamic Programming for Technical Interviews

#141

Post by Asooka »

msla wrote: post #76
hn_throwaway_99 wrote: post #54

Earlier quoted context omitted.

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

> For some reason most people seem to be born without the part of the brain that understands pointers. If you can understand P.O. box numbers, you can understand pointers. They're the same concept at the level of modern application programming, where the OS, MMU, and cache are comprehensively lying to your code to present the illusion of a completely flat address space. At that level, all a pointer is is a box number…

Yes, and then you have to make people understand that box [number 23] is itself in a box and 23 can change at any time. And you can ask for the thing in box [the thing in box [the thing in box [the number that was passed to this function]]]. It's a double and sometimes triple indirection and understanding that pointers and the things pointed to are the same kind of data is the hard part. It's numbers all the way down.

Re: Dynamic Programming for Technical Interviews

#142

Post by jonfw »

collyw wrote: post #121
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…

If you really do need to know that stuff, you can read up on it when it's needed. Been programming professionally for over 15 years and have had to use this stuff once that i can remember. Knowing how to design and index a database well is way more useful.

To give the other side of the coin here- you at least need to know the basic logic behind it if you're going to be able to recognize when reading up on it might be needed.

If you have never considered the benefits of caching certain computational results in a recursive algorithm, than you probably wouldn't be as quick to recognize when that technique would be useful.

Re: Dynamic Programming for Technical Interviews

#143

Post by vardhanw »

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

Re: Dynamic Programming for Technical Interviews

#144

Post by pavlov »

srean wrote: post #140
pavlov wrote: post #115

Earlier quoted context omitted.

> "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 wouldn't want to work with a person whose idea of a useful job interview is: "I'll pick an esoteric bullshit problem, put my nice guy hat on, and guide you towards the solution as I bask in your admiration of my largesse." It's like when self-declared "nice guys" approach women…

I think its a win win. They get to pick someone who is more suited to their needs (problem solving that needs some algorithms thinking) and you get to work at a place where things are more rote.

Do you think that "I'll put my nice hat on and guide you to the solution, if I feel like it" is an optimal way to measure "problem solving that needs some algorithms thinking"?

Re: Dynamic Programming for Technical Interviews

#145

Post by baobabKoodaa »

deepGem wrote: post #75
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…

"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 parent poster attempts with "it's just a simple cache mechanism")

- DP is not a "trick" that you can learn and then solve any DP problem

If we have a DP solution, we can write it in many ways. We can write it top-down with recursion and memoization, or we can write it bottom-up without memoization. Whether we use memoization in our solution or not is a minor implementation detail. Both solutions are DP. Other posters seem to make a distinction between these two solutions as if they are entirely different and as if the recursive solution is not dp - this is also incorrect. The challenge in DP tasks is about improving time complexity by recognizing repeated sub calculations.

Re: Dynamic Programming for Technical Interviews

#146

Post by collyw »

dnautics wrote: post #94
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…

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…

If I was given a new problem like this, the first thing I would do is google to see if it has been solved before and the approaches other people have taken. Not try to think up shit myself. With 15 years of tech experience I have found it to be a far superior approach to solving problems.

Some people may well not want to ask for help with a task during an interview seeing as its obvious that some interviewers may well mark you down for asking.

Re: Dynamic Programming for Technical Interviews

#147

Post by wizzairflyer »

Jach wrote: post #105
PopeDotNinja wrote: post #79

Earlier quoted context omitted.

I don't know anything about dynamic programming in the manner that it is taught. I also don't get why it's even a thing (which is to say I haven't studied the topic, and haven't yet seen a need to do so). Someone recently gave me the egg dropping problem in an interview. I had never seen it before, but the answer eas obvious, and I verbally stated the solution in under a minute. I asked the interviewer if I could out…

Talk is cheap, code is what matters. But maybe the interviewer wanted to save time not writing an incorrect solution if he believed your approach was wrong and you could talk yourself out of it? Did you get to step through how your solution would arrive at the number 14 given 2 eggs and 100 floors? And if you wrote it out, would it produce that number? (Personally I have no idea what you mean with the binary search a…

A funny trick is to ask this question but first give the candidate an infinite amount of eggs. Once he succeeds, ask the question with only 2 eggs. That might explain the binary search answer.

Re: Dynamic Programming for Technical Interviews

#148

Post by srean »

pavlov wrote: post #144
srean wrote: post #140

Earlier quoted context omitted.

I think its a win win. They get to pick someone who is more suited to their needs (problem solving that needs some algorithms thinking) and you get to work at a place where things are more rote.

Do you think that "I'll put my nice hat on and guide you to the solution, if I feel like it" is an optimal way to measure "problem solving that needs some algorithms thinking"?

Well, of course one can be a dick about it, but nothing in the parent post indicated that he was. May be you had a bad experience in the past and projecting it on the author of the comment. I tend to / try to assume good faith.

Picking up loosely specified directions and filling up the gaps is indeed an important skill to have. If I had the time to describe the solution in the minutest detail to a co-worker, I would have the time to write it myself. Often, its a luxury that I dont have. In such situations I would certainly appreciate the skill that a co-worker can fill in the necessary detail from pointers and rough directions.

Re: Dynamic Programming for Technical Interviews

#149

Post by baobabKoodaa »

deepGem wrote: post #84
tikhonj wrote: post #82

Earlier quoted context omitted.

The tricky thing with dynamic programming is realizing that it fits—you have to understand how the problem you're solving decomposes into overlapping subproblems that are worth caching. Once you know what the subproblems are, implementing the algorithm is mostly a matter of getting some fiddly indexing logic right. Take string edit distance for example: the key to the dynamic programming problem is seeing how the exp…

Absolutely, but I attribute the ability to decompose a problem into overlapping subproblems as an understanding of recursion, so I had implicitly assumed such an understanding.

Try solving some difficult DP problems on CodeForces. You will find that an "understanding of recursion" is not enough to solve them.

Re: Dynamic Programming for Technical Interviews

#150

Post by [deleted] »

jonsen wrote: post #99
mafm wrote: post #81

Earlier quoted context omitted.

> [...] 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. […

Formatted for mobile: 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 c…

[deleted]
Post reply on HN