Newton's method is dead simple to implement, you just have to remember it. http://mitpress.mit.edu/sicp/chapter1/node9.html

Esoteric algorithms would be much more useful questions, IMO, if the interviewer gave you a birds-eye overview of an algorithm you cannot possibly have heard of and then have you implement it. That actually tests your chops rather than your memory.

For example, everybody knows merge sort, but assuming they didn't, draw out a couple iterations in a graph and ask them to code it.

If you're handy with simple algebra (and can remember that the derivative of x^2 is 2x) then you can remember the picture. If f(x) = x^2 - N, then you're looking for the (positive) zero of f. You take a succession of tangent lines and look at the zeros of those. So, you start with a guess (call it x_0), take the tangent line at your guess (so it has slope 2x_0 and goes through (x_0, x_0^2 -N)), then find the x-intercept of this line and make it your new guess. This is all Newton's method is. With square roots, it takes the form of averaging your previous guess and N over it.

If true, that'd make it an awesome interview question. After all, the professed goal of these kinds of questions is to see how somebody thinks and approaches programming problems. If they flop around without a clue, it's then the interviewer's job to start them on the right track. Surely any competent programmer should be able to come up with some kind of a iterative solution and then have an intelligent discussion about how it could be improved.

(I don't think it's an awesome interview question in practice though, too many people do already know how to do it.).

Now, it's entirely possible that I shouldn't work wherever you work but I think this is a terrible question to ask. The experience of 'flopping around without a clue' during an interview is both unpleasant and massively distracting. My experience so far as both interviewer and interviewee is that seeing how someone responds when freaked out is only useful if the job involves being in that state most of the time.

The only reason somebody should be flopping around with such a softball question is if they for some reason think that they're being asked to find a near-optimal way of computing square roots. The only reason the candidate would be allowed to get stuck in a dead end for a long period of time is if the interviewer doesn't know what he's doing. But I see absolutely nothing wrong with asking questions of this general type.

And again, I do not think this is a good interview question. I just think it's bad for a different reason than the original poster claimed. Which was that it's supposedly not solvable even by top engineers unless they've recently implemented the algorithm.

Implementing a square root algorithm is actually very simple:

    def sqrt(x):
      a = 1.0
      for _ in range(100): a = (a + x/a)/2
      return a

This is just Newton's method to find a solution of the equation a^2 - x = 0. For certain classes of jobs knowing Newton's method is definitely required, as it is the simplest and most widely used numerical method. And even if you don't know Newton's method I expect any programmer worth his salt to be able to come up with a bisection algorithm.

Geez. It's time for me to retire.

I've written 100,000s lines of code and released 9 different commercial products over the last 15 years, and Newton's method is far from being in my working memory.

Now, if you ask about best practices in shipping software...

Easier to remember is the bisection method: essentially, a binary search for where the graph crosses the x-axis. It's what I would have pulled out if I got asked the square root problem in an interview:

http://en.wikipedia.org/wiki/Bisection_method

Interestingly enough, I recently wrote a post explaining how to take a binary search and derive Newton's method from it: http://stevekrenzel.com/articles/newtons-law

It's a fairly straight-forward transformation.

hehe... I interviewed at a hedge fund once, 6 technical interviews in a row. One of the interviewers summed it up well when he said: "Brace yourself... The next guy is fresh out of CMU and is going to ask you questions you haven't thought about since school" (which had been about 10 years prior).

Read again what I wrote: there exist jobs that require knowledge of Newton's method, and in those cases this would be a valid interview question. This is not in disagreement with your "there exist jobs that do not require knowledge of Newton's method". You're likely to need to know about Newton's method for jobs in the area of machine learning, robot control, or some kind of physics simulation.

That said, Newton's method is not rocket science. The basic algorithm is iterating this line:

    z = z - f(z)/f'(z)

Where f is some function and f' is its derivative. In many cases this will rapidly converge to a root of f (i.e. z will converge such that f(z) = 0). As far as algorithms go, this one is pretty damn simple. It is not in my working memory either, and I expect that many people rederive it when they need it.

