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

81–90 of 176 posts

Re: Solving dynamic programming interview problems

#81

Post by foota »

jacquesm wrote: post #60
blackflame7000 wrote: post #37

Earlier quoted context omitted.

Is recursion really worth the loss of clarity? Almost always no. The more clever you are in your code, the less likely anyone will ever see it (or want to).

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.

You generally need to be familiar with making arguments about aggregate complexity (e.g., every element will only be visited X times because... so the complexity is O(N)) to show complexity for a recursive solution, as opposed to the iterative solution where the complexity is generally more apparent ime.

Re: Solving dynamic programming interview problems

#82

Post by nordsieck »

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…

It really depends on the kind of problem. For example, recursive solutions to linked-list/tree/graph problems are typically substantially easier to understand than their iterative counterparts, in large part because the data structures themselves are recursively defined.

Re: Solving dynamic programming interview problems

#83

Post by hk__2 »

extesy wrote: post #59
nilkn wrote: post #24

Earlier quoted context omitted.

We pay very well for the area. We are not in Silicon Valley, but I know some of our salaries are higher than those of my friends who are at Google's MV campus.

Can you share your company name?

I’ll let OP share it if they want, but FYI if you search a bit that information is freely available on the Internet.

Re: Solving dynamic programming interview problems

#84

Post by dub »

I have a fantasy. In the fantasy, an interview candidate says "this problem has an optimal substructure" or "this problem can be broken into overlapping subproblems" and then observes "reusing the results of overlapping subproblems to avoid re-computing them is sometimes called dynamic programming"

At this point, balloons and confetti fall from the ceiling as Donald Knuth jumps out from under the table to hand the candidate an award for being the first known example of a candidate using "dynamic programming" correctly in a sentence.

Re: Solving dynamic programming interview problems

#86

Post by kolpa »

blackflame7000 wrote: post #80
joefkelley wrote: post #77

Earlier quoted context omitted.

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…

In an iterative solution, you have to get your loop conditions correct, and you have to create a bunch of inputs before you know how you are going to use them, sort of a "solution in search of the problem". Recursion takes a problem and expresses it terms of similar, but smaller, unsolved problems, unless you can solve it directly (base case). It's a "problem in search of a solution", that always makes progress (unless you have a bad algorithm, as always).

If a recursive solution works on a small input, it will work on a big input. If you missed a base case, you'll see it immediately because trivial (literally!) input will make your solution fail to terminate.

In production, the main problem with recursion is stack size limits (or more generally memory limits) if you can't/don't use tail-call elimination.

Re: Solving dynamic programming interview problems

#87

Post by kolpa »

danmg wrote: post #44
blackflame7000 wrote: post #41

Earlier quoted context omitted.

Experience, tells me so. To be fair some items like Fibonacci numbers are probably equally as clear.

Divide an conquer type algorithms usually lend themselves to naive recursive solutions more often than not. DP usually requires you to find that solution and find some clever relationships that allow you to build up the final solution from the bottom up.

If you systematically analyze it, you don't need to be clever on a per-problem basis. Every recursive solution can me methodically converted to DP.

Re: Solving dynamic programming interview problems

#88

Post by kolpa »

coastal-fiesta wrote: post #72
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".

Indeed, it sounds like someone is just saying "memorize" incorrectly.

That's what happens when you "recurse".

Re: Solving dynamic programming interview problems

#89

Post by drb91 »

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…

It's only more intuitive to see the shape of the serial execution. That same property makes it more difficult to prove qualities about the code (say, correctness) because you need to keep track of state in your head as you trace through the program, rather than encoding it structurally as you would with a recursive solution.

So, intuitive is not so valuable unless you get correctness out of it.

Re: Solving dynamic programming interview problems

#90

Post by scarface74 »

mikec3010 wrote: post #78
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.

I did have to do one algorithm type interview in 1999, but the company was actually writing cross platform (Windows console, Unix, and MVS) C code where we had to implement everything from scratch, so it made sense. But unless you're Google, Facebook, Netflix, etc. where you have to solve problems at a scale that no one has had to solve before, most of the algorithm style questions are meaningless in your day to day work.
Post reply on HN