Dynamic Programming vs. Divide-and-Conquer (2018) | Hacker News Reader

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

trekhleb.dev

214 pointstrekhleb115 comments

i'm late to the comments but hopefully this helps someone:

i struggled with DP as much as anyone. i read all of the standard resources (CLRS, vazirani, kleinberg, etc), watch all the youtube videos, did all of the practice problems in the books, and still couldn't solve the kinds that are asked on interviews. i even went as far as emailing kleinberg for help.

what made it basically unconsciously fluent for me (i.e. i can read a problem statement and sketch out the recursion and subproblems in about 60s and then just perform fixup) was doing hordes of them on leetcode in preparation for a FB interview. it got to the point where i could solve hard ones in about 5 minutes using either bottom-up or top-down (i.e. memoization). so if you're struggling with DP for interviews my suggestion (which is basically the standard suggestion) is to just grind the problems on leetcode.

and contrary to popular belief they do come up outside of interviews - i had to solve a circuit synthesis problem last week and it turned out to be basically DP substring counting problem. took me all of 5 minutes.

brute force recursive solution + @lru_cache annotation.

works for me every time on leetcode.

I've solved some DP problems (I call it: "find the right table/array and then decide whether you feel recursive or iterative").

I know about lru caches.

Yet, I'm not fully understanding what your implying with your comment.

Op's saying (I think) that the difference between brute force recursion and DP ( top down ) is memoization, and that the language / library construct lru_cache will perform that memoization for you.

Its not a fascinating insight. If you can express a problem as a recursive brute force solution and there's a least a little recalculation involved, you're one step from DP. The lru_cache just does that step.

Just google lru_cache

edit: "op"

it is a particular part of the Python 3 standard library. it is one extra line of code to automatically memoize a recursive function.

you just do:

    from functools import lru_cache
    
    @lru_cache(maxsize=None)
    def brute_recursive_func(x):
        ...

And you're good to go.

Very nice! I often forget this handy thing during interviews. Good thing to impress your interviewer with :)

One thing of note: The arguments to the method you are memoizing need to be hashable. For example, if you want to memoize a method call whose parameters include a list, you will get an error!

everyone always says this as if it's some kind of galaxy brain epiphany. it's not because

1) on interviews they want you to explicitly construct the array very often i.e. it's the different between hire and a strong hire exactly because @lru_cache is much easier

2) you can easily blow the stack for real production grade implementations using recursion (think edit distance for genome sequences). you also lose time actually doing the recursion. on the other hand, it's easier to prune the search space with explicit recursion vs tabulation.

edit: btw i'll also say that dynamic programming proper, i.e. as a technique for solving optimization problems defined by recurrence relations, uses tables and recursion (fixed points). so good luck understanding something like the linear quadratic regulator if you think it's just @lru_cache

https://berkeley-me233.github.io/static/ME233_Sp16_L1_DP_Opt...

> on interviews they want you to explicitly construct the array very often i.e. it's the different between hire and a strong hire exactly because @lru_cache is much easier

are you serious? someone really asked you to "use array". Beyond stupid if they really did.

> you can easily blow the stack for real production grade implementations using recursion

recursive solution doesn't automatically mean using a the method stack. you can implement recursive solutions using explicit stack .

> dynamic programming proper

please. There is no "proper" dynamic programming. Please watch this MIT intro https://www.youtube.com/watch?v=OQ5jsbhAv_M .

you're wrong on all counts but i'm going to be the one to correct you.

Nah, you're the one whose wrong on this one.

You both made some great points

> are you serious? someone really asked you to "use array". Beyond stupid if they really did.

Google interview. Explicitly told me not to use recursion.

It's not stupid to use an array, because it's the most natural data structure for representing one, two or more variables that can have different ranges and capturing their values.

For example, if I have a function 'foo(a, b, c)' and I am using subproblems whose solutions use smaller values of a, b, and c, then the most natural solution is to tabulate the solutions in a 3-d array with the (fixed) values of a, b, and c indexing into the 3-d array to get at the (solved) subproblem.

