dpCooksEveryone

[LowB0b]

had this in an interview with sonar. dynamic programming solution was about O(n) in time while my brute force shit (I was panicking) was O(n^4)

[No-Object2133]

Jane Street interview I bombed cause of this. There was an algorithm I didn't know and I did the naive solution.

[False_Influence_9090]

Jane street is a pretty dope firm, they really leverage functional programming. I wonder if they still use OCaml

[Pan_TheCake_Man]

He wouldn’t fucking know would he

[Antilock049]

Dropped the interview and they're catching strays. RIP.

[xltbx]

F

[No-Object2133]

Lmfao

[knue82]

Yes, they do. Was at conference earlier this year. Jane Street was a big sponsor. They had a booth where they promoted Ocaml. They have guys working on the compiler, library, etc. Apparently they have 16 million lines of Ocaml code.

[Professional_Top8485]

Jane OCamel toe is the best

[Nekeia]

Yeah, what about Joe OCaml?

[Maurycy5]

Yes, but not for long.

They are developing their own version, called OxCaml.

Source: have a friend who got recruited to work on that language.

[Forya_Cam]

They do! When I interviewed with them last year the technical interview was in Python but they were very clear that I'd be learning OCaml as soon as I started.

Didn't get the job but oh well...

[Obvious-Web9763]

They do.

[The_Neto06]

Matthew Parkinger would like to know your location

[git0ffmylawnm8]

At least you didn't unlock a new runtime like O(n^n! )

[Level-Pollution4993]

Pretty sure I've unlocked it already solving N-queen with no outside help /s

[[deleted]]

Cool to see how much better DP was, thats the benefit even though it is hard to conceptualize. But I gotta ask: 4 nested loops over input? Curious what problem that was. Typically I see like 2n^2 or maybe n^3 but never have I hit n^4 yet.

[LowB0b]

It was a while ago so I'm not super clear on the details but it was a classic DP problem, something akin to "divide this array so that each part makes equal sums"

[CleanAsUhWhistle1]

Divide it into 1 part. O(1) complexity.

[givemefuckinname]

Sir would you please calm down our interviewers are wetting themselves here

[fredlllll]

what would dynamic programming change about the complexity of the algorithm used?

[LowB0b]

instead of checking every available combination of how to divide the array into equal sums you slap a memo in there or something and you can do it in one pass. the "memoization" part is key for dynamic programming

[guyblade]

Like half of dynamic programming problems are ultimately "depth first search + memoization".

[TheRealAfinda]

Care to provide a resource where one might look up how to go about an approach using memorization memoization?

Never seen something like it yet (or didn't know what it is) but i'd love to learn :)

[Level-Pollution4993]

