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

111–120 of 120 posts

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

#111

Post by slumpt_ »

_0w8t wrote: post #93
piva00 wrote: post #47

Earlier quoted context omitted.

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.

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.

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

#112

Post by slumpt_ »

globular-toast wrote: post #39
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.

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…

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

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

#113

Post by _0w8t »

slumpt_ wrote: post #111
_0w8t wrote: post #93

Earlier quoted context omitted.

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.

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

#114

Post by slumpt_ »

_0w8t wrote: post #113
slumpt_ wrote: post #111

Earlier quoted context omitted.

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.

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

#115

Post by kar5pt »

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

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

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

#116

Post by piva00 »

_0w8t wrote: post #113
slumpt_ wrote: post #111

Earlier quoted context omitted.

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

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

#117

Post by _0w8t »

piva00 wrote: post #116
_0w8t wrote: post #113

Earlier quoted context omitted.

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

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.

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

#118

Post by rmk »

rmk wrote: post #89
currymj wrote: post #76

Earlier quoted context omitted.

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!

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

#119

Post by tomduncalf »

trekhleb wrote: post #65
tomduncalf wrote: post #29

Earlier quoted context omitted.

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)

Thanks for that! :)

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

#120

Post by thealig »

chalst wrote: post #108
thealig wrote: post #35

Earlier quoted context omitted.

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