It's of course also fine to use a hash table to construct the triplet (a, b, c) and use it as the key to store (and look up) the solution to the subproblem that corresponds to the particular value of (a, b, c), and most reasonable interviewers would be happy to accept this as a valid approach.

As for recursive solutions automatically using the method stack, the overwhelming majority of programming languages provide the ability to do this, and the generally accepted understanding is that if you use this facility, you are using automatic recursion, letting the compiler/machine/runtime maintain the stack for you. The generally accepted terminology when you explicitly allocate your own stack is 'iterative'.

Also, the generally accepted terminology is 'Dynamic Programming' == 'Bottom-up tabulation', and 'Memoization' == 'Top-down recursion with caching to avoid solving the same subproblem'.

Take a problem that you could brute force. Does it have repeating sub problems? If so, it's a candidate for DP.

DP and Greedy problems are the hardest to nail because they are the broadest and widest category of problems. Almost everything can be a DP problem.

DP is basically brute-force but you can reuse some of the subproblems.

Another approach is trying to find a "starting point" and solving subproblems. Imagine an array of problems and starting at the left.

>DP is basically brute-force but you can reuse some of the subproblems.

this is like saying

"integration is basically weighing a bunch of buckets but the buckets are really small"

cool but that won't help you find the correct trig sub to perform the integral. anyone that's familiar with the calc grind knows getting a good grade for the anti-derivative (indefinite integral) module is about the number of exercises you've done rather than the conceptual understanding.

I don't think the comparison is accurate. The subproblem explanation of DP immediately lends itself to a strategy for solving problems: come up with a brute force solution then look for where you are duplicating where, i.e., how can a hash table help me? Even if there is a more efficient way to do things in the end than a hash table, I find it easier to go from brute force, to hash table, then finally look at it and see if I can optimize it further.

> "integration is basically weighing a bunch of buckets but the buckets are really small"

> cool but that won't help you find the correct trig sub to perform the integral. anyone that's familiar with the calc grind knows getting a good grade for the anti-derivative (indefinite integral) module is about the number of exercises you've done rather than the conceptual understanding.

I am a mathematician and teacher of mathematics.

Understanding the first point is way more valuable than teaching the second. I have to ask and grade trigonometric-substitution problems for my Calculus II class because the curriculum includes it, but I'd way rather have a student come out of my class with a solid understanding of why your quoted statement about integration is true than to be able to find just the right substitution but have no idea why. They can look up the trigonometric-substitution stuff when they need it.

But we're not talking about hypothetical pedagogy here. Exams cover usub and trig sub and methods of partial fractions. In fact we're not even talking about calc at all but software interviews, which, like or it not, examine tricks.

That's exactly how I approach these problems: I think that's a hard problem so how about just a brute force solution first to validate correctness? Then a few minutes later you realize the repeated subproblem structure and turn brute force into DP.

They can even come up completely outside of work. I recently had an optimization problem come up around the house that could have been straight out of an exam. Here it is:

Tzs wants to install gutter guards on his house and detached garage. His garage has two 29' straight gutters, and his house has two straight gutters of 43' and 19', and one L-shaped gutter with arms of 19' and 18'.

The guards tzs is going to use [1] are available from Home Depot in 3 ft and 4 ft sections. The 3 ft ones are sold in boxes of 13 for $79.97. The 4 ft ones are sold in boxes of 20, 10, or 3 for $139.97, $99.97, or $39.16.

To cover a gutter, you need slightly more length of guard than length of gutter. You cut off the rails on the end of the guards at the ends of the gutter, leaving a few inches of mesh that you can tuck down into the gutter to keep stuff from getting in through the ends. Assume that the section you cut off is waste.

Question 1: What boxes of guards should tzs buy to cover all his gutters for minimum cost, assuming he needs 3" of mesh at the ends to cover the sides? For the L shaped gutter, assume it effectively has 3 ends.