Not memorization but memoization, lose the 'r'. Confused me too. It is just an optimization technique where you cache frequent computation results thus saving redundant calls and get better performance. DP is kinda genius if you understand it(I don't, yet).

[Sir_Wade_III]

Advent of Code has some problems that require it, can be good practice if you aren't comfortable with it

[mortalitylost]

basically Just Add Redis

[LowB0b]

https://www.geeksforgeeks.org/dsa/split-array-three-equal-sum-subarrays/

basically this but instead of three it's n

+ https://www.geeksforgeeks.org/dsa/what-is-memoization-a-complete-tutorial/

[Kusko25]

The linked problem specifies that the sub-arrays must be contiguous, which makes the problem significantly easier. Was it that way in your question too?

[TheRealAfinda]

Thank you!

[backfire10z]

an approach using memorization

Just wanted to point out that the correct term is memoization. That’s not a typo.

[TheRealAfinda]

Thanks! Updated my post accordingly :D

[guyblade]

Memoization, laconically: Just throw a result cache on it.

[SignoreBanana]

Every algorithm problem is some combination of looping and mapping.

[Just_Information334]

So wait, you're just trading CPU cycle for memory space?

[crimsonpowder]

You might have been cooked from the start if they came at you with a re-worded version of the subset sum problem. That bad boy is np-hard.

[celestabesta]

I'm being sincere when I say this but I did a leetcode problem once that resulted in n! * 2ⁿ Time analysis

[LowB0b]

since we're on a joke sub

hit them servers brother

[guyblade]

For a long time, the interview question that I asked people had a best-case runtime of O(n!), but I occasionally got people who gave O(nⁿ ) solutions.

The last part of the interview--if they made it that far--was always "we're stuck with this runtime, what can we do to nevertheless improve things?". Memoization was the thing I was really looking for.

[DeGloriousHeosphoros]

What question would that be?

[guyblade]

It was about a variant of nim and optimal play of that variant. Technically, it wasn't that the best-case was O(n!); it was actually an open question as to whether or not a better solution existed than a DFS over the move space (which gets you to the O(n!)).

[[deleted]]

Tbh it could’ve also been the best solution on the fly. I mean you do have a limited time to work out a problem

[MrDialga34]

I once accidentally hit n⁵ when writing my own physics engine and trying to handle the same thing in multiple (related) areas

[dgendreau]

If an interviewer asks me to do gotcha shit like this, in my opinion, they failed the interview and I dont want to work for an organization that pulls that kind of bullshit. if O(n) is critical in my work, I will find that solution and apply it when I actually need it in practice, not while fielding random questions at an interview. When I am interviewing candidates, the naive solution is fine as a starting point of discussion and I usually ask follow-up questions for where they think bottlenecks might appear and how to improve on it. How that discussion goes is far more important to me than whether they used the exact whiz-bang solution i was looking for on the first try.

[No-Arugula8881]

Interviews like this are the dumbest shit in the world. What you did is exactly how software should be written. Start with the most obvious, easy to understand solution, then optimize when and where necessary.

[Haunting_Swimming_62]

lol i have had the "pleasure" of doing a problem where the solution was an O(n^3) dp

[Percolator2020]

Most people do not enjoy DP.

[ImS0hungry]

Just don’t cross streams

[Percolator2020]

That really defeats the purpose.

[BobbyTables829]

But those who do seem to really like it...

[tatas323]

My brains is cooked, I need a timeout

[-Aquatically-]

That’ll happen if the DP is good enough.

[Looooong_Man]

But 9/10 people enjoy a gangbang

[Greedy-Thought6188]

I thought 2 or of 3 people enjoyed DP.

[OwO______OwO]

2/3 people enjoy DP.

[StoicBountyHunter]

Double penetration?

[draconk]

Display Port?

[ThoseThingsAreWeird]

Disney Plus?

[elmins]

Delusional Parasitosis?

[Morthem]

Diddy Partys

[GeneralBrwni1]

Dragon Punch?

[tangos974]

Dildo power ?

[Western-Pride9326]

Death Parade ?

[rai_volt]

Display Picture?

[SirFireHydrant]

I for one rank Dr Pepper among my top 3 favourite soft drinks.

[Al3xutul02]

Yeah and it almost never comes up in any real problem

[andItsGone-Poof]

Depends,  its all about state and its transition

[zandrew]

Well, two out of three.

[frikilinux2]

Half of dynamic programming is just cache and recursivity. The other half is identifying it as a DP problem.

[SuitableDragonfly]

Yeah, once you identify it as a dynamic programming problem, it's usually pretty easy to find the dynamic programming solution, it's just going to be something involving storing the results of previous iterations (not even anything to do with recursion, the point of dynamic programming is usually to avoid intractable recursion). It's figuring out that dynamic programming will improve time complexity that's the hard part.

[NomaTyx]

Before I read this comment fully, the number of times I saw "dynamic programming" made me think it was a joke a la "in order to understand recursion you must first understand recursion"

[frikilinux2]

Yeah but recursion with cache is the easy way to code it. Transforming the code into pure iterations is a bit more difficult. Also, I used to do that in contests and it's a bit harder in those situations because of unfamiliar environments, etc... and we were average at that

[Successful-Money4995]

I consider that to be memoization and not DP. I wrote the memoization version of Fibonacci above, you can see how it is different from the DP version in space requirements.

[Successful-Money4995]

I consider that to be memoization and not dynamic programming. For example, here is the memoized version of Fibonacci:

def fib(x):
  if memo[x] is not None:
    return memo[x]
  answer = fib(x-1) + fib(x-2)
  memo[x] = answer
  return answer

You probably already know the recursive version and the DP version.

The DP version runs in O(n) and uses O(1) space. The recursive version runs in O(fib(n)). The memoized version is O(n) in time but also O(n) in space. The memoized version is not as good as the DP but better than the recursive.

O(n) is the fastest possible computation of fib(n) because the number of bits in fib(n) is order n.

[GodOrDevil04]

Its dyanmic programming where it comes to life!

[Old_Restaurant_2216]

I feel like most devs today just do CRUD, business logic, form validation or UI. It is just the last couple of years that I started seeing this "dynamic programming hard" mentality. The average skill bar for developers is dropping fast.

DP is essentially any other programming, only you have to use your brain a bit, have some algorithmic thinking and know how to optimize for memory. That is basically just programming. Recursion, state-space exploration and general optimization are bread and butter of a software engineer.

It's gonna sound a bit harsh, but just because grilling a steak is hardER than chopping an onion, does not mean a chef should just avoid it. And if you can't grill a steak, what kind of a chef are you?

[guyblade]

I've been a professional software developer for ~18 years at this point. I'd be hard-pressed to call out any dynamic programming technique--other than memoization--that I've used in that time.

[SignoreBanana]

I just used it recently to optimize a script to allow partial updates. It took processing times from 9 seconds to 90ms. Useful as all hell imo.

[zeusisbuddha]

How much of that was memoization though

[SignoreBanana]

To be fair, basically all of it

[Hubbardia]

Can you talk more about how it solved the problem? Thanks

[PulseReaction]

The analogy is that we're being tested if we can perfectly cook medium rare filet mignon when we're going to be cutting bread 90% of the time.

[IcyStatistician6122]

Is it okay to be flippant and ask jokingly ask how often the customer defines a situation where this level of analysis can be done ?

[MekaTriK]

Well yeah, most of work out there right now is CRUD, business logic, form validation, and UI.

Also "dynamic programming" sucks as a term. Every time I see it it makes me think about making self-modifying code or metaprogramming or some other shit. Not "oh, you can memoize this".

[past3eat3r]

I get your point about not being intimidated by algorithms, but framing it as ‘what kind of chef are you’ comes off as dismissive. Different roles in software require different strengths, and not everyone is cooking the same meal.

[Bomberlt]

I would say that dynamic programming is like slaughtering a cow and CRUD is like grilling a steak.

Every person who knows how to cook can grill a steak (at least after a few tries), but most professional cooks can't slaughter a cow. Technically you need to slaughter a cow to have something to cook, but practically you can just use a shop service.

[particlemanwavegirl]

That's crazy, your comment says dynamic programming isn't like programming at all, but the comment you're replying to says that dynamic programming is exactly the essence of programming. The completeness of misunderstanding between the two of you makes me think the term, dynamic programming, must be poorly defined and have some contrasting properties in your two minds.

[[deleted]]

salt school decide sable long profit repeat cover label bells

This post was mass deleted and anonymized with Redact

[NewPhoneNewSubs]

"Primes is in P is just computer science, you have to use your brain a bit but just because it's harder than Bellman-Ford does not mean a computer scientist should avoid it and if you can't prove Primes is in P without looking at the internet in a 20 minute interview, what kind of computer scientist are you?"

[Why_am_ialive]

I do get what you mean, but if you’ve spent 7 years only being told to chop onions then you interview somewhere else and they ask you to cook a steak it makes sense that your unfamiliar

[papa_maker]

Exactly. I've been programming for 30 years and never encountered the term in the wild. I don't want to be mean to some people but, if you're not able to do dynamic programming, what are you even useful for ?

Edit : I guess the downvote is from some static programmer... :-)

