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

Solving dynamic programming interview problems

blog.refdash.com

Post reply on HN
Print view View original

71–80 of 176 posts

Re: Solving dynamic programming interview problems

#71

Post by [deleted] »

blackflame7000 wrote: post #62
jacquesm wrote: post #60

Earlier quoted context omitted.

Recursion is usually clearer that iterative because it assigns names to the work being done. I find that much easier to read. Better yet: when you can state your cases separately. That's even more readable.

I don't think you represent the average coder. I'm willing to bet most people if shown 10 recursive and 10 iterative solutions to the same problems would admit the iterative approach is more intuitive. Especially since with a for loop you can control the number of iterations which has a number of optimization benefits. Now if its just while loops vs recursive then there's not much of a difference, however that is not…

[deleted]

Re: Solving dynamic programming interview problems

#74

Post by czinck »

Karishma1234 wrote: post #63

I have always found the word DP to be a bit confusing. DP problems are essentially recursion + caching. I do not even like the word "memoise".

"Dynamic programming" was intentionally a super-vague but cool sounding term, it wasn't meant to be descriptive (unfortunately). https://en.wikipedia.org/wiki/Dynamic_programming#History

Re: Solving dynamic programming interview problems

#75

Post by [deleted] »

blackflame7000 wrote: post #62
jacquesm wrote: post #60

Earlier quoted context omitted.

Recursion is usually clearer that iterative because it assigns names to the work being done. I find that much easier to read. Better yet: when you can state your cases separately. That's even more readable.

I don't think you represent the average coder. I'm willing to bet most people if shown 10 recursive and 10 iterative solutions to the same problems would admit the iterative approach is more intuitive. Especially since with a for loop you can control the number of iterations which has a number of optimization benefits. Now if its just while loops vs recursive then there's not much of a difference, however that is not…

[deleted]

Re: Solving dynamic programming interview problems

#76

Post by FractalLP »

blackflame7000 wrote: post #62
jacquesm wrote: post #60

Earlier quoted context omitted.

Recursion is usually clearer that iterative because it assigns names to the work being done. I find that much easier to read. Better yet: when you can state your cases separately. That's even more readable.

I don't think you represent the average coder. I'm willing to bet most people if shown 10 recursive and 10 iterative solutions to the same problems would admit the iterative approach is more intuitive. Especially since with a for loop you can control the number of iterations which has a number of optimization benefits. Now if its just while loops vs recursive then there's not much of a difference, however that is not…

Agreed. HackerNews has a greater than average amount of developers that use Haskell, F#, OCaml, Scheme, and other languages which heavily promote recursion. I'm not sure if I personally find iteration easier because I learned it first, it matches my brain better, or if it is indeed easier for most of the population.

Re: Solving dynamic programming interview problems

#77

Post by joefkelley »

blackflame7000 wrote: post #62
jacquesm wrote: post #60

Earlier quoted context omitted.

Recursion is usually clearer that iterative because it assigns names to the work being done. I find that much easier to read. Better yet: when you can state your cases separately. That's even more readable.

I don't think you represent the average coder. I'm willing to bet most people if shown 10 recursive and 10 iterative solutions to the same problems would admit the iterative approach is more intuitive. Especially since with a for loop you can control the number of iterations which has a number of optimization benefits. Now if its just while loops vs recursive then there's not much of a difference, however that is not…

You might be able to trace the execution of the iterative code more easily, but in my experience it is often much less clear why that produces the correct result and how that code was written in the first place.

Take a look at the wikipedia page for computing Levenshtein distance: https://en.wikipedia.org/wiki/Levenshtein_distance#Computing...

The recursive version needs barely any explanation. But ask me to carry it out by hand and I'm sure I'll pretty quickly get lost. The iterative version needs a lot more explanation for why it is the way it is, but I also think I could carry it out on paper quite easily.

Re: Solving dynamic programming interview problems

#78

Post by mikec3010 »

scarface74 wrote: post #70

And most of the interviewers asking these questions just want someone who can help develop yet another software as a service CRUD app....

Exactly. I've been a C, C++, and java developer for the past 12 years and never used Big-O for anything other than a shibboleth to get past the door. A couple places practically used C++ itself as a gatekeeper: they want people who are smart enough to program in C++ and survive it's rigorous interview process, but their main product is filling out forms and routing documents through a document management system.

Re: Solving dynamic programming interview problems

#79

Post by rsp1984 »

I've done a fair amount of interviews in my professional career, both as an engineer at Google as well as for my own startup.

In an eng. interview you want to maximize information divided by time, i.e. you want to learn as much as possible about whether the candidate would be a good fit for the company and spend as little time as possible doing so (because you have other things to do -- such as interviewing more candidates).

In my experience these kind of interview questions have a very poor information by time ratio. They are poor on information because they may give you an idea how well the candidate can do on puzzle questions but not so much how the candidate would do on actual real-world assignments. And they are especially poor on the denominator (time) because you are probably going to spend at least 1h with the candidate before you get past the obvious stuff.

Also I guess about 70% of (pre-qualified) candidates would outright fail the question, so if you let this influence your hiring decision, given that the question is really quite "puzzly", you're inevitably going to miss out on a lot of talent (the kind that does well on actual work assignments).

Re: Solving dynamic programming interview problems

#80

Post by blackflame7000 »

joefkelley wrote: post #77
blackflame7000 wrote: post #62

Earlier quoted context omitted.

I don't think you represent the average coder. I'm willing to bet most people if shown 10 recursive and 10 iterative solutions to the same problems would admit the iterative approach is more intuitive. Especially since with a for loop you can control the number of iterations which has a number of optimization benefits. Now if its just while loops vs recursive then there's not much of a difference, however that is not…

You might be able to trace the execution of the iterative code more easily, but in my experience it is often much less clear why that produces the correct result and how that code was written in the first place. Take a look at the wikipedia page for computing Levenshtein distance: https://en.wikipedia.org/wiki/Levenshtein_distance#Computing... The recursive version needs barely any explanation. But ask me to carry it…

I mean if you label all your variables i,j, and k and use minimal formatting or bracketing then I see your point it is harder to read. Whats complicated about an iteration. If it works properly after the first one chances are it will continue to work for the millionth one. If you see problems, its because something is modifying it between runs, but that wasn't a fault of the iterative strategy, it was the fault of a bad programmer. Conversely, you must always make sure the stopping condition and all base cases are met during recursion. Forget one corner base case and you got a rare production bug.
Post reply on HN