Live data from Hacker News

Dynamic Programming for Technical Interviews

blogarithms.github.io

221–225 of 225 posts

Re: Dynamic Programming for Technical Interviews

#221

Earlier quoted context omitted.

See another comment above for explanation how I got to that count. (In essence: reviewing lots of interviews) > Do you have some examples of how this might be done? I do :) We did it at a previous company. We brought in several candidates at the same time, declared them a team, and gave them a half-finished video game (since it was a games company). With the goal of turning it into a better game by the end of the day…

I won't lie, it sounds like an interesting process and I wouldn't mind participating once if I'm qualified. I wonder if you could answer some more questions about it. Sorry, I know it's asking a lot, I understand if you don't answer: 1. What if you want to hire a primarily Python-writing programmer to write Ruby or C#? They're not going to be super-productive on day 1 - maybe they'll struggle to run gem install or wh…

1) Games are somewhat easier, because C++ is pretty common. It'd also work for larger companies, because you can group candidates by languages. I don't have a good answer for companies that can't do that.

2) That's why there's an observer with the team the whole time. If there were a truly toxic person, they'd have the power to pull them. I didn't see it happen (likely because everybody is on their best behavior during interviews), but I did see a few large egos - and they were pretty much always shunted into a corner of the project.

3) You obviously shouldn't do that if you can't afford to hire everybody. Which means it's likely not the right process for smaller companies.

4) Both by the embedded observer, and by looking at commit history. But it rarely comes down to that - what you want is "smart, and gets stuff done", and that fairly clearly separates out without counting commits. Or maybe we just got lucky.

5) All we told candidates is that we'd expect them to have a working game by end of day. Grading was less by cooperation, and more by how much of a positive contribution people were. We e.g. had candidates that up-front said "look, I work best by thinking quietly, and I'm an expert on X - would you mind if we carved out a subproject around that, and we reintegrate from time to time". And we did hire them - because a person who knows what their style is, and how to collaborate with a team with a different style, is a huge win.

Re: Dynamic Programming for Technical Interviews

#222

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

Dynamic programming is a mathematical term for a certain kind of problems that have certain properties and can be solved in a certain way.

Memoization is specific form of caching for functions.

That is all there is to it. Your link seems to conflate memoization with a global store that you must apply in an all or nothing fashion for functions. You do not, and calculating the n'th fibonacci number is a great example of how to use memoization without using O(n) space.

Re: Dynamic Programming for Technical Interviews

#223
post #131

>"I'll show you how to do DP" Hey it's the same 3 example problems that are in every textbook, GeeksforGeeks, Leetcode, etc.

Thanks for taking the time to read my post. :) Like I mentioned, this article only lays the groundwork. The next article I intend to write on is DP+Strings (for example, finding the longest substring of a string which is a subsequence of another, etc) I'm starting with classical problems and I'll soon diverge into non-classical problems, as I've mentioned in my article too. In any case, hope my other articles on my b…

Yeah, I was being snarky up above, but will definitely look forward to the future articles.

Re: Dynamic Programming for Technical Interviews

#224
post #158

Earlier quoted context omitted.

No, no, it is an understanding of how to recurse just right. Not an understanding of the concept of recursion in general. Basically, recursion plus memoization is almost the same in terms of power and approach as dynamic programming.

No, it's not, and if you actually tried to solve one of the harder DP problems, this would become very obvious to you. Here's one for you: https://codeforces.com/problemset/problem/1097/G It's a dp problem, and you understand how to recurse just right, and you understand memoization, so you'll be able to solve it, right? Link your solution when you reply please.

...That's what I thought.

Re: Dynamic Programming for Technical Interviews

#225

Earlier quoted context omitted.

No, it's not, and if you actually tried to solve one of the harder DP problems, this would become very obvious to you. Here's one for you: https://codeforces.com/problemset/problem/1097/G It's a dp problem, and you understand how to recurse just right, and you understand memoization, so you'll be able to solve it, right? Link your solution when you reply please.

...That's what I thought.

Behaving like an asshole and not getting a response is not proof of anything other than people not being interested in engaging with assholes.
Post reply on HN