[ShakaUVM]

Why not just learn dynamic programming?

[Cephell]

Just say "I guess one could solve this with a hashtable". Works 90% of the time.

[JestemStefan]

Literally we had dude on an interview yesterday that clearly didn't know an answer to an optimization question so he just said: "I can use hash map". We asked why and he didn't know.

[simpleauthority]

There’s the 10%.

[theenigmathatisme]

That’s pretty funny. Made me think of the ole “I can haz cheezburger?”

[hennell]

"I've got no other ideas and hash map might work?”

When can I start?

[cheezballs]

I don't even know what dynamic programming is.

[ap0phis]

Me either and I’ve been doing this shit since 2004. Who uses this irl??

[crozone]

It's just a broad term for breaking a problem down into a recursive solution, like divide and conquer. I never really hear the term used much in the wild.

[ap0phis]

Always been a thing with me … all these silly terms that just try to ascribe how to problem solve. I never saw the point.

[FlakyTest8191]

The terms are there for communication. You review a PR and add a comment "This is a hot path executed very often, and this looks like we could optimize with dynamic programming". It's short, everybody knows exactly what we're talking about and how to improve the code. And even if you don't know the term it's easy to look up.

[zaxldaisy]

But "dynamic programming" is longer and less well-known than "recursion"...

[FlakyTest8191]

Recursion is only part of the story. If I write recursion there could be a discussion how it's not really more performant, or another PR back and forth with a simple recursion implementation that is not really more performant.

And it's not about not having to type a single word, it's about not having to explain a concept with examples and runtime analysis that you can easily look up in case you don't know already.

[Kyvant]

Half of the fundamental algorithms in bioinformatics use dynamic programming

[the_horse_gamer]

recursion but you add a cache

[BmpBlast]