Question 2: The only ladder tzs has is a 6 ft step ladder. This is sufficient for installing the guards on the front side of his garage. It is not sufficient for anyplace else. To do the rest of the house, at a level of ladder safety he is comfortable with, will require buying at least one new ladder for $260, and might require a second new ladder for $129. Before committing to that, he is considering doing a test on the front of the garage.

If he buys one 13 pack and uses 10 of them on the front of garage, and then decides from there to go ahead with doing all the rest, what boxes should he then buy to finish the project taking into account the 3 leftover 3 ft segments? How much, if any, does this add to the minimum total project cost?

Question 3: the prices given earlier were actually sale prices for the 20 pack and 13 pack. If they go back to normal prices, which are $160.97 and $88.83, how does that change things?

Question 4: Due to rapidly sloping ground behind the garage, tzs has not been able to figure out a way to reach more than about half the gutter there. He is thinking of just not bothering with it. There are a lot of weeds and wildflowers and such in that area, so it doesn't really actually matter much if the gutters are clogged and the water just runs off the edge--it will just land on plants so won't erode the soil, and there is no basement or crawlspace under the garage for the water to leak into.

How do all the previous answers chance if the back garage gutter is omitted? If tzs figures out a way to actually reach the damn thing later, what will be the incremental cost to add that?

Question 5: When you cut an end segment, sometimes the waste piece can be significant. For example, suppose you have 1 ft to cover at the right end of a gutter and use a 3 ft segment. You might cut that segment 1 ft from the left end, and cut the mesh 4" to the right of that to get the mesh flap to fold over the gutter end. That leaves you with a 2ft segment with 4" of missing mesh. You could cut the rails 4.5" from the left of that (4.5" rather than 4" because the mesh needs to be slightly longer than the segment to overlap the adjacent segment). That would leave with a 1.75' segment that could be used just like any other segment.

Can you adapt your algorithm for finding minimal cost to take into account these small, usually non-integral, segments that would be produced as a by product of dealing with gutter end points?

Question 6: Can you adapt your algorithm to handle the possibility of purposefully breaking a long segment down into shorter segments, with the algorithm determining the optimal set of short segments to make? Assume that at each place you split a segment you loss 1" of total length due to the need for overlapping adjacent meshes.

[1] https://www.gutterglove.com/

> i read all of the standard resources (CLRS, vazirani, kleinberg, etc), watch all the youtube videos, did all of the practice problems in the books, and still couldn't solve the kinds that are asked on interviews. i even went as far as emailing kleinberg for help.

I dread at the thought of coming across you in an interview loop some day.

You dread the thought of coming across someone who mastered a challenging technique? Ok

Yeah, when the challenge is dynamic programing and the goal is a FAANG job.

I don't mean it as a put down, but it is a realization of my own how much the field has moved on since the last time I applied for a programer job.

