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

Dynamic Programming vs. Divide-and-Conquer (2018)

trekhleb.dev

Post reply on HN
Print view View original

41–50 of 120 posts

Re: Dynamic Programming vs. Divide-and-Conquer (2018)

#41

Post by globular-toast »

nicoburns wrote: post #37
globular-toast wrote: post #27

Earlier quoted context omitted.

It depends what you're looking for. If you want someone who can turn the handle on your typical daily task then, sure, test them on your typical daily task. But if you want someone capable of developing solutions to brand new problems then it's not so easy and testing fundamental computer science theory is important.

There are plenty of people who have a fantastic knowledge of CS theory and are pretty useless at solving real world problems.

Again, it depends what you're looking for. If the real world problem is "we need a fast optimising compiler that runs on our embedded platform" then hiring someone who is great solving problems but knows nothing of compiler theory is going to be very inefficient.

Re: Dynamic Programming vs. Divide-and-Conquer (2018)

#42

Post by lifthrasiir »

kryptiskt wrote: post #40
water8 wrote: post #2

The ratio of importance placed on these algorithm design in interviews vs the amount of times they actually come up in real world problems seems skewed IMO.

I disagree. There are so much code out there that nest loops and become accidentally quadratic, where a little knowledge would have helped make it perform well at scale. Knowledge about the time complexity of algorithms isn't valuable only for people implementing libraries. Every single time you iterate over things or partition things by a predicate you are using the building blocks of algorithms to make a new custom…

There are only a few useful parts of the algorithm theory in practice. The time complexity is surely one of them, but it is still overvalued in a sense that the actual performance on the real hardware and realistic input distribution is more important. And when you actually need algorithms, you always have a luxury of existing literatures and implementations. Real-time algorithm design in the interview is very unrealistic and in most cases only exists to detect interviewee's signaling.

Re: Dynamic Programming vs. Divide-and-Conquer (2018)

#43

Post by goldenkey »

vs Pure Reason

Reason gets you a closed form for F(n), the nth Fibonacci number. The author's naive fib with memoization is O(n). The closed form is O(1) if you consider exponentiation to be a constant time operation.

https://en.m.wikipedia.org/wiki/Fibonacci_number#Closed-form...

Quite a thing to overlook in an article about efficiency of algorithms... why am I not surprised?

Re: Dynamic Programming vs. Divide-and-Conquer (2018)

#44

Post by EvilEy3 »

slumpt_ wrote: post #28
globular-toast wrote: post #27

Earlier quoted context omitted.

It depends what you're looking for. If you want someone who can turn the handle on your typical daily task then, sure, test them on your typical daily task. But if you want someone capable of developing solutions to brand new problems then it's not so easy and testing fundamental computer science theory is important.

It’s not. Theory can be referenced. People do not work in a vacuum. Interviewing in eng is broken, but afaict its a “worst solution save all others” kind of scenario. But let us not begin to deem these intrinsically important. Some of the most creative and productive coworkers I’ve had struggled with leetcode style interviews. They’re a bad tool for anyone who isnt a new grad, and even then.

> It’s not.

Yes it is.

> Theory can be referenced

How do you know that the person is even able to comprehend theory?

> Interviewing in eng is broken, but afaict its a “worst solution save all others” kind of scenario.

That's your opinion.

> Some of the most creative and productive coworkers I’ve had struggled with leetcode style interviews.

Good for you. But "slumpt_'s most creative and productive coworkers" is not a good metric for hiring.

> They’re a bad tool for anyone who isnt a new grad, and even then.

Again, that's your opinion. I'm not a pro in those interviews, but studying DS and algos opened up and pushed my mind to its limits like nothing else. Your whole thinking process changes when you start working on this, you start thinking about constraints, performance implications, pro and cons of different approaches. It is called Computer SCIENCE for a reason.

Re: Dynamic Programming vs. Divide-and-Conquer (2018)

#45

Post by DaiPlusPlus »

Bancakes wrote: post #38
water8 wrote: post #2

The ratio of importance placed on these algorithm design in interviews vs the amount of times they actually come up in real world problems seems skewed IMO.

It's not just the algorithm, but the frame of mind to consider an optimisation. I guess it's a rare sight in the age of electron apps and cloud startups.

Oh c'mon...

Electron apps aren't slow, bloated, and awkward because the new junior SWE on the team used a O(n^2) tree-walking algorithm for the app's search feature - they're like that because it's inherent in using a general-purpose web-browser engine for your desktop GUI.

Micro-optimizing application software programs by implementing different algorithms is completely detached from the big engineering choices made at the very start of a project where the application's substrate and platform are chosen - and those decisions are made not with a view towards program computational efficiency, but primarily towards developer-productivity. Thanks to Electron someone who grew-up making websites as a teenager with little to no exposure to the horrendously unproductive and beginner-hostile world of MFC, GTK, and Qt can make an engaging and appropriate cross-platform desktop UI in under a day.

-----