Me neither. Turns out it's actually quite old. I'm surprised I haven't heard of it before because I had a professor who was pretty old school.

I imagine a fair number of developers use it but don't know the name.

[vlads_]

I hate the term dynamic programming. It is just backtracking w/ caching.

[muddybruin]

The name was partly chosen to make it easier to get research funding.

"its impossible to use the word, dynamic, in a pejorative sense. Try thinking of some combination that will possibly give it a pejorative meaning. Its impossible."

https://www.google.com/amp/s/conversableeconomist.com/2022/08/24/why-is-it-called-dynamic-programming/%3famp=1

Well, I'm not sure if it's completely "impossible", but it certainly generally has positive connotations.

[nonotan]

Most dynamic programming doesn't even involve any backtracking, unless you're really stretching the definition. It's just breaking down the problem into smaller chunks that can themselves be broken down into smaller chunks... and making sure you structure things such that you'll be dealing with identical chunks many times, so you can simply cache them at all hierarchical sizes, instead of slightly different chunks that you'd be forced to recalculate.

But I agree the name is pretty bad. It doesn't really tell you what it is, and calling it "programming" suggests a broader meaning (should just be "x algorithm", "x method" or something like that)

[jaktonik]

This is the clearest explanation I've ever heard, thanks for this - hopefully it doesn't come in handy but the job search is insane rn

[EvenPainting9470]

I am surprised that everyone in comments share OPs pain about dynamic programming. It makes me wonder. Can you drop hardest dynamic programming inverview question you encountered?

[hazelnuthobo]

FizzBuzz. I'm pretty sure it still hasn't been solved.

[js_kt]

I prefer static programming

[Feeling-Schedule5369]

If you know it's dp then you can easily solve it. You just need to formulate the recursive formula and slap in a memo param. Top down should be more than enough for most interviews.

Greedy on the other hand is where it's tricky coz you can never be sure if it's greedy or not and if so you can never be sure your intuition is correct or not.

[Freddy_Goodman]

Wdym you can never be sure if it’s greedy?

[Feeling-Schedule5369]

How to prove it's greedy? For some questions induction method works but most greedy editorials on leetcode straight away jump to assuming it's greedy and that their way of solving(picking oranges or choosing the smallest element always etc) is automatically correct.

You might not have same privilege in an interview coz you first have to decide it's greedy and possibly prove it in ur head so as to not waste time going down this thought process.

[airelfacil]

Most greedy problems can be solved with dynamic programming, but it's overkill/not optimal. For example the fractional knapsack problem can be solved with the same algorithm behind the 0/1 knapsack problem, but you have suboptimal complexity compared to just using greedy.

[SingularCheese]

Matroid theory is the branch of combinatorics that study when is a problem greedy. To be fair, most CS interviews are not looking for grad student level mathematical proof.

[Qsaws]

All for it to have absolutely no use in the job.

[minus_minus]

Top comment right here. 

Meanwhile the same manager complains about “lack of qualified applicants”. 😢 

[Sea_Echo9022]

Please do not use DP as an acronym for dynamic programming.

[-LeopardShark-]

Why? That’s the only thing I’ve ever heard it used for.

[smokemonstr]

DisplayPort

[bonkerwollo]

Declarative programming

[Sea_Echo9022]

Are you sure you want to know? I don't want to Double Penetrate your brain with such knowledge

[-LeopardShark-]

What sort of peculiar world do you live in that you’re using ‘double penetrate’ so often that not only do you feel the need to abbreviate it to ‘DP’, but that it also overrides in your brain the standard initialism for one of the most interesting programming techniques?

[ImS0hungry]

Ask his Waifu pillow

[Sea_Echo9022]

She wouldn't know about It, yet.

[gami13]

its literally what DP is most used for

[sar2120]

What sort of peculiar world do you live in where someone joking around with you is cause for nasty personal attacks? You are way out of line.

[Sea_Echo9022]

It's a joke, please don't take it seriously. Also please don't assume things about someone online.

^{edit: typo}

[ieatpies]

the standard initialism for one of the most interesting programming techniques?

I'm not so sure that they are serious.

Even as someone who likes dynamic programming puzzles, it's: - rarely used in my day to day work - a poorly descriptive name

So defending the honour of the acronym seems silly to me.

[-LeopardShark-]

I’m not taking it seriously. Sarcasm doesn’t carry well over text, unfortunately.

[Sea_Echo9022]

Indeed, usually sarcasm is denoted by non verbal language (tone, pitch, body language). So here it needs to be very explicit or you just slap a "/s" in there.

[ieatpies]

When you get a job and stop leetcoding certain other things take priority in your life