fwiw I don't ask dp questions on interviews and most of FB doesn't either (I didn't know that before I got hired)

I’m currently working through Leetcode now. I’m really taking the time to understand the various solutions with the goal of bettering myself as a software engineer. It’s honestly just fun working on the problems.

Anyways, did you get the FB job?

>Anyways, did you get the FB job?

Yup

It should be noted that FB stopped using DP problems in interviews for this very reason (they measure how much you've practiced rather than innate intelligence).

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 would argue that it's a pretty good measure of programming and CS problem solving skill with weak alternatives.

Most of these types of algorithms already have tons of research available online as people try to figure out what the lower bound of optimization is. It's far more telling to just talk about previous projects the person has worked on to gauge their level of competence. Asking them to explain why they made the choice they did vs trying to see how much they can memorize tests two different skill sets. The person who makes better choices is the one you want to hire.

How does someone talking tell you if they can actually do basic programming... I think you would be surprised at the number of people that apply for software engineering jobs but barely know how to program.

To be fair, I know a fair number of people who are good at competitive programming but are absolutely awful at writing maintainable code.

Yeah, competitive programming forces you to use short variable names and write makeshift code which is fast enough to pass all the test cases ...

Yeah, those competitions are not really representative of actual skill.

I was into competitive math as a teenager and was somewhat successful, but I actually kind of suck at math.

Similarly, I'm a professional developer but I'm really bad at competitive programming: what usually happens is that I know how to solve the problems but the time limit is too low (for me, at least).

I'd say success in competitions is a good indicator of dedication and perseverance, but not sufficient to spot someone who's good at the job.

By the same way we have doctors do surgery in place, construction workers do a toy house, teachers give a class for free, cooks spend one day serving meals for free,...

Because you can determine if they organize and test things in a repeatable and maintainable way or do they have trouble organizing structures and make questionable performance decisions. Are they clear on the hasA vs isA. Do they know what a mutex or static scope is? These are the things that will cause huge debugging nightmares. Syntax issues are no where close to as problematic so why use whiteboards vs an actual computer? In my experience of interviewing, questions about Security and Threading(performance / micro-opts) are good for separating the wheat from the chaff.

Are these mutually exclusive? I've never been through an interview that didn't ask questions about previous work regardless of how the technical test was structured.

You'd think so, but from my experience the folk that are very interested in algorithmic design and so forth produce highly abstract and hard to understand solutions to simple problems, which, in the end, are the majority in the regular dev work.

Sure if you're applying for a job that really demands algorithmic design skills it should be a great asset but in general the most valuable skills any programmer has is producing simple and robust code that works and others can continue building on. I don't deny that knowing algorithmic design skills well helps a lot but it does seem to feed the egos of the programmers to produce overly complicated solutions.

This is a nice point -

I'd answer this type of algorithm question in truth by identifying the relevant library wherever possible, not by coding it myself, and I'd strongly expect anyone I was working with to do the same.

"I always code my own AES libraries because I'm an expert" - said no expert ever.

It's much better to give a candidate a simplified version of your typical daily task. Give them enough time so they can google and learn if needed. That usually means very simple task that you could solve in hour or two at your leisure at home.

Now, I do get that there's a lot of people who don't like spending time at home for interview tasks but when you think about AND it's not skewed to extreme (say, big task 8 working hours worth) then, in terms of time wasted, it's not such a big difference. Interviewer can then see the code quality, can talk about it with candidate, clarify some missing pieces or pitfalls found, etc.

IMHO most important is not if the candidate knows how to solve some hard or even medium problem when I speak to them and they are stressed enough already. What is important is if they're willing to learn, if they know how to search for stuff they may not know and if they can produce performant enough, but excellent to read, code.

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.

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 The Art of Computer Programming and The Art of Electronics on my shelf. I could find the sections to help sorting a list in seconds. As for the latter, I have no idea why the majority of that book even exists. I can't call myself an electrical engineer, even though all the theory I need is within arm's reach.

I assume you're arguing against the "recite the textbook" approach. I would agree that this is not the way to do things. But equally, "throw the textbooks out" is not the right way either. We need to evaluate a high-level grasp of the literature/theory but don't punish for forgetting minutiae. I might ask a candidate to talk about choice of sorting algorithms. There is, of course, no perfect answer, but what I'll be expecting is general evaluation of algorithms: time/memory tradeoffs, probing for more domain knowledge (e.g. does the data often come in sorted or random), platform constraints etc. I won't even expect a name drop of an actual sorting algorithm as that's not really the point. What they're telling me is they know why Knuth has a whole chapter on sorting. That's the important thing.

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?

Some companies want to test if a person spent time preparing for the interview. So asking all those quiz questions does make sense even if they are no relevant. At least it shows that the person knows the rules of the game and is willing to invest substantial efforts to follow them even if the rules are arbitrary and irrelevant for day-to-day activities.

Okay. So arbitrary preparation - when nearly any other professional interview requires little preparation beyond updating your resume - has merit because... rules of the game?

Stop supporting baseless metrics for assessment just because some old person used them before you showed up. We can and should do better.

This is how it is with IT companies paying well above average. Given that they are able to pay such salaries this interview strategy is compatible with big profits.

It could be that by changing interview strategy to look more similar to other professions that profit can be increased even farther, but nobody is risking it.

I’ve worked at several shops paying well above average with interview processes that hinged on more representative work.

Not everyone is playing the absurdly doofy “game,” just most.

Local maximum that laziness has us trapped in. Nothing to do with merit.

I can use your argument to push to another side: wouldn't this strategy also tell us a huge bias that it is selecting for and presenting itself in tech companies? With that I mean the bias of "learning to play the game", selecting for people that are going to conform to arbitrary rules for their promotions, caring about playing the game instead of analysing the impact of their work?

And I can ask that given the recent issues with data privacy and data abuse by the tech giants, would we be in this place if the interview processes had selected for more holistic engineers, technically able but that refuse to play the game just for the sake of playing the game, that are opinionated and don't conform to something just for the sake of money?

I know that I might be creating a false dichotomy but I would like to think about what kind of pressure this selection process creates, what biases arises from it? How can we make it better?

Because your argument is the most conservative and pro-establishment one: it works so don't touch it and just emulate.

I was not arguing for these types of interviews. My point was that one can rationally explain apparently useless quiz questions. And yes, this is a strong selection bias to pick people that agree to play by arbitrary rules without questioning them.

Being able to refresh one’s memory / reference previously learned approaches is not akin to learning them from scratch. Your opener is preposterous.

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

The person who's going to come up with new idea's isnt spending their time memorizing old ones. They learn to index where to retrieve knowledge when necessary in order to allow them to cover a wider breadth of knowledge. And this will allow themand to pick the best one for the job at hand as opposed to the tool they are an expert in. Sometimes you need a handyman instead of a master plumber because they are better able to see the big picture beyond all the shit.

My best coworkers is about as good of a metric as things that “stretched your mind to its limits.”

The point is neither is demonstrated to bear any relationship to jack shit

Interviewing is and has been broken, even with the changes we’ve made over the years.

If you’re holding onto leetcode challenges that make you think hard as representative of engineering prowess we’re never going to have a reasonable conversation.

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.

> solving real world problems

Define this first.

changing color of a button in an Electron app, or moving JSONs back and forth (from backend to frontend)

It's a much better measure of how many leetcode DP problems you solved while grinding interview prep. I'd argue it's a pretty poor measure of software engineering ability.

i believe the claim is the ability to understand these algorithms vs understand business problems is not.

Yeah, interviews should really be asking more questions about graph algorithms instead. Those are so much more useful.

I do mostly not too sophisticated web apps and binary search and minimum edit distance do come up regularly. I agree you don't have to remember the implementation details, but you have to know they exist and which problems they solve.

But that doesn't mean you need to be able to implement them though. Shouldn't having a high level knowledge about these problem be enough if all you are doing is building apps.

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.

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.

"Bad programmers worry about the code. Good programmers worry about data structures and their relationships." —Linus Torvalds

I think you hit the nail on the head. Data structures are so much more important than throwing more threads at the problem. Someone could write beautiful lock-free code but choose a ring buffer (lock free queue) instead of a concurrent set and it's all for not.

If one implements a low-level code, then one has freedom to pick good data structures. But when writing GUI apps there is simply no such freedom as data structures are already defined by libraries.

For example, a GUI framework typically uses a notion of widget tree that is fundamental to the library design. But the end user UI does not look as an arbitrary tree with deep nesting. It is easy to see that using a tree for this leads to extreme denormalization of data. Normalizing that to a relational form should remove a lot of duplication and code (often hidden) to synchronize that duplicated state. But try that with a popular framework. It is not doable in practice. So one sticks with tree architecture and its inefficiencies.

> Sometimes it's as simple and silly as using a list and constantly iterating over it instead of using a dictionary/KV-map.

It's pretty easy to walk away from an algorithms course with the very basic intuitive understanding that "dictionaries trump all other data structures." Certainly that misses out on all of the cases when hash maps are a liability, e.g. when dealing with sequential data, but most questions end up being pro-dictionaries anyway.

A dictionary is an interface, not a structure.

Hashmaps, priority-queues/heap-trees, and others are all wildly different approaches of implementing a dictionary - all with their own different Big-O characteristics.

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

¿Por qué no los dos? If we're going to implement a desktop GUI via a general-purpose web browser, it should at least be as fast as a generic webpage.

Chromium supports a single process switch at least to use for development of Chromium itself. While it does reduce memory consumption, it does not help much. All data structures in Chromium are tailored for multi-process case with no memory sharing. Replacing processes with threads do not change that.

As for removing V8 JS engine from blink I guess it is possible. But again, blink is tailored for accessing from JS and the layout and rendering code is huge so one does not save much.

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.

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.

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

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

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

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.

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.

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.

A good history about how bellman came up with this name

https://en.wikipedia.org/wiki/Dynamic_programming#History

Btw people should read his books, they'll be surprised.

If anyone is interested, I recorded a beginners course about Dynamic Programming during the lock-downs: https://www.youtube.com/playlist?list=PLVrpF4r7WIhTT1hJqZmjP...

The paradigmatic example of a DP algorithm for me is the simple DP solution of the 0-1 knapsack problem, which, although because of NP-hardness of the general case, becomes infeasible on many easily constructed cases, actually performs pretty well on many non-artificial examples.

It's an example of what the article calls bottom-up dynamic programming, but I think it is a poor example of divide-and-conquer, because it naturally fits the following purely functional form:

h(foldr f a weights)

where weights is the problem, expressed as a list of (item, weight) pairs, and f, h and a are subfunctions. This is a pretty paradigmatic non-divide-and-conquer form in functional programming: it's a one-at-a-time iteration through the list expressing the problem

So while I think this is good article with plenty of food for thought, I reject the central claim.

The example given in the article for bottom-up DP is edit distance, unless you're referring to something I missed?

I was commenting on the high-level claims of the article, not the specific algorithms the article describes. When you move from the article's example of a DP algorithm to the simple implementation I sketch of the 0-1 knapsack problem, the claim that DP is a kind of divide-and-conquer looks harder to sustain.

Yes, agreed. The examples seem fine to me as far as DP is concerned, but the claim of divide and conquer is a bit weird

Looks great, bookmarked.

A big problem with explaining/learning this area is the name. Names are important but unfortunately the name "dynamic programming" is, according to the people responsible for choosing the name, just BS that they made up one day for their employer.

> unfortunately the name "dynamic programming" is, according to the people responsible for choosing the name, just BS that they made up one day for their employer.

For people interested, Richard Bellman who apparently came up with the name, put down the story in his autobiography which is cited on wikipedia: https://en.wikipedia.org/wiki/Dynamic_programming#History

"I spent the Fall quarter (of 1950) at RAND. My first task was to find a name for multistage decision processes. 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". I’m not using the term lightly; I’m using it precisely. His face would suffuse, he would turn red, and he would get violent if people used the term research in his presence. You can imagine how he felt, then, about the term mathematical. The RAND Corporation was employed by the Air Force, and the Air Force had Wilson as its boss, essentially. Hence, I felt I had to do something to shield Wilson and the Air Force from the fact that I was really doing mathematics inside the RAND Corporation. What title, what name, could I choose? In the first place I was interested in planning, in decision making, in thinking. But planning, is not a good word for various reasons. I decided therefore to use the word "programming". I wanted to get across the idea that this was dynamic, this was multistage, this was time-varying. I thought, let's kill two birds with one stone. Let's take a word that has an absolutely precise meaning, namely dynamic, in the classical physical sense. It also has a very interesting property as an adjective, and that is it's impossible to use the word dynamic in a pejorative sense. Try thinking of some combination that will possibly give it a pejorative meaning. It's impossible. Thus, I thought dynamic programming was a good name. It was something not even a Congressman could object to. So I used it as an umbrella for my activities."

I originally had trouble with this term because I learned about it after learning the unrelated (afaict) terms "dynamic programming language" and "dynamic typing". So perhaps it's not so much that dynamic programming was a bad choice when it was named, but that we've overloaded the term "dynamic" too much since then.

Hang on, did you read the quote above from the guy that named it?! He says explicitly that he chose it not because it was accurate but because non-technical employers/funders would be unlikely to object since it sounds positive. Does that not meet your definition of "bad choice" for a technical term?

"dynamic programming language" means a "dynamically typed" language; and "dynamically typed" means the types are acquired at run time, and vary at run time according to run time events. So "dynamic" is a good choice there in that it is consistent with the use of the word outside programming.

Merge sort seems to be a more classic example for divide-and-conquer which involves merging the results from two subproblems.

i personally like quick sort because it leads to understanding other divide and conquer algorithms like finding the kth order statistic.

This is really good. Much more understandable explanation than anything I have read, or seen, about DP before.

The diagrams in this article are excellent. Does anyone know what the author used to make them?

Powerpoint I'm guessing?

I made them in draw.io

Awesome, I had no idea this existed and was free! Recently had to do a few diagrams and Google Drawing is just too basic so ended up using Lucidchart, but for the tiny amount of diagramming I do, it’s too pricey. This looks perfect so thanks for sharing.

Also I thoroughly enjoyed your post, well done on explaining a potentially complex area so clearly - I’ve signed up for future posts!

Cool! I’m glad that the link was useful! Another alternative that I’ve been using and that I liked is https://sketch.io/sketchpad/. Also pretty good tool (online and free)

Also https://whimsical.com/ and https://miro.com/ are great for beautiful diagrams!

Thanks for that! :)

Nicely done. You have a gift for technical communication.

DP and DC there's lot left to learn but feels like you learnt so much already...

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?

My understanding why this is usually not discussed is the following: The fibonacci sequence is usually used as an illustrative example or motivating problem for a given topic, not as a problem in itself. I believe a side note might most likely detract from the overall point for a technicality.

For the same reason you only wrote "if you consider exponentiation to be a constant time operation" instead of including a side analysis of how everything changes once you can't do that anymore, possible problems with accuracy of floating point representations of phi and it's exponentiation and everything else one has to consider once we leave the comfortable home of architecture native integers.

It is usually very valid to do so.

Why are you assuming exponentiation is constant time? For machine integers it near-enough is, but there are fewer than 100 Fibonacci numbers that fit in a 64-bit integer so you may as well use a lookup table. For arbitrary precision integers it definitely isn't.

I think that what the author calls "divide and conquer" is actually "recursion".

Also the complexity of naive fibonacci is exactly the fibonacci sequence so O(2^n) is correct but less precise than O(phi^n)

"Recursion" is part of the "how" of the "why" of "divide and conquer" :P

Recursion is not the same as divide and conquer. Divide and conquer is a category of algorithms that you would often implement with recursion, but you don't have to.

For example, consider the bottom-up implementation of merge sort [1]. This implementation is not recursive, but merge sort uses divide and conquer regardless of whether or not you implement it top-down or bottom-up.

On the other hand, the naive fibonacci implementation that runs in exponential type is recursive, but it does not use divide and conquer.

[1]: https://en.wikipedia.org/wiki/Merge_sort#Bottom-up_implement...

All recursion can be translated into a loop and a stack. In the tail recursive case you don’t even need a stack, a loop would suffice.

That means all divide and conquer algorithms can be implemented without recursion.

Seems you got down-voted. I guess you're doing competitive programming? People that are good at CP never call "recursion with memoization" as "divide and conquer". Yeah, they just call it recursion.

"Divide and conquer" in CP world seems to be specific to those problems whose subproblems are not overlapping (therefore completely "divided"), e.g. merge sort, segment trees.

Considering the classic problem "Tower of Hanoi", is it "divide and conquer"? No to CP people, and even Wikipedia [0] does not explicitly regard it as "divide and conquer".

[0]: https://en.wikipedia.org/wiki/Tower_of_Hanoi

Reply on news.ycombinator.com