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

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

trekhleb.dev

Post reply on HN
Print view View original

61–70 of 120 posts

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

#61

Post by sidpatil »

jorl17 wrote: post #50
DaiPlusPlus wrote: post #45

Earlier quoted context omitted.

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

People in these arguments always talk about the algorithms, but I think that entirely misses the point. It rarely is about the algorithms themselves, but, rather, it's about the data structures. One is obviously tied to the other, but what I mean is that many slow apps are slow because the people just used the wrong data structure. Sometimes it's as simple and silly as using a list and constantly iterating over it in…

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

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

#62

Post by bidirectional »

goldenkey wrote: post #43

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?

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.

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

#63

Post by water8 »

EvilEy3 wrote: post #44
slumpt_ wrote: post #28

Earlier quoted context omitted.

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

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

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.

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

#64

Post by water8 »

fakename11 wrote: post #17
water8 wrote: post #13

Earlier quoted context omitted.

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 ma…

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.

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.

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

#65

Post by trekhleb »

tomduncalf wrote: post #29
trekhleb wrote: post #8

Earlier quoted context omitted.

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)

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

#66

Post by water8 »

jorl17 wrote: post #50
DaiPlusPlus wrote: post #45

Earlier quoted context omitted.

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

People in these arguments always talk about the algorithms, but I think that entirely misses the point. It rarely is about the algorithms themselves, but, rather, it's about the data structures. One is obviously tied to the other, but what I mean is that many slow apps are slow because the people just used the wrong data structure. Sometimes it's as simple and silly as using a list and constantly iterating over it in…

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.

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

#67

Post by specialist »

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

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

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

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.

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

#68

Post by water8 »

teachingassist wrote: post #36
tekkk wrote: post #23

Earlier quoted context omitted.

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 produ…

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.

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

#70

Post by dominotw »

anon_tor_12345 wrote: post #60

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

brute force recursive solution + @lru_cache annotation.

works for me every time on leetcode.

Post reply on HN