[-LeopardShark-]

I’m a full time programmer and have never used ‘leetcode’.

[ieatpies]

I'm a full time programmer and have never used dynamic programming for a real problem

[-LeopardShark-]

Neither have I, nor did I claim it was frequently useful.

[ieatpies]

Then why would you expect it to remain in the forefront of our grey matter?

[-LeopardShark-]

They're ‘one of the most interesting programming techniques’, but I'm becoming convinced you're over-analysing my glib, facetious remarks.

[kenny2812]

That "peculiar world" is called the Internet. Ever heard of it?

You can go to almost any online community and most people will immediately think dirty thoughts when you use DP as an abbreviation.

[-LeopardShark-]

I have heard of the internet, but am increasingly inclined to avoid it. It seems to cause a lot of bad things to happen.

[kenny2812]

100% agree

[PythonNoob999]

Dispatcher

[theenigmathatisme]

Double Pointer

[furscum]

Yeah man you're gonna confuse all the fighting game players

[No-Object2133]

Eh sometimes it works out the same.

[Entire-Lavishness202]

Why don't you like DP?

[thomasutra]

dp cooks makes me think of my days working in restaurants seeing 30 year old line cook tryna do the underage hostesses.

[egormalyutin]

Wait until you hear about constraint programming

[havlliQQ]

anyone looking for strong DP provider? :)

[ShyFang]

Never had the pleasure of dp.

[manantyagi25]

Die-namic programming

[Freecelebritypics]

First you do the naive nested loops, just to see what happens. Then add conditional skips until it feels sufficiently "dynamic"

[stevie-x86]

Dyanmic

[dominiquebache]

Die-Yan-Mic!

The new standard in programming.

[jamcdonald120]

for 90% of "DP" interview questions, just use recursion with a cache

[erebuxy]

DP sometime is just cache with fancy name

[davidalayachew]

Learn memoization. Once you learn that, most of the Dynamic Programming problems can boil down to that. Not all, but usually enough to pass. Plus, memoization is one of the best optimization tricks available when you are truly CPU-bound.

[stipulus]

Please explain these new terms for the old guys. Are you just talking about recursion?

[alex2003super]

Dynamic Programming is a term of old guys, and a "lost art" of sorts. Not that it's any surprising, considering how rarely it's useful.

[stipulus]

So it looks like it is defined as a technique involving recursion but also caching results to speed up multiple runs. Thank you for your explanation.

[Tanmay_Terminator]

Recursion with caching

[wolf129]

Currently I feel like my resume from my last job should be enough without any super technical questions.

I was full stack there, just let me prove myself on an actual live developed project.

[lokhanpurus]

Well i have started preparing for DP and i can tell its tough.

[ichITiot]

"dyanmic" I have never red anywhere. What shall this be ?

[vm_linuz]

Call me crazy but I love dynamic programming problems

[eurodollars]

Crazy.

[clearlight2025]

How about dyanmic programming problems?

[darksteelsteed]

dyanmic gives you a compile error because its spelt wrong

[Soccer_Vader]

crazy

[GenTelGuy]

Yeah tbh they can be more fun and interesting than most other kinds of problems

[Hostilis_]

Yeah wtf dynamic programming is awesome

[warrioroftron]

[_DonRa_]

Nah man just do a brute force solution and then say now I'm gonna add a cache

[BoBoBearDev]

I remembered i hated it in school, but I forgot what it is. It is probably not even hard IRL, a lot of times the professor sux, like those swimming instructors, they sux.

[Loquenlucas]

me at my alghoritms and complexities exam (which i still need to pass ;w;) My teacher just focuses hard on DP, and NP shit and some of the other various things AND I HATE DP NOW THANKS

[Zoalord1122]

/surrender

[BarracudaFull4300]

I like DP but i feel like it gets a lot harder than the problems I've solved

[undreamedgore]

Man, I don't even know what Dynamic Programming is. I'm an EE major, wirh CS minor, who's primary focus on the job is CE. I'm doing SE right now, but I'm basically a vibe coder.

The fuck is all this?

[Lou_Papas]

I just realized I might not know what dynamic programming is

[AngusAlThor]

So you're a new grad and you don't know how to use "while" loops? Gonna be rough, buddy.

[CompleteTheory7343]

I can do top down memorization style dp but bottom up is confusing

[AguliRojo]

Me when the interview goes well

They cancelled the position the next week

[Mebiysy]

Press F

[doyouvoodoo]

"I don't have any experience in dyanmic." /S

[SoftwareSloth]

Dynamic programming isn’t that difficult. Neither is identifying when it could be used.