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

21–30 of 120 posts

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

#21

Post by beforeolives »

water8 wrote: post #13
mightymercado wrote: post #4

Earlier quoted context omitted.

I would argue that it's a pretty good measure of programming and CS problem solving skill with weak alternatives.

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…

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.

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

#22

Post by pjmlp »

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.

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

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

#23

Post by tekkk »

mightymercado wrote: post #4
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 would argue that it's a pretty good measure of programming and CS problem solving skill with weak alternatives.

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.

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

#24

Post by qsort »

saagarjha wrote: post #18
fakename11 wrote: post #17

Earlier quoted context omitted.

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.

To be fair, I know a fair number of people who are good at competitive programming but are absolutely awful at writing maintainable code.

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.

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

#25

Post by wst_ »

mightymercado wrote: post #4
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 would argue that it's a pretty good measure of programming and CS problem solving skill with weak alternatives.

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.

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

#26

Post by paraph1n »

mightymercado wrote: post #4
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 would argue that it's a pretty good measure of programming and CS problem solving skill with weak alternatives.

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.

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

#27

Post by globular-toast »

wst_ wrote: post #25
mightymercado wrote: post #4

Earlier quoted context omitted.

I would argue that it's a pretty good measure of programming and CS problem solving skill with weak alternatives.

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

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.

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

#28

Post by slumpt_ »

globular-toast wrote: post #27
wst_ wrote: post #25

Earlier quoted context omitted.

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

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.

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.

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

#29

Post by tomduncalf »

trekhleb wrote: post #8
Veen wrote: post #6

The diagrams in this article are excellent. Does anyone know what the author used to make them?

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!

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

#30

Post by tarsinge »

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