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

131–140 of 176 posts

Re: Solving dynamic programming interview problems

#131

Post by zodiac »

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…

Depends on the problem. Some problems have very explicit recursive structure (eg http://rosettacode.org/wiki/Arithmetic_evaluation) such that an iterative solution is more "unnatural". Not saying that most problems are like that, just that this shows it depends on the problem.

Re: Solving dynamic programming interview problems

#132

Post by zodiac »

sumeno wrote: post #106
hinkley wrote: post #27

Earlier quoted context omitted.

I got screwed like that on my Google interview. You should not be blamed for assuming, when talking to Google, that the O(n!) or O(n^2) solution is not even worth talking about. So I flopped around on O(n), O(nm) and O(nlogn) solutions after trying to whiteboard a recurrence relationship and giving up on O(1). Interviewer had already decided that somehow the crazy rules I related to him about the industry I was comin…

> You should not be blamed for assuming, when talking to Google, that the O(n!) or O(n^2) solution is not even worth talking about. If the naive solution is O(n!) then describing an O(n^2) solution is perfectly acceptable.

Interesting fact: the standard DP algorithm for TSP reduces the running time from O(n!) to O(n^2 2^n)

Re: Solving dynamic programming interview problems

#133

Post by triska »

I often use the declarative programming language Prolog to solve dynamic programming tasks, because it is easy to type and helps you to declaratively express what a solution looks like. After you have expressed what must be the case in a solution, you can easily enable memoization on top of the existing code.

For example, here is how you can use Prolog to solve the task from the article. The following Prolog predicate is true iff a given runway (represented as a list of "t" and "f" elements) is safe with a given speed:

    :- use_module(library(clpfd)).

    safe_runway(0, [t|_]).
    safe_runway(Speed0, Rs) :-
            Speed0 #> 0,
            Rs = [t|_],
            (   Speed = Speed0
            ;   Speed #= Speed0 - 1
            ;   Speed #= Speed0 + 1
            ),
            length(Prefix, Speed),
            append(Prefix, Rest, Rs),
            safe_runway(Speed, Rest).
Sample query and answer:

    ?- safe_runway(4, [t,f,t,t,t,f,t,t,f,t,t]).
    true .
One interesting aspect of this solution is that we can generalize this query, and also use the same program to answer the question: Which speeds are actually safe for a given runway?

For example:

    ?- safe_runway(Speed, [t,f,t,t,t,f,t,t,f,t,t]).
    Speed = 0 ;
    Speed = 2 ;
    etc.
To enable memoization for this task, you only have to use your Prolog system's tabling mechanism. For example, in SWI-Prolog, you turn this into a dynamic programming solution by adding the directive

    :- table safe_runway/2.
This makes the Prolog engine automatically remember and recall solutions it has already computed.

Re: Solving dynamic programming interview problems

#134

Post by irq11 »

x1798DE wrote: post #114
BurningFrog wrote: post #113

Earlier quoted context omitted.

When I interviewed at $BigCompany, I really enjoyed the whiteboard programming problems I got. But I noticed that 2/3 of them ended up with recursive solutions. Meanwhile, I spend less than 1% of my real professional programming time writing recursive code, and it's a bit silly that so much focus is on such relatively obscure technique.

I think it's a mistake to think of whiteboard problems as attempting to recreate a real work environment. They are a proxy for the kind of quality you are looking for that can be "measured" within the alotted time. They can show that the person is prepared (they studied), generally knowledgable (they remember obscure stuff), or just clever (they come up with interesting approaches to the problem). I'm not surprised y…

They’re used because “that’s what company X uses”. People are cargo culting each other, and making up post hoc rationalizations for their behavior.

Unless you work for a major tech company where optimizing the false positive rate is your primary concern, using these problems is counterproductive.

Re: Solving dynamic programming interview problems

#135

Post by hikarudo »

paxy wrote: post #99
rsp1984 wrote: post #79

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

> Also I guess about 70% of (pre-qualified) candidates would outright fail the question This is probably right. Companies still use these questions, though, because they do a good job failing candidates who are not technical enough for the role. What you're essentially doing is filtering out bad candidates and selecting from good ones based on luck.

In other words, the companies are optmizing for precision, rather than recall, which makes sense.

Re: Solving dynamic programming interview problems

#136

Post by xab9 »

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

Yep. We need superman, but we are a bicycle repair shop.

Only superman will do, that is the only thing we know for sure.

Re: Solving dynamic programming interview problems

#137

Post by barrkel »

hn_throwaway_99 wrote: post #130
rsp1984 wrote: post #79

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

I very much disagree with this assessment, the reason being that, as an interviewer, the least important part for me is whether or not the interviewee "gets" the problem initially. I have no problem giving the interviewee tons of hints about (a) it's a dynamic programming problem and (b) what the different cases are. At that point though, what I'm really interested in, and what I think tells me a ton of valuable info…

Yup. Building up a shared understanding of a potential solution, and then fluency in converting that shared understanding into code, is my goal from a code pairing interview.

Crucially, I don't think it's important to have critical insight into the problem and come up with a solution unaided. We don't work alone - if we can come up with a solution together, and the candidate can be trusted to implement the solution, it's what we need.

Re: Solving dynamic programming interview problems

#138

Post by ghettoimp »

hikarudo wrote: post #135
paxy wrote: post #99

Earlier quoted context omitted.

> Also I guess about 70% of (pre-qualified) candidates would outright fail the question This is probably right. Companies still use these questions, though, because they do a good job failing candidates who are not technical enough for the role. What you're essentially doing is filtering out bad candidates and selecting from good ones based on luck.

In other words, the companies are optmizing for precision, rather than recall, which makes sense.

I've done a lot of interviewing and participated in a lot of hiring decisions at a very large tech company.

I think our process is guided far more by tradition than deliberate optimization for anything in particular. :)

Re: Solving dynamic programming interview problems

#139

Post by barrkel »

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…

Most recursive functions have a tree structure, either in the control flow or data flow. For loops don't really cut it; you minimally need auxiliary storage to track which branch you're currently on for every ancestor level, either explicitly by pushing indexes or structures onto a stack or queue, or implicitly with a work stack or queue. That's a bunch of accounting in an iterative solution you don't need with a recursive solution. The iterative solution will end up harder to read as a result. It'll also be a lot harder to reason about if the tree-like structure of the code is obscured.

If you need to return values for processing each child, and integrate them at the parent, then your solution gets tougher to reason about, as there's an ordering constraint and a dependency.

Recursion doesn't come up super often in most domains, but it's not rare. E.g. doing anything non-trivial with the DOM in a web front end, parsing an XML or JSON document, etc.

Re: Solving dynamic programming interview problems

#140

Post by ghettoimp »

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…

Very much agree.

If you are working on any kind of tree structure, graph, parse tree, etc., recursion can be really beautiful and clear.

My theory: folks like iteration because 90% of the "for" loops they write are really just "foreach".

Post reply on HN