The idea behind Newton's algorithm is that you approximate the function f(x) with the tangent line L at z:

    L(x) = A + B*(x-z)
    with A = f(z) and B = f'(z)

Now L(x) is an approximation of f(x). How well an approximation this is depends on how much f(x) looked like a line in the first place. Then instead of solving f(x) = 0 (which is our goal, but hard) you solve L(x) = 0 (which is not exactly our goal but almost our goal, and it is easy). So:

    f(z) + f'(z)(x-z) = 0

Rewriting:

    x = z - f(z)/f'(z)

Now the approximation of f(x) at that x is 0. Because it's only an approximation to f(x) it will probably not make the real f(x) = 0. Therefore we apply the method again and again with x as the new starting point:

   z = some starting value
   until f(z) is small enough:
      z = z - f(z)/f'(z)

Because we're iterating, this method works even if f(x) doesn't look much like a line. For example x^2 - a doesn't look much like a line, but Newton's method is very effective at computing its root to compute sqrt. To see how outrageously effective it is, lets compute sqrt(2.0) with it. Lets start with a starting guess x = 1.0. We get the following numbers:

    iteration    x
    ---------    -
    1            1.0
    2            1.5
    3            1.416666666666666
    4            1.414215686274509
    5            1.414213562374689
    6            1.414213562373095
    7            1.414213562373095

Note that at the 6th iteration already all 16 digits are correct.

Newton's method is perhaps the most beautiful algorithm due to its simplicity and effectiveness, and worth knowing even if only for its beauty. It is also quite probably the most important algorithm ever invented. It is used everywhere from division in hardware to optimizing all kinds of things and solving differential equations.

Last time I implemented it, it was in FORTRAN 77.

No. Not really. During a test I quickly coded the solution to a numeric problem in BASIC on a Casio PB-700. It was fun to watch the HP-41 crowd tearing their hair off. That's when I first learned pg's "beating the averages" lesson.

Machanics are not asked to recite from memory how to install a cruise control. The fact that programmers are is just to make us feel bad so we accept low pay.

They need us so badly that they grasp at anything to show us we dont deserve to be paid. Its economics.

How sinister! I have an alternate hypothesis: they want to filter out people who can't solve simple problems, and the people coming up with the problems sometimes forget that a problem is only simple if you remember (say) Newton's method and the fact that square root finding is equivalent to solving x^2 - num = 0.

This seems more plausible to me. Recruiting is hard.

Yep. It's Hanlon's Razor.

You'd be surprised how many people with a master's in CS show up to an interview and can't write a recursive method to compute n factorial out on a whiteboard. Hell, I'd say about 10% of the people I interviewed couldn't successfully complete FizzBuzz.

Technical weed-out questions are an unfortunate but necessary part of tech recruiting until other, better signals of ability are widely available.

Yes, because it's not like any such signals are now available: http://devinterviews.pen.io/

Seriously, this is one reason I like the emphasis smart companies are putting on github accounts. Better signals are available, and portfolios are one such signal, and one that works great for many other professions.

tl;dr; - Too many good people have 'portfolios' that they can't legally show me; until that changes, I have to ask people to code on a whiteboard.

Here's the more nuanced version (in which I largely agree with jnbiche):

The stuff listed in that article under "An Alternative" describes the exact tech interview I used to give. And we had several people pass it with flying colors who we later had to let go because they couldn't actually translate a requirement into code.

So we adjusted our interview to make sure that people had the ability to write basic code. I'm not talking about stupid puzzles or API quizzes. I'm talking about 'show me you understand what recursion is'. I'm talking about 'given a detailed description of the FizzBuzz problem, can you write me a loop (in any language; pseudocode is fine, too) that outputs the right answer? And can you adjust your code if I change the requirements slightly?' Stuff that anyone who codes on a daily basis should be able to breeze through.

