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

211–220 of 225 posts

Re: Dynamic Programming for Technical Interviews

#211

Post by 01100011 »

ajbeach22 wrote: post #188
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…

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

> if there is IO or api calls involved

Right. In my case, the operation was an extra memory comparison. For something already in the cache.

Sure, constraints can change and your assumptions about n<10k may prove unwise, but that's our call to make as engineers. YAGNI. If you know n is never going to grow, then why waste time on it? We're not paid to write pristine code. We're paid to solve problems while hopefully not creating new ones. Pragmatism and all that.

Re: Dynamic Programming for Technical Interviews

#212

Post by 01100011 »

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

Sadly, Perfectionists share a trait when it comes to building software, obsession to their craft at the expense of everythng else, shipping times included.

I think we all derive joy from writing 'perfect' software...but then the rules are changed and perfection becomes garbage :)

Like the other piece of software I was working on for this project. Nice little test framework with a beautiful OOP structure... which became a noose as soon as I wanted to add a new feature. Now it's this frankenbeast with a weird appendage glued on.

Re: Dynamic Programming for Technical Interviews

#213

Post by dahart »

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…

The quote from Wikipedia is factually correct, but it seems you misunderstood my comment.

> It’s not about how much time you’re gonna take

It most definitely is about predicting running time, or memory consumption. Big-O is literally a straightforward way to write the formula for best/avg/worst case time or memory of a program, modulo a constant. The second part of your sentence contradicts the first part.

I’m not sure I buy that there’s any common misconception about Big-O either, I’ve never seen much evidence of that. Anyone who’s learned Big-O in school, or has used it at work, or read past the first sentence on Wikipedia, or commented about it on HN, knows what Big-O means and that for small n, O(n) can be bigger than O(n^2). It’s just not that tricky.

I like Wikipedia a lot, and I agree this one’s right. Why do you dislike it, and why is that relevant?

Re: Dynamic Programming for Technical Interviews

#214

Post by jogjayr »

lawn wrote: post #125
groby_b wrote: post #74

Earlier quoted context omitted.

> It's probably true that programmers who are good at solving DP problems are generally quite good, which is why DP problems get asked at interviews. Yeah, no. (Source: I've seen a few interviews in my time. On the order of 5k of them) DP problems are absolute shit at giving a signal, even if the candidate knows DP problems. Because "knows DP" is pretty much the only bit of information you get, with possibly a slight…

I was in a team with a very talented competitive programmer guy. He came up with solutions for some pretty tough problems I couldn't wrap my head around. Fantastic programmer right? The other 99% except hardcore algorithmic optimizations, like structuring code, creating simple code, naming variables, splitting code into classes/functions and refactoring? No clue about any of that. All he produced was "read-only" and…

> The other 99% except hardcore algorithmic optimizations, like structuring code, creating simple code, naming variables, splitting code into classes/functions and refactoring? No clue about any of that.

So...you're saying a student wrote code like...a student? Color me shocked.

You can coach talented programmers to write neat code, design classes, and name their variables right. It's part of turning a junior engineer into a senior engineer. It's far harder to teach someone how to solve programming problems.

Re: Dynamic Programming for Technical Interviews

#215

Post by jogjayr »

groby_b wrote: post #203
jogjayr wrote: post #83

Earlier quoted context omitted.

> I've seen a few interviews in my time. On the order of 5k of them) That's actually pretty cool. May I ask how? > Because "knows DP" is pretty much the only bit of information you get Yes if the candidate meets with only one interviewer or if every interviewer asks only DP. I hope most companies don't interview that way - that would truly be a broken interview process. Obviously you ask about other stuff in the othe…

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 whatever. Even though they'd have made a perfectly fine employee given a week's worth of ramp-up, they may end up flunking the interview (Maybe it's a less of a problem in games because everything is C++? I don't know). How do you calibrate these performance variances due to lack of familiarity with the specific tech?

2. How do you ensure that the odd toxic candidate doesn't ruin the team dynamic? It's hardly fair to reject everyone if they'd have done well without the one asshole.

3. It seems odd to expect people to collaborate in a situation where (for all they know) they are actually competing for the same position(s). What if you don't actually have enough open positions to hire everyone?

4. How do you track contributions by individual candidates? Commits? Observations by the embedded employee?

5. Do you tell candidates upfront they're being graded for co-operation as well as productivity? (and is that how you're actually grading?)

Re: Dynamic Programming for Technical Interviews

#217

Post by caspar »

dahart wrote: post #213
rafiki6 wrote: post #184

Earlier quoted context omitted.

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

The quote from Wikipedia is factually correct, but it seems you misunderstood my comment. > It’s not about how much time you’re gonna take It most definitely is about predicting running time, or memory consumption. Big-O is literally a straightforward way to write the formula for best/avg/worst case time or memory of a program, modulo a constant. The second part of your sentence contradicts the first part. I’m not su…

I'm not the person you're replying to, but it seems to me that there may be an example of a common misconception about Big-O in your comment here:

> Big-O is literally a straightforward way to write the formula [describing] best/avg/worst case time or memory of a program

Technically, Big-O notation should only be used to provide an upper bound on the best/avg/worst case[0]. And typically people only use it to discuss the worse case or average case, just because talking about the upper bound on an algorithm when its inputs are restricted to its best possible inputs is typically much less useful.

But providing an upper bound is not quite "writing the formula" (giving a complete picture), because you haven't specified the lower bound (Big/Little-Omega) - very loosely speaking, if you only ever talk in terms of Big/Little[1]-O, you've only provided half the picture. Of course to be fair, Big-O of an algorithm is the side of the picture that is way more likely to bite you in production!

Disclaimer: not a mathematician, so salt to taste :)

0: https://stackoverflow.com/a/12338937/775982 1: https://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachm...

Re: Dynamic Programming for Technical Interviews

#218

Post by frosted-flakes »

stan_rogers wrote: post #118
matt-snider wrote: post #114

Earlier quoted context omitted.

Thanks :-). This comes up so often! Is there a reason HN doesn't use a more mobile-friendly format for preformatted text?

The feature is intended for code, note block quotes. Auto line wraps would be less than helpful.

Yeah, but code blocks are still limited in width on mobile. At least let them flow to the edge of the screen before scrolling.

Re: Dynamic Programming for Technical Interviews

#219

Post by dahart »

caspar wrote: post #217
dahart wrote: post #213

Earlier quoted context omitted.

The quote from Wikipedia is factually correct, but it seems you misunderstood my comment. > It’s not about how much time you’re gonna take It most definitely is about predicting running time, or memory consumption. Big-O is literally a straightforward way to write the formula for best/avg/worst case time or memory of a program, modulo a constant. The second part of your sentence contradicts the first part. I’m not su…

I'm not the person you're replying to, but it seems to me that there may be an example of a common misconception about Big-O in your comment here: > Big-O is literally a straightforward way to write the formula [describing] best/avg/worst case time or memory of a program Technically, Big-O notation should only be used to provide an upper bound on the best/avg/worst case[0]. And typically people only use it to discuss…

Ugh.

The “worst case” is the part referring to the upper bound. Big-O is referring to the “order” of the run time, meaning the largest term in the formula for large n.

Again, everyone knows this if they know Big-O at all. I am intentionally not being picky and pedantic with my words, because the context of this thread was people complaining about unnecessary formality and unnecessary and unhelpful over-concern about academic correctness rather than practicality. There is no widespread misconception, but there are people who like to wax philosophical and try to demonstrate their superior knowledge...

My side intention was to detail why @rafiki6 might have been incorrect without knowing it, since they claimed correctness and complained about downvotes.

Re: Dynamic Programming for Technical Interviews

#220

Post by roryokane »

clickok wrote: post #9
sanderjd wrote: post #4

I have always felt that dynamic programming is only confusing because of the name. The concept of caching previously calculated values in order to save time by avoiding recalculation (at the cost of using more space) is intuitive. What am I missing?

Richard Bellman coined the name, and according to legend it was because the phrase 'dynamic programming' was so anodyne that not even the most officious bureaucrat could object. In Bellman's own words[0]: "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 Secr…

A link to the original paper that your source quotes: https://web.archive.org/web/20060209011347/http://www.eng.ta.... “Richard Bellman on the Birth of Dynamic Programming” by Stuart Dreyfus.
Post reply on HN