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

91–100 of 120 posts

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

#91

Post by _0w8t »

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…

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.

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

#92

Post by mavelikara »

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

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

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

#93

Post by _0w8t »

piva00 wrote: post #47
globular-toast wrote: post #39

Earlier quoted context omitted.

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

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…

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.

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

#94

Post by slaymaker1907 »

anon_tor_12345 wrote: post #80
crazypython wrote: post #77

Earlier quoted context omitted.

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

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.

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

#95

Post by tnel77 »

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

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?

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

#96

Post by anon_tor_12345 »

mavelikara wrote: post #92
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.…

> 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

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

#97

Post by anon_tor_12345 »

tnel77 wrote: post #95
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.…

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

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

#98

Post by Apocryphon »

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…

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

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

#99

Post by mavelikara »

anon_tor_12345 wrote: post #96
mavelikara wrote: post #92

Earlier quoted context omitted.

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

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

#100

Post by anon_tor_12345 »

mavelikara wrote: post #99
anon_tor_12345 wrote: post #96

Earlier quoted context omitted.

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)
Post reply on HN