This was dead-easy stuff. Just me and the candidate in a room - there wasn't a giant audience, there was not ticking clock, and I was explaining the algorithms. And again, quite a few people could not do it.

If they could do it, we moved on to the original interview where I asked about technology, past projects, etc. Some people didn't pass that part of the interview.

Believe me, we were stoked when we got a candidate who listed open-source projects on a resume or brought it up in the interview, because we got to see real-world code that the candidate had written. But that was a relatively rare occurrence.

This brings me to the crux of the 'until other, better signals of ability are widely available' comment. I think it's widely agreed (at least, in a place like HN) that code is the best signal of ability. But there are many, many candidates who write excellent code that no one outside of their company will (or even legally can) ever see. If I turned away candidates just because they didn't have a github account, I would have missed out on some of the greatest coders I ever worked with. There are plenty of people who passionately write excellent software every day, but who do so under NDA. They may not work on OS projects in their off time because they may not have any (or they have kids, or other time-consuming hobbies).

So for a lot of fantastic coders, the best possible signal of their ability is not publicly available. I would even go as far as to suggest that this may be true for the majority of fantastic coders. Everyone has to pay the bills, which means 8 hours of writing custom business software for a lot of people. I know for a fact that some of the best stuff I've ever written is buried with companies that failed, never to see the light of day. I can't show that in an interview. How many other people are in the same boat? http://xkcd.com/664/

Obviously, one huge part of the solution to this problem is for companies to open-source their code. That movement has already begun; lots of successful companies have come to the realization that keeping their code 'secret' has no value while allowing outside review and contribution has immense value. And some smart companies which use a lot of open-source tools and libraries are paying their employees to contribute bug fixes and features. Those trends are starting to address the 'widely available' part of my comment, and the day may eventually come where employers can simply throw away resumes which don't have any links to code contributions. In fact, if you're looking for another bullet point on your presentation to your employer about "why we should do open source", I would suggest mentioning the hiring benefits to the entire community.

But until we hit that critical mass, I'm still going to have to ask people to implement n-factorial on a whiteboard.

Oops, I fat fingered a downvote, but this deserves upvotes.

I actually do know offhand that I use the Taylor series to calculate it, and that the Carmack method works by using a couple tricks of binary floating point format to do a really good starting point and then run the Taylor series through a single round of iteration. I've also implemented it myself before since library methods were too slow. This probably puts me in the top 0.001% of developers world wide in terms of what I happen to have memorized and from personal experience about square roots. However, I don't offhand remember the details at all and wouldn't pretend to. I would never use this an an interview question because it doesn't test for anything at all. 99% of candidates would have no clue regardless of skill level, and of the 1% who knew anything, most would be because they happened to study the right "interview tricks" site while cramming for the interview. So I still think these sorts of questions are absolutely terrible for the purpose of finding competent developers.

Top 0.001%? Newton's method was high school math for me. Surely more than 1 in 100,000 programmers can remember basic Calculus.

Depends on what the job is though, if your building web apps and your unlikely to ever need to even use a built in sqrt function I don't think it's a good question. A good question would be one the candidate doesn't know but can think their way through. For a lot if candidates I'd imagine this question wouldn't let you learn to much about their problem solving.

My solution was far worse than this one... :)

Binary search is a pretty obvious algorithm.

Sometimes you have to improvise. If you have never heard of newton's method, binary search should probably come to mind next. It should be O(log N) which is a bit worse than constant-complexity square root but not too bad.

    DELTA = 0.0000001
    def sqrt_bin_search(squared_value, lower, higher)
      middle = (lower + higher) / 2.0
      if ((middle * middle) - squared_value).abs < DELTA
        middle
      elsif middle * middle > squared_value
        sqrt_bin_search(squared_value, lower, middle)
      else
        sqrt_bin_search(squared_value, middle, higher)
      end
    end

    def sqrt(x)
      sqrt_bin_search(x, 0, x)
    end

that was my answer!