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

Re:Dynamic Programming vs. Divide-and-Conquer (2018) by kryptiskt on Sunday April 25, 2021 @07:01AM (#26931841)

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 algorithm, and knowledge of the theory will help you avoid bad performance.

All nested loops are harbingers of algorithmic doom, and should be treated as such, and they come up all the time in real code.

[ Parent | on HN ]

Re:Dynamic Programming vs. Divide-and-Conquer (2018) by lifthrasiir on Sunday April 25, 2021 @08:16AM (#26932152)

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.

[ Parent | on HN ]

Re:Dynamic Programming vs. Divide-and-Conquer (2018) by EvilEy3 on Sunday April 25, 2021 @08:29AM (#26932220)

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

[ Parent | on HN ]

Re:Dynamic Programming vs. Divide-and-Conquer (2018) by lifthrasiir on Sunday April 25, 2021 @09:10AM (#26932420)

> How will candidate even know where to look at if he has no idea what he needs to find?

That happens all the time, not just for algorithms. I don't expect candidates to know every possible algorithm (as I surely don't), I expect candidates to identify and learn what's required for the task. A knowledge of the specific algorithm is not of much value. The ability to learn and possibly implement algorithms is.

[ Parent | on HN ]

Re:Dynamic Programming vs. Divide-and-Conquer (2018) by EvilEy3 on Sunday April 25, 2021 @09:23AM (#26932501)

> I expect candidates to identify and learn what's required for the task

And that comes for free in people who spent time on Algorithms and Data Structures.

[ Parent | on HN ]

Re:Dynamic Programming vs. Divide-and-Conquer (2018) by lifthrasiir on Sunday April 25, 2021 @09:31AM (#26932563)

Yes, I haven't said that you should not learn algorithms. The best way to learn that skill is to learn (some) algorithms; DP is particularly worthwhile to learn because it is pretty hard to invent by one's own. But as an interviewer I would spend more time to check the general ability to adapt than the algorithmic knowledge.

[ Parent | on HN ]

Re:Dynamic Programming vs. Divide-and-Conquer (2018) by specialist on Sunday April 25, 2021 @10:46AM (#26933113)

Then shouldn't the interview focus on identifying and mitigating those problematic nested loops?

For day jobs, I've done very little computer science relevant work. Instead, it's communication, coordination, code maintenance, infrastructure, verification, managing upwards, ad nauseum.

That includes greenfield development, when I invented entirely new solutions to old problems. Even during the bursts of hardest parts (creatively), the algorithms and such were maybe 5% of the effort.

[ Parent | on HN ]