6 ms·

Wow, having someone implement a square root algorithm on the spot, that's quite a question to ask. I agree that is a terrible question because not many top deve

Wow, having someone implement a square root algorithm on the spot, that's quite a question to ask. I agree that is a terrible question because not many top developers would be able to answer it on the spot unless they had recently happened to have implemented it. It's not like it's an obvious algorithm. I could mention the existence of Carmack's root algorithm, which I don't have memorized but I do know he got from someone else, and flop around a bit. It's weird there are so many companies claiming to not be able to find people but you hear about their hiring process and it's no wonder.

dpritchett 15y ago
Newton's method is dead simple to implement, you just have to remember it. http://mitpress.mit.edu/sicp/chapter1/node9.html http://mitpress.mit.edu/sicp/chapter1/node9.html
- drbaskin 15y ago
  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.
  - deleted 15y ago
    [deleted]
- sliverstorm 15y ago
  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.
jsnell 15y ago
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.).
- scanr 15y ago
  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.
  - jsnell 15y ago
    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.
jules 15y ago
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.
- ap22213 15y ago
  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...
  - maeon3 15y ago
    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.
    - pjscott 15y ago
      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.
      - hartez 15y ago
        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.
icedpulleys 15y ago
Binary search is a pretty obvious algorithm.
xentronium 15y ago
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
- masylum 15y ago
  that was my answer!

dpritchett 15y ago

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

drbaskin 15y ago
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.
- deleted 15y ago
  [deleted]
sliverstorm 15y ago
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.

jsnell 15y ago

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

scanr 15y ago
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.
- jsnell 15y ago
  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.

jules 15y ago

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.

ap22213 15y ago
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...
- maeon3 15y ago
  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.
  - pjscott 15y ago
    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.
    - hartez 15y ago
      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.

icedpulleys 15y ago

Binary search is a pretty obvious algorithm.

xentronium 15y ago

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

masylum 15y ago
that was my answer!