[HN Gopher] Dynamic Programming vs. Divide-and-Conquer (2018)
___________________________________________________________________
Dynamic Programming vs. Divide-and-Conquer (2018)
Author : trekhleb
Score : 195 points
Date : 2021-04-25 06:11 UTC (16 hours ago)
(HTM) web link (trekhleb.dev)
(TXT) w3m dump (trekhleb.dev)
| codetrotter wrote:
| This is really good. Much more understandable explanation than
| anything I have read, or seen, about DP before.
| chalst wrote:
| 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.
| thealig wrote:
| The example given in the article for bottom-up DP is edit
| distance, unless you're referring to something I missed?
| anon_tor_12345 wrote:
| 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.
| crazypython wrote:
| 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.
| kccqzy wrote:
| 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.
| anon_tor_12345 wrote:
| >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.
| JadeNB wrote:
| > "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.
| slaymaker1907 wrote:
| 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.
| jorblumesea wrote:
| 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.
| tzs wrote:
| 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/
| tnel77 wrote:
| 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?
| anon_tor_12345 wrote:
| >Anyways, did you get the FB job?
|
| Yup
| dominotw wrote:
| brute force recursive solution + @lru_cache annotation.
|
| works for me every time on leetcode.
| anon_tor_12345 wrote:
| 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...
| dominotw wrote:
| > 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 .
| anon_tor_12345 wrote:
| you're wrong on all counts but i'm going to be the one to
| correct you.
| Der_Einzige wrote:
| Nah, you're the one whose wrong on this one.
| BeetleB wrote:
| > 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.
| rmk wrote:
| 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'.
| [deleted]
| mettamage wrote:
| 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.
| jvanderbot wrote:
| 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"
| currymj wrote:
| 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.
| rmk wrote:
| Very nice! I often forget this handy thing during
| interviews. Good thing to impress your interviewer with
| :)
| mavelikara wrote:
| > 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.
| anon_tor_12345 wrote:
| You dread the thought of coming across someone who mastered a
| challenging technique? Ok
| mavelikara wrote:
| 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.
| anon_tor_12345 wrote:
| 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)
| da39a3ee wrote:
| 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.
| ketzu wrote:
| > 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."
| rory wrote:
| 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.
| water8 wrote:
| 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.
| thrower123 wrote:
| 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.
| Bancakes wrote:
| 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.
| DaiPlusPlus wrote:
| 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.
| fpoling wrote:
| 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.
| jorl17 wrote:
| 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.
| water8 wrote:
| 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.
| Apocryphon wrote:
| > 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.
| sidpatil wrote:
| "Bad programmers worry about the code. Good programmers
| worry about data structures and their relationships."
| --Linus Torvalds
| fpoling wrote:
| 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.
| zozbot234 wrote:
| > 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 que 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.
| tarsinge wrote:
| 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.
| philips4350 wrote:
| 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.
| kryptiskt wrote:
| 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.
| specialist wrote:
| 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.
| lifthrasiir wrote:
| 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.
| EvilEy3 wrote:
| > 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?
| lifthrasiir wrote:
| > 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.
| EvilEy3 wrote:
| > 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.
| lifthrasiir wrote:
| 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.
| aliceryhl wrote:
| Yeah, interviews should really be asking more questions about
| graph algorithms instead. Those are so much more useful.
| mightymercado wrote:
| I would argue that it's a pretty good measure of programming
| and CS problem solving skill with weak alternatives.
| tekkk wrote:
| 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.
| teachingassist wrote:
| 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.
| water8 wrote:
| "I always code my own AES libraries because I'm an
| expert" - said no expert ever.
| wst_ wrote:
| 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.
| globular-toast wrote:
| 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.
| nicoburns wrote:
| There are plenty of people who have a fantastic knowledge
| of CS theory and are pretty useless at solving real world
| problems.
| globular-toast wrote:
| 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.
| EvilEy3 wrote:
| > solving real world problems
|
| Define this first.
| slt2021 wrote:
| changing color of a button in an Electron app, or moving
| JSONs back and forth (from backend to frontend)
| slumpt_ wrote:
| 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.
| globular-toast wrote:
| 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.
| piva00 wrote:
| 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?
| fpoling wrote:
| 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.
| EvilEy3 wrote:
| > 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.
| water8 wrote:
| 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.
| paraph1n wrote:
| 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.
| water8 wrote:
| 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.
| fakename11 wrote:
| 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.
| pjmlp wrote:
| 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,...
| water8 wrote:
| 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.
| saagarjha wrote:
| To be fair, I know a fair number of people who are good
| at competitive programming but are absolutely awful at
| writing maintainable code.
| qsort wrote:
| 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.
| Flex247A wrote:
| Yeah, competitive programming forces you to use short
| variable names and write makeshift code which is fast
| enough to pass all the test cases ...
| beforeolives wrote:
| 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.
| waynesonfire wrote:
| i believe the claim is the ability to understand these
| algorithms vs understand business problems is not.
| [deleted]
| andreygrehov wrote:
| If anyone is interested, I recorded a beginners course about
| Dynamic Programming during the lock-downs:
| https://www.youtube.com/playlist?list=PLVrpF4r7WIhTT1hJqZmjP...
| tracyhenry wrote:
| Merge sort seems to be a more classic example for divide-and-
| conquer which involves merging the results from two subproblems.
| Labo333 wrote:
| 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)
| slver wrote:
| "Recursion" is part of the "how" of the "why" of "divide and
| conquer" :P
| aliceryhl wrote:
| 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...
| limoce wrote:
| 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
| neonological wrote:
| 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.
| lokesh1729 wrote:
| A good history about how bellman came up with this name
|
| https://en.wikipedia.org/wiki/Dynamic_programming#History
| agumonkey wrote:
| Btw people should read his books, they'll be surprised.
| goldenkey wrote:
| 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?
| ketzu wrote:
| 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.
| bidirectional wrote:
| 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.
| lokesh1729 wrote:
| DP and DC there's lot left to learn but feels like you learnt so
| much already...
| Veen wrote:
| The diagrams in this article are excellent. Does anyone know what
| the author used to make them?
| [deleted]
| lasfter wrote:
| Powerpoint I'm guessing?
| trekhleb wrote:
| I made them in draw.io
| tomduncalf wrote:
| 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!
| trekhleb wrote:
| 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)
| the_arun wrote:
| Also https://whimsical.com/ and https://miro.com/ are
| great for beautiful diagrams!
| specialist wrote:
| Nicely done. You have a gift for technical communication.
___________________________________________________________________
(page generated 2021-04-25 23:02 UTC)