If we want to see the Electron "problem" fixed, then the best solution is for the Electron team to figure out how to cut down their build of Chromium to remove all of the features unnecessary for trusted desktop applications (no, we don't need process isolation!). I'd love to see a build of Electron+Chromium with all of the JavaScript removed, so that it's a bare-bones HTML+CSS layout and rendering system, and have it wired-up to some OOP application binary (be it Java, .NET, C/C++, etc) which manipulates the DOM - I don't see why that should need more than a few dozen MB RAM and run in a single process.

Re: Dynamic Programming vs. Divide-and-Conquer (2018)

#46

Post by EvilEy3 »

nicoburns wrote: post #37
globular-toast wrote: post #27

Earlier quoted context omitted.

It depends what you're looking for. If you want someone who can turn the handle on your typical daily task then, sure, test them on your typical daily task. But if you want someone capable of developing solutions to brand new problems then it's not so easy and testing fundamental computer science theory is important.

There are plenty of people who have a fantastic knowledge of CS theory and are pretty useless at solving real world problems.

> solving real world problems

Define this first.

Re: Dynamic Programming vs. Divide-and-Conquer (2018)

#47

Post by piva00 »

globular-toast wrote: post #39
slumpt_ wrote: post #28

Earlier quoted context omitted.

It’s not. Theory can be referenced. People do not work in a vacuum. Interviewing in eng is broken, but afaict its a “worst solution save all others” kind of scenario. But let us not begin to deem these intrinsically important. Some of the most creative and productive coworkers I’ve had struggled with leetcode style interviews. They’re a bad tool for anyone who isnt a new grad, and even then.

When you apply for jobs do you simply look for "engineering" positions? Why am I always applying for software engineering and not electrical engineering? It's all engineering, and theory can be referenced, right? In fact, why doesn't everyone just buy a book and become a top engineer? The point is not (or shouldn't be) to recite a textbook. The point is you can navigate your way around the textbooks. I've got both Th…

This is a false dichotomy. Specific theory that is hard (and useless) to memorise all details can be easily referenced if you are knowledgeable enough in a field, if you know about a red-black tree, the gist of its properties you can easily Google usage cases if you've forgotten, examples of it and algorithms related to it (rebalancing, how it relates to search, etc.), if you had never studied, used or seen one there is no way to reference to these properties easily.

I'd much rather hire and work with someone who has the skill to easily assess a situation and use referencing to rebuild knowledge than someone who memorised how to implement tree balancing, so why do we test for the latter rather than the former?

Re: Dynamic Programming vs. Divide-and-Conquer (2018)

#48

Post by EvilEy3 »

lifthrasiir wrote: post #42
kryptiskt wrote: post #40

Earlier quoted context omitted.

I disagree. There are so much code out there that nest loops and become accidentally quadratic, where a little knowledge would have helped make it perform well at scale. Knowledge about the time complexity of algorithms isn't valuable only for people implementing libraries. Every single time you iterate over things or partition things by a predicate you are using the building blocks of algorithms to make a new custom…

There are only a few useful parts of the algorithm theory in practice. The time complexity is surely one of them, but it is still overvalued in a sense that the actual performance on the real hardware and realistic input distribution is more important. And when you actually need algorithms, you always have a luxury of existing literatures and implementations. Real-time algorithm design in the interview is very unreal…

> And when you actually need algorithms, you always have a luxury of existing literatures and implementations.

And how well that works in practice? How will candidate even know where to look at if he has no idea what he needs to find?

Re: Dynamic Programming vs. Divide-and-Conquer (2018)

#49

Post by thrower123 »

water8 wrote: post #2

The ratio of importance placed on these algorithm design in interviews vs the amount of times they actually come up in real world problems seems skewed IMO.

Software interviewing tends to be selecting for neurosurgeons, and then the job is putting them in a rickety ambulance with some steristrips and a shot of narcan.

Re: Dynamic Programming vs. Divide-and-Conquer (2018)

#50

Post by jorl17 »

DaiPlusPlus wrote: post #45
Bancakes wrote: post #38

Earlier quoted context omitted.

It's not just the algorithm, but the frame of mind to consider an optimisation. I guess it's a rare sight in the age of electron apps and cloud startups.

Oh c'mon... Electron apps aren't slow, bloated, and awkward because the new junior SWE on the team used a O(n^2) tree-walking algorithm for the app's search feature - they're like that because it's inherent in using a general-purpose web-browser engine for your desktop GUI. Micro-optimizing application software programs by implementing different algorithms is completely detached from the big engineering choices made…

People in these arguments always talk about the algorithms, but I think that entirely misses the point. It rarely is about the algorithms themselves, but, rather, it's about the data structures.

One is obviously tied to the other, but what I mean is that many slow apps are slow because the people just used the wrong data structure. Sometimes it's as simple and silly as using a list and constantly iterating over it instead of using a dictionary/KV-map. I think the idea with having people know about "algorithms" is to get them in a state of mind where they will automatically pick more appropriate data structures. I really don't remember how to implement RB-trees or AVL-trees, nor do I really know their pros and cons against each other at this moment (I have a very very faint idea), but I know they exist and I certainly have a better idea of when to use a tree versus a list, versus whatever.

Would I fail these interviews? Probably, unless I studied a bit, but do I think that the concepts that they ask about are pointless? No, not at all. I've looked at my fair share of legacy code bases built by subpar developers and the one thing that always pops up is the bad data structures chosen. Once we fix that, usually everything else automatically falls into place.

EDIT: To be clear, what I mean is that in most cases, just picking the right data structure, among the most basic and elementary data structures given to you by the language, is more than enough. Only in rare cases does one then have to go beyond that and carefully engineer a more precise algorithm. The data structures are way more than half the problem, in nearly every application.

Post reply on HN