That frist one?
All I'm thinking is about how the dreamer will chase the coder around the moons of Nibia...
What? There was a nebula involved during that, and that's the cloud.....

Remy Porter2012-09-18 08:08

I'm not taking the Star Trek job unless I get a free trip to TechEd on Risa.

coder guy2012-09-18 08:09

It seems to me that anyone who can't even come up with a lame attempt at successive approximation to figure out a square root without running to a reference isn't fit for a programming job.

vwiggins2012-09-18 08:10

The second one has made me really sad. I get lost all the time, especially if I'm nervous. If someone judged my ability as a developer based on my inability to learn left from right or find my way around a place I've never been before I'd be horrified.

Rhywden2012-09-18 08:14

coder guy:

It seems to me that anyone who can't even come up with a lame attempt at successive approximation to figure out a square root without running to a reference isn't fit for a programming job.

Then again, if you don't have access to the internet, don't have anyone to ask and there's no other source of information around...

... then it's most likely the time of the Zombie Apocalypse, in which case I'd ask myself as to why in the seven frozen hells I'd need to calculate the square root of two.

Some smart guy once said: “I don't need to know everything, I just need to know where to find it, when I need it”

snoofle2012-09-18 08:15

coder guy:

It seems to me that anyone who can't even come up with a lame attempt at successive approximation to figure out a square root without running to a reference isn't fit for a programming job.

Why? The guy wanted an exact value, not an approximation.

If I asked you to come up with a formula for something you honestly didn't know how to calculate, you might approximate, but you won't get it exact.

Rodnas2012-09-18 08:17

M: So, there is no one around. The people that aren't around have not invented the book yet or the internet, but trough some magic occurence there is a computer... I guess would get completely naked run around town, get drunk and destroy random objects. I would certainly not go solve some stupid programming problem

Dim2012-09-18 08:19

square root.

Asking someone to solve a problem using the most creative,original or complicated solution is clearly the best way to hire programmers who will create the worst thing possible to solve everyday problems.

Leaving the interview is clearly the best approach to that kind of question, your clearly don't want to work with people who answer "correctly"

Niels2012-09-18 08:20

An iterative approximation for a square root shouldn't be hard to come up with.

the real wtf is to consider Carmack's formula for solving sqrt.

Michael2012-09-18 08:21

I have been in one of those "Square Root of Stupid" before. I once interviewed with a bank, when the interviewer asked:
He: So, imagine our data center in London goes down, what are you going to do?
Me: We hopefully automatically fall over to NYC.
He: What if NYC also goes down?
Me: We hopefully automatically fall over to Tokyo.
He: What if Tokyo also goes down?
Me: I will go to the nearest supermarket, grab all the cans of food and drinks I can get and drive up North as fast as I can.

asdbsd2012-09-18 08:30

That last one was awful. Although you don't get to write square root formulas often, in real life not all answers are readily available. Being a programmer means that sometimes there's no site, no person, no book with the answer, and you have to patch something up by yourself. It is this ability which the interviewer obviously wanted to test. Walking away at this point is just stupid.

I know no formula for square root calculation, but I'd suggest some variation of binary search for instance. Take (a+b)/2, check it's square, if it's bigger than x then a:=(a+b)/2 else b:=(a+b)/2, repeat until you have the required precision.
This probably sucks in terms of speed, but hey, at least it works.

Matt2012-09-18 08:32

>> I: What if there were no bookstore?

I'd ask you as you obviously seem to know all the answers...

captcha : secundum (but not fristum...)

asdbsd2012-09-18 08:33

snoofle:

Why? The guy wanted an exact value, not an approximation.

If I asked you to come up with a formula for something you honestly didn't know how to calculate, you might approximate, but you won't get it exact.

Just to remind you, there's no such thing as "exact" with floating point numbers. So they didn't ask him to give "exact" value. They asked to do his best at approximation.

TheRider2012-09-18 08:36

Niels:

An iterative approximation for a square root shouldn't be hard to come up with.

What if you can't use the multiplication operator to square a number?

Andrew2012-09-18 08:38

What if there were no square root function?

This tells me that I am not working in a language I know, as all of them require sqrt implementations in their libraries. I wouldn't look for an approximation; I'd look for another job.

It's funny how it's always Carmack's approximation, when in fact it was done by someone else at SGI. I wonder if that guy did it in 640k of RAM?

Studley2012-09-18 08:41

What if there were no numbers?

Anonymous Coward2012-09-18 08:47

1. How do you know he wanted an exact value? You left without offering a non-exact solution.

2. Successive approximation WILL give you an exact value. You just repeat it until it converges. You know when it has converged because either square(x)==y or square(x)<y && square(Math.nextAfter(x))>y .

3. The problem is that the interviewer didn't portray it very well as a brainteaser and/or mathematical aptitude type question. If he'd started out by asking, "How would you calculate a floating-point square root without using the library function? (or the whole math library, depending on how easy you want to make the problem)", hopefully you wouldn't have given silly answers like, "ask someone".

Calculating a square root isn't something where you either know it or you don't. If you ask someone the arguments to an API function, they have to either know it, say they don't know, or walk out or whatever. For a square root, there are a large number of solutions of varying degrees of quality. Obviously it is not a hugely relevant question for upgrading a legacy system, but neither is asking how many golf balls would fill the Washington Monument or something. Giving up a feasible problem without attempting it is not going to help your job prospects.

Ron Moses2012-09-18 08:47

...although I do agree with the guy's assessment of THE CLOUD. Pure marketing cr*p.

This morning I commuted to work on this new thing called THE GRID. It's a nationwide network of interconnected asphalt lanes - it really is the future of personal and commercial transportation. We have an IPO coming up if you're interested...?

Fool2012-09-18 08:50

If I was writing java code and there were no Math.sqrt function i would try to figure out what what jar file is missing, where and then contact IT to fix it.

snoofle2012-09-18 08:52

asdbsd:

That last one was awful. Although you don't get to write square root formulas often, in real life not all answers are readily available. Being a programmer means that sometimes there's no site, no person, no book with the answer, and you have to patch something up by yourself. It is this ability which the interviewer obviously wanted to test. Walking away at this point is just stupid.

I know no formula for square root calculation, but I'd suggest some variation of binary search for instance. Take (a+b)/2, check it's square, if it's bigger than x then a:=(a+b)/2 else b:=(a+b)/2, repeat until you have the required precision.
This probably sucks in terms of speed, but hey, at least it works.

True, one can approximate, but coming up with an algorithm usually requires a little thought (aka: time), and in an interview, you don't get to take the required time to think things out; you either know it or you don't.

After that interview, I had time to think about it and I came up with:

Start squaring numbers from 1 up until you exceed the target value, then back up one, and start incrementing the next smaller digit (1's, then tenths, then hundredths, etc) until you arrive at the required precision. Big deal; I can come up with a crappy algorithm for calculating something for which there are known formulas. I make no claims of being a mathematician. nor would I even want a job where I was responsible for coming up with such formulas.

A more sensible question might be to ask me: we've got A amount of data, B amount of storage, C transaction rate and D throughput. There is a problem xxx. How would you diagnose this? What are the likely causes and possible solutions?

That tells the interviewer how I think in terms of things pertinent to the job.

@Deprecated2012-09-18 08:53

Studley:

What if there were no numbers?

That's easy!

function sqrt() { return NaN; }

Chris P. Peterson2012-09-18 08:56

There is no way the guy wanted an exact answer. He was trying to see the candidate's thought process when the answer was not available. The interviewer could've done a better job at asking the question and the candidate should've done a better job at realizing what was being asked and made an attempt.

John2012-09-18 08:56

snoofle:

...
The guy wanted an exact value, not an approximation. If I asked you to come up with a formula for something you honestly didn't know how to calculate, you might approximate, but you won't get it exact.

Hey, where can I get a computer like yours, that can represent sqrt(2) exactly? I could really use a computer with infinite-precision reals.

The REAL WTF2012-09-18 08:57

snoofle:

coder guy:

It seems to me that anyone who can't even come up with a lame attempt at successive approximation to figure out a square root without running to a reference isn't fit for a programming job.

Why? The guy wanted an exact value, not an approximation.

If I asked you to come up with a formula for something you honestly didn't know how to calculate, you might approximate, but you won't get it exact.

Without commenting on the value of the question for the interview, the above is simply wrong, at least for square root. Your approximation function should either find the exact value (what's the square root of 25?) or there IS no exact value (what's the square root of 2?) and it should be able to calculate it to any desired precision.

Anonymous Coward2012-09-18 08:59

[quote="snoofle"]That tells the interviewer how I think in terms of things pertinent to the job.[/quote]
Do you walk out of interviews whenever posed any problem to solve that's not directly pertinent to your job?

Anoldhacker2012-09-18 09:01

Niels:

An iterative approximation for a square root shouldn't be hard to come up with.

This should be considered a good example of precisely why you don't do things like this yourself. The square root of x for small x is much larger than x. The quick return is not needed for non-negative numbers, and if it were, the boundary would be EPSILON * EPSILON. (And no, the square root of -1.0 is NOT even close to 0.0.)

Yes, my degrees are in mathematics, and I did floating point validation in the '90s. Seriously, don't try this at home, kids.

(The way that we actually compute floating point square roots is fun. We look up the first several digits for the inverse square root, and then refine it based on polynomials designed to cancel the error term, usually quadratically. Once there is enough precision, you multiply back the original value to get the square root. Yes, you want a real proof that the algorithm works.)

AGray2012-09-18 09:02

Snoofle's tale of the interview is probably the most alarming - you apply for a job where apparently the boss expects you to work with zero resources?

I think Snoofle was right - the employer was totally wasting his time, and did a great job of letting Snoofle know that that was totally the wrong place to be, let alone work. The place next door that lets developers use Internet is a vast improvement!

Wide Awake2012-09-18 09:02

we're dreamers, we're entirely conceptual

Wow! That is one refreshing level of honesty there! I know there are at least a hundred million "business leaders" who should stand up to the same admission, but I never thought any of them actually would!

foo2012-09-18 09:06

vwiggins:

The second one has made me really sad. I get lost all the time, especially if I'm nervous. If someone judged my ability as a developer based on my inability to learn left from right or find my way around a place I've never been before I'd be horrified.

That's not what happened. The candidate walked away.

The way I read it, he "pimped up" his CV and was trying to cheat his way through the interview. When he learned there'd be a technical test, he was "not prepared for" cheating it, so he made up a lame excuse to leave.

DES2012-09-18 09:07

If I was conducting interviews for a programmer position, I'd immediately fail any candidate who didn't know Newton's method and was unable to come up with it (or a similar successive approximation method) on the spot. It is blindingly obvious, and trivial to implement.

I'd probably also fail any candidate who didn't, at some point, suggest Math.exp(Math.log(x) / 2). And even if Math.log() isn't available, you can easily compute a rough lower bound of log(x) through successive division, as an initial guess for successive approximation.

(to those who complained that Newton's method does not give an exact value: where does it say that the interviewer expected an exact value? in any case, with a few exceptions, the floating-point representation of a number will always be an approximation of the actual value.)

As for Carmack's method: assuming it can be implemented in Java (it can't—not without a lot of contortions), it can easily be derived from first principles if you know basic algebra and the layout of IEEE 754 floating-point numbers. If you don't know the layout, you can easily figure it out by looking at the binary representation of a handful of test values.

So TRWTF is that the candidate refused to even try to think of an answer, then blamed the interviewer for asking him a question he should have been able to answer but wasn't.

emaNrouY-Here2012-09-18 09:07

TheRider:

Niels:

An iterative approximation for a square root shouldn't be hard to come up with.
<SNIP>

What if you can't use the multiplication operator to square a number?

And What if you can't use addition?

(It's a flipping adding machine!!!)

Spastic Weasel2012-09-18 09:08

Newtons method of iterative approximation would be doable off the top of my head.

Sebastian Buchannon2012-09-18 09:10

double Sqrt(double val)
{
double ret;
while (true)
{
ret = rand() * double.Max;
if (double.Equals(ret,val))
return ret;
}
}

He never said he wanted it quick

snoofle++2012-09-18 09:10

When you give an amateur programmer a problem, their first impulse is to roll their own solution.

A pro goes to the language libraries first, the in-house code base second, the world of pre-written solutions third, then asks "has anyone else poured some thought into this problem" before inventing his own wheel.

Snoofle, I think you bailed 5 seconds early. Based on your answers I would have been offering you a job in the next breath.

Helpfull2012-09-18 09:10

If you answer ARM and Intel have built in assembly squareroot instructions the next question will be what if you don't have a processor :)

QJo2012-09-18 09:10

snoofle:

coder guy:

It seems to me that anyone who can't even come up with a lame attempt at successive approximation to figure out a square root without running to a reference isn't fit for a programming job.

Why? The guy wanted an exact value, not an approximation.

If I asked you to come up with a formula for something you honestly didn't know how to calculate, you might approximate, but you won't get it exact.

Fail. You can't get it exact because square roots are (in all cases except when all the prime factors are to an even power) irrational.

Granted that you may not be able to come up with: guess, divide your number by that guess, take mean of result with guess, and repeat, IMO it's something that you might be expected to be able to work out.

Depends on whether your expertise is borne of a lot of experience or a combination of that and the ability to figger things out from scratch. Fair enough, though, it certainly appears that you and your prospective employer would not have been a good match.

foo2012-09-18 09:11

John:

snoofle:

...
The guy wanted an exact value, not an approximation. If I asked you to come up with a formula for something you honestly didn't know how to calculate, you might approximate, but you won't get it exact.

Hey, where can I get a computer like yours, that can represent sqrt(2) exactly? I could really use a computer with infinite-precision reals.

Ever heard of computer algebra systems? Representing sqrt(2) exactly isn't hard, yet outputting it in decimal (or any other base) will take ... some time ...

foo2012-09-18 09:13

emaNrouY-Here:

TheRider:

Niels:

An iterative approximation for a square root shouldn't be hard to come up with.
<SNIP>

What if you can't use the multiplication operator to square a number?

And What if you can't use addition?

(It's a flipping adding machine!!!)

If you need anything more than NAND gates, you're not qualified.

Joe2012-09-18 09:16

DES:

I'd probably also fail any candidate who didn't, at some point, suggest Math.exp(Math.log(x) / 2).

I've been programming for 30 years and I can guarantee you I've never had the slightest use for Math.exp or Math.log. Some programming jobs aren't about math, despite what your Computer Science teacher told you. And I'm talking real code, not drag-and-drop crap.

Hell, half the stuff I see CS grads crank out barely works. But I suppose it's mathematically sound, so there's that.

foo2012-09-18 09:17

Sebastian Buchannon:

double Sqrt(double val)
{
double ret;
while (true)
{
ret = rand() * double.Max;
if (double.Equals(ret,val))
return ret;
}
}

He never said he wanted it quick

I know you just forgot to square, but this way it's even more ridiculous. :)

Anonymous Coward2012-09-18 09:17

snoofle++:

When you give an amateur programmer a problem, their first impulse is to roll their own solution.

A pro goes to the language libraries first, the in-house code base second, the world of pre-written solutions third, then asks "has anyone else poured some thought into this problem" before inventing his own wheel.

Snoofle, I think you bailed 5 seconds early. Based on your answers I would have been offering you a job in the next breath.

I think it was poorly posed, but it's a legitimate question. If I started off the way snoofle's interviewer did, after the "Google" response I would have said something like: "Of course, we would never want a programmer to try to implement their own square root. However, as an interview puzzle, I'd like to know how you'd calculate a square root without the library." Hopefully that would rule out answers like, "buy a book".

Zecc2012-09-18 09:18

John:

snoofle:

...
The guy wanted an exact value, not an approximation. If I asked you to come up with a formula for something you honestly didn't know how to calculate, you might approximate, but you won't get it exact.

Hey, where can I get a computer like yours, that can represent sqrt(2) exactly? I could really use a computer with infinite-precision reals.

I'm no expert, but I believe Mathematica can probably represent the exact value of 2, even if "only" symbolically.

robert2012-09-18 09:19

[quote user="Anonymous Coward"]1. How do you know he wanted an exact value? You left without offering a non-exact solution.

2. Successive approximation WILL give you an exact value.

That's impossible.
Most square root functions return an irrational number, i.e.: their digits repeat endlessly without a recurring pattern. There is no representation for the number in a digit-based system.

onitake2012-09-18 09:19

I remember our math teacher showing us what Wikipedia calls Digit-by-digit calculation, just for the fun of it.
But I totally forgot how it went, so I probably would have failed that interview too.

Yaos2012-09-18 09:21

If you want a clever programmer that's exactly what you're going to get. Why use the built-in square root function when you can create your own version that somehow only works 50% of the time? Any way, I would just pre-compute trillions of square roots.

Schmitter2012-09-18 09:22

The square root issue is easy. Just convert the whole system to HTML5, put it on network 3.0 (the cloud) where every number automatically shows it square root next to it. 9(3)

P.S. Why can't I copy/paste the CAPTCHA?

jonnyq2012-09-18 09:23

Anyone who comes up with a lame attempt at approximation to figure out a square root without checking a reference, and puts that code in production with the obvious zombie apocolypse going on, isn't fit for a programming job.

Jeff2012-09-18 09:24

Me: How does my ability to pontificate about unrealistic problems in an artificially constrained setting under unusual pressure relate to the projects for which you are hiring?

Interviewer: I want to see how you think.

Me: I think I want to work somewhere that is evaluating me for my technical skills, not my game show skills.

Graham Dunn2012-09-18 09:26

also, you should really not suggest coding up one of the most advanced data analytics programs in a markup language.

Unless Apple is now shuffling their Siri searches off to Deep Blue, maybe you should not refer to a wrapper around a voice to text system + search engine as "one of the most advanced data analytics programs"

¯\(°_o)/¯ I DUNNO LOL2012-09-18 09:27

Chris P. Peterson:

There is no way the guy wanted an exact answer. He was trying to see the candidate's thought process when the answer was not available. The interviewer could've done a better job at asking the question and the candidate should've done a better job at realizing what was being asked and made an attempt.

And the point is that if the interviewer is that bad at asking questions, it probably indicates a general level of WTFery at the company. "What if there were no bookstores?" Then society has fallen apart and I have more important things to do than your silly square roots. Leaving was the correct answer.

Anonymous Coward2012-09-18 09:30

robert:

Anonymous Coward:

1. How do you know he wanted an exact value? You left without offering a non-exact solution.

2. Successive approximation WILL give you an exact value.

That's impossible.
Most square root functions return an irrational number, i.e.: their digits repeat endlessly without a recurring pattern. There is no representation for the number in a digit-based system.

As you can see in the portion of my point 2 that you omitted, I didn't really mean "exact", but rather "as exact as representable". More generally, I meant, "you can do just as good as Math.sqrt with successive approximation".

Franky2012-09-18 09:31

asdbsd:

That last one was awful. Although you don't get to write square root formulas often, in real life not all answers are readily available. Being a programmer means that sometimes there's no site, no person, no book with the answer, and you have to patch something up by yourself.

jeah, but up to that point until you have consulted all (easily available) it would be stupid to invent anything ... and if you want your programmer to show some skill, ask him for some real problem from the area he will actually be hired for (I am pretty sure the job didn't involve squareroots to begin with). Some ppl are great in writing formulas, others are great in working with data, others are great getting security right, etc. etc.

Rick2012-09-18 09:32

¯\(°_o)/¯ I DUNNO LOL:

Chris P. Peterson:

There is no way the guy wanted an exact answer. He was trying to see the candidate's thought process when the answer was not available. The interviewer could've done a better job at asking the question and the candidate should've done a better job at realizing what was being asked and made an attempt.

And the point is that if the interviewer is that bad at asking questions, it probably indicates a general level of WTFery at the company. "What if there were no bookstores?" Then society has fallen apart and I have more important things to do than your silly square roots. Leaving was the correct answer.

Maybe the interviewer was testing to see whether the applicant would perform any task, no matter how stupid. This is an important quality at many jobs.

Interviewing is a totally different skill from actually doing the job and I would have stayed for the practice.

Sebastian Buchannon2012-09-18 09:33

I am surprised JAVA doesn't come with a square root function. I thought all these new flash-in-the-pan modern languages were supposed to have all the bells and whistles.

Yet another case where I would shine in an interview, possibly even convincing the company to undergo an organizational switch to a real programming language in the process.

01 WS-INPUT COMP-2.
02 WS-OUTPUT COMP-2.

COMPUTE WS-OUTPUT = FUNCTION SQRT (WS-INPUT)

StMarc2012-09-18 09:37

Perhaps he wanted to know if that last fellow knew anything about how algorithms are actually *created.* Since anybody who knows what a square root actually *is* should be able to create an algorithm to approximate one to any desired precision in about ten seconds.

@Deprecated2012-09-18 09:38

jonnyq:

Anyone who comes up with a lame attempt at approximation to figure out a square root without checking a reference, and puts that code in production with the obvious zombie apocolypse going on, isn't fit for a programming job.

If you are trying to program your way out of a zombie apocalypse, you probably have a heck of a lot of code to write, and you'd better get it done NOW NOW NOW!
Plus you might not want to venture outside to go the bookstore.

English Man2012-09-18 09:39

Yeah. I mean tell them you don't know a formula but it's clear they want you to try and figure it out. This isn't a dumb "how many piano tuners are there" question, but an attempt to see if you can do maths.

Anonymous Coward2012-09-18 09:40

jonnyq:

Anyone who comes up with a lame attempt at approximation to figure out a square root without checking a reference, and puts that code in production with the obvious zombie apocolypse going on, isn't fit for a programming job.

This needlessly excludes simple programming questions that happen to have a library function. Years ago, I had an interviewer ask me something like, "You have a string of words separated by spaces. How do you reverse the order of the words in-place?" I didn't say, "What kind of crazy person would do that in-place in production code? That's grossly premature optimization. Also, you'd have to be a terrible programmer not to just use split() and reverse(). We haven't even considered localization issues with the whitespace characters!" I answered the damn question.

How can you possibly answer interview questions if you treat them like production code? It's a bizarre standard, but suddenly everyone pulls it out because some guy was asked how he'd implement a library function.

snoofle2012-09-18 09:41

Rick:

[I would have stayed for the practice.

If it's at the beginning of a job search, I probably would have stayed for the practice, if only to get current on my list of good-snappy-answers-to-stupid-questions for subsequent interviews. Unfortunately, this was near the end of my job search, and I was on-my-game w.r.t. interviewing, so I just cut it short.

I found out much later that I knew someone in another department at that company, and walking away from this person (interviewer) was absolutely the right thing to do.

Captcha:luctus2012-09-18 09:42

Snoofle quit his job‽?

Sebastian Buchannon2012-09-18 09:42

@Deprecated:

jonnyq:

Anyone who comes up with a lame attempt at approximation to figure out a square root without checking a reference, and puts that code in production with the obvious zombie apocolypse going on, isn't fit for a programming job.

If you are trying to program your way out of a zombie apocalypse, you probably have a heck of a lot of code to write, and you'd better get it done NOW NOW NOW!
Plus you might not want to venture outside to go the bookstore.

Bookstore is one of the places you want to go in an apocalypse. It's not a priority but with no internet it'll be pretty useful in the longterm to get books on basic medicine and electronics, etc.

DES2012-09-18 09:44

Helpfull:

If you answer ARM and Intel have built in assembly squareroot instructions the next question will be what if you don't have a processor :)

Please show me how to use those built-in instructions in a Java program.

Severity One2012-09-18 09:44

asdbsd:

That last one was awful. Although you don't get to write square root formulas often, in real life not all answers are readily available. Being a programmer means that sometimes there's no site, no person, no book with the answer, and you have to patch something up by yourself. It is this ability which the interviewer obviously wanted to test. Walking away at this point is just stupid.

If he wanted to know how you'd deal with a situation where you don't have all the information readily available, he should have bloody asked and not come up with some Interview 2.0 rubbish that he clearly didn't understand himself.

DES2012-09-18 09:53

Joe:

I've been programming for 30 years and I can guarantee you I've never had the slightest use for Math.exp or Math.log. Some programming jobs aren't about math, despite what your Computer Science teacher told you. And I'm talking real code, not drag-and-drop crap.

None of my computer science teachers ever told me that programming was about math. Where did you get that idea? However, I'd expect candidates to have at least completed high school.

BTW, “I've been programming for 30 years” doesn't impress me. I've worked with people with as much experience as you or more who were still totally incompetent.

me myself and I2012-09-18 09:54

John:

Hey, where can I get a computer like yours, that can represent sqrt(2) exactly?

Your computer can already represent that perfectly.

√2

See, that was not soo difficult, or was it?

taustin2012-09-18 09:54

Weird -- that was exactly what I thought up after I read that. It's a crappy, but simple as...

Sockatume2012-09-18 09:55

The interviewer doesn't want to know how the candidate *thinks* he would react to a problem outside of his training. The interviewer wants to know how the candidate would *actually* react. Apparently in this case it's to rage out of the office.

I'd love to see his take on the Kobiyashi Maru.

("Interview 2.0"? Problems like that have been a standard part of technical interviews for decades.)

Barc2012-09-18 09:56

For the last one, I think it was a fail on both parts. The interviewer should've known when to cut his losses and tried a different tact. But the interviewee is obviously a bit of a prima donna without patience. His side of the story is the interviewer was being unreasonable but to the interviewer he wasn't answering the question, just deflecting it. The interviewer probably told his co-workers about the bullet they just dodged in the guy who would have trouble holding down a job if he didn't curb the attitude. Truth is they're probably better off without each other.

Poster #sqrt(2)2012-09-18 09:58

The REAL WTF:

Your approximation function should either find the exact value (what's the square root of 25?) or there IS no exact value (what's the square root of 2?) and it should be able to calculate it to any desired precision.

Now you've done it and insulted sqrt(2), claiming that it does not even exist.

ammoQ2012-09-18 09:59

Back in 1994, the programmers responsible for maintaining a legacy ERP systems asked me how to calculate the cubic root of a number, because they were using COBOL and apparently they didn't have a math library available. I explained them how to do that using Newton's approximation, which was good enough for the problem at hand.

In my experience, being completely unable to handle this kind of problem without using a library function is not something I'd like to see in my fellow team members.

mrs_helm2012-09-18 09:59

Actually, it was a test to see how patient and creative you are when your superiors give you completely unrealistic project specs. Which happens often at many, many employers.

Sockatume2012-09-18 10:08

"Now you've done it and insulted sqrt(2), claiming that it does not even exist."

Yeah, you don't want to piss of sqrt(2). He's been working out. Stomach crunches mostly. His physique is completely ab-surd.

snoofle2012-09-18 10:12

Sockatume:

The interviewer doesn't want to know how the candidate *thinks* he would react to a problem outside of his training. The interviewer wants to know how the candidate would *actually* react. Apparently in this case it's to rage out of the office.

I'd love to see his take on the Kobiyashi Maru.

("Interview 2.0"? Problems like that have been a standard part of technical interviews for decades.)

Rage?

Yes, Interview 2.0 questions have been around for a long time; but they've been mostly pointless for a long time too.

I have found, mostly through sheer repetition, that certain things done by interviewers during an interview are (at least in my case) pretty good indicators that I don't want the job. I used to try my darnedest to answer such questions, only to get the job and realize I should have run away. After a while, you just learn to recognize the clues.

Does it apply in every situation? Of course not. Are there times when I will try and answer such questions? That depends on how they are framed.

But just because you're in an interview doesn't mean you should put up with pointlessness. It wastes your time, tells you a great deal about the interviewer and possibly what the job would be like were you to accidentally get it. It's not an absolute rule, but at least in my own experience, is usually a reasonably reliable indicator.

golddog2012-09-18 10:12

snoofle++:

When you give an amateur programmer a problem, their first impulse is to roll their own solution.

A pro goes to the language libraries first, the in-house code base second, the world of pre-written solutions third, then asks "has anyone else poured some thought into this problem" before inventing his own wheel.

Snoofle, I think you bailed 5 seconds early. Based on your answers I would have been offering you a job in the next breath.

It's also amazing how differently people perceive the same interaction.

Last time I was on the interview trail, a person asked how to reverse the characters in a string (C#, asp.net). I suggested using String.reverse.

"Well, what if that wasn't available?"...We then talked a bit about creating a method to do so, null-checking, what's their requirements for a cases like that or empty string. I may have even mentioned extension methods to avoid the null problem.

Anyway, I got home, called the recruiter and said that I didn't think it had gone very well, as the interview just kind of ended after that.

Twenty minutes later, she called back and said they loved me, asking if I had time that afternoon to meet with the VP-type guy for a final interview.

Strange how I thought that part went really badly, and they thought it went well, apparently. Never thought that they might be going for, "does this guy not reinvent the wheel?" until I saw snoofle++'s answer.

snoofle2012-09-18 10:14

ammoQ:

Back in 1994, the programmers responsible for maintaining a legacy ERP systems asked me how to calculate the cubic root of a number, because they were using COBOL and apparently they didn't have a math library available. I explained them how to do that using Newton's approximation, which was good enough for the problem at hand.

In my experience, being completely unable to handle this kind of problem without using a library function is not something I'd like to see in my fellow team members.

So they were able to ask a co-worker? Nobody said I was completely unable to handle it; only that I couldn't do it in the 10ish seconds you have to answer an interview question before the silence becomes awkward.

Anonymous Coward2012-09-18 10:17

snoofle:

the 10ish seconds you have to answer an interview question before the silence becomes awkward.

There's your problem...
Interviews can't have questions that require more than 10ish seconds of thought?

TGV2012-09-18 10:17

myke:

the real wtf is to consider Carmack's formula for solving sqrt.

Come one, the first port of call for any mathematical problem is most definitely the Quake code. It's all in there.

BTW, I imagine the dialog would have continued like this:
Me: I'd try to remember or work out Newton's formula.
Interviewer: Assume Newton was never born.
Me: Then we wouldn't be here.

TheCPUWizard2012-09-18 10:25

It's going to like Siri

That could get interesting, what if this turned into something more? Would Siri go out on a date with it?

ammoQ2012-09-18 10:25

snoofle:

ammoQ:

Back in 1994, the programmers responsible for maintaining a legacy ERP systems asked me how to calculate the cubic root of a number, because they were using COBOL and apparently they didn't have a math library available. I explained them how to do that using Newton's approximation, which was good enough for the problem at hand.

So they were able to ask a co-worker?

No, they were able to ask an expensive consultant ;-)

Nobody said I was completely unable to handle it; only that I couldn't do it in the 10ish seconds you have to answer an interview question before the silence becomes awkward.

Well, maybe something along the lines of "approximation" would have been good enough for an answer. Just walking away is a sign of a short-tempered personality, you should work on it.

ping floyd2012-09-18 10:28

Jeff:

Me: How does my ability to pontificate about unrealistic problems in an artificially constrained setting under unusual pressure relate to the projects for which you are hiring?

Interviewer: I want to see how you think.

Me: I think I want to work somewhere that is evaluating me for my technical skills, not my game show skills.

Sorry, Jeff, but we have some lovely parting gifts for you!

snoofle2012-09-18 10:28

Anonymous Coward:

snoofle:

the 10ish seconds you have to answer an interview question before the silence becomes awkward.

There's your problem...
Interviews can't have questions that require more than 10ish seconds of thought?

Of course they can, but based upon personal experience, I've noticed that if you don't answer very quickly, the interviewer starts acting like you can't do it at all and need hints, as opposed to a minute or two to just think it through. It doesn't matter if you answer correctly, you look like you aren't a good fit. At that point, if the interviewer becomes somewhat aggressive, it tells me that they are a) impatient, b) unrealistic (not everyone who doesn't know something can figure it out in an instant) and c) at least for me - not someone I want to work with/for

Sebastian Buchannon2012-09-18 10:31

Assume you weren't even asked the question and this interview isn't actually happening. You are back at home. A path leads to the North and the South.

snoofle2012-09-18 10:38

ammoQ:

Just walking away is a sign of a short-tempered personality, you should work on it.

After all the stories I've posted about my present client, if I had even the slightest short-tempered personality, I doubt that I'd still be working here.

Usually, the walking-away is in response to more than one warning sign. This was just the last bit of pointlessness I was willing to tolerate. The previous questions all caused alarms.

As I said earlier, it turned out that my PHB-radar was dead-on with this guy.

Besides, if I had taken that job, I wouldn't be working HERE!

Pluvius2012-09-18 10:40

The neverending "you can't win" questions always remind me of the bear joke.

"Hey, Jim, what would you do if you were in the forest and you met a bear?"
"I'd back away slowly."
"But it's mad, it attacks you!"
"I shoot it."
"You don't have a gun!"
"I run away."
"It runs faster than you!"
"I climb a tree."
"It climbs better than you!"
"I jump in the river."
"It swims faster than you!!"
"Listen, Mike, whose side are you on, mine or the bear's?"

And the punchline variation:

"I'd hide."
"It's much better than you at hiding and you'll never find it again!"

A.S.2012-09-18 10:41

The WTF in the square root of stupid is that the candidate didn't understand that one workable solution (that doesn't involve a formula) would be an algorithm based around recursion. I think the interviewer learned more than the interviewee.

David2012-09-18 10:42

ammoQ:

Just walking away is a sign of a short-tempered personality, you should work on it.

Au contraire: some of us are *proud* of the fact that we do not suffer fools gladly. Sometimes this can hurt a fools feelings. Isnt life tragic?

David2012-09-18 10:45

Pluvius:

"Listen, Mike, whose side are you on, mine or the bear's?"

And the punchline variation:

"I'd hide."
"It's much better than you at hiding and you'll never find it again!"

And the other punchline variation:

"Id pick up a handful of shit and fling it at the bear."
"What if there is no shit?"
"There will be!"

jaybird2012-09-18 10:59

golddog:

It's also amazing how differently people perceive the same interaction.

...

Strange how I thought that part went really badly, and they thought it went well, apparently. Never thought that they might be going for, "does this guy not reinvent the wheel?" until I saw snoofle++'s answer.

I had a similar experience when interviewing for a job after graduation.

At school we'd learned to use those automated design tools with round-trip code generation. Rational Rose being the prime example.

In the job interview, they asked me what I thought about tools like that. I had listed it on my resume, and they used it within the company.

So I was honest. I told them I didn't think they were very practical beyond "toy" scale projects. They were great for academia but I didn't feel they would be useful beyond a very general design session. Often you realize mid-way through coding that the design you drew out just isn't going to work, and you need to redo things. Change method names, change class relationships. Trying to "round trip" between the design tool and your code IDE would take too long. Better to hash out the broad-strokes design in the tool, then code and test, and then when things are relatively stable, reverse-engineer from the code to generate your final UML diagrams for the documentation.

I was bracing for the worst, but everyone in the room was smiling. Apparently I had just described their exact frustrations with the new processes being pushed down from upper management. They were impressed that my answer was realistic, well-reasoned, that I didn't completely trash-talk the tool or its usefulness, nor did I unrealistically embrace it.

I got the job!

zxms2012-09-18 11:04

Am I crazy, or could you not have just done this? Math.pow(x, 0.5)

Jack2012-09-18 11:13

English Man:

Yeah. I mean tell them you don't know a formula but it's clear they want you to try and figure it out. This isn't a dumb "how many piano tuners are there" question, but an attempt to see if you can do maths.

I don't "do maths". That's what computers are for.

Spaatz2012-09-18 11:14

If the interviewer is using his communications skills at full throttle, then I certainly wouldn't like to work with/for him!
If that's his best about explaining the requirements, I cannoy imagine what kinf of hell he makes for others when he's workign with a real project.

qux2012-09-18 11:14

zxms:

Am I crazy, or could you not have just done this? Math.pow(x, 0.5)

What if there were no power function?

¯\(°_o)/¯ I DUNNO LOL2012-09-18 11:16

For those who still don't see the WTFery of the square root thing, how about this. A guy is interviewing to be a carpenter.

Interviewer: If you had to put two pieces of wood together, how would you do it?
Carpenter: I guess I could nail them together, or maybe glue.
I: But what if you didn't have any nails or glue?
C: I'd go out to Home-O-Rama and buy some.
I: But what if there was no Home-O-Rama?
C: Then I'd go to a hardware store.
I: But what if there were no such thing as nails or glue? How would you make them?
C: Can I have some of what you're smoking?

Yeah, maybe he could have come up with a different question, but using square root as the subject was like asking a carpenter how he would make nails if they hadn't been invented yet.

Besides, how many of you even use square roots in your day-to-day work? I've been programming for decades and never had to do something that used square roots.

ggeens2012-09-18 11:20

The ancient Babylonians had a square root algorithm:

y(n+1) = (y(n) + x/y(n))/2

This series converges on sqrt(x).

If that doesn't shut him up, leave.

Brendan2012-09-18 11:23

The real WTF is expecting someone to come up with a square root function during an interview. Maybe some people could remember enough about it to figure it out, but I'd say that candidate's answers were perfect. Is the next question going to require the candidate to invent calculus on the spot too?

Larry2012-09-18 11:23

qux:

zxms:

Am I crazy, or could you not have just done this? Math.pow(x, 0.5)

What if there were no power function?

What if there were no math?

caffiend2012-09-18 11:24

jonnyq:

Anyone who comes up with a lame attempt at approximation to figure out a square root without checking a reference...

Isn't the answer $10 per window. If it's good enough for Google...

My name is unimportant2012-09-18 11:24

English Man:

Yeah. I mean tell them you don't know a formula but it's clear they want you to try and figure it out. This isn't a dumb "how many piano tuners are there" question, but an attempt to see if you can do maths.

More import would be an attempt to see if you write proper Englishes.

Carl2012-09-18 11:27

I want to kill this whole cloud thing

Me too. Where can I invest in your startup?

It will be an intelligent network that will be completely client-focused

How would you code that if there were no library functions? No google? No books?

¯\(°_o)/¯ I DUNNO LOL2012-09-18 11:30

Larry:

qux:

zxms:

Am I crazy, or could you not have just done this? Math.pow(x, 0.5)

What if there were no power function?

What if there were no math?

Imagine there's no math
No electricity
Imagine all the people
Banging rocks together

You may say that I'm a cultist
But I'm not the only one
I hope someday you'll join us
And the world will die as one!

fing lam2012-09-18 11:32

Along the lines of those conceptual dreamers, I once posted a question to a perl discussion board. I said my boss had directed me that his web site must always appear at the top of every search result page, and would someone send me a perl function to do that. Oh boy did that ignite a fun flamefest.

A Nerd With a View2012-09-18 11:35

That last one bugs me, and not for the usual WTF reasons.

A square root is easy to calculate, if you know anything at all about any of the standard algorithms you should have learned in college.

In fact, the algorithm is a simple game of "guess the number," and if you can't write a "guess the number" algorithm in less than 5 minutes, you should be coding CSS templates for cybersquatters, not developing enterprise software.

If you can't think on your feet enough to answer a question like that, perhaps you really are not the man for the job.

DES2012-09-18 11:38

My name is unimportant:

English Man:

[...] an attempt to see if you can do maths.

More import would be an attempt to see if you write proper Englishes.

Since “maths” is the correct idiom in British English, it is arguably more correct than “math”.

Ohle2012-09-18 11:40

snoofle:

Why? The guy wanted an exact value, not an approximation.

If I asked you to come up with a formula for something you honestly didn't know how to calculate, you might approximate, but you won't get it exact.

I'd be impressed if you came up with a square root function that returns exact values. Feel free to use any reference you like.

Erik2012-09-18 11:41

If I was conducting interviews for a programmer position, I'd immediately fail any candidate who didn't know Newton's method and was unable to come up with it (or a similar successive approximation method) on the spot. It is blindingly obvious, and trivial to implement.

I'd probably also fail any candidate who didn't, at some point, suggest Math.exp(Math.log(x) / 2). And even if Math.log() isn't available, you can easily compute a rough lower bound of log(x) through successive division, as an initial guess for successive approximation.

If you ever, for any reason, find yourself in a situation where you your developers need to do complicated approximations of floating-point numbers, and you value their willingness to turn to a vaguely-recalled Newton's method as their first step, you have failed so completely that I can only hope that you aren't writing code for any crucial features of my life.

Will2012-09-18 11:44

DES:

Helpfull:

If you answer ARM and Intel have built in assembly squareroot instructions the next question will be what if you don't have a processor :)

Please show me how to use those built-in instructions in a Java program.

You write that in the language of your choice and then make a CORBA call in your Java.

moz2012-09-18 11:48

Brendan:

The real WTF is expecting someone to come up with a square root function during an interview. Maybe some people could remember enough about it to figure it out, but I'd say that candidate's answers were perfect. Is the next question going to require the candidate to invent calculus on the spot too?

Maybe; it's not that hard so long as you know how to work out the area of a rectangle.

The interview question sounds to me like one which would be fine for a job where you're likely to come across some mildly complicated mathematics, and the answer suggests that snoofle would not be comfortable with that.

Not sure why such a successful interview question found its way onto this site, though.

Recursive Reclusive2012-09-18 11:53

StMarc:

Perhaps he wanted to know if that last fellow knew anything about how algorithms are actually *created.* Since anybody who knows what a square root actually *is* should be able to create an algorithm to approximate one to any desired precision in about ten seconds.

Yes, this isn't about finding a square root, it's about exploring how you'll go about finding a solution. By all means mention that it's a solved problem, but then go on to having a go at it.

It's been really sad to read this thread. It gives me the impression that many programmers don't what their library functions actually do, or why the patterns they've memorized work.

cellocgw2012-09-18 11:59

snoofle:

coder guy:

It seems to me that anyone who can't even come up with a lame attempt at successive approximation to figure out a square root without running to a reference isn't fit for a programming job.

Why? The guy wanted an exact value, not an approximation.

If I asked you to come up with a formula for something you honestly didn't know how to calculate, you might approximate, but you won't get it exact.

Ummm, you failed math class too, eh? For all but a trivial set of numbers, there is no exact, closed-form solution to sqrt(x).

DES2012-09-18 12:00

Erik:

If you ever, for any reason, find yourself in a situation where you your developers need to do complicated approximations of floating-point numbers, and you value their willingness to turn to a vaguely-recalled Newton's method as their first step, you have failed so completely that I can only hope that you aren't writing code for any crucial features of my life.

You're cute. And also an idiot—unless you intentionally misunderstood the point of the interview question.

Come to think of it, you're an idiot either way.

FWIW, I've worked with various SOLAS equipment vendors. If I told you even half of the stuff I've seen, you'd never set foot on an ocean-going ship again.

Sockatume2012-09-18 12:03

snoofle:

Yes, Interview 2.0 questions have been around for a long time; but they've been mostly pointless for a long time too.

I have found, mostly through sheer repetition, that certain things done by interviewers during an interview are (at least in my case) pretty good indicators that I don't want the job. I used to try my darnedest to answer such questions, only to get the job and realize I should have run away. After a while, you just learn to recognize the clues.

Does it apply in every situation? Of course not. Are there times when I will try and answer such questions? That depends on how they are framed.

But just because you're in an interview doesn't mean you should put up with pointlessness. It wastes your time, tells you a great deal about the interviewer and possibly what the job would be like were you to accidentally get it. It's not an absolute rule, but at least in my own experience, is usually a reasonably reliable indicator.

Begging your pardon, but free of context there's no reason for the reader to conclude any of that. If you were interviewing to be a code monkey, then clearly a problem-solving question is a waste of yours and the interviewer's time, but the post provided no context. Free of context it's a natural assumption on the part of the reader that a problem-solving question was pertinent to the job.* The archetypal problem solving question asks the interviewee to solve a standard problem ab initio.

*"I went to an interview, and this guy asked me what programming languages I knew! WTF?!"

-beat-

"Wait, did I mention it was for Burger King?"

Sockatume2012-09-18 12:16

snoofle:

Nobody said I was completely unable to handle it; only that I couldn't do it in the 10ish seconds you have to answer an interview question before the silence becomes awkward.

It's an interview, not a date. If you need time to think about your response, you can ask for it instead of sitting mutely. Heck, most places will let you go to town on their whiteboard while you figure out a problem.

Mike2012-09-18 12:22

Less wrong attempt in Java:

public static double sqrt(double val)
{
final double aprox = 0.0001;
double tryH = val > 1 ? val : Integer.MAX_VALUE;
double tryL = 0;
double res = Double.NaN;
while(tryH - tryL > aprox && val >= 0)
{
res = (tryH + tryL) / 2.0;
if(res * res > val)
tryH = res;
else
tryL = res;
}
return res;
}

neminem2012-09-18 12:24

Recursive Reclusive:

It's been really sad to read this thread. It gives me the impression that many programmers don't what their library functions actually do, or why the patterns they've memorized work.

I'm fully willing to admit that, in many cases, I don't, and I'm completely fine with that. Would it help me to know them? In some cases, yes, and in those cases (where the API isn't perfect and I have to know why, in what cases, and how to fix it), I do try to know. But should I remember every random bit of mathematical trivia I've needed to use once or twice, just to impress people with my smartness? I can't think why.

Unlike taking a square root, my job does involve some manipulation of pdfs - and I generally trust that our pdf library works without needing to know exactly what it does. Except when it fails, in which case, at that point, I look into why it's failing (which requires learning more about its code, and often the pdf specification, which is enormous.)

If I had to work out how to approximate a sqrt by myself, I could probably do that. If I had to tell someone right now how to approximate a sqrt, I wouldn't be able to. I don't think I even ever learned it, but there's a lot of math I have learned and then completely forgot because I haven't used it for anything in like 7 years - I took a semester of Linear Algebra, a semester of MultiVs and a semester of DEs, but I'm not an engineer and I don't do 3d graphics, so what good did that do me after I graduated? (And stuff I learned in high school, other than basic algebra with does come up daily in really any kind of programming, would have been forgotten even longer ago. Sad, but true.)

RFmich2012-09-18 12:24

How would I calculate the square root of a number during the zombie apocalypse?

Use Newton Raphson's method for finding roots of x**2-n=0
Somewhere I should have some old 8080 assembly handy for that....if fixed point arithmetic is ok.

For the cyclist? Well I wouldn't want the interview to be proceeded by a programming test either... preceded I could live with.

C-Octothorpe2012-09-18 12:28

Has anyone yet mentioned that the interviewer wasn't asking for an exact value? If not, I think we need someone to create thirty math-porn posts repeating the same thing over and over again...

Glenn Lasher2012-09-18 12:29

I view the square root question as a valid problem solving question. No doubt you would encounter problems in actual work where there is no existing valid solution, or at least you can't find one. It's not going to be square root, of course, but the fact remains.

If you were a math wiz, of course, then there are two solutions I know of, one using a specific algorithm I won't describe now, the other involving manipulating exponents and logarithms.

BUT! If you asked, instead, what the tolerance was (only perfect squares have rational results, so no tolerance means no solution), you could use a binary search to find a square root that falls within it. This is the approach I would have used.

Tim2012-09-18 12:33

This is actually the point. I've run interviews similar to this, where I ask the candidate to implement a basic library function.

The point is NOT to reinvent the wheel, nor to encourage NIH behavior.

The point is to see how a candidate thinks. How they handle edge cases. How they respond when flaws are pointed out in their code.

I would expect a binary-search solution for anyone without a strong math background (there are algorithms for calculating square root, but I don't expect a candidate to know them offhand). As you've pointed out, there are problems with the first-pass implementation. When you point them out (what about negative numbers? What about numbers between 0 and 1?), you learn a lot about the candidate. How they respond to criticism of their code, how they would approach fixing their code to work, etc.

Again, the point is NOT to implement a production system in an interview. That would be silly, it's an interview. The point is to see how a candidate thinks and adapts.

The candidate was unnecessarily rude an obnoxious. I wouldn't want an arrogant jerk like that.

That said, the Interviewer should have approached it better, and simply said "We'd like you to implement a sqrt() function".

Sockatume2012-09-18 12:34

neminem:

But should I remember every random bit of mathematical trivia I've needed to use once or twice, just to impress people with my smartness? I can't think why.

You're not asked these questions to demonstrate that you know the answer! You're asked them to show that you can *think*!

Okay, sure, some people don't want to do that kind of work, but don't expect a pat on the back for taking the attitude of "I don't know the answer, therefore the question is stupid". That attitude will get you doing grunt work for the rest of your life.

PiisAWheeL2012-09-18 13:01

For the founders: http://www.escapistmagazine.com/articles/view/comics/critical-miss/9811-Steampunk-Feminists-Vs-Zombies

For the math Nerds (I don't have much time to elaborate):

while (x%2 == 0)
{y =* x/2;}
while (x%3 == 0)
{y =* x/3;}
...
continue loops using prime numbers until you are happy...
...
repeat until you are at a high enough prime number to be happy.
you answer will be y sqrt(x), with x being a prime number.
ps... this is what I remember from high school so I may be wrong.

The interviewer was probably looking for the guy to tell him out to write an iterative program that approaches the value with an error tolerance for when it was reached.

Where X is the original value
R' = (X + R / X) /2 Error= X - R'^2
While Error > some limit, let R = R', lather rinse repeat.

I'm sure there are good formulas out there and having access to google would help, but surely someone should be able to figure out a solution by taking convergent averages.

LogosMio2012-09-18 13:15

If I were conducting interviews for a hiring manager I'd immediately fail any candidate who took such an asinine position as you. I've been writing software for 24 years (professionally for 21) and the only time in my life I've ever had to use Newton's method was 23 years ago in a college course.

Knowing Newton's method, fully understanding Newton's method, being able to implement Newton's method... those are all things of limited value and more limited usefulness beyond very specific applications and positions. Even for specific positions working on specific applications which might make use of these concepts I wouldn't rule out a candidate just because he wasn't aware of them. Ideas can be taught and learned.

¯\(°_o)/¯ I DUNNO LOL2012-09-18 13:16

A Nerd With a View:

If you can't think on your feet enough to answer a question like that, perhaps you really are not the man for the job.

The problem isn't being able to do that (again, not that I have ever needed square roots or any complex maths in any programming I've been paid to do since my first computer job in my senior year of high school back in 1981), but the insulting way in which the question was continued with the completely stupid "What if there weren't any bookstores"?

Before that question was asked, things were going fine. After that question was asked, the interviewer showed himself to be an idiot, plowing forward with his plan regardless of how stupid it sounded. In other words, pure PHB-ism. Since an interviewer is typically going to become your boss or co-worker, you had better be pretty damn desperate for employment to be subject yourself to months or years of that.

If he had laughed while asking that (telegraphing that he was joking), that would have been cool. But to seriously continue past a point where basic foundations of our civilization would have to fall apart first?

foo2012-09-18 13:33

Ohle:

snoofle:

Why? The guy wanted an exact value, not an approximation.

If I asked you to come up with a formula for something you honestly didn't know how to calculate, you might approximate, but you won't get it exact.

I'd be impressed if you came up with a square root function that returns exact values.

Shouldn't you be able to come up with an algorithm to approximate a square root? That doesn't seem like that egregious of a question to me.

da Doctah2012-09-18 14:05

[quote user="Anonymous Coward"][quote="snoofle"]That tells the interviewer how I think in terms of things pertinent to the job.[/quote]
Do you walk out of interviews whenever posed any problem to solve that's not directly pertinent to your job?[/quote]Damn skippy! I get on my bicycle and go home!

smxlong2012-09-18 14:12

The point is, a programmer should be able to figure out how to compute a square root without using references. It was a perfectly legitimate question. He didn't ask, "How would you compute a square root as efficiently as possible," he asked for you to produce *some* method for computing the square root of a number.

Hell, you could have answered "I'd go in a loop and exhaustively check the square of every possible number and see which one is closest to the true root," and you would have technically solved the problem.

Maybe a lot of people don't know, off-hand, how to compute a square root, but what grade do they teach that in? 5th? 6th? Starting from *first principles*, i.e. the definition of what a "square root" is, you could have produced a solution by sheer brute force.

If you can't even do that, or can't be bothered to, why should anyone believe you can produce a solution to a novel problem for which there are no references already?

Fredrik2012-09-18 14:15

Why? The guy wanted an exact value, not an approximation.

If I asked you to come up with a formula for something you honestly didn't know how to calculate, you might approximate, but you won't get it exact.

Math.sqrt() wont give you an exact value either.

If the candidate can't even blurt out binary search would be a really bad sign for me. That's somebody who knows nothing pf algorithms and only know how to combine library calls.

Spewin Coffee2012-09-18 14:16

I disagree. Taking resources away from programmers for trivial tasks is a serious insult to the programmer if they've been writing software long enough. Also, interviews are two-way streets: You are evaluating them as much as they are evaluating you.

For programmers who have been writing software for more than 10 years, find a different avenue of evaluation such as looking at the source code they've published and systems they have built. I don't know who snoofle is, but I like his attitude toward this ridiculous question. Frankly, snoofle should have identified the "I'm going to restrict you to the exact answer I have in front of me" question sooner and walked away sooner. I certainly would. Then again, I would also hand the interviewer my business card and say something like, "Keep this card. When you are tired of hiring people who don't know how to actually write software, call me. I'll train your employees how to select and interview programmers and weed out the garbage from the good ones as well as train you on how to keep good programmers around. Programming jobs are different from most other jobs. My consulting rate is $200/hr, but well worth the cost."

neminem2012-09-18 14:26

smxlong:

If you can't even do that, or can't be bothered to, why should anyone believe you can produce a solution to a novel problem for which there are no references already?

Because, unless your job is -really- out there, the vast majority of problems that don't already have exact solutions, are still -related- to other problems that have solutions. So even if I knew there would be a novel solution required, I'd still want to see what other similar questions had been asked and answered before I started off on my own path. (And of course, sometimes you get lucky, and a problem you think is unique to you, actually isn't.)

Regardless, I feel like if you want an interviewee to answer a question with some other answer than "I'd implement this using an algorithm that I know exists on stackoverflow and/or a math textbook, but which I don't have memorized", you should ask a question whose exact answer is unlikely to exist on stackoverflow and/or a math textbook. (Even if it's related to one that is, you can still see how they think.)

lanmind2012-09-18 14:31

DES:

If I was conducting interviews for a programmer position, I'd immediately fail any candidate who didn't know Newton's method and was unable to come up with it (or a similar successive approximation method) on the spot. It is blindingly obvious, and trivial to implement.

I'd probably also fail any candidate who didn't, at some point, suggest Math.exp(Math.log(x) / 2). And even if Math.log() isn't available, you can easily compute a rough lower bound of log(x) through successive division, as an initial guess for successive approximation.

(to those who complained that Newton's method does not give an exact value: where does it say that the interviewer expected an exact value? in any case, with a few exceptions, the floating-point representation of a number will always be an approximation of the actual value.)

As for Carmack's method: assuming it can be implemented in Java (it can't—not without a lot of contortions), it can easily be derived from first principles if you know basic algebra and the layout of IEEE 754 floating-point numbers. If you don't know the layout, you can easily figure it out by looking at the binary representation of a handful of test values.

So TRWTF is that the candidate refused to even try to think of an answer, then blamed the interviewer for asking him a question he should have been able to answer but wasn't.

mbe2012-09-18 14:32

Depending on the job the square root thing isn't that unreasonable. It is not that it demonstrates a useful piece of code you would normally write, but it demonstrates that you can look at a bit of math and do some numerics if necessary. My own ugly hack without looking at any references certainly wont win any prices, but I think it is a reasonable attempt during an interview:

double sqrt(double x) {
/* guess will be the square root in the end, I hope! */
double guess = x;

if(x < 0.0)
/* ERROR */

/* Start with guess below what it needs to be */
while(guess*guess > x + EPS)
guess *= 0.5;
/* Then increase guess by small increments until it is close enough */
while(guess*guess < x - EPS) {
double step = guess;
while((guess+step)*(guess+step) > x)
step *= 0.5;
guess += step;
}
return guess;
}

It's no Newton-Rhapson, but I suspect it will work.

foo2012-09-18 14:32

smxlong:

If you can't even do that, or can't be bothered to, why should anyone believe you can produce a solution to a novel problem for which there are no references already?

Don't you remember the words of the wise prophet Alex: Programming should be boring. Novel problems are for nerds. Real business programmers aren't expected to solve them. Even trying to is evil, since either a solution exists somewhere and you must reuse it, or no solution exists and the problem is unworthy of solving. What you must do is move data around, from client to server, from server to client, from the web or the destop to the database, from one format to the other and back, etc. You must known how to use XML-Lib, HTML-Lib, *SQL-Lib, WoodenTable-Lib, and all that stuff. Thinking about solving problems makes you suspect. You could be an insurgent, or as we say nowadays, a terrorits. Used any maths recently, more than counting items in a row? You're really dangerous and should be watched. (Not by us, you know by whom.)

mbe2012-09-18 14:37

Hehe, I somehow failed to see the number of comments, so I am way late. Also one of the mistakes I make above has already been pointed out in an earlier try. You live and learn. But the more I look at it the better I like this interview question, just within the realm of things one can do on the fly, while being almost guaranteed to make some mistakes that one can then discuss (letting the interviewer see that you don't get rattled by such things).

snoofle2012-09-18 14:40

To all who think I was rude/arrogant/whatever:

You weren't there and didn't hear this jerk and his condescending attitude. Yet you've made lots of assumptions about mine. Fascinating.

FWIW: I happen to be one of those folks who sometimes hears something and has a brain-software-glitch and gets flustered. I usually don't think quickly on my feet, so if thrown a question on something I don't happen to know, it takes me few minutes to reset. As I said above, I figured it out in a few minutes afterward.

For those of you who obviously missed it: I walked out because the guy was a jerk, not because of the question.

ctd2012-09-18 14:56

The sqrt() question is no worse than any of the "How Would You Move Mount Fuji?" type questions (which Microsoft is famous for featuring in their interviews). In this case, do you understand enough algebra & algorithms to put together a simple sensible function to solve a typical (albeit atypically-limited) problem?

Not a WTF. His response of walking out, however, was.

Mithrandir2012-09-18 15:00

The thing with the square root question is that it filters out above a certain level of competence.

Obviously it filters out anyone without the wit to even try successive approximation. But it <em>also</em> filters out those who know just enough about numerical programming to know that rolling your own numerical algorithms is a really bad idea, not because of efficiency but because of the vagaries of floating point numbers.

If you want sqrt for any scientific purpose, you <em>really</em> need to know what it does with the last digits of precision. You want <em>stable</em> behavior - you want the last sig fig to increment at the right rate relative to the argument. Successive approximation will not give you that stable behavior.

If I were desperate enough for the job, I'd have proceeded beyond that point to ask the interviewer <em>why</em> I needed a square root, try to find out if they actually cared about square roots or if it was just Interview 2.0 crap. Only once I was satisfied that the interviewer would be comfortable with any old square root would I do successive approximation (and my first approximation would come from "shift right until it's 1, then shift left half as many times").

ME22012-09-18 15:01

The correct answer to the Square root question is obviously:

How does having me re-implement standard library functions bring in revenue to this company?

You god damn geekass bastards.

Tom2012-09-18 15:04

Sockatume:

Heck, most places will let you go to town on their whiteboard while you figure out a problem.

It has been a very long time since I wrote code on a whiteboard. Give me a computer (preferably one with all my stuff available and customizations loaded) and then you can test my ability to do my job.

Malcom2012-09-18 15:09

M: I'm not a math whiz; I'd drive to a bookstore and get a book on how to do it.
I: What if there were no bookstore?

M: Pop up a window and ask the user to grab a calculator and input the answer.

Mike2012-09-18 15:21

Yep I agree. If not having access to technical books or the internet is a common occurrence here than I probably won't be very good at developing software for you. Perhaps you should remove calculators and computers from your accounting department too.

Ralph2012-09-18 15:26

Windows 8 is full of messages like "slide your finger across the screen" even if you're using a desktop, not a tablet.

From what I've seen in this business, I can almost guarantee that is the quality work of a CS grad who is great at reimplementing basic math functions on the whiteboard during interviews.

For some types of programming jobs, you don't even need to know what a square root is, much less how to calculate one.

JohnFx2012-09-18 15:29

Then shit got real: What if there were no NUMBERS!?!?!

"First I'd create a number wheel function that could instantly calculate the square root of a given number. Then I would throw away that wheel and create a new wheel that does the exact same thing. Repeat for each project."

Do you have any questions for us: "How would you compensate me for the work I do here?.... Yeah, but what if there were no checks?....What if there were no banks?....what if money hadn't been invented? Sorry, I'm not convinced you are prepared to pay me in a timely manner."

Nagesh2012-09-18 15:30

snoofle:

To all who think I was rude/arrogant/whatever:

You weren't there and didn't hear this jerk and his condescending attitude.

I'm here, and I'm reading the article, and what the article describes (after being run through the usual WTF embellishment engine, I assume) is a slightly inept interviewer who for some strange reason couldn't just come right out and say he want to see a solution being developed from scratch, and a completely full-of-himself candidate who must have been willfully ignoring the clear hints that the development of a solution from scratch is nevertheless plainly what the interviewer wants to observe.

That is what the article, as posted, describes. Whether the description in the article has any discernible relation to any real interview you or someone else has been in, is sort of beside the point.

When we hire developers, we expect them to be able to solve novel problems that are orders of magnitude more complex than approximating a square root. We also expect that they will need orders of magnitude more time than there's available in an interview to do so, however. So in order to get some kind of handle on how they'll handle actual problems, we ask them to solve some toy problems that (by experience) can usually be solved within the available time.

Good toy problems tend to be ones that have prepackaged solutions readily available, but it's not the solution the interviewer wants -- it's how the candidate constructs solutions.

A candidate who deliberately refuses to demonstrate his solution-construction skills during the interview is not one we'd want to hire.

shadowman2012-09-18 15:39

vwiggins:

The second one has made me really sad. I get lost all the time, especially if I'm nervous. If someone judged my ability as a developer based on my inability to learn left from right or find my way around a place I've never been before I'd be horrified.

Um, he was being judged on his prima donna attitude, his walking out on the interview, and his refusal to take a test. Nobody was judging him for his ability to find the place. In fact, he *did* find the place, he just left to never return. And the writer of the story noted how he understood why he looked lost.

William2012-09-18 15:40

I see on your resume that you have 6 years experience designing data structures. Before we get into that, could you recite the capital cities of New York, Maryland, and Vermont? Because I'm sure they talked about that one day in third grade.

No fair using the Internet. Or a map.

Anyway, if during an interview you're asked to code a math function, and that isn't the skill you're interested in marketing, it makes perfect sense to move along... either to the next question, or if they continue in the same vein, to the next job.

ctd2012-09-18 16:07

snoofle:

You weren't there and didn't hear this jerk and his condescending attitude. Yet you've made lots of assumptions about mine. Fascinating.

I'll second Nagesh's comment.

The description sounds like a perfectly normal interview, with a little normal confusion over the point of the question. The question itself represents the essence of the job: not everything you'll be required to develop has a cookbook solution ready for you to just look up, you'll have to conjure up your own solutions (imperfect but sufficient as they may be).

Yup, sometimes I'll glitch and get flustered too. Glitching and flustering on something which is perfectly normal for the job ("here's a simple but unsolved problem, go solve it") isn't a good sign; insofar as I've been known to do so at inopportune times is my problem, not the questioner's.

'tis good to develop the social skill of tactfully saying "your question is valid and I'm capable of answering it, but I'm suffering a brain fart right now - how 'bout we come back to this one." If you'd just redirected the discussion for a few minutes, you'd have given the answer. I had a notable case when interviewing at Microsoft years ago: given a comparable question and comparable "brain-software-glitch", I told the interviewer "I know I'm completely missing a simple solution that you're looking for, but I'm just gonna plow ahead with a line of reasoning and let's see where I end up." (Didn't get the job, but did seem in line as a final contender.) In another interview, I knew they'd pull the "write code on a whiteboard" line, so I brought a notebook computer, and explained "writing code on a whiteboard sucks and so does writing code while someone stares at me, so I'll just write it on this computer while you go ahead and ask me other questions and I multi-task". (Got an offer, but got a better offer elsewhere.) Learned to do those after completely blowing several otherwise successful interviews due to mental misfires.

The article says nothing about the guy being a jerk. The guy who walked out in response to a representative question typical of the work, well...

Niels2012-09-18 16:10

Anoldhacker:

This should be considered a good example of precisely why you don't do things like this yourself. The square root of x for small x is much larger than x. The quick return is not needed for non-negative numbers, and if it were, the boundary would be EPSILON * EPSILON. (And no, the square root of -1.0 is NOT even close to 0.0.)

Yes, my degrees are in mathematics, and I did floating point validation in the '90s. Seriously, don't try this at home, kids.

(The way that we actually compute floating point square roots is fun. We look up the first several digits for the inverse square root, and then refine it based on polynomials designed to cancel the error term, usually quadratically. Once there is enough precision, you multiply back the original value to get the square root. Yes, you want a real proof that the algorithm works.)

Heh yeah, I was pretty sure there was some glaring problem with it, but I also did try to come up with it as fast as possible.

ctd2012-09-18 16:31

M: I'd Google for John Carmack's formula to calculate it.

That the interviewee knew of that solution is a good sign.
That the interviewer did not, it seems, know of that solution is a bad sign.

Kasper2012-09-18 16:36

I have interviewed more than 100 people, and I have come across a few with an attitude like snoofle. With such candidates, I'd recommend that we did not hire them, because of their attitude.

Of course programmers are not supposed to reinvent square root every time they need to calculate it. But somebody has to implement it in the first place. And whenever new platforms are put into use, there are some pieces of basic code that has to be written over again. So there is actually a need for people who can write those basic pieces of code again.

But that's not the point in asking such a question. The point surely was to test the candidates ability to write some code to solve a simple problem.

The interviewer learned three things about snoofle from that question:
1. He doesn't know any of the many possible algorithms to solve this problem.
2. He doesn't have the skills to derive an algorithm from scratch to solve a quite simple problem.
3. He displays a bad attitude when faced with a task he doesn't like.

Given how much the interviewer learned about the candidate from that one question, I think it was a great question.

raboof2012-09-18 16:39

Situations like the third example always reminds me of the literal meaning of 'intelligent'.

'Intelligent', from the latin verb, roughly means 'he who understands'.

This means to answer a question intelligently, you should not just take the question and find an answer that matches it, but understand why it is asked, and what the interviewer is actually trying to learn.

"Use the language API function" is a great first answer to that question. From the follow-up questions, however, it should be fairly obvious that the interviewer wants to see how the interviewee approaches a problem independently.

sqrt is a fairly good example problem to test this with: the problem is easily and clearly defined and there's a couple of solutions anyone should be able to invent on-the-spot. In practice of course the problems you'll have to be able to independently solve are not sqrt, but domain-specific problems - however, explaining a foreign domain first would distract from the point of the excercise, hence a well-known problem like sqrt is better suited to test this ability. Even a 'wrong' answer can be an acceptable one, especially when you can refine it after getting feedback on it.

Inferring that because the interviewer asks this question, developers at this company will always be forbidden to use google or other reference material, is ludicrous and anyone who does this deserves unemployment.

Next time, be intelligent, and answer the question the interviewer is trying to ask, not the one he is actually asking.

Sam I am2012-09-18 16:47

As far as that last one goes the interviewer could probably have come out and initially asked to "come up with an algorithm to calculate a square root", but beyond that, there really wasn't much else to do.

even after the first couple "google it" responses, the interviewee should have gotten a clue by then.

"snoofle" didn't even appear to allow the interviewer to lead him a little bit.

If the interviewee wasn't referred to as "me" so many times, I'd think that he was the WTF

OccupyWallStreet2012-09-18 16:49

foo:

emaNrouY-Here:

TheRider:

Niels:

An iterative approximation for a square root shouldn't be hard to come up with.
<SNIP>

What if you can't use the multiplication operator to square a number?

And What if you can't use addition?

(It's a flipping adding machine!!!)

If you need anything more than NAND gates, you're not qualified.

What if you're not allowed to use NAND gates? And no, wiring transistors up to form NAND gates is not allowed. You are, however, free to wire up transistors to form any other logic gate (except NAND), but the gate you choose is the only one you can use.

Coyne2012-09-18 16:56

For the interviewer in "...Stupid":

for (i=0; (i*i) <= n; i++); i--;

Submitted on the theory that the interviewer doesn't know "sensible algorithm" from beans anyway. Especially since I can show exact result for a cherry-picked input of, say, 64.

(Trust me to also carefully point out how elegant this one-liner is...)

Oh, BTW, haven't we seen this interviewer before? Right here in TDWTF?

This should be considered a good example of precisely why you don't do things like this yourself. The square root of x for small x is much larger than x. The quick return is not needed for non-negative numbers, and if it were, the boundary would be EPSILON * EPSILON. (And no, the square root of -1.0 is NOT even close to 0.0.)

Yes, my degrees are in mathematics, and I did floating point validation in the '90s. Seriously, don't try this at home, kids.

(The way that we actually compute floating point square roots is fun. We look up the first several digits for the inverse square root, and then refine it based on polynomials designed to cancel the error term, usually quadratically. Once there is enough precision, you multiply back the original value to get the square root. Yes, you want a real proof that the algorithm works.)

Clearly Anoldhacker, you were a Discrete Mathematician. All REAL Mathematicians know root(x)=root(x) and that's the end of it. Just like pi = pi. None of this 3.1415... blasphemy.

Pete2012-09-18 17:31

¯\(°_o)/¯ I DUNNO LOL:

For those who still don't see the WTFery of the square root thing, how about this. A guy is interviewing to be a carpenter.

Interviewer: If you had to put two pieces of wood together, how would you do it?
Carpenter: I guess I could nail them together, or maybe glue.
I: But what if you didn't have any nails or glue?
C: I'd go out to Home-O-Rama and buy some.
I: But what if there was no Home-O-Rama?
C: Then I'd go to a hardware store.
I: But what if there were no such thing as nails or glue? How would you make them?
C: Can I have some of what you're smoking?

Yeah, maybe he could have come up with a different question, but using square root as the subject was like asking a carpenter how he would make nails if they hadn't been invented yet.

Besides, how many of you even use square roots in your day-to-day work? I've been programming for decades and never had to do something that used square roots.

The whole point of a simplified toy examples is to allow to see the problem solving approach of candidates within a short interview.

Asking a carpenter how he would make a glueless joint for two pieces of wood is a natural question - it's not done in "production" nowadays since glue is usually simpler and sturdier, but any reasonable professional carpenter should either know or figure it out in 5 minutes.

Asking a programmer in how he would reimplement a simple function from scratch is a natural question - it's not commonly done in production, but any reasonable programmer should know or be able to figure it out in 5 minutes. Asking to build a more complex function than sqrt (one that wouldn't be in libraries) would simply require more time to see the same effect.

The exam showed: Candidate is able to reimplement well known techniques by looking up the details in a reference book or internet. Candidate is unable or unwilling to develop solutions independently even when requested to do so.

wizofaus2012-09-18 17:44

Working out (or at least, approximating) the square root of a number is a pretty basic exercise in recursive programming though - I'd be a bit concerned by a programmer that would give up that easily.

Enrique2012-09-18 17:52

raboof:

Inferring that because the interviewer asks this question, developers at this company will always be forbidden to use google or other reference material, is ludicrous and anyone who does this deserves unemployment.

I have seen a couple of companies whose developers didn't have access to internet or books, so it is not unreasonable to infer that. Also, I remember one company where you couldn't use JOINs in stored procedures. There are many WTF companies out there.
English is not my native language, sorry for any mistakes.

Sam I am2012-09-18 18:08

snoofle should feel a little bit silly when writing that diatribe about being asked to approximate the square root, and later reading a comments section where half the people knew how to come up with the answer.

Warren Young2012-09-18 18:23

Are there any real programming languages without a square root function? I don't mean toy languages, I mean those in actual production use.

I was thinking back over my programming history to see if I could spot one, and everything back to Applesoft Basic from the late 1970's on a 1 MHz 8-bit CPU had a square root implementation. Languages I learned later but which are older (C, Pascal, etc.) have had it from the beginning, too.

What I'm trying to get at is, is the interviewer's question anything more than an impossible hypothetical? Never mind that the context was Java. Is there even a snowball's chance someone would be required to do this?

Riffing on snowballs, here's a new hypothetical:

You're in Antarctica, a blizzard is blocking the satellite uplink to the Internet, and you have to fix a bug in an embedded system or Dooooom happens. The bug must be fixed in the next 2 hours, and the blizzard is expected to last another day. The embedded system is an 8-bit microcontroller with a toolchain you've never used before, but it uses a well-known programming language, and you have complete reference manuals for the toolchain and the language. You have no other reference material. It turns out that the bug fix requires a square root operation. The language entirely lacks what we'd call a math library today: so, no raising the number to a half power, no trickery with logarithms. You have to build the sqrt() implementation using nothing more than sixth-grade arithmetic.

Is that also an impossible hypothetical?

herby2012-09-18 18:26

TheRider:

Niels:

An iterative approximation for a square root shouldn't be hard to come up with.

What if you can't use the multiplication operator to square a number?

No multiplication? Multiplication "expensive"?

Use the "odd integer method" with proper scaling. I know of one computer system that did it that way.

Of course, you could always use n^(0.5) which also works.

If all else fails, try a slide rule!

Warren Young2012-09-18 18:47

herby:

No multiplication? Multiplication "expensive"?

Sure. A great many 8-bit CPUs (and microcontrollers) lack a hardware multiplier. High level languages for such systems typically provide a software multiplication implementation, but if it's general-purpose, its going to be hundreds of instructions long. If you're writing in assembly, you get to write (or swipe) the implementation yourself.

Even on systems with a hardware multiplier, multiplication may take many cycles, whereas an integer addition is typically the fastest sort of instruction.

You might not be aware of it, but there are still — today — more 8-bit CPUs sold than any other, by volume. There's even new code being written for 4-bit CPUs.

Here's such a CPU, still being sold, though Atmel recommends against using it in new designs. It's a 4-bit CPU with an instruction set optimized for a dialect of Forth. No hardware multiply instruction. The programming manual claims there is a software multiplier at the qForth level, but more reading suggests the only thing that actually works is 2* which is implemented in software as a shift-left operation.

I guess this answers my question above, but I'd still appreciate more answers.

snoofle2012-09-18 19:00

Kasper:

I have interviewed more than 100 people, and I have come across a few with an attitude like snoofle. With such candidates, I'd recommend that we did not hire them, because of their attitude.

Sadly, most of you still seem to be missing the entire point, so let me illustrate...

Hypothetically, you are the interviewer, I am the candidate, and for the sake of argument, I am Mr. Math Wizard. You ask your question (in an intelligent way): We'd like to see how you think and go about problem solving; please explain how you might go about designing a method to compute a square root. As a shrewd interviewee, I ponder for a second, then respond with iterative approximation, perhaps mentioning some edge cases, negative numbers, numbers < 1, etc.

You probably think to yourself: Hey, this guy knows his stuff, and will probably use that as a significant portion of your hiring decision.

Epic Fail.

The only thing you have learned about me is if I can come up with a way to compute a square root. Unless the job entails figuring out new mathematical algorithms, or computing square roots, you have learned absolutely nothing about my ability to do the actual job.

It's actually worse than that, because you now have a false sense of positive security that I am a good fit. I may or may not actually be a good fit, but you don't know that based upon your question.

I, OTOH, know that you have chosen a question that fails to give you the sole piece of information it was designed to detect: Can I think?

In fact, that is not the complete question you wanted to answer. What you wanted to know was: Can he think in a way that helps him accomplish what we want to hire somebody to do?

A good question along those lines is: Our production environment looks like x. Every now and then, y happens with symptoms a, b and c. Given limited knowledge of the details, how might you go about diagnosing the problem and how might you proceed to solve it? This tells you whether I can think AND if I know how to do the job.

It's not that I have an attitude about answering questions; I get it; you have to play nice to get the job. It's just that I've learned over the decades that certain types of questions are red flags, and depending upon the tone/manner with which they are posed, I may play along, or just accept it as a wasted trip and leave - because some jobs just aren't worth having.

consequat2012-09-18 19:08

coder guy:

It seems to me that anyone who can't even come up with a lame attempt at successive approximation to figure out a square root without running to a reference isn't fit for a programming job.

And I think that anyone who's wasting time to unnecessarily disassemble anything is a time waster and probably a bullshit programmer, too.

consequat2012-09-18 19:19

DES:

If I was conducting interviews for a programmer position, I'd immediately fail any candidate who didn't know Newton's method and was unable to come up with it (or a similar successive approximation method) on the spot. It is blindingly obvious, and trivial to implement.

I'd probably also fail any candidate who didn't, at some point, suggest Math.exp(Math.log(x) / 2). And even if Math.log() isn't available, you can easily compute a rough lower bound of log(x) through successive division, as an initial guess for successive approximation.

(to those who complained that Newton's method does not give an exact value: where does it say that the interviewer expected an exact value? in any case, with a few exceptions, the floating-point representation of a number will always be an approximation of the actual value.)

As for Carmack's method: assuming it can be implemented in Java (it can't—not without a lot of contortions), it can easily be derived from first principles if you know basic algebra and the layout of IEEE 754 floating-point numbers. If you don't know the layout, you can easily figure it out by looking at the binary representation of a handful of test values.

So TRWTF is that the candidate refused to even try to think of an answer, then blamed the interviewer for asking him a question he should have been able to answer but wasn't.

You're a heavy unit-test guy, aren't you?

consequat2012-09-18 19:27

StMarc:

Perhaps he wanted to know if that last fellow knew anything about how algorithms are actually *created.* Since anybody who knows what a square root actually *is* should be able to create an algorithm to approximate one to any desired precision in about ten seconds.

I'll give you my salary for a month if you even copy it from another piece of paper in 10 seconds, let alone come up with even relatively accurate solution without anticipation or prior practice.

In other words, you're a dumbass.

consequat2012-09-18 19:33

Sockatume:

The interviewer doesn't want to know how the candidate *thinks* he would react to a problem outside of his training. The interviewer wants to know how the candidate would *actually* react. Apparently in this case it's to rage out of the office.

I'd love to see his take on the Kobiyashi Maru.

("Interview 2.0"? Problems like that have been a standard part of technical interviews for decades.)

No, dude - the interviewer is a plain old dumbass with no good intention at all. He simply couldn't think of any other good-quality question, so he thought of going down th what-if route. My child often does this to me, and the interviewer probably hasn't advanced much from that age.

foo2012-09-18 19:37

OccupyWallStreet:

foo:

emaNrouY-Here:

TheRider:

Niels:

An iterative approximation for a square root shouldn't be hard to come up with.
<SNIP>

What if you can't use the multiplication operator to square a number?

And What if you can't use addition?

(It's a flipping adding machine!!!)

If you need anything more than NAND gates, you're not qualified.

What if you're not allowed to use NAND gates? And no, wiring transistors up to form NAND gates is not allowed. You are, however, free to wire up transistors to form any other logic gate (except NAND), but the gate you choose is the only one you can use.

That's neither funny nor relevant.

derp2012-09-18 19:40

The interviewer in #3, in my mind, was looking for snoofle to implement a function that could compute the square root. The fact that he was unable to communicate that very simple requirement to his interviewee puts the WTF ball in his court. There is no inherent problem with asking someone to implement their own sqrt function, it's simply that it was not asked properly.

I would not like to work for such a person either, because I would much rather work for someone who has the ability to make their expectations and needs clear.

Mark2012-09-18 19:44

Yes, being able to solve something on your own is a useful skill, but really, the interviewer should have framed the problem more clearly, stating that was what was expected, instead of inventing hypothetical "what if" scenarios that aren't ever going to happen.

Mark2012-09-18 20:08

Uhmmm.... I'd like to see you use newton's method to calculate the square root of a number without having access to the square root function.

It probably doesn't help matters that the first derivative of sqrt(x) contains a square root.

While yes, one can argue that the interviewer was almost certainly asking the person to describe how they would personally approach solving a new problem that they hadn't had to solve before, it would have probably been better if this particular question had been framed very differently, and the expectation that the interviewee should take some time to think about it had been clarified up front, instead of adding all these highly contrived "what ifs" after the question had already been posed, and an answer given.

SQRT2012-09-18 20:22

snoofle:

Kasper:

I have interviewed more than 100 people, and I have come across a few with an attitude like snoofle. With such candidates, I'd recommend that we did not hire them, because of their attitude.

Sadly, most of you still seem to be missing the entire point, so let me illustrate...

Hypothetically, you are the interviewer, I am the candidate, and for the sake of argument, I am Mr. Math Wizard. You ask your question (in an intelligent way): We'd like to see how you think and go about problem solving; please explain how you might go about designing a method to compute a square root. As a shrewd interviewee, I ponder for a second, then respond with iterative approximation, perhaps mentioning some edge cases, negative numbers, numbers < 1, etc.

You probably think to yourself: Hey, this guy knows his stuff, and will probably use that as a significant portion of your hiring decision.

Epic Fail.

The only thing you have learned about me is if I can come up with a way to compute a square root. Unless the job entails figuring out new mathematical algorithms, or computing square roots, you have learned absolutely nothing about my ability to do the actual job.
<snip>

I respectfully submit that you are also missing the point. I fall in the camp that thinks this is a reasonable interview question. I might consider using it in the future.

Your assumption that I would think "Hey, this guy knows his stuff, and will probably use that as a significant portion of your hiring decision" would be wrong. It's only 1 question. You don't know that the next question wouldn't have started with 'Our production environment looks like x...'. You judged the interviewer based on 1 question. I judge an interviewee based on answers to multiple questions.

I even like the approach the guy used of pulling the rug out from under you as you give the right answers. It's actually better than jumping straight to write a sqrt function from scratch.

Here's what would go through my mind as the interviewer in that scenario:
Interviewer: How would you calculate a square root (java)?
Me: Math.sqrt(double)
+5 for knowing the obvious solution without having to look it up. I: What if there were no square root function?
M: I'd Google for John Carmack's formula to calculate it.
+20 for being able to name an existing algorithm to solve the problem. +10 for knowing that Google is your friend here. +10 for knowing that this is a solved problem, no need to reinvent the wheel here. I: What if you couldn't use Google?
M: Assuming you mean no access to the internet, since I don't happen to know how to calculate a square root, I'd ask someone...
+10 for not being afraid to ask someone when you don't know the answer, rather than wasting hours trying to figure it out yourself. I: What if there were nobody to ask?
M: I'm not a math whiz; I'd drive to a bookstore and get a book on how to do it.
+5 for admitting you don't know everything. +5 for remembering that there were bookstores before there was Google. I: What if there were no bookstore?
M: Ok, so you want me to come up with a formula I've told you I don't know, in the next 10 seconds, without access to any of the usual reference sources?
Yes, I would like you to come up with an algorithm to solve the problem, even if it isn't a very good one. Take as much time as you would like. There is no 10 second time limit. Think about it while I check my email. Take your time. Use the whiteboard if you want.

M: <Walks Out>
-1000. Too bad. He was doing fine at +65. But hiring this guy would have been an Epic Fail. When faced with a difficult challenge, he chooses flight over fight. Not what we need here.

Norman Diamond2012-09-18 20:25

Joe:

I've been programming for 30 years and I can guarantee you I've never had the slightest use for Math.exp or Math.log. [...] And I'm talking real code, not drag-and-drop crap.

I've been programming for longer, so I HAVE had use for exp2 and log2. Once. In a device driver. The Linux kernel for x86 had some macros that could be used before and after floating point calculations so they could be used safely in a driver. The Linux kernel for other architectures didn't, so I had to convert my code to use lookup tables instead of calculating how much power to apply to the antenna.

I have a feeling programmers at NASA, Spar, and maybe oil companies use those functions more.

derp2012-09-18 20:42

SQRT:

I even like the approach the guy used of pulling the rug out from under you as you give the right answers. It's actually better than jumping straight to write a sqrt function from scratch.

I: What if there were no bookstore?
M: Ok, so you want me to come up with a formula I've told you I don't know, in the next 10 seconds, without access to any of the usual reference sources?
Yes, I would like you to come up with an algorithm to solve the problem, even if it isn't a very good one. Take as much time as you would like. There is no 10 second time limit. Think about it while I check my email. Take your time. Use the whiteboard if you want.

Then you should just say "please give me a function" somewhere and totally sidestep this bullshit. It's the obvious and easy thing to do as an interviewer. YOU have to make your expectations clear so then it falls upon them to rise to meet them.

foo2012-09-18 21:15

Mark:

Uhmmm.... I'd like to see you use newton's method to calculate the square root of a number without having access to the square root function.

It probably doesn't help matters that the first derivative of sqrt(x) contains a square root.

While yes, one can argue that the interviewer was almost certainly asking the person to describe how they would personally approach solving a new problem that they hadn't had to solve before, it would have probably been better if this particular question had been framed very differently, and the expectation that the interviewee should take some time to think about it had been clarified up front, instead of adding all these highly contrived "what ifs" after the question had already been posed, and an answer given.

Yeah, what if Google actually existed and told you how to use Newton's method to calculate the square root? Nice try.

foo2012-09-18 21:27

Norman Diamond:

Joe:

I've been programming for 30 years and I can guarantee you I've never had the slightest use for Math.exp or Math.log. [...] And I'm talking real code, not drag-and-drop crap.

I've been programming for longer, so I HAVE had use for exp2 and log2. Once. In a device driver. The Linux kernel for x86 had some macros that could be used before and after floating point calculations so they could be used safely in a driver. The Linux kernel for other architectures didn't, so I had to convert my code to use lookup tables instead of calculating how much power to apply to the antenna.

I have a feeling programmers at NASA, Spar, and maybe oil companies use those functions more.

I don't work at any of those, yet I occasionally need math functions, sometimes for simple tasks such as laying out items in a 2D grid regularly with correct aspect ratio (integer sqrt, round-up). And I'm talking cheap desktop crap, not real code (graphics, sound, real-time device control) where these functions occur a lot more, obviously (and which fortunately makes up most of my work).

Mark2012-09-18 21:37

foo:

Yeah, what if Google actually existed and told you how to use Newton's method to calculate the square root? Nice try.

My bad... I was thinking of Newton's method being used to calculate zeros of the square root function itself (which actually isn't even useful... I feel foolish for even bringing it up), rather than finding the zero's of the inverse function, which of course is x^2, and offsetting it by the value whose square root you want.

Although my main point still stands. It would have been better if the interviewer had framed the question more clearly with respect to what he was expecting.

Lee2012-09-18 22:10

I was invited to interview for a position on the security team of a major website. In preparation, I ran some tools I've written to do some benign reconnaissance. Nothing illegal or harmful, just the types of requests a search engine like google would perform, coupled with my specialized knowledge of what to look for.

I arrived prepared to tell them "It looks like you might have trouble here and here, and I propose this and this to cover yourselves while you fix it like this."

Instead, the interviewer wanted me to write some code to calculate prime numbers on the whiteboard.

So, now, they've hired their submissive puzzle solver, and I have a handful of vulnerabilities -- still not fixed -- that give me access to a major slice of e-commerce. Guess who (potentially) wins?

JustSomeGuy2012-09-18 22:33

asdbsd:

snoofle:

Why? The guy wanted an exact value, not an approximation.

If I asked you to come up with a formula for something you honestly didn't know how to calculate, you might approximate, but you won't get it exact.

Just to remind you, there's no such thing as "exact" with floating point numbers. So they didn't ask him to give "exact" value. They asked to do his best at approximation.

And, just to remind *you*, there *is* such a thing as exact with floating point numbers. IEEE754 can represent negative-powers of two quite nicely thank you very much. Things like 1/2, 1/4, 1/64 or any number that can be represented by summations of those (within the bounds of the bits available) are, to all intents and purposes, exactly representable.

It's only when you get outside the bounds of precision, or have a number like 0.1 which can't be represented as sums of 2^(-whatever).

Don't be a pedant on the net. There are so many of us around :-)

JustSomeGuy2012-09-18 22:34

TheRider:

Niels:

An iterative approximation for a square root shouldn't be hard to come up with.

What if you can't use the multiplication operator to square a number?

Use repeated addition? :-)

JustSomeGuy2012-09-18 22:35

Studley:

What if there were no numbers?

Then there is no concept of a square root?

dookdook2012-09-18 22:38

In some semi-fringe circles of mathematics (Constructivists) an "exact" value of sqrt(2) is nothing more or less than an algorithm which can in principle calculate it to any desired precision.

Thus to "exactly" calculate sqrt(2), you'd only need to write a class to handle arbitrarily high precision decimal numbers (unless this already exists in Java) and implement your favorite iterative algorithm on it.

JustSomeGuy2012-09-18 22:39

Anoldhacker:

Niels:

An iterative approximation for a square root shouldn't be hard to come up with.

This should be considered a good example of precisely why you don't do things like this yourself. The square root of x for small x is much larger than x. The quick return is not needed for non-negative numbers, and if it were, the boundary would be EPSILON * EPSILON. (And no, the square root of -1.0 is NOT even close to 0.0.)

Yes, my degrees are in mathematics, and I did floating point validation in the '90s. Seriously, don't try this at home, kids.

(The way that we actually compute floating point square roots is fun. We look up the first several digits for the inverse square root, and then refine it based on polynomials designed to cancel the error term, usually quadratically. Once there is enough precision, you multiply back the original value to get the square root. Yes, you want a real proof that the algorithm works.)

So the actual answer should have been "I'd give my mate Anoldhacker" a call and get him in to do the work".

SQRT2012-09-18 22:41

derp:

SQRT:

I even like the approach the guy used of pulling the rug out from under you as you give the right answers. It's actually better than jumping straight to write a sqrt function from scratch.

I: What if there were no bookstore?
M: Ok, so you want me to come up with a formula I've told you I don't know, in the next 10 seconds, without access to any of the usual reference sources?
Yes, I would like you to come up with an algorithm to solve the problem, even if it isn't a very good one. Take as much time as you would like. There is no 10 second time limit. Think about it while I check my email. Take your time. Use the whiteboard if you want.

Then you should just say "please give me a function" somewhere and totally sidestep this bullshit. It's the obvious and easy thing to do as an interviewer. YOU have to make your expectations clear so then it falls upon them to rise to meet them.

Yes, I suppose you are right. Because that is how it works in the real world. Your boss always comes to you with requirements that are absolutely clear cut from the start, will never change, have no oddball restrictions, and no bullshit. That's because your boss got the requirements directly from Sales And Marketing, and they obviously always state the requirements clearly from the start. Why wouldn't they? They get the requirements directly from the customer. And not only does the customer know *exactly* what they want, they are also always right.

So, yes, you are right. Failing to give the programmer the precise requirements and restrictions from the start is my WTF. One that would never happen in the real world.

Thank you for pointing that out.

JustSomeGuy2012-09-18 22:43

[quote user="robert"][quote user="Anonymous Coward"]1. How do you know he wanted an exact value? You left without offering a non-exact solution.

2. Successive approximation WILL give you an exact value.

That's impossible.
Most square root functions return an irrational number, i.e.: their digits repeat endlessly without a recurring pattern. There is no representation for the number in a digit-based system.[/quote]

Rubbish. In base sqrt(2), the square root of two is exactly 1 :-)

Roger Garrett2012-09-18 22:57

This is so damn true. I have 40 years experience as a software engineer and in one recent job interview I was told to take a programming test. The "company" consisted of two guys in their early twenties, clearly right out of college, and the test looked like something you'd get from your instructor on Friday for the lessons you'd attended during the week. Just little tidbits of specific elements of a language and to see if you'd recognize the + where a ++ should be. Absolutely nothing about actual software engineering. I got about halfway through the "test" before my frustration got the better of me and I handed it back to them and walked out.

Gary Capell2012-09-19 00:36

I would expect any programmer who at least understands what a square root is to be able to come up with at least some binary search approach at approximating a square root.

Mike Hunt2012-09-19 00:47

I'm no programmer or maths genius, but I'd have thought you'd guess a number, times it by itself, see if it was greater than or less than the origianl number, refine the guess and iterate that a few times. But that's just me. Here's some dodgy VBA code (as I don't have access to anything else):

Option Explicit
Const ITERATIONS As Integer = 20

Sub SquareRootBitchez()
Dim num As Double
Dim i As Integer
Dim cntGuess As Double, cntGuessSquared As Double
Dim cntMin As Double, cntMax As Double
Dim isNeg As Boolean

num = InputBox("Enter Number")
If num < 0 Then
isNeg = True
num = Abs(num)
End If
If num > 1 Then
cntMin = 1
cntMax = num
Else
cntMin = num
cntMax = 1
End If

For i = 1 To ITERATIONS
cntGuess = (cntMax - cntMin) / 2 + cntMin
cntGuessSquared = cntGuess * cntGuess
If cntGuessSquared > num Then
cntMax = cntGuess
ElseIf cntGuessSquared < num Then
cntMin = cntGuess
Else
GoTo ExitFor
End If
Next
cntGuess = (cntMax - cntMin) / 2 + cntMin
ExitFor:
MsgBox cntGuess & IIf(isNeg, "i", "") & vbCrLf & "After " & i & " iterations"
End Sub

Mike Hunt2012-09-19 00:48

Ooops... I didn't see the "All Comments" link. I'm probably not the first person to make that point.

Ignore my last post :P

Derp2012-09-19 00:58

SQRT:

derp:

SQRT:

I even like the approach the guy used of pulling the rug out from under you as you give the right answers. It's actually better than jumping straight to write a sqrt function from scratch.

I: What if there were no bookstore?
M: Ok, so you want me to come up with a formula I've told you I don't know, in the next 10 seconds, without access to any of the usual reference sources?
Yes, I would like you to come up with an algorithm to solve the problem, even if it isn't a very good one. Take as much time as you would like. There is no 10 second time limit. Think about it while I check my email. Take your time. Use the whiteboard if you want.

Then you should just say "please give me a function" somewhere and totally sidestep this bullshit. It's the obvious and easy thing to do as an interviewer. YOU have to make your expectations clear so then it falls upon them to rise to meet them.

Yes, I suppose you are right. Because that is how it works in the real world. Your boss always comes to you with requirements that are absolutely clear cut from the start, will never change, have no oddball restrictions, and no bullshit. That's because your boss got the requirements directly from Sales And Marketing, and they obviously always state the requirements clearly from the start. Why wouldn't they? They get the requirements directly from the customer. And not only does the customer know *exactly* what they want, they are also always right.

So, yes, you are right. Failing to give the programmer the precise requirements and restrictions from the start is my WTF. One that would never happen in the real world.

Thank you for pointing that out.

So thanks for responding to my point by being a smart ass. Let me retort though with a serious response:

If you're going to deliberately be a shit head when you're interviewing a candidate, then you're only going to hire people who are stupid enough to not see the red flag that you are yet another dumb shit employer.

Naturally, you're going to get a bunch of tool higher ups that won't give you good requirements. The smart man at least makes sure that he gets as few possible derps like that giving him orders. I don't think it's really strategic from a recruiting perspective to make yourself look like a dumb ass who can't even get his own interview questions straight. That's how you scare the competent people away.

Derp.

Seraph2012-09-19 01:00

SQRT:

Yes, I suppose you are right. Because that is how it works in the real world. Your boss always comes to you with requirements that are absolutely clear cut from the start, will never change, have no oddball restrictions, and no bullshit. That's because your boss got the requirements directly from Sales And Marketing, and they obviously always state the requirements clearly from the start. Why wouldn't they? They get the requirements directly from the customer. And not only does the customer know *exactly* what they want, they are also always right.

So, yes, you are right. Failing to give the programmer the precise requirements and restrictions from the start is my WTF. One that would never happen in the real world.

Thank you for pointing that out.

The point is, if my Boss isn't capable of giving coherent requirements for problems that he's making up himself without going to several iterations, why should I expect that he is going to come up with the requirements for a customers problem correctly? I imagine that Snoofle doesn't want to discover he's been wasting time working on the wrong problem because his boss is an idiot and didn't ask the right questions.

Derp2012-09-19 01:03

Also if I may add, the question in this example is clearly NOT a question where the candidate is supposed to gather requirements. The interviewer wanted a function, but couldn't articulate that desire and instead threw out a bunch of stupid hypotheticals.

Asking questions that force the candidate into situations where they should try to gather requirements is a great strategy. Is the sqrt question a good way of doing that? I'd say it isn't. So I'm going to say your point is a touch moot and unrelated.

Unless of course you would use the sqrt question to look for requirement gathering skills, in which case God help you.

Anon2012-09-19 01:29

Fool:

If I was writing java code and there were no Math.sqrt function i would try to figure out what what jar file is missing, where and then contact IT to fix it.

This is basically what I did when applying for a support position once with one of those "If you're lost in the woods and mysteriously have absolutely none of the items which people would normally carry into the woods, are then suddenly attacked by a velociraptor, and now need to cross a magma flow with only toothpaste, a ball of twine, and an Eagles 'Greatest Hits' LP..." questions.

"This question is stupid. What possible reason could I have for being in the woods without any weapons or survival gear?"

Konstantin Lopyrev2012-09-19 02:31

The last one is a reasonable question and if you don't know how to do it you shouldn't be hired as a programmer.

tchize2012-09-19 03:09

vwiggins:

The second one has made me really sad. I get lost all the time, especially if I'm nervous. If someone judged my ability as a developer based on my inability to learn left from right or find my way around a place I've never been before I'd be horrified.

No, indeed. But i think he was judged by his refusal to do the technical test and fleeing from the area :) I mean he got in touch with Human ressources. Why not just say "er i'm lost in you place" ? I really think the bycicle what juste an excuse to leave when he learned about the written test :)

Scarlet Manuka2012-09-19 03:12

JustSomeGuy:

In base sqrt(2), the square root of two is exactly 1 :-)

No, it isn't. 1 in any base is 1; in base sqrt(2), sqrt(2) is of course represented as 10.

I'd have gone with Newton-Rhaphson as well. But then, I have actually had to use Newton-Rhaphson in my job to derive iterative approximations we can use to solve intractable equations. For what it's worth, I also have to use exp() and log() functions in some of the data modelling I do.

For reference, I work in the financial industry, and the Newton-Rhaphson stuff comes into play when answering questions like "what is the maximum loan amount you can borrow in this scenario, given that as the loan amount changes a whole lot of other things change which affect your net serviceability amount?" These things are typically implemented by lenders as Excel spreadsheets with a button that calls the Solver (which internally does its own iterative approximation technique), and we have to replicate the results on our in-house system.

I haven't had to use these things often. But I certainly have had to use them.

boh2012-09-19 04:50

OccupyWallStreet:

What if you're not allowed to use NAND gates? And no, wiring transistors up to form NAND gates is not allowed. You are, however, free to wire up transistors to form any other logic gate (except NAND), but the gate you choose is the only one you can use.

I don't know if you are trolling or not, but for the record:

Use NOR gates.

Level 22012-09-19 04:55

snoofle:

coder guy:

It seems to me that anyone who can't even come up with a lame attempt at successive approximation to figure out a square root without running to a reference isn't fit for a programming job.

Why? The guy wanted an exact value, not an approximation.

If I asked you to come up with a formula for something you honestly didn't know how to calculate, you might approximate, but you won't get it exact.

Your computer does not have enough memory for an exact representation of sqrt(2).

Iain2012-09-19 05:00

I hope that everyone saying that the last one was a perfectly valid interview has never got annoyed while making a support call; never pushed the drone on the phone to deviate from the script that they're trained to follow; patiently performed any diagnostic/remedial tasks that they are asked to without lying about it.

Otherwise they're hypocrites.

dv2012-09-19 05:09

You do know that square roots tend to be irrational, yes?

Spaatz2012-09-19 05:45

That has never stopped the people at sales/marketing from asking for the square root of a non number, and the saying, "Just be creative, man! I have to delived to the client by the end of next week!"

Captcha: facilisi : Of course it is!

Spaatz2012-09-19 05:47

Yucks, I forgot toe mention this in my previous comment...

Captcha: haero : he who saves the day

Spaatz2012-09-19 06:00

Kasper:

I have interviewed more than 100 people, and I have come across a few with an attitude like snoofle. With such candidates, I'd recommend that we did not hire them, because of their attitude.

Of course programmers are not supposed to reinvent square root every time they need to calculate it. But somebody has to implement it in the first place. And whenever new platforms are put into use, there are some pieces of basic code that has to be written over again. So there is actually a need for people who can write those basic pieces of code again.

But that's not the point in asking such a question. The point surely was to test the candidates ability to write some code to solve a simple problem.

The interviewer learned three things about snoofle from that question:
1. He doesn't know any of the many possible algorithms to solve this problem.
2. He doesn't have the skills to derive an algorithm from scratch to solve a quite simple problem.
3. He displays a bad attitude when faced with a task he doesn't like.

Given how much the interviewer learned about the candidate from that one question, I think it was a great question.

OMG. I'd love to interview YOU... You must be a really acommodating worker, never questioning stupid situations and accepting anything you boss says:
Kasper, please, today I want you to write all your code without using the letter 'e'.
(Kasper thinks: what a sensible demand, of course some day my e key might break, and there will be no keyboard replacement, the chance to buy a new one in the shop down the street, use a colleague's keyboard, bring my portable from home... mmm. let's reinvent the while loop for starters... man I love my boss and this job!).

What I would learn from someone not leaving the room is:
1. This guy takes everthing!
2. This guy can be abused with silly demands
3. This guy goes for the complex, unneeded solution first and only (if ever) goes for the obvious, he must be very productive if/when we need to reinvent the wheel! (which of course is something we do every week).
4. This guys must be desperate for a job, I'll offer him less than what should the salay for this position!
5. Maybe he will bring a cup of coffee before the interviews ends...
6. Some little more mental abuse and he will call me "Lord"
7. Oh, and I can blame him for all that goes wrong, since he accepts so happily that everything goes wrong...

csrster2012-09-19 06:00

It strikes me that you can't even begin to answer nr. 3 without a much more precise specification of the question:
i) What range? integer, real, complex?
ii) What level of precision?
iii) What performance?
and to be pedantic iv) what error handling?

But yes, I agree with all the posters that any candidate who can't come up with some sort of algorithm off the top of their head is out of the door.

Mr.'; Drop Database --2012-09-19 06:16

Malcom:

M: I'm not a math whiz; I'd drive to a bookstore and get a book on how to do it.
I: What if there were no bookstore?

M: Pop up a window and ask the user to grab a calculator and input the answer.

Your software doesn't have any users. Now what do you do?

I don't need to build any additional ****ing pylons!2012-09-19 06:25

Mark:

Uhmmm.... I'd like to see you use newton's method to calculate the square root of a number without having access to the square root function.

You are looking for roots to a function, in this case, if you look for sqrt(5), you want to find the root(s) of the function f(x) = x*x - 5. No sqrt in the function, none in the derivative.

frg5672012-09-19 06:35

How horrifying, he asked a developer to compose an algorithm! What will be next - telling that there are no method WebSite.CreateEnterpriseWebSiteWithDatabaseAndEverytnig()

Cbuttius2012-09-19 06:35

Ok, we have 4 solutions to get the square root.

1. Binary interpolation. I have seen a few solutions of this. This is O(precision) where precision is the number of bits of precision you require. Processing time will only use fast additions, subtractions and divisions by 2 (which are fast because they just shift the expononent by one in floating point).

2. Secant interpolation. Like binary interpolation, you need two values and you interpolate between them, but instead of picking the point halfway between them, you assume the "curve" between them is a straight line and pick the point that solves your equation. It can be a problem when you have a local maximum but not an issue with square roots as long as you deal only with positive roots as they are monotonic (i.e. sqrt(x) > sqrt(y) whenever x > y, which is monotonically increasing). The merge is usually quicker than binary interpolation I think O(log(precision)) actually. It does however require doing floating-point division per iteration.

3. Newton-Raphson. Unlike the other two methods above it does not use interpolation between two points. Instead you know the slope of the function (derivative) and assume the slope at your particular point remains constant. Thus you draw a line using just your one point. This can fail badly for non-monotonic functions too as you can head in the wrong direction but works for square-root. I recall this is marginally more efficient in number of iterations than secant but may require more complex calculations per iteration so may actually take more processing time. For square-root of y, I think x -> (x+(y/x))/2 is the correct iterative step, and you will alternate between numbers that are too high and too low.

4. Tables. Assuming we can split our number into an exponent and mantissa: actually we need always an even exponent, so the mantissa will have the range 1-3.999999 or 0.5 to 1.9999999. If we can store square-roots of these numbers to certain precision we already have a rough estimate. We can then interpolate the last few steps (probably with the secant method) but it gives us a head start. We could use tables of logarithms instead which means we can divide by two, but then we'll have to perform a "power" function back.

If I were writing an operating system kernel and a processor that had to be math-heavy and fast, there would probably be some cached tables.

Of course, an implementation detail is that as we will often be dealing with floating point approximations, we have to ensure we don't iterate forever even if we don't have a perfect solution. So we may need to store our last 2 solutions anyway to see if we meet the same one again.

Remember in Newton Raphson, that our value moves alternately below and above the correct answer? That means we might revisit the number we had 2 iterations ago, so we need to store it anyway.

Cbuttius2012-09-19 06:43

snoofle:

ammoQ:

Back in 1994, the programmers responsible for maintaining a legacy ERP systems asked me how to calculate the cubic root of a number, because they were using COBOL and apparently they didn't have a math library available. I explained them how to do that using Newton's approximation, which was good enough for the problem at hand.

In my experience, being completely unable to handle this kind of problem without using a library function is not something I'd like to see in my fellow team members.

So they were able to ask a co-worker? Nobody said I was completely unable to handle it; only that I couldn't do it in the 10ish seconds you have to answer an interview question before the silence becomes awkward.

they don't have log and exp? log, divide by 3, exp...

cube itself is monotonic but cubics in general are not.

Cbuttius2012-09-19 06:45

Pluvius:

The neverending "you can't win" questions always remind me of the bear joke.

"Hey, Jim, what would you do if you were in the forest and you met a bear?"
"I'd back away slowly."
"But it's mad, it attacks you!"
"I shoot it."
"You don't have a gun!"
"I run away."
"It runs faster than you!"
"I climb a tree."
"It climbs better than you!"
"I jump in the river."
"It swims faster than you!!"
"Listen, Mike, whose side are you on, mine or the bear's?"

And the punchline variation:

"I'd hide."
"It's much better than you at hiding and you'll never find it again!"

"I'm in the forest so I grab two sticks off a tree and rub them together to make a fire then use that to scare off the bear"

Neil2012-09-19 06:54

The binary search method using consecutive powers of two for the first approximation has the attraction of not needing any multiplication or division (although shifting is required), by the expedient of maintaining the error in the approximation as the accuracy of the square root is improved. If you normalise the error then you can simply compare the error against the average of the current approximation and the next candidate (if it is less then the candidate is too large).

GeoffM2012-09-19 06:57

+NaN

I said "+NaN" but Akismet complained.

Malcom2012-09-19 07:29

Mr.'; Drop Database --:

Malcom:

M: I'm not a math whiz; I'd drive to a bookstore and get a book on how to do it.
I: What if there were no bookstore?

M: Pop up a window and ask the user to grab a calculator and input the answer.

Your software doesn't have any users. Now what do you do?

Pretty much whatever I feel like, because it won't matter, and you're going to go broke before my next paycheck.

Jack2012-09-19 07:51

Mr.'; Drop Database --:

Malcom:

M: I'm not a math whiz; I'd drive to a bookstore and get a book on how to do it.
I: What if there were no bookstore?

M: Pop up a window and ask the user to grab a calculator and input the answer.

Your software doesn't have any users. Now what do you do?

M: Refactor it as a CAPTCHA and outsource the solving to India.
I: India has been vaporized by a nuclear blast. What do you do?
M: Ask for a raise.

Echelon2012-09-19 08:16

Simple method to calculate sqrt in 100x standard time when you have no sources: try and retry

for (i=2; i< int.max; i++)
if (i*i==operand) return i;

After you tried this (the square root is not an integer) consider approximating. I don't remember the code and while I have Google with me I'm not using it

1. Pick the highest integer such as "i*i < operand". (i+1)*(i+1) must be > operand
2. Pick a=i, b=i+1, c=(a+b)/2
3. If abs((c*c)-operand) < EPSILON return c
4. If (c*c)-operand<0 pick a=a, b=c, c=(a+b)/2, repeat 2
5. If (c*c)-operand>0 pick a=c, b=b, c=(a+b)/2, repeat 2

This algorithm has an exact scientific name but I currently don't remember it. More efficient methods include Newton's approximation but I don't remember the code and I'm voluntarily not using Google.

Can I consider myself hired?

Captcha: refoveo

snoofle2012-09-19 08:28

SQRT:

snoofle:

Kasper:

I have interviewed more than 100 people, and I have come across a few with an attitude like snoofle. With such candidates, I'd recommend that we did not hire them, because of their attitude.

Sadly, most of you still seem to be missing the entire point, so let me illustrate...

Hypothetically, you are the interviewer, I am the candidate, and for the sake of argument, I am Mr. Math Wizard. You ask your question (in an intelligent way): We'd like to see how you think and go about problem solving; please explain how you might go about designing a method to compute a square root. As a shrewd interviewee, I ponder for a second, then respond with iterative approximation, perhaps mentioning some edge cases, negative numbers, numbers < 1, etc.

You probably think to yourself: Hey, this guy knows his stuff, and will probably use that as a significant portion of your hiring decision.

Epic Fail.

The only thing you have learned about me is if I can come up with a way to compute a square root. Unless the job entails figuring out new mathematical algorithms, or computing square roots, you have learned absolutely nothing about my ability to do the actual job.
<snip>

I respectfully submit that you are also missing the point. I fall in the camp that thinks this is a reasonable interview question. I might consider using it in the future.

Your assumption that I would think "Hey, this guy knows his stuff, and will probably use that as a significant portion of your hiring decision" would be wrong. It's only 1 question. You don't know that the next question wouldn't have started with 'Our production environment looks like x...'. You judged the interviewer based on 1 question. I judge an interviewee based on answers to multiple questions.

I even like the approach the guy used of pulling the rug out from under you as you give the right answers. It's actually better than jumping straight to write a sqrt function from scratch.

Here's what would go through my mind as the interviewer in that scenario:
Interviewer: How would you calculate a square root (java)?
Me: Math.sqrt(double)
+5 for knowing the obvious solution without having to look it up. I: What if there were no square root function?
M: I'd Google for John Carmack's formula to calculate it.
+20 for being able to name an existing algorithm to solve the problem. +10 for knowing that Google is your friend here. +10 for knowing that this is a solved problem, no need to reinvent the wheel here. I: What if you couldn't use Google?
M: Assuming you mean no access to the internet, since I don't happen to know how to calculate a square root, I'd ask someone...
+10 for not being afraid to ask someone when you don't know the answer, rather than wasting hours trying to figure it out yourself. I: What if there were nobody to ask?
M: I'm not a math whiz; I'd drive to a bookstore and get a book on how to do it.
+5 for admitting you don't know everything. +5 for remembering that there were bookstores before there was Google. I: What if there were no bookstore?
M: Ok, so you want me to come up with a formula I've told you I don't know, in the next 10 seconds, without access to any of the usual reference sources?
Yes, I would like you to come up with an algorithm to solve the problem, even if it isn't a very good one. Take as much time as you would like. There is no 10 second time limit. Think about it while I check my email. Take your time. Use the whiteboard if you want.

M: <Walks Out>
-1000. Too bad. He was doing fine at +65. But hiring this guy would have been an Epic Fail. When faced with a difficult challenge, he chooses flight over fight. Not what we need here.

Sadly, in spite of my stating it REPEATEDLY, you are still missing my main point: I USED to answer those questions AND GET THE JOB. Then I found out that working for people who pose questions in that manner is a BAD THING.

As a reasonably intelligent person, I learned that certain actions on the part of the interviewer tell me that I DON'T WANT THAT JOB - that is why I walk out.

It's not that *I* fail the interview; it's that the INTERVIEWER has already failed MY interview.

Remember, interviewing is a two way street.

JimFin2012-09-19 08:47

The square root question is about finding your own solutions to a well-defined problem. It's meant to asses your inventive capabilities, not your knowledge.

The answer is dead-simple once you realize that the problem is actually: how do you find number y for which y * y = x, where x is the number whose square root is being calculated?

Failing this, you showed the interviewer that you might be prone to getting confused when left to your own devices.

ceiswyn2012-09-19 09:40

JimFin:

Failing this, you showed the interviewer that you might be prone to getting confused when left to your own devices.

And the candidate cares about this why?

Everyone here seems to keep getting hung up on what the interviewer now thinks about the candidate, but the interviewer's opinion has become completely irrelevant. What is relevant is that the impression the interviewer has made on the candidate has led to the candidate rejecting the job.

Interviewers aren't the only decision-makers in an interview situation. They need to impress good candidates just as much as - if not sometimes more than - candidates need to impress them, and it's rather depressing that so many supposedly experienced people here seem not to know that.

ctd2012-09-19 10:11

foo:

OccupyWallStreet:

What if you're not allowed to use NAND gates? And no, wiring transistors up to form NAND gates is not allowed. You are, however, free to wire up transistors to form any other logic gate (except NAND), but the gate you choose is the only one you can use.

That's neither funny nor relevant.

Sure it's relevant. Having followed a line of reasoning (Brownian motion though it may be) we're discovering how far the candidate's knowledge goes. Knowing one can build a full computer out of NAND gates indicates (not guarantees; that's why we keep digging!) his knowledge goes pretty deep. Now, let's see if he just happens to know the random factoid "you can create a computer with just NAND gates", or is his knowledge at that point broad enough to also know the same of NOR gates?

What snoofle and others miss in their insistence "you're not learning anything useful about the candidate! but the interviewer's tone shows he's an idiot!" is the reverse is true too: the candidate's tone (including the quasi-hypothetical "that's neither funny nor relevant") derives the same conclusion.

Sure, you're not going to be required to code up square root functions, nor will you be limited to your choice of non-NAND gates. If you don't find inherent challenge or humor in such hypotheticals, if http://xkcd.com/505/ or http://ioccc.org/ don't intrigue you despite their obtuse irrelevance, you're not the droid we're looking for.

linepro2012-09-19 10:27

asm { FSQRT }

ctd2012-09-19 10:30

ceiswyn:

What is relevant is that the impression the interviewer has made on the candidate has led to the candidate rejecting the job.

What's relevant is that this fact was not made anywhere close to clear in the dWTF article, until enough people piled on the candidate about how the allegedly WTF question was quite reasonable and the walking-out was the real WTF, then he backtracked hard and claimed the real WTF was the impression the interviewer made. The real WTF now is the bifurcation of this thread.

ctd2012-09-19 10:35

snoofle:

As a reasonably intelligent person, I learned that certain actions on the part of the interviewer tell me that I DON'T WANT THAT JOB - that is why I walk out.

OK, fair enough. Certain questions, and methods of asking them, are red flags warning you it's not the job you want. Good. He asked a question suitable for screening a candidate for what he wants, you screen questions for whether you want to work there; you both concluded it wasn't a mutual fit, and you didn't waste his time any further (see prior dWTF discussions).

So what's the WTF?

NMe2012-09-19 10:55

The story about the startup is not entirely fair. Yes, those "businessmen" were probably clueless about what they were getting into, but they are being discredited a bit more than necessary. When speaking about HTML5, people generally mean the combination of HTML, CSS and JS, sometimes even the server side bits required for AJAX. Personally I dislike misusing the HTML5 name for what used to be called dynamic HTML or DHTML, and even DHTML wasn't a proper name. But I'm guessing these people at least meant to use javascript and not just the markup language.

Granted, even in this broader light HTML5 would not be great choice for data analysis, but it's not as bad an idea as the submitter portrayed.

Andy2012-09-19 10:57

snoofle:

Remember, interviewing is a two way street.

QFT.

I recently spent a full day in interviews during which nobody made the slightest attempt to convince me why I would want to work there. Nor did their highly scripted interview schedule allow time for my questions, unless they expected me to brazenly divert them off their script and demonstrate that I was determined to put my own interests first.

If that's what it's like during the "sales pitch" can you imagine how it turns once you're locked in?

Cbuttius2012-09-19 11:02

At present this has generated the most comments since 10 July when this: Just A Warm Up was the WTF of the day.

DES2012-09-19 11:22

consequat:

DES:

If I was conducting interviews for a programmer position [...]

You're a heavy unit-test guy, aren't you?

Your mind truly works in mysterious ways.

What is “a heavy unit-test guy”, and how is my being so (or not) relevant?

coder guy2012-09-19 11:27

That's why you use *successive approximation* to get closer to the truth. You're not likely to get the exact value of the root of 2 since it's irrational, but you can guess 1.4, then 1.42, then 1.41, then 1.415...

Come on, am I really a Mensa candidate for knowing this? This is basic problem solving, people.

Nohbdy2012-09-19 11:38

I want to disagree just a little bit with the last story (and people's reaction to it so far). The point of questions like that are to see how you think in relation to new problems you encounter that don't have solutions already made. Granted, this is a very poor example because square root calculation is a solved problem, but I do think seeing how you think about new problems is an important thing for interviewers to do. Basically, they should come up with their own "new" problem instead of asking about square roots.

Alin2012-09-19 11:39

Niels:

An iterative approximation for a square root shouldn't be hard to come up with.

With binary search as with all others, you have to "square" your guess to compare against the target.

Incidentally you can also do a Taylor Series expansion here but for it to converge quickly you would need a close square number to start from. Still, our methods do give us some approximations which we square.

If we are going to reduce to numbers between 1 and 4, we can also split that range into squares e.g. 1-1.25, 1.25-1.5, 1.5-1.75, 1.75-2 squared, then factor down, and then employ our Taylor series.

CSCDave2012-09-19 12:54

Clearly, it needs to be TDD:

[Test]
public void ShouldReturnTwoWhenPassedFour() {
Assert.AreEqual(2, NewMath.SqRoot(4));
}

[Test]
public void ShouldReturnThreeWhenPassedNine() {
Assert.AreEqual(3, NewMath.SqRoot(9));
}

You must be a really acommodating worker, never questioning stupid situations and accepting anything you boss says

You think you know me. You don't. Anybody who has worked with me can testify, that I will point out when somebody is making ridiculous suggestions on how something should be done, regardless of who is saying it.

On one occasion I have told off a manager. It wasn't my own manager, but another on the same level. I basically told him that's my decision to make, not yours. The next day he came to me and apologized for his behaviour, and thanked me for my effort.

I have never needed to speak to my own manager in such a voice, so nobody can say how I would have reacted in such a situation.

On some occasions you will find yourself in a situation, where sensible arguments won't work on otherwise sensible persons. In those cases it may be counter productive to keep arguing for a sensible solution. On a few occasions I have accepted to go with a solution, I knew to be a bad idea. If nothing else, that gave me opportunities to come back and say "told you so"

Spaatz:

What I would learn from someone not leaving the room is

Nothing.

I have interviewed lots of people. Nobody ever left the room before time.

Lucas2012-09-19 14:02

I am totally with snoofle here. Interviewing is a two way street and when faced with silly hypothetical questions it gives you warnings signs.

Good employers normally either ask you how you know a particular technology, let you talk about it and then judge if you know what you are talking about.

Some less technical people want to get a sense of your skills by asking you a questions such as "describe a situation where you solved a difficult task." ... you describe what the problem is, why it was difficult and how you went about solving it and what you have learned along the way.

The first answers snoofle gave were decent and fair answers to the questions, once the situation presented becomes so ridiculous that the situation isn't grounded in reality, then you know that your boss is most likely a bit of a dick ... and you don't want to work for them.

Jack2012-09-19 14:38

The interviewer just asked the question wrong. What s/he should hae said, right from the start, is, "Write a function to find your best approximation of the square root of the input, without using the Math class. Take me through your thought process." That's not so unreasonable.

jay2012-09-19 14:45

DES:

If I was conducting interviews for a programmer position, I'd immediately fail any candidate who didn't know Newton's method and was unable to come up with it (or a similar successive approximation method) on the spot. It is blindingly obvious, and trivial to implement.

As someone who happens to be familiar with Newton's method of approximation, I can say that that is simply a silly criterion. How many mathematical formulas and theorems have been invented over the centuries? I'll bet you don't know 99.9% of them and probably wouldn't understand most of them if someone tried to explain them to you. But you would reject a candidate because he didn't know one particular formula off the top of his head? Maybe this one is more important and fundamental than most. But so what? Maybe the candidate has never had occassion to need it.

By the way, Newton's method of approximation does not use successive approximations as you indicate in your post. See, for example, http://www.math.wpi.edu/Course_Materials/MA1021C06/lin_approx/node1.html for an explanation of how it works. Apparently you do not know this method yourself. You fail your own test! :-)

And "it's blindingly obvious"? Than how come it took a genius like Newton to invent it? Why wasn't it invented 500 or 1000 years earlier? Maybe you re-invented it on your own with no hints whatsever when you were in third grade. But I suspect that it's only "obvious" now that someone else has explained it to you. I always get a laugh out of people who say that they could have made some great discovery or invention if only so-and-so hadn't done it first. Sure. Prove it by making some equally great discovery on your own now.

(I get an even bigger laugh out of people who ridicule a genius for wasting his time on an idea that was just obviously wrong. Like people who make fun of Galileo for trying to find a correspondance between the platonic solids and the orbits of the planets, or Newton for investigating alchemy. Sure, it's obvious NOW, after great geniuses spent decades investigating and demonstrating that these ideas don't work. But nobody would know that unless these men had done the work to prove it. Someone builds a boat and travels thousands of miles to discover a new continent, and then you proclaim that it was all a waste of time because you could have told him that continent was there without making the trip. Sure, but you only know that because HE made the trip. But I digress.)

Sam I am2012-09-19 14:56

I don't know about that, I'm told that I have some comprehension problems, but in reading this I knew exactly what the interviewer wanted.

The interviewer seemed to, at the time, be stuck in a train of thought and yes, he did not phrase the question optimally, but that makes him only human.

The fact that the interviewee misunderstood the question at first was also understandable.

nobody was particularly unreasonable UNTIL after, the interviewee understood that the interviewer wanted him to implement sqrt(), where he effectively said "fuck that" and stormed off.

jay2012-09-19 15:07

On the square root one: I'm sympathetic to the interviewer. Okay, if he really asked the question this way, rejecting every proposed solution with an "okay, what if that didn't work", that's annoying.

But suppose he had asked the question in a way that made it clear what he wanted, like: "How would you calculate a square root if the language you are using does not have a square root function? Assume that you cannot ask anyone for help or use any reference material: you must come up with a solution yourself." I think that's a fair interview question. Sure, in real life a programmer probably won't have to come up with his own formula to find square roots. But he will have to come up with solutions to problems where there will be no handy answers available on the Internet, and he can't ask co-workers to do his work for him all the time.

Saying that this problem isn't relevant to the job is itself irrelevant. The real problems that would be relevant to the job would likely require hours, days, or even months of explanation of company business practices, existing systems, market conditions, etc etc. If a potential employer asked you to write a complete employee benefits system that would interface with the company's existing payroll system and the insurance company's system, and that handles all the benefits that the company presently offers, adjusting for recent changes in the law that may affect those benefits, and taking into account new benefits that the company is considering offerring ... Surely you would object that it is impossible to even collect all the requirements in the couple of hours available in an interview, never mind actually build such a system. Any problem that can be posed in an interview must, of practical necessity, be something abstract and probably generic.

When I was interviewing for my present job, they asked me to write a program that plays Bizz-Buzz. I didn't suppose that a company that develops web sites for hotels would often have occassion to need Bizz-Buzz programs. But I understood that the point was to see if I could write working code.

Lucas2012-09-19 15:09

I totally agree with the fact the question should have been asked as such, but snoofles comments were along the lines of

"I am deciding whether I want to work for them or not, and if he asks questions like this I don't want to work with them based on what I have heard hear and what I experienced before".

AN AMAZING CODER2012-09-19 15:17

The Cloud story probably went more along the lines of booger eater CS students with zero life experience mocking business guys because they can afford suits and investments by overblowing their pitch on their technology.

Yeah, "Siri for Data Analytics" isn't realistic....

I'm guessing those business guys saw the level of idiocracy amongs those CS students, and decided to not bother giving them a real pitch.

AN AMAZING CODER2012-09-19 15:33

jay:

DES:

If I was conducting interviews for a programmer position, I'd immediately fail any candidate who didn't know Newton's method and was unable to come up with it (or a similar successive approximation method) on the spot. It is blindingly obvious, and trivial to implement.

As someone who happens to be familiar with Newton's method of approximation, I can say that that is simply a silly criterion. How many mathematical formulas and theorems have been invented over the centuries? I'll bet you don't know 99.9% of them and probably wouldn't understand most of them if someone tried to explain them to you. But you would reject a candidate because he didn't know one particular formula off the top of his head? Maybe this one is more important and fundamental than most. But so what? Maybe the candidate has never had occassion to need it.

By the way, Newton's method of approximation does not use successive approximations as you indicate in your post. See, for example, http://www.math.wpi.edu/Course_Materials/MA1021C06/lin_approx/node1.html for an explanation of how it works. Apparently you do not know this method yourself. You fail your own test! :-)

And "it's blindingly obvious"? Than how come it took a genius like Newton to invent it? Why wasn't it invented 500 or 1000 years earlier? Maybe you re-invented it on your own with no hints whatsever when you were in third grade. But I suspect that it's only "obvious" now that someone else has explained it to you. I always get a laugh out of people who say that they could have made some great discovery or invention if only so-and-so hadn't done it first. Sure. Prove it by making some equally great discovery on your own now.

(I get an even bigger laugh out of people who ridicule a genius for wasting his time on an idea that was just obviously wrong. Like people who make fun of Galileo for trying to find a correspondance between the platonic solids and the orbits of the planets, or Newton for investigating alchemy. Sure, it's obvious NOW, after great geniuses spent decades investigating and demonstrating that these ideas don't work. But nobody would know that unless these men had done the work to prove it. Someone builds a boat and travels thousands of miles to discover a new continent, and then you proclaim that it was all a waste of time because you could have told him that continent was there without making the trip. Sure, but you only know that because HE made the trip. But I digress.)

The interviewer was trying to weed out people like you.

The point of the question, although delivered terribly, was for you to think about what a square root is and how to get to it. If I was the interviewer, I would have rephrased with the following:

You do know the square root of A = B*B. How would you figure out B?

If you can't get past the FORMULA and get a better idea of what you're actually trying to do, you probably shouldn't be rebuidling legacy systems. Your ability to see the whole problem and solution is narrow.

Another big point in this situation is the interviewee's inability to accept someone elses reality. Instead of being curious, he was arrogant.

If the question was "how do you find the distance between two points?" You wouldn't agree with the interviewee. You're all caught up on "square roots are hard, waaaaa".

Thomas Wright2012-09-19 15:43

My solution,
implement a natural logarithm function and exponential function if they not available (it can be implemented easily enough using their taylor series if they are not provided). After that it is easy enough to find the square point.

Otherwise, one can also use either fixed point iteration, or Newton Raphson to find square roots.

(I am not saying being able to answer this unrealistic question makes me more or less qualified for a programming position; technically I cheated, being a Maths student).

Sam I am2012-09-19 16:00

Thomas Wright:

My solution,
implement a natural logarithm function and exponential function if they not available (it can be implemented easily enough using their taylor series if they are not provided). After that it is easy enough to find the square point.

Otherwise, one can also use either fixed point iteration, or Newton Raphson to find square roots.

(I am not saying being able to answer this unrealistic question makes me more or less qualified for a programming position; technically I cheated, being a Maths student).

If I were the interviewer, I'd then ask you to go ahead derive the taylor series.

Also, I don't understand why everyone seems to be expecting "realistic" questions. If they were asking you to solve realistic actual job-related problems, those problems would take you all day.

Sam I am2012-09-19 16:00

Thomas Wright:

My solution,
implement a natural logarithm function and exponential function if they not available (it can be implemented easily enough using their taylor series if they are not provided). After that it is easy enough to find the square point.

Otherwise, one can also use either fixed point iteration, or Newton Raphson to find square roots.

(I am not saying being able to answer this unrealistic question makes me more or less qualified for a programming position; technically I cheated, being a Maths student).

If I were the interviewer, I'd then ask you to go ahead derive the taylor series.

Also, I don't understand why everyone seems to be expecting "realistic" questions. If they were asking you to solve realistic actual job-related problems, those problems would take you all day.

JJ2012-09-19 16:22

To everyone who said, "Perhaps the interviewer could have phrased the question better," THAT'S THE WHOLE POINT! It's not that snoofle didn't understand what the interviewer wanted; it's that he recognized that the interviewer (who would probably have become his boss) was a bad communicator, and that was a red flag. I've worked with people like that, and I'd prefer never to again. If I were to glean such insight from interview questions, I'd end the interview as well.

derp2012-09-19 17:46

JJ:

To everyone who said, "Perhaps the interviewer could have phrased the question better," THAT'S THE WHOLE POINT! It's not that snoofle didn't understand what the interviewer wanted; it's that he recognized that the interviewer (who would probably have become his boss) was a bad communicator, and that was a red flag. I've worked with people like that, and I'd prefer never to again. If I were to glean such insight from interview questions, I'd end the interview as well.

This. The core of the interview question in and of itself is in no way unreasonable, in my opinion. I think it's a fine candidate for a programming question. But it should be phrased as such right off the bat: "Please implement a function that calculates the square root of an integer without using a Math library." or whatever.

Going through a chain of "what if's" is 90% of the time irritating and petty UNLESS you are, in fact, trying to iron out an obscure problem and gather requirements. That is not the case here, however. And if you wanted to have such a question, it would be approached with "what if you had this input," or "what if there was this corner case" but probably not "what if you didn't have this basic technology that you might actually need to solve this problem effectively."

That said, anything where you want to have the candidate explore the problem needs to be designed that way right off the bat, and needs to be much more complex than "implement sqrt."

DSkoll2012-09-19 18:14

snoofle:

coder guy:

It seems to me that anyone who can't even come up with a lame attempt at successive approximation to figure out a square root without running to a reference isn't fit for a programming job.

Why? The guy wanted an exact value, not an approximation.

OK, snoofle. I won't be hiring you.

DSkoll2012-09-19 18:15

Level 2:

Your computer does not have enough memory for an exact representation of sqrt(2).

Actually, mine does because it represents numbers in base(sqrt(2)). It seems to have problems with numbers like "1", however.

DSkoll2012-09-19 18:20

QJo:

Fail. You can't get it exact because square roots are (in all cases except when all the prime factors are to an even power) irrational.

Oh? So sqrt(0.789 * 0.789) is irrational?

PG42012-09-19 19:15

Snoofle for president!!!!!!!!!!

OK, yes we know that interviewer wanted to find out how snoofle would approach a problem. However......

The BS of keep taking away valid answers is just stupid. Others have said it, the interviewer should have asked the question in a different way. If you ask the question that way because that's the only way you have heard it done, then it shows just how small minded the interviewer is.

And snoofle said it, he has seen what happens in job when they ask these types of questions, and he doesn't like it.

Whatever2012-09-19 19:56

I think snoofle makes too much about the specific problem, sqrt. The interviewer is trying to find out his problem solving skills, and the only thing snoofle is thinking about is how he can copy it off of someone or sth.
I wonder how many hours he will spend trying to find a design pattern for each and every small problem that comes at him. Would he even do any creative work?
Or maybe he just designs gui. I dont know.
I mean, he know what a square root is, doesnt he?

PG42012-09-19 21:07

Well I think you would fail in just about any security situation.

Ever see the code that people write when they really don't understand all the crypto issues? Better to take a WELL proven chunk of code and use it than reinvet the wheel with all kinds of security issues.

Anonymous Coward2012-09-19 22:18

DSkoll:

QJo:

Fail. You can't get it exact because square roots are (in all cases except when all the prime factors are to an even power) irrational.

Oh? So sqrt(0.789 * 0.789) is irrational?

No, in sqrt(3^2 * 263^2 / 2^6 / 5^6), all the prime factors are to an even power.

scooby5092012-09-20 00:19

Niels:

An iterative approximation for a square root shouldn't be hard to come up with.

It's really worth it to (re)learn Newton's method. Just to see if I can do this off the top of my head:

You're looking for a zero, right? So you're going to guess an x, calculate f(x), giving you a y. Then you want to draw a line tangent to the curve at that (x, y), and the zero of that line is your next guess.

Obviously, the slope of the tangent line is the derivative, and we're looking for is the solutions to x^2 - n = 0, where 'n' is the number we're taking the square root of.

The derivative of x^y (where y is constant) is the first rule you learned: y * x^(y-1). n is constant, so the derivative is just 2x

To find the tangent line from a point, expess it parametrically by setting the slope equal to itself:

m = (0 - Y) / (x - X)
x = X - Y/m

In python:

def newton(func, deriv, guess):
x = guess
while True:
y = func(x)
yield (x, y)
x = x - y / deriv(x)

n = 20.0
eps = 1e-12
for x, y in newton(lambda x: x * x - n, lambda x : 2 * x, 1.0):
print x
if abs(y) < eps:
break

To make it more robust, you can pick some random number if 'm' turns out to be zero :-)

dv2012-09-20 04:28

ME2:

The correct answer to the Square root question is obviously:

How does having me re-implement standard library functions bring in revenue to this company?

You god damn geekass bastards.

No, the correct answer to the Square root question is obviously: "Is this to be an empathy test?"

David2012-09-20 05:16

derp:

Going through a chain of "what if's" is 90% of the time irritating and petty UNLESS you are, in fact, trying to iron out an obscure problem and gather requirements. That is not the case here, however. And if you wanted to have such a question, it would be approached with "what if you had this input," or "what if there was this corner case" but probably not "what if you didn't have this basic technology that you might actually need to solve this problem effectively."

Doublethis.

Being asked "what if $REASONABLE_THING" is perfectly valid. But being asked "what if $DUMB_THING" is as redflagful as being asked to "code up a web 2.0 app to leverage our synergies going forward". Both should be treated accordingly.

Clearly the interviewer heard about this really cool interview techique and cant wait to try it out without actually understanding it at all. Of course, that may be his *only* fault. And unlike snoofle, others might be quite happy to take a chance on that being his only fault, and go to work for him anyway.

Indeed, I look forward to seeing some of their code on this very blog.

Cbuttius2012-09-20 05:37

A Taylor series works as a calcuation of f(x+a) based on the evalution of f(x) being simple to calculate as well as all the derivatives of f at x.

The derivatives of sqrt are powers of -.5, -1.5, -2.5 etc so you need the square root of the x. Therefore we start based on a squared number.

mod(a) should be < x for this and you should probably factor it down to make x==1 so divide the whole series by a constant so it ends up being that way.

If you want the square root of 29, for example, you would divide by 25 to get the square root of 1.16 so x = 1 and a = 0.16

If you want the square root of 47, you could divide by 49 (better than 36) and a would be negative.

Incidentally if x is rational then you would be able to store root(x) "exactly" in your memory as long as you don't store it in IEEE format but store it in a special class either as a square-root (algebraic number in general) or as a recurring continued fraction. Irrational square roots are always recurring continued fractions.

pi and e are transcendental (numbers that are real but not algebraic) but both are sums of an infinite series of rationals. pi/4 is atan(1) so usually pi is calculated as atan(1)*4.

Understanding Taylor series expansions, interpolation techniques and other solving problems may well be required in a programming job. Most of the equations you will be solving won't be square-roots and won't be solvable by a library function. Of course the interviewer may have said after the square root one, "ok now solve this" and give a function that has no library solution...

Incidentally I would normally only ask at interview something that either:
- was relevant for the job
or
- was something the user specified on their CV.

and usually the latter. So if the candidate doesn't want to be tested on it, they shouldn't put it on their CV.

Cbuttius2012-09-20 06:51

You see it is interesting to read the solutions here as to how you handle the "epsilon" situation.

I am seeing people use absolute epsilon which is faulty. Error is relative, not absolute.

IEEE numbers allow exponents of 2 to the power of something like 1023 so if you are asked to find the square root of 2 to the power of -1022, you can find it exactly, it will be 2 to the power of -511. Not approximately that, exactly that. No rounding errors. Similarly 9*pow(2,-1022) (yeah, 1.125*pow(2,-1019) has an exact square root of 3*pow(2,-511) (1.5*pow(2,-510)).

If it is 5*pow(2,-1022) there won't be an exact square root, of course, but have your answer out by 2 to the power of -15 and you are way out...

Conversely if we are going to find the square root of 5 * pow(2,1014) your epsilon will need to be a LOT higher...

The "error" needs to be in the square root, not in the square.

For me, the ability to ensure the algorithm terminates properly is more important than the fastest merging numerical method, so I would rather see a correctly-terminating binary interpolation algorithm than a faulty Newton-Raphson.

The weird way doubles are processed means that when you do reach the final destination, it won't neceesarily equate "equal" to either of your lower and upper bounds. (And actually I was not quite correct earlier. You won't always move between solutions too low and too high. You will for square root but not for functions in general).

Incidentally alternative interpolation methods are:

- Quadratic interpolation, although it requires you know how to calculate square-roots. Also assumes you know derivatives, but works in "general". You solve current value, last value and current slope (but not last scope).

- Cubic spline interpolation. For just 2 points you would use values and slopes at both points. The only issue is actually "solving" the cubic (which is solvable, Nicolo Tartaglia).

Normally used to interpolate when you don't have absolute values and usually done with multiple values, and the "slope" is not known at the key points but continual ranges are assumed to be continuous in slope at these points, which does give you a bit of scope at the end points.

These interpolations are worth using when the function you need to evaluate is very expensive compared to all else.

Cbuttius2012-09-20 06:53

Ok, I am going to comment on the Founders issue, and the real WTF there is that in most cases, the business of the start-ups should be based on market research on what they are going to sell, and not on how they will implement it.

The development side should be trusted to the technical architects.

Wazza2012-09-20 07:51

Its not hard:

public static double sqrt(double val)

{
return 1; # accuracy increases as val -> 1

}

chfexcel2012-09-20 07:53

How about: "Imagine all the people / Living life in trees"

* it rhymes better

DES2012-09-20 09:41

dv:

No, the correct answer to the Square root question is obviously: "Is this to be an empathy test?"

This.

eil2012-09-20 10:43

My final answer to the last interview question would have gone something like:

"I wouldn't have time to be worrying about square roots, I would be with my family trying to find the nearest fallout shelter."

Cbuttius2012-09-20 11:31

1. In the hypothetical situation there is no google or search engines so I can now have a great idea for a start-up.. No need to be reinventing the wheel of calculating the square root, I will reinvent the wheel that is google instead and make billions.

Sam I am2012-09-20 13:06

I'm disturbed by everyone suggesting that the square root problem is some sort of interview 2.0 question.

it is a numeric theory and algorithmic question, and the skills that you need to solve it can actually be very relevant to your job even if it might not seem so at first.

It's as though everyone expects you to be given actual problems from production when you go to an interview.

no laughing matter2012-09-20 13:40

Sam I am:

I'm disturbed by everyone suggesting that the square root problem is some sort of interview 2.0 question.

it is a numeric theory and algorithmic question, and the skills that you need to solve it can actually be very relevant to your job even if it might not seem so at first.

The skills to correctly solve it "in real life" are exactly the skills that have been shown by the author:

1.) Don't reinvent the wheel (badly). Know that it is a solved problem. Know what your platform provides.
2.) If your platform does not provide it, use a search engine to find out if it already has been solved by someone else (bonus points for knowing a good search term for this).
3.) If that still is insufficient, look up (scientific) literature about the problem. If others already have tackled the problem, chances are that they know about problems that you will run into with a "invent-it-myself-in-10-seconds" approach. (see sqrt(x) when x < 1)

Shea2012-09-20 15:02

Wow that last one sounds like an old naval joke:

CO: "Sailor, what would you do if a strong wind came up the port side?"
Sailor: "I'd drop an anchor off the port side, sir."
CO: "Then what would you do if there was a strong gust from starboard?"
Sailor: "I'd drop an anchor off the starboard side, sir."
CO: "But what if a wind came up from astern?"
Sailor: "I'd drop an anchor off the stern, sir."
CO: "Wait a minute, sailor. Where are you getting all of those anchors?"
Sailor: "The same place you're getting all of the wind, sir."

The first sign of a bad technical job is often a bad interviewer.

Shea

Capt. Obvious2012-09-20 16:03

Severity One:

If he wanted to know how you'd deal with a situation where you don't have all the information readily available, he should have bloody asked and not come up with some Interview 2.0 rubbish that he clearly didn't understand himself.

He did: "What if you couldn't use Google"

Leaving aside whether Google is "all information", the interviewee clearly understood it to mean "no internet". After all, the next suggestion wasn't to Bing it.

TheFifthHorseman2012-09-20 16:17

That recruitment question is far from stupid in my opinion. The point of it was most likely determining whether or not the candidate is capable of coming up with an ad-hoc solution to a relatively simple problem when having nothing to rely on outside his own memory and reasoning ability.

The solution to the problem is a simple - if slow - approach known as the bisection method. It's not unlike binary search (which you should be familiar with): given a range between a and b where the root should be present (for numbers larger than 1 this initial range will be between 1 and 1/2 x) and then check whether the number between a and b is within set precision from the root ( return it ), smaller than the root ( set a to this number, repeat ) or larger than the root ( set b to this number, repeat ).

This is literally something out of a beginner grade algorithms course, and a fairly reasonable way of finding out whether you can reason your way out of a wet paper bag. The problem is simple, practical and can be solved in a few minutes without bizzarro lateral logic.

no laughing matter2012-09-20 16:19

Capt. Obvious:

Severity One:

If he wanted to know how you'd deal with a situation where you don't have all the information readily available, he should have bloody asked and not come up with some Interview 2.0 rubbish that he clearly didn't understand himself.

He did: "What if you couldn't use Google"

Leaving aside whether Google is "all information", the interviewee clearly understood it to mean "no internet". After all, the next suggestion wasn't to Bing it.

Well the interviewee understood! Severity One's point however was that the interviewer did not understand his own questions - and that you have proven: He asked "What if you couldn't use Google?" when he should have asked "What if you couldn't access the internet?".

satoshi2012-09-20 16:26

Personally I'd rather work with somebody who already knew what "square root" means than somebody who knows details of an old TV series, apparently I'm in a minority around here.

foo2012-09-20 18:45

ctd:

foo:

OccupyWallStreet:

What if you're not allowed to use NAND gates? And no, wiring transistors up to form NAND gates is not allowed. You are, however, free to wire up transistors to form any other logic gate (except NAND), but the gate you choose is the only one you can use.

That's neither funny nor relevant.

Sure it's relevant. Having followed a line of reasoning (Brownian motion though it may be) we're discovering how far the candidate's knowledge goes. Knowing one can build a full computer out of NAND gates indicates (not guarantees; that's why we keep digging!) his knowledge goes pretty deep. Now, let's see if he just happens to know the random factoid "you can create a computer with just NAND gates", or is his knowledge at that point broad enough to also know the same of NOR gates?

What snoofle and others miss in their insistence "you're not learning anything useful about the candidate! but the interviewer's tone shows he's an idiot!" is the reverse is true too: the candidate's tone (including the quasi-hypothetical "that's neither funny nor relevant") derives the same conclusion.

Sure, you're not going to be required to code up square root functions, nor will you be limited to your choice of non-NAND gates. If you don't find inherent challenge or humor in such hypotheticals, if http://xkcd.com/505/ or http://ioccc.org/ don't intrigue you despite their obtuse irrelevance, you're not the droid we're looking for.

I repeat: That's neither funny nor relevant.

Got it now?

raduma2012-09-20 18:59

I'm not sure I agree with that reasoning. It seems to imply that for every single problem you might run across there's already an sdk or book or such that tells how to solve it. Which if true it basically says that there's nothing new to solve in the realm of CS. I don't think lots of people would agree with that.

While asking for something like implement sqrt may be a bit lacking in signal since it's very math oriented instead of cs oriented (though personally I'd expect most decent engineers to be able to come up with even a bad solution), asking interview candidates to try and solve problems that aren't in their comfort zone I do think can give you some good insights into the candidate. You do get to see how they *think* as opposed to how regurgitate patterns and solutions they've been repeating for years. God knows I've interviewed plenty of people who on paper were serious engineers but couldn't solve a basic problem like reverse-a-singly-linked-list w/o access to their precious sdks.

qbolec2012-09-20 19:00

I find amussing comments from people who claim to have forgotten the formula for square root. Let us know when you recall it. It will be fun.

So many of you are missing the beauty of binary search which lays preceisly in the fact that it does not require you to know anything more about the function than if its argument is too large.

Recently I had to icompute number of weekes between two timestamp. After writing unit tests and considering for a moment precomputing for all possible inputs, I given the standard library a chance. Unfortuanately php's date_diff returned wrong number of weeks. But I knew that there is strtotime function which uses very robust linux library and I knew it had +n weeks functionality, so in a minute I hacked a simple binary search workaround for a buggy library.

Another example. I had a system in which I could access rows only by a key, yet I needed to know number of rows. Again, binary search came in handy.

Please, skip "trwtf is php" and "a man with a hammer sees only nails" comments, and admit it: the real wtf is not knowing binary search, and not recognizing theoretical question despite hints. I doubt the same attitide at school was helpful. If someone treats everything so literally he might have some troubles with abstract thinking whoch might be necessary to model parts of the reality in a program.

TheFifthHorseman2012-09-21 08:06

raduma:

I'm not sure I agree with that reasoning. It seems to imply that for every single problem you might run across there's already an sdk or book or such that tells how to solve it. Which if true it basically says that there's nothing new to solve in the realm of CS. I don't think lots of people would agree with that.

Let's remember Finagle's Law. :)
For every simple and effective Plan A you have, you may end up going through Plans B up to F when that plan meets reality.
Likewise, that there is an SDK, book, guide or implementation does not mean we have it on hand - or that we have time to obtain it.

In a practical scenario, I'd implement the bisection method as a temporary stopgap solution, leaving myself a note to redo it properly when I have access to my precious reference materials.

Cbuttius2012-09-21 08:38

Sam I am:

It's as though everyone expects you to be given actual problems from production when you go to an interview.

For which the answer should be "if you want me to solve your production issues you have to hire me first, or at least pay me a one-off consultancy fee of £500 (or whatever)".

katastrofa2012-09-21 08:59

snoofle failed the interview and made an idiot of himself. The interviewer was clearly trying to check if snoofle knows about Newton's root finding algorithm. This is basic stuff which every programmer who's ever worked with numerical code should know.

There were many ways to handle this situation with dignity:

1. describe the root finding algo snoofle would have used to solve the equation x*x = y for given y
2. answer "I'm sorry, I don't know much about numerical programming"
3. if 2. would be false, attempt 1. but fail, and consider this a lesson learned

This was a valid question and I think snoofle's interviewer showed him much patience as things were.

no laughing matter2012-09-21 09:32

qbolec:

So many of you are missing the beauty of binary search which lays preceisly in the fact that it does not require you to know anything more about the function than if its argument is too large.
...
Please, skip "trwtf is php" and "a man with a hammer sees only nails" comments, and admit it: the real wtf is not knowing binary search (...)

Three points:
1.) TRWTF is PHP
2.) A man with a hammer sees only nails.
3.) The real real WTF is not knowing the limits of your silver bullet: binary search works if you have a monotonic function.
sqrt(x) is monotonic when x >= 1.
However for non-monotonic functions a binary search will fail.

byobg2012-09-21 09:39

Just to pile on snoofle some more here...

I've gotten job offers out of interviews that were really, really easy, where I knew all the answers AND could come up with them in ten seconds. I've never taken one of those offers, though I certainly would if I had no other options and needed the paycheck - I'm not an idiot.

But if the interview was easy, then they don't KNOW I'm not an idiot. Which means that they don't know if my future co-workers or bosses were idiots when they hired THEM. Maybe they got really lucky, but idiots are really easy to find, especially at job interviews, so the odds aren't great.

And snoofle - leaving aside the whole issue of not figuring out the point of the question, even after many (admittedly coy & overly-"cute") hints - would you *really* drive to a bookstore and buy a book about square roots (that'd be some dry reading) rather than try to figure out your own solution? Even assuming a car parked nearby, no traffic, and no line at the checkout, that shouldn't be the fastest way to solve the problem.

There are all sorts of approaches to take to a "How would you solve this hypothetical problem?" question. Yours, repeatedly, was basically, "I'd look for somebody else's solution to it and copy that into my code and probably change some variable names until it compiled. That would be efficient, because I'd never have to waste time understanding the problem OR its solution." I've seen a depressingly large number of programmers who take that approach to their jobs, but few who actually admit to it in interviews.

qbolec2012-09-21 10:19

i assume you are joking based on the first two points, but i will answer anyway.
1. Sqrt is monotone in whole domain of no negative real numbers
2. One should apply binary search to the inverse of the function(in this case squaring) and not to the function itself (in this case square root). Although i will admit that function is monotone iff its inverse is as well.

no laughing matter2012-09-21 14:00

qbolec:

i assume you are joking based on the first two points, but i will answer anyway.
1. Sqrt is monotone in whole domain of no negative real numbers
2. One should apply binary search to the inverse of the function(in this case squaring) and not to the function itself (in this case square root). Although i will admit that function is monotone iff its inverse is as well.

1. I did not claim contrary.
2. Binary search is still the wrong tool if the function is not monotone.

Sam I am2012-09-21 14:18

no laughing matter:

Sam I am:

I'm disturbed by everyone suggesting that the square root problem is some sort of interview 2.0 question.

it is a numeric theory and algorithmic question, and the skills that you need to solve it can actually be very relevant to your job even if it might not seem so at first.

The skills to correctly solve it "in real life" are exactly the skills that have been shown by the author:

1.) Don't reinvent the wheel (badly). Know that it is a solved problem. Know what your platform provides.
2.) If your platform does not provide it, use a search engine to find out if it already has been solved by someone else (bonus points for knowing a good search term for this).
3.) If that still is insufficient, look up (scientific) literature about the problem. If others already have tackled the problem, chances are that they know about problems that you will run into with a "invent-it-myself-in-10-seconds" approach. (see sqrt(x) when x < 1)

Would you rather the interviewer spend the time to invent an unsolved unconventional question, what would really serve no additional benefit other than the fact that you don't get smarmy answers from people like snoofle and you?

Gabe2012-09-21 15:33

My guess was the interviewer was feeling the waters to see how he thinks through recursion. Interviewer won that one. NEXT!

Meep2012-09-22 23:07

katastrofa:

snoofle failed the interview and made an idiot of himself.

As he said, the interviewer was condescending. If you get a bad vibe from an interviewer or during any business deal, you have to trust your instincts.

Ides2012-09-23 01:41

The interviewer did learn how he *thought*: the guy told him all the steps he would go through, i.e. ask someone, go to a bookstore. After the interviewer learned this information he kept asking for the guy to solve the problem that the guy already explained how he would solve! Definite fail. The job wasn't a good fit -- walking away was probably short tempered, but definite time saver for them both!

Andrew Au2012-09-23 07:33

Can't help to comment on the last line. It was wrong.

In the square root case, the Newton iteration values will always be a upper bound to the root, to see why:

Let square root of y be z, and x is an upper estimate of it, we have

(x - z)^2 > 0
x^2 - 2xz + z^2 > 0
x^2 - 2xz + y > 0
x^2 + y > 2xz
x + y/x > 2z

Now we see the value of next iteration = (x+y/x)/2 > z and therefore is also another upper estimate of z.

That is critical because you can also compute a lower estimate of z by simply doing y/x and have an interval estimate of z - one can stop at any point the both estimate agree to the level of precision one is good enough.

qbolec2012-09-23 17:36

this is also a direct effect of covexity of f(x)=x^2

belzebub2012-09-25 06:15

I'm not so sure about that snoofle's interview. I can see what the interviewer was trying to do - find out how resourceful he is. Which is fine by me. Snoofle on the other hand proved that he is not willing to find solution by himself being proud that he is not "math wiz" (I really don't understand why people claim this so proudly).
I'll bet the interviewer would be happy even with a STUPID, SIMPLE, APPROXIMATED and SLOW solution (like computing squares of increasing numbers and comparing result with given number), but snoofle was too lazy to think.
Don't get me wrong, I do not thing that creating your own sqrt in java is important programmer's skill, I just think that while people who REFUSE to think may be good enough for some "generic" code monkey positions, they may not be good enough for position where you have to design and not just code.

Thomas2012-09-25 09:00

Trouble With Founders pretty much sums up Deep Space 9.

YourMoFoFriend2012-09-25 14:40

Snoofle isn't an idiot, he is an arrogant type that storms off an interview if he doesn't like the questions he is asked... or the attitude of an interviewer... or something else that triggers his red flag. Whatever. Never mind that he might be interviewed by someone who is:
- new,
- young,
- inexperienced,
- wants something other than a canned answer,
- want's a canned answer,
- is not going to be working on his team at all,
- will be working in his team and wants to see how he does under stress,
- does not represent the company at all,
any combination of above plus a gazillion other reasons this situation could've come up... who cares, snoofle already knows that this job is not for him, so he walks out. Good for him, good for the company he walked out on. It's a win-win, as far as I am concerned, in fact I think these kinds of questions should be used more often if nothing else just to weed out the snoofle types of people because from what I've read in the post and in the comments it doesn't look like he is a pleasant person to be working with, especially under pressure... of course I could be wrong, that is just an impression I got from reading this thread.

Narpas2012-09-25 18:04

Regarding "What's the Square Root of Stupid?"

Most people don't really know how to do this, obviously. The interviewer might want somebody who's willing to take an earnest crack at something that they're pretty sure is impossible. Or maybe the interviewer's looking for somebody who is humble enough to say, "Unfortunately, I don't really have a good idea on that."

If I were the interviewer, I'd keep that question on the list to weed out people who couldn't accept that their job might push them past their reasonable limits.

Besides, I don't think it's that hard. "First, we're going to find the two integers that the square root is between. Let's take an example of sqrt(30). We can iterate though integers to find this, although if we weren't in an interview I might think of a better way of getting these. 1 goes to 1, 2 goes to 4, 3 goes to 9, 4 goes to sixteen, 5 goes to 20. Then, we'll iterate though 4.1 to 4.9 to determine the next digit. 4.4^2 is 19.36, 4.5^2 is 20.25. Then, we repeat the process to the desired precision. Eventually, we'd get 4.472."

There. I just answered the damn interview question in less than five minutes.

Narpas2012-09-25 18:28

To anybody who reads my last comment, I've never commented on TDWTF before, and I am just now learning that the two "Featured Comments" are not the entire comment chain. XD

I still think storming out of an interview over a bad question might be a self-damaging habit. Having a mediocre job offer is better than having no job offer.

me2012-09-26 18:11

me myself and I:

John:

Hey, where can I get a computer like yours, that can represent sqrt(2) exactly?

Your computer can already represent that perfectly.

√2

See, that was not soo difficult, or was it?

that is presentation not representation. The computer see's that as (U+221A) '2'. It can't use that value in a computation nor would it present it as the result of one, it will always present 1.141..

Buddy2012-09-27 04:05

From way back!

double sqrt(double d)
{
int n, invert, exponent;
double working;

/* Handle bad input */
if (d < 0.0) return -HUGE_VAL;

/* Handle 0.0 case */
if (d == 0.0) return d;

/* Invert any input less than 1.0 */
invert = (d < 1.0);
if (invert) d = 1.0 / d;

/*
* Normalize the input to 1.0 <= d < 2.0 by splitting it into a
* mantissa and exponent.
*/
d = frexp(d, &exponent);

/* Save the mantissa */
working = d;

/* Do a first approximation */
d = (d + 1.0) / 2.0;

/* Iterate using Newton's method */
for (n = 0; n < 4; n++)
{
d += working / d;
d /= 2.0;
}

/* Correct for odd exponents */
if (exponent & 1) d *= 1.414213562373095049;

/* Recombine the comp1.0nts */
d = ldexp(d, exponent / 2);

/* Invert if required */
if (invert) d = 1.0 / d;

return d;
}

Bubblicious2012-09-27 08:08

DES:

You're cute. And also an idiot—unless you intentionally misunderstood the point of the interview question.

Regardless of your talent or ability, I would have failed you based on your people skills. After reading your responses, it's increasingly apparent you're unable to get along with your peers.

You could be the 2nd coming of Sir Isaac Newton, but I would not recommend hiring you. You would only manage to piss off all our coworkers, clients, and customers. You would alienate our team within our company and make our work much more difficult to accomplish.

I think the only work environment suitable for you is a solitary office in Antarctica where your nearest coworker is several thousand miles away. Not to worry though. You'll receive drop shipments of supplies on the first day of every month. You can upload your completed work via file transfer over HAM radio.

Dave the Snave2012-09-27 08:20

Come on, the interviewer was trying to see how the candidate would react to difficult situations. Clearly the candidate on this occasion was a quitter.

Cbuttius2012-09-27 14:19

[quote user="no laughing matter sqrt(x) is monotonic when x >= 1.
However for non-monotonic functions a binary search will fail.[/quote]

I will fail you on two points.

Firstly sqrt is monotonic even for x < 1. It is strictly increasing as f(x) > f(y) whenver x > y. It doesn't matter that, below 1, sqrt(x) > x.

Incidentally, the derivative of sqrt(x) = 0.5/sqrt(x) which is always > 0 and therefore we know it is monotonic for x > 0.

The second point I will fail you on is that binary search will not work on a non-monotonic function. If you have two values a and b, and your function is continuous at all points between a and b, and f(a) < y and f(b) > y then there must be at least one point x between a and b such that f(x)=y. There might be more than one but there always must be at least one.

binary search won't work if you have two start points a and b such that f(a) and f(b) are both > y even if there happens to be a solution in between so if y is a (local) minima (or local maxima) there is no way to find it with binary search. Newton Raphson will possibly get you there, secant will also fail.

The point is that, when you take the halfway point between and b, you will either have hit a solution or you will still have a pair of values that wrap your target (a and (a+b)/2 or (a+b)/2 and b) even if your y-range is now bigger than it was before.

Cbuttius2012-09-27 14:21

Narpas:

Regarding "What's the Square Root of Stupid?"

throw std::invalid_argument( \""Stupid\"" is not valid input for square root );

Warbo2012-09-28 05:20

@snoofle

They were probably waiting to hear "Newton-Raphson iteration, with d(sqrt)/dx = 2x". My guess is they were testing whether you went to high school. Looks like you failed...

Buddy2012-09-28 18:21

Warbo:

@snoofle

They were probably waiting to hear "Newton-Raphson iteration, with d(sqrt)/dx = 2x". My guess is they were testing whether you went to high school. Looks like you failed...

They would like to hear things like this:

* handling < 0
* handling 0
* normalizing for < 1
* simplifying the problem to 1 <= x < 2 by removing the exponent
* getting a first approximation
* using Newton's on x
* divide the exponent by two
* put the exponent back in
* correct for odd exponents
* undo any normalization for < 1

This is a complete procedure for the square root function in the real domain. Say stuff like this and they'll be impressed.

Mark Wilden2012-09-29 18:03

I would've gone back and forth with snoofle for a while, up until the point where it was obvious he wasn't interested in 1) writing a square root function (it's not rocket science), or 2) answering the question the interviewer was actually asking.

bob_long_nose2012-10-01 18:32

Spewin Coffee:

I disagree. Taking resources away from programmers for trivial tasks is a serious insult to the programmer if they've been writing software long enough. Also, interviews are two-way streets: You are evaluating them as much as they are evaluating you.

For programmers who have been writing software for more than 10 years, find a different avenue of evaluation such as looking at the source code they've published and systems they have built. I don't know who snoofle is, but I like his attitude toward this ridiculous question. Frankly, snoofle should have identified the "I'm going to restrict you to the exact answer I have in front of me" question sooner and walked away sooner. I certainly would. Then again, I would also hand the interviewer my business card and say something like, "Keep this card. When you are tired of hiring people who don't know how to actually write software, call me. I'll train your employees how to select and interview programmers and weed out the garbage from the good ones as well as train you on how to keep good programmers around. Programming jobs are different from most other jobs. My consulting rate is $200/hr, but well worth the cost."

The correct answer would have been "I probably couldn't do it." r "I could come up with something but it wouldn't be pretty, brute force for example."

Wyrd2012-10-09 20:58

Leaving was definitely the right move. I don't know exactly what that interviewer's game was, But he struck me as highly manipulative. Especially that stupid "we're not through yet" crap at the end.

It seems like he was just trying to establish dominance by making you feel weak. With that kind of attitude what kind of programmers do you suppose he's able to retain? Certainly no one good. just a bunch of people who are trying to say "yes you're right, sir" all the time. And then that interviewer guy will wonder why they can't hire a good programmer and blame the programmers.

--
Furry cows moo and decompress.

Wyrd2012-10-09 21:08

Please tell me how to write sqrt(). And remember don't use Google. If you don't have the formula already memerized at the time that you read this, then I'm gonna have to count that as a fail.

--
Furry cows moo and decompress.

The Business man's view2012-10-11 03:14

So I've interviewed countless people, managed various types in various settings, and the game game works the same EXCEPT when it comes to computer people.

If a non-tech person shows up for an interview, they do their best to impress. When a tech person shows up, they all have entitlement issues and think they are infallible.

The normal procedure goes along the lines of the candidate trying to impress the interviewer and making them feel like this person belongs on the team.

The normal procedure when hiring a tech guy is trying to impress them and convince them they belong on the team.

This stuff takes time to get used to. Tech people are dangerous, because they control you assess and your access to them. But because there is such demand for skilled PC guys, they have the upper hand. Most of them seem to think they are better than what they actually are however.

MadCow422012-10-11 15:05

or the other option...

"I'd reach down, grab a pile of poop and throw it at the bear."

"What if there were no poop?"

"Oh, there would be by this point..."

gumby2012-10-16 13:00

"What if there were no one to ask?"

Ummm.... I appreciate the idea of seeing how someone thinks and can deconstruct a problem, but at some point, there *has* to be someone to ask - the client/manager/customer/user/someone.

If there's no one to ask, there's no one to verify if it's right or not, so I'll just return 0 or null and move on.

Captain (Ab)Surd2012-11-26 12:37

I agree. I would've calmed the submitter down and given him the problem again as finding the f^(-1)(x) where we had a black box for computing f(x). Then tell him that f(x) was in fact x^2 and he's solved my square root problem after all and watch his head explode. Then tell him to GTFO obviously.

CFO Idiot2012-11-28 09:56

How about this awesome code (written by a CFO):

public static double findTheGoddamnSqrt(double num) {
int godamnAnswer = 0;
while (++godamnAnswer * godamnAnswer != num);
return godamnAnswer;
}

Concise and to the point and wastes a lot of time like the stupid question

Verbok-52013-02-25 13:11

Ya, well - depending on how clever he wants this programmer to be , determines the appropriateness of the question. As for the Zombie apocolypse , that is a non-real event and a non-real 'number'... [Lolz]

Simon2013-08-06 06:22

(In response to the square root of stupid)

M: I'd approximate the number one digit at a time.
I: What if you couldn't do that?
M: I'd, uh... guess randomly?
I: What if you had no random number generator?
M: I'd weep and cry out.
I: What if... you had no mouth?

itu2014-05-23 22:50

If your story is true you were really really rude and stuck up for no reason. Every computer science freshman should have an idea of how to successively approximate a function to arbitrary precision, at least with methods as inefficient as binary search.

However your "you might approximate but you won't get it exact" thing shows you know nothing about what that means.

The problem is hardly unrealistic. It's a trivial function everyone knows about and the question tests very simple computing ability.

if (x >= 1)
while (val*val > x)
val = val - $eps
end
else
while (val*val < x)
val = val + $eps
end
end

return val
end

This is basically as exact as your computer can handle (accurate to a step maybe). It will take forever to calculate a single value, but will work nonetheless.

All I'm thinking is about how the dreamer will chase the coder around the moons of Nibia...

What? There was a nebula involved during that, and that's the cloud.....

Then again, if you don't have access to the internet, don't have anyone to ask and there's no other source of information around...

... then it's most likely the time of the Zombie Apocalypse, in which case I'd ask myself as to why in the seven frozen hells I'd need to calculate the square root of two.

Some smart guy once said: “I don't need to know everything, I just need to know where to find it, when I need it”

If I asked you to come up with a formula for something you honestly didn't know how to calculate, you might approximate, but you won't get it exact.

Asking someone to solve a problem using the most creative,original or complicated solution is clearly the best way to hire programmers who will create the worst thing possible to solve everyday problems.

Leaving the interview is clearly the best approach to that kind of question, your clearly don't want to work with people who answer "correctly"

He: So, imagine our data center in London goes down, what are you going to do?

Me: We hopefully automatically fall over to NYC.

He: What if NYC also goes down?

Me: We hopefully automatically fall over to Tokyo.

He: What if Tokyo also goes down?

Me: I will go to the nearest supermarket, grab all the cans of food and drinks I can get and drive up North as fast as I can.

I know no formula for square root calculation, but I'd suggest some variation of binary search for instance. Take (a+b)/2, check it's square, if it's bigger than x then a:=(a+b)/2 else b:=(a+b)/2, repeat until you have the required precision.

This probably sucks in terms of speed, but hey, at least it works.

I'd ask you as you obviously seem to know all the answers...

captcha : secundum (but not fristum...)

Just to remind you, there's no such thing as "exact" with floating point numbers. So they didn't ask him to give "exact" value. They asked to do his best at approximation.

It's funny how it's always Carmack's approximation, when in fact it was done by someone else at SGI. I wonder if that guy did it in 640k of RAM?

2. Successive approximation WILL give you an exact value. You just repeat it until it converges. You know when it has converged because either square(x)==y or square(x)<y && square(Math.nextAfter(x))>y .

3. The problem is that the interviewer didn't portray it very well as a brainteaser and/or mathematical aptitude type question. If he'd started out by asking, "How would you calculate a floating-point square root without using the library function? (or the whole math library, depending on how easy you want to make the problem)", hopefully you wouldn't have given silly answers like, "ask someone".

Calculating a square root isn't something where you either know it or you don't. If you ask someone the arguments to an API function, they have to either know it, say they don't know, or walk out or whatever. For a square root, there are a large number of solutions of varying degrees of quality. Obviously it is not a hugely relevant question for upgrading a legacy system, but neither is asking how many golf balls would fill the Washington Monument or something. Giving up a feasible problem without attempting it is not going to help your job prospects.

This morning I commuted to work on this new thing called THE GRID. It's a nationwide network of interconnected asphalt lanes - it really is the future of personal and commercial transportation. We have an IPO coming up if you're interested...?

After that interview, I had time to think about it and I came up with:

Start squaring numbers from 1 up until you exceed the target value, then back up one, and start incrementing the next smaller digit (1's, then tenths, then hundredths, etc) until you arrive at the required precision. Big deal; I can come up with a crappy algorithm for calculating something for which there are known formulas. I make no claims of being a mathematician. nor would I even want a job where I was responsible for coming up with such formulas.

A more sensible question might be to ask me: we've got A amount of data, B amount of storage, C transaction rate and D throughput. There is a problem xxx. How would you diagnose this? What are the likely causes and possible solutions?

That tells the interviewer how I think in terms of things

pertinent to the job.That's easy!

Hey, where can I get a computer like yours, that can represent sqrt(2) exactly? I could really use a computer with infinite-precision reals.

Without commenting on the value of the question for the interview, the above is simply wrong, at least for square root. Your approximation function should either find the exact value (what's the square root of 25?) or there IS no exact value (what's the square root of 2?) and it should be able to calculate it to any desired precision.

pertinent to the job.[/quote]Do you walk out of interviews whenever posed any problem to solve that's not directly pertinent to your job?

This should be considered a good example of precisely why you don't do things like this yourself. The square root of x for small x is much larger than x. The quick return is not needed for non-negative numbers, and if it were, the boundary would be EPSILON * EPSILON. (And no, the square root of -1.0 is NOT even close to 0.0.)

Yes, my degrees are in mathematics, and I did floating point validation in the '90s. Seriously, don't try this at home, kids.

(The way that we actually compute floating point square roots is fun. We look up the first several digits for the inverse square root, and then refine it based on polynomials designed to cancel the error term, usually quadratically. Once there is enough precision, you multiply back the original value to get the square root. Yes, you want a real proof that the algorithm works.)

I think Snoofle was right - the employer was totally wasting his time, and did a great job of letting Snoofle know that that was totally the wrong place to be, let alone work. The place next door that lets developers use Internet is a vast improvement!

The way I read it, he "pimped up" his CV and was trying to cheat his way through the interview. When he learned there'd be a technical test, he was "not prepared for" cheating it, so he made up a lame excuse to leave.

I'd probably also fail any candidate who didn't, at some point, suggest Math.exp(Math.log(x) / 2). And even if Math.log() isn't available, you can easily compute a rough lower bound of log(x) through successive division, as an initial guess for successive approximation.

(to those who complained that Newton's method does not give an exact value: where does it say that the interviewer expected an exact value? in any case, with a few exceptions, the floating-point representation of a number will always be an approximation of the actual value.)

As for Carmack's method: assuming it can be implemented in Java (it can't—not without a lot of contortions), it can easily be derived from first principles if you know basic algebra and the layout of IEEE 754 floating-point numbers. If you don't know the layout, you can easily figure it out by looking at the binary representation of a handful of test values.

So TRWTF is that the candidate refused to even try to think of an answer, then blamed the interviewer for asking him a question he should have been able to answer but wasn't.

And What if you can't use addition?

(It's a flipping adding machine!!!)

{

double ret;

while (true)

{

ret = rand() * double.Max;

if (double.Equals(ret,val))

return ret;

}

}

He never said he wanted it quick

A pro goes to the language libraries first, the in-house code base second, the world of pre-written solutions third, then asks "has anyone else poured some thought into this problem" before inventing his own wheel.

Snoofle, I think you bailed 5 seconds early. Based on your answers I would have been offering you a job in the next breath.

Fail. You can't get it exact because square roots are (in all cases except when all the prime factors are to an even power) irrational.

Granted that you may not be able to come up with: guess, divide your number by that guess, take mean of result with guess, and repeat, IMO it's something that you might be expected to be able to work out.

Depends on whether your expertise is borne of a lot of experience or a combination of that and the ability to figger things out from scratch. Fair enough, though, it certainly appears that you and your prospective employer would not have been a good match.

orMath.log. Some programming jobs aren't about math, despite what your Computer Science teacher told you. And I'm talking real code, not drag-and-drop crap.Hell, half the stuff I see CS grads crank out barely works. But I suppose it's mathematically sound, so there's that.

I think it was poorly posed, but it's a legitimate question. If I started off the way snoofle's interviewer did, after the "Google" response I would have said something like: "Of course, we would never want a programmer to try to implement their own square root. However, as an interview puzzle, I'd like to know how you'd calculate a square root without the library." Hopefully that would rule out answers like, "buy a book".

2. Successive approximation WILL give you an exact value.

That's impossible.

Most square root functions return an irrational number, i.e.: their digits repeat endlessly without a recurring pattern. There is no representation for the number in a digit-based system.

But I totally forgot how it went, so I probably would have failed that interview too.

P.S. Why can't I copy/paste the CAPTCHA?

Interviewer: I want to see how you think.

Me: I think I want to work somewhere that is evaluating me for my technical skills, not my game show skills.

Unless Apple is now shuffling their Siri searches off to Deep Blue, maybe you should not refer to a wrapper around a voice to text system + search engine as "one of the most advanced data analytics programs"

And the point is that if the interviewer is that bad at asking questions, it probably indicates a general level of WTFery at the company. "What if there were no bookstores?" Then society has fallen apart and I have more important things to do than your silly square roots. Leaving was the correct answer.

As you can see in the portion of my point 2 that you omitted, I didn't really mean "exact", but rather "as exact as representable". More generally, I meant, "you can do just as good as Math.sqrt with successive approximation".

Interviewing is a totally different skill from actually doing the job and I would have stayed for the practice.

Yet another case where I would shine in an interview, possibly even convincing the company to undergo an organizational switch to a real programming language in the process.

If you are trying to program your way out of a zombie apocalypse, you probably have a heck of a lot of code to write, and you'd better get it done NOW NOW NOW!

Plus you might not want to venture outside to go the bookstore.

This needlessly excludes simple programming questions that happen to have a library function. Years ago, I had an interviewer ask me something like, "You have a string of words separated by spaces. How do you reverse the order of the words in-place?" I didn't say, "What kind of crazy person would do that in-place in production code? That's grossly premature optimization. Also, you'd have to be a terrible programmer not to just use split() and reverse(). We haven't even considered localization issues with the whitespace characters!" I answered the damn question.

How can you possibly answer interview questions if you treat them like production code? It's a bizarre standard, but suddenly everyone pulls it out because some guy was asked how he'd implement a library function.

I found out much later that I knew someone in another department at that company, and walking away from this person (interviewer) was absolutely the right thing to do.

Bookstore is one of the places you want to go in an apocalypse. It's not a priority but with no internet it'll be pretty useful in the longterm to get books on basic medicine and electronics, etc.

Please show me how to use those built-in instructions in a Java program.

he should have bloody askedand not come up with some Interview 2.0 rubbish that he clearly didn't understand himself.None of my computer science teachers ever told me that programming was about math. Where did you get that idea? However, I'd expect candidates to have at least completed high school.

BTW, “I've been programming for 30 years” doesn't impress me. I've worked with people with as much experience as you or more who were still totally incompetent.

Your computer can already represent that perfectly.

√2

See, that was not soo difficult, or was it?

I'd love to see his take on the Kobiyashi Maru.

("Interview 2.0"? Problems like that have been a standard part of technical interviews for decades.)

In my experience, being completely unable to handle this kind of problem without using a library function is not something I'd like to see in my fellow team members.

Yeah, you don't want to piss of sqrt(2). He's been working out. Stomach crunches mostly. His physique is completely ab-surd.

Rage?Yes, Interview 2.0 questions have been around for a long time; but they've been mostly pointless for a long time too.

I have found, mostly through sheer repetition, that certain things done by interviewers during an interview are (at least in my case) pretty good indicators that I don't want the job. I used to try my darnedest to answer such questions, only to get the job and realize I should have run away. After a while, you just learn to recognize the clues.

Does it apply in every situation? Of course not. Are there times when I will try and answer such questions? That depends on how they are framed.

But just because you're in an interview doesn't mean you should put up with pointlessness. It wastes your time, tells you a great deal about the interviewer and possibly what the job would be like were you to accidentally get it. It's not an absolute rule, but at least in my own experience, is

usuallya reasonably reliable indicator.It's also amazing how differently people perceive the same interaction.

Last time I was on the interview trail, a person asked how to reverse the characters in a string (C#, asp.net). I suggested using String.reverse.

"Well, what if that wasn't available?"...We then talked a bit about creating a method to do so, null-checking, what's their requirements for a cases like that or empty string. I may have even mentioned extension methods to avoid the null problem.

Anyway, I got home, called the recruiter and said that I didn't think it had gone very well, as the interview just kind of ended after that.

Twenty minutes later, she called back and said they loved me, asking if I had time that afternoon to meet with the VP-type guy for a final interview.

Strange how I thought that part went really badly, and they thought it went well, apparently. Never thought that they might be going for, "does this guy not reinvent the wheel?" until I saw snoofle++'s answer.

There's your problem...

Interviews can't have questions that require more than 10ish seconds of thought?

Come one, the first port of call for any mathematical problem is most definitely the Quake code. It's all in there.

BTW, I imagine the dialog would have continued like this:

Me: I'd try to remember or work out Newton's formula.

Interviewer: Assume Newton was never born.

Me: Then we wouldn't be here.

That could get interesting, what if this turned into something more? Would Siri go out on a date with it?

No, they were able to ask an expensive consultant ;-)

Well, maybe something along the lines of "approximation" would have been good enough for an answer. Just walking away is a sign of a short-tempered personality, you should work on it.

Sorry, Jeff, but we have some lovely parting gifts for you!

Usually, the walking-away is in response to more than one warning sign. This was just the last bit of pointlessness I was willing to tolerate. The previous questions all caused alarms.

As I said earlier, it turned out that my PHB-radar was dead-on with this guy.

Besides, if I had taken

thatjob, I wouldn't be working HERE!"Hey, Jim, what would you do if you were in the forest and you met a bear?"

"I'd back away slowly."

"But it's mad, it attacks you!"

"I shoot it."

"You don't have a gun!"

"I run away."

"It runs faster than you!"

"I climb a tree."

"It climbs better than you!"

"I jump in the river."

"It swims faster than you!!"

"Listen, Mike, whose side are you on, mine or the bear's?"

And the punchline variation:

"I'd hide."

"It's much better than you at hiding and you'll never find it again!"

Au contraire: some of us are *proud* of the fact that we do not suffer fools gladly. Sometimes this can hurt a fools feelings. Isnt life tragic?

And the other punchline variation:

"Id pick up a handful of shit and fling it at the bear."

"What if there is no shit?"

"There will be!"

I had a similar experience when interviewing for a job after graduation.

At school we'd learned to use those automated design tools with round-trip code generation. Rational Rose being the prime example.

In the job interview, they asked me what I thought about tools like that. I had listed it on my resume, and they used it within the company.

So I was honest. I told them I didn't think they were very practical beyond "toy" scale projects. They were great for academia but I didn't feel they would be useful beyond a very general design session. Often you realize mid-way through coding that the design you drew out just isn't going to work, and you need to redo things. Change method names, change class relationships. Trying to "round trip" between the design tool and your code IDE would take too long. Better to hash out the broad-strokes design in the tool, then code and test, and then when things are relatively stable, reverse-engineer from the code to generate your final UML diagrams for the documentation.

I was bracing for the worst, but everyone in the room was smiling. Apparently I had just described their exact frustrations with the new processes being pushed down from upper management. They were impressed that my answer was realistic, well-reasoned, that I didn't completely trash-talk the tool or its usefulness, nor did I unrealistically embrace it.

I got the job!

If that's his best about explaining the requirements, I cannoy imagine what kinf of hell he makes for others when he's workign with a real project.

What if there were no power function?

Interviewer: If you had to put two pieces of wood together, how would you do it?

Carpenter: I guess I could nail them together, or maybe glue.

I: But what if you didn't have any nails or glue?

C: I'd go out to Home-O-Rama and buy some.

I: But what if there was no Home-O-Rama?

C: Then I'd go to a hardware store.

I: But what if there were no such thing as nails or glue? How would you make them?

C: Can I have some of what you're smoking?

Yeah, maybe he could have come up with a different question, but using square root as the subject was like asking a carpenter how he would make nails if they hadn't been invented yet.

Besides, how many of you even use square roots in your day-to-day work? I've been programming for decades and never had to do something that used square roots.

This series converges on sqrt(x).

If that doesn't shut him up, leave.

Isn't the answer $10 per window. If it's good enough for Google...

More import would be an attempt to see if you write proper Englishes.

How would you code that if there were no library functions? No google? No books?

No electricity

Imagine all the people

Banging rocks together

You may say that I'm a cultist

But I'm not the only one

I hope someday you'll join us

And the world will die as one!

A square root is easy to calculate, if you know anything at all about any of the standard algorithms you should have learned in college.

In fact, the algorithm is a simple game of "guess the number," and if you can't write a "guess the number" algorithm in less than 5 minutes, you should be coding CSS templates for cybersquatters, not developing enterprise software.

If you can't think on your feet enough to answer a question like that, perhaps you really are not the man for the job.

Since “maths” is the correct idiom in British English, it is arguably more correct than “math”.

I'd be impressed if you came up with a square root function that returns exact values. Feel free to use any reference you like.

If you ever, for any reason, find yourself in a situation where you your developers need to do complicated approximations of floating-point numbers, and you value their willingness to turn to a vaguely-recalled Newton's method

as their first step, you have failed so completely that I can only hope that you aren't writing code for any crucial features of my life.You write that in the language of your choice and then make a CORBA call in your Java.

Maybe; it's not that hard so long as you know how to work out the area of a rectangle.

The interview question sounds to me like one which would be fine for a job where you're likely to come across some mildly complicated mathematics, and the answer suggests that snoofle would not be comfortable with that.

Not sure why such a successful interview question found its way onto this site, though.

Yes, this isn't about finding a square root, it's about exploring how you'll go about finding a solution. By all means mention that it's a solved problem, but then go on to having a go at it.

It's been really sad to read this thread. It gives me the impression that many programmers don't what their library functions actually do, or why the patterns they've memorized work.

Ummm, you failed math class too, eh? For all but a trivial set of numbers, there is no exact, closed-form solution to sqrt(x).

You're cute. And also an idiot—unless you

intentionallymisunderstood the point of the interview question.Come to think of it, you're an idiot either way.

FWIW, I've worked with various SOLAS equipment vendors. If I told you even half of the stuff I've seen, you'd never set foot on an ocean-going ship again.

Begging your pardon, but free of context there's no reason for the reader to conclude any of that. If you were interviewing to be a code monkey, then clearly a problem-solving question is a waste of yours and the interviewer's time, but the post provided no context. Free of context it's a natural assumption on the part of the reader that a problem-solving question was pertinent to the job.* The archetypal problem solving question asks the interviewee to solve a standard problem ab initio.

*"I went to an interview, and this guy asked me what programming languages I knew! WTF?!"

-beat-

"Wait, did I mention it was for Burger King?"

It's an interview, not a date. If you need time to think about your response, you can ask for it instead of sitting mutely. Heck, most places will let you go to town on their whiteboard while you figure out a problem.

I'm fully willing to admit that, in many cases, I don't, and I'm completely fine with that. Would it help me to know them? In some cases, yes, and in those cases (where the API isn't perfect and I have to know why, in what cases, and how to fix it), I do try to know. But should I remember every random bit of mathematical trivia I've needed to use once or twice, just to impress people with my smartness? I can't think why.

Unlike taking a square root, my job

doesinvolve some manipulation of pdfs - and I generally trust that our pdf library works without needing to know exactly what it does. Except when it fails, in which case, at that point, I look into why it's failing (which requires learning more about its code, and often the pdf specification, which is enormous.)If I had to work out how to approximate a sqrt by myself, I could probably do that. If I had to tell someone

right nowhow to approximate a sqrt, I wouldn't be able to. I don't think I even ever learned it, but there's a lot of math Ihavelearned and then completely forgot because I haven't used it for anything in like 7 years - I took a semester of Linear Algebra, a semester of MultiVs and a semester of DEs, but I'm not an engineer and I don't do 3d graphics, so what good did that do me after I graduated? (And stuff I learned in high school, other than basic algebra withdoescome up daily in really any kind of programming, would have been forgotten even longer ago. Sad, but true.)Use Newton Raphson's method for finding roots of x**2-n=0

Somewhere I should have some old 8080 assembly handy for that....if fixed point arithmetic is ok.

For the cyclist? Well I wouldn't want the interview to be proceeded by a programming test either... preceded I could live with.

If you were a math wiz, of course, then there are two solutions I know of, one using a specific algorithm I won't describe now, the other involving manipulating exponents and logarithms.

BUT! If you asked, instead, what the tolerance was (only perfect squares have rational results, so no tolerance means no solution), you could use a binary search to find a square root that falls within it. This is the approach I would have used.

The point is NOT to reinvent the wheel, nor to encourage NIH behavior.

The point is to see how a candidate thinks. How they handle edge cases. How they respond when flaws are pointed out in their code.

I would expect a binary-search solution for anyone without a strong math background (there are algorithms for calculating square root, but I don't expect a candidate to know them offhand). As you've pointed out, there are problems with the first-pass implementation. When you point them out (what about negative numbers? What about numbers between 0 and 1?), you learn a lot about the candidate. How they respond to criticism of their code, how they would approach fixing their code to work, etc.

Again, the point is NOT to implement a production system in an interview. That would be silly, it's an interview. The point is to see how a candidate thinks and adapts.

The candidate was unnecessarily rude an obnoxious. I wouldn't want an arrogant jerk like that.

That said, the Interviewer should have approached it better, and simply said "We'd like you to implement a sqrt() function".

You're not asked these questions to demonstrate that you know the answer! You're asked them to show that you can *think*!

Okay, sure, some people don't want to do that kind of work, but don't expect a pat on the back for taking the attitude of "I don't know the answer, therefore the question is stupid". That attitude will get you doing grunt work for the rest of your life.

For the math Nerds (I don't have much time to elaborate):

while (x%2 == 0)

{y =* x/2;}

while (x%3 == 0)

{y =* x/3;}

...

continue loops using prime numbers until you are happy...

...

repeat until you are at a high enough prime number to be happy.

you answer will be y sqrt(x), with x being a prime number.

ps... this is what I remember from high school so I may be wrong.

Step 2: ?

Step 3: Profit

The interviewer was probably looking for the guy to tell him out to write an iterative program that approaches the value with an error tolerance for when it was reached.

Where X is the original value

R' = (X + R / X) /2 Error= X - R'^2

While Error > some limit, let R = R', lather rinse repeat.

I'm sure there are good formulas out there and having access to google would help, but surely someone should be able to figure out a solution by taking convergent averages.

Knowing Newton's method, fully understanding Newton's method, being able to implement Newton's method... those are all things of limited value and more limited usefulness beyond very specific applications and positions. Even for specific positions working on specific applications which might make use of these concepts I wouldn't rule out a candidate just because he wasn't aware of them. Ideas can be taught and learned.

Before that question was asked, things were going fine. After that question was asked, the interviewer showed himself to be an idiot, plowing forward with his plan regardless of how stupid it sounded. In other words, pure PHB-ism. Since an interviewer is typically going to become your boss or co-worker, you had better be pretty damn desperate for employment to be subject yourself to months or years of that.

If he had laughed while asking that (telegraphing that he was joking), that would have been cool. But to seriously continue past a point where basic foundations of our civilization would have to fall apart first?

Feel free to fuck Akismet whenever you like.

pertinent to the job.[/quote]Do you walk out of interviews whenever posed any problem to solve that's not directly pertinent to your job?[/quote]Damn skippy! I get on my bicycle and go home!

Hell, you could have answered "I'd go in a loop and exhaustively check the square of every possible number and see which one is closest to the true root," and you would have technically solved the problem.

Maybe a lot of people don't know, off-hand, how to compute a square root, but what grade do they teach that in? 5th? 6th? Starting from *first principles*, i.e. the definition of what a "square root" is, you could have produced a solution by sheer brute force.

If you can't even do that, or can't be bothered to, why should anyone believe you can produce a solution to a novel problem for which there are no references already?

Math.sqrt() wont give you an

exactvalue either.If the candidate can't even blurt out binary search would be a really bad sign for me. That's somebody who knows nothing pf algorithms and only know how to combine library calls.

For programmers who have been writing software for more than 10 years, find a different avenue of evaluation such as looking at the source code they've published and systems they have built. I don't know who snoofle is, but I like his attitude toward this ridiculous question. Frankly, snoofle should have identified the "I'm going to restrict you to the exact answer I have in front of me" question sooner and walked away sooner. I certainly would. Then again, I would also hand the interviewer my business card and say something like, "Keep this card. When you are tired of hiring people who don't know how to actually write software, call me. I'll train your employees how to select and interview programmers and weed out the garbage from the good ones as well as train you on how to keep good programmers around. Programming jobs are different from most other jobs. My consulting rate is $200/hr, but well worth the cost."

Because, unless your job is -really- out there, the vast majority of problems that don't already have exact solutions, are still -related- to other problems that have solutions. So even if I knew there would be a novel solution required, I'd still want to see what other similar questions had been asked and answered before I started off on my own path. (And of course, sometimes you get lucky, and a problem you think is unique to you, actually isn't.)

Regardless, I feel like if you want an interviewee to answer a question with some other answer than "I'd implement this using an algorithm that I know exists on stackoverflow and/or a math textbook, but which I don't have memorized", you should ask a question whose exact answer is unlikely to exist on stackoverflow and/or a math textbook. (Even if it's related to one that is, you can still see how they think.)

It's no Newton-Rhapson, but I suspect it will work.

You weren't there and didn't hear this jerk and his condescending attitude. Yet you've made lots of assumptions about mine. Fascinating.

FWIW: I happen to be one of those folks who sometimes hears something and has a brain-software-glitch and gets flustered. I usually don't think quickly on my feet, so if thrown a question on something I don't happen to know, it takes me few minutes to reset. As I said above, I figured it out in a few minutes afterward.

For those of you who obviously missed it: I walked out because the guy was a jerk, not because of the question.

Not a WTF. His response of walking out, however, was.

Obviously it filters out anyone without the wit to even try successive approximation. But it <em>also</em> filters out those who know just enough about numerical programming to know that rolling your own numerical algorithms is a really bad idea, not because of efficiency but because of the vagaries of floating point numbers.

If you want sqrt for any scientific purpose, you <em>really</em> need to know what it does with the last digits of precision. You want <em>stable</em> behavior - you want the last sig fig to increment at the right rate relative to the argument. Successive approximation will not give you that stable behavior.

If I were desperate enough for the job, I'd have proceeded beyond that point to ask the interviewer <em>why</em> I needed a square root, try to find out if they actually cared about square roots or if it was just Interview 2.0 crap. Only once I was satisfied that the interviewer would be comfortable with any old square root would I do successive approximation (and my first approximation would come from "shift right until it's 1, then shift left half as many times").

How does having me re-implement standard library functions bring in revenue to this company?

You god damn geekass bastards.

verylong time since I wrote code on a whiteboard. Give me a computer (preferably one with all my stuff available and customizations loaded) andthenyou can test my ability to do my job.From what I've seen in this business, I can almost guarantee that is the quality work of a CS grad who is great at reimplementing basic math functions on the whiteboard during interviews.

For some types of programming jobs, you don't even need to know what a square root

is, much less how to calculate one."First I'd create a number wheel function that could instantly calculate the square root of a given number. Then I would throw away that wheel and create a new wheel that does the exact same thing. Repeat for each project."

Do you have any questions for us: "How would you compensate me for the work I do here?.... Yeah, but what if there were no checks?....What if there were no banks?....what if money hadn't been invented? Sorry, I'm not convinced you are prepared to pay me in a timely manner."

anda completely full-of-himself candidate who must have been willfully ignoring the clear hints that the development of a solution from scratch is nevertheless plainly what the interviewer wants to observe.That is what the article, as posted, describes. Whether the description in the article has any discernible relation to any real interview you or someone else has been in, is sort of beside the point.

When we hire developers, we expect them to be able to solve novel problems that are orders of magnitude more complex than approximating a square root. We

alsoexpect that they will need orders of magnitude more time than there's available in an interview to do so, however. So in order to get some kind of handle on how they'll handleactualproblems, we ask them to solve some toy problems that (by experience) can usually be solved within the available time.Good toy problems tend to be ones that have prepackaged solutions readily available, but it's not the solution the interviewer wants -- it's how the candidate

constructssolutions.A candidate who deliberately refuses to demonstrate his solution-construction skills during the interview is not one we'd want to hire.

Um, he was being judged on his prima donna attitude, his walking out on the interview, and his refusal to take a test. Nobody was judging him for his ability to find the place. In fact, he *did* find the place, he just left to never return. And the writer of the story noted how he understood why he looked lost.

surethey talked about that one day in third grade.No fair using the Internet. Or a map.

Anyway, if during an interview you're asked to code a math function, and that isn't the skill you're interested in marketing, it makes perfect sense to move along... either to the next question, or if they continue in the same vein, to the next job.

I'll second Nagesh's comment.

The description sounds like a perfectly normal interview, with a little normal confusion over the point of the question. The question itself represents the essence of the job: not everything you'll be required to develop has a cookbook solution ready for you to just look up, you'll have to conjure up your own solutions (imperfect but sufficient as they may be).

Yup, sometimes I'll glitch and get flustered too. Glitching and flustering on something which is perfectly normal for the job ("here's a simple but unsolved problem, go solve it") isn't a good sign; insofar as I've been known to do so at inopportune times is my problem, not the questioner's.

'tis good to develop the social skill of tactfully saying "your question is valid and I'm capable of answering it, but I'm suffering a brain fart right now - how 'bout we come back to this one." If you'd just redirected the discussion for a few minutes, you'd have given the answer. I had a notable case when interviewing at Microsoft years ago: given a comparable question and comparable "brain-software-glitch", I told the interviewer "I know I'm completely missing a simple solution that you're looking for, but I'm just gonna plow ahead with a line of reasoning and let's see where I end up." (Didn't get the job, but did seem in line as a final contender.) In another interview, I knew they'd pull the "write code on a whiteboard" line, so I brought a notebook computer, and explained "writing code on a whiteboard sucks and so does writing code while someone stares at me, so I'll just write it on this computer while you go ahead and ask me other questions and I multi-task". (Got an offer, but got a better offer elsewhere.) Learned to do those after completely blowing several otherwise successful interviews due to mental misfires.

The article says nothing about the guy being a jerk. The guy who walked out in response to a representative question typical of the work, well...

Heh yeah, I was pretty sure there was some glaring problem with it, but I also did try to come up with it as fast as possible.

That the interviewee knew of that solution is a good sign.

That the interviewer did not, it seems, know of that solution is a bad sign.

Of course programmers are not supposed to reinvent square root every time they need to calculate it. But somebody has to implement it in the first place. And whenever new platforms are put into use, there are some pieces of basic code that has to be written over again. So there is actually a need for people who can write those basic pieces of code again.

But that's not the point in asking such a question. The point surely was to test the candidates ability to write some code to solve a simple problem.

The interviewer learned three things about snoofle from that question:

1. He doesn't know any of the many possible algorithms to solve this problem.

2. He doesn't have the skills to derive an algorithm from scratch to solve a quite simple problem.

3. He displays a bad attitude when faced with a task he doesn't like.

Given how much the interviewer learned about the candidate from that one question, I think it was a great question.

'Intelligent', from the latin verb, roughly means 'he who understands'.

This means to answer a question intelligently, you should not just take the question and find an answer that matches it, but understand why it is asked, and what the interviewer is actually trying to learn.

"Use the language API function" is a great first answer to that question. From the follow-up questions, however, it should be fairly obvious that the interviewer wants to see how the interviewee approaches a problem independently.

sqrt is a fairly good example problem to test this with: the problem is easily and clearly defined and there's a couple of solutions anyone should be able to invent on-the-spot. In practice of course the problems you'll have to be able to independently solve are not sqrt, but domain-specific problems - however, explaining a foreign domain first would distract from the point of the excercise, hence a well-known problem like sqrt is better suited to test this ability. Even a 'wrong' answer can be an acceptable one, especially when you can refine it after getting feedback on it.

Inferring that because the interviewer asks this question, developers at this company will always be forbidden to use google or other reference material, is ludicrous and anyone who does this deserves unemployment.

Next time, be intelligent, and answer the question the interviewer is trying to ask, not the one he is actually asking.

even after the first couple "google it" responses, the interviewee should have gotten a clue by then.

"snoofle" didn't even appear to allow the interviewer to lead him a little bit.

If the interviewee wasn't referred to as "me" so many times, I'd think that he was the WTF

What if you're not allowed to use NAND gates? And no, wiring transistors up to form NAND gates is not allowed. You are, however, free to wire up transistors to form any other logic gate (except NAND), but the gate you choose is the only one you can use.

Submitted on the theory that the interviewer doesn't know "sensible algorithm" from beans anyway. Especially since I can show exact result for a cherry-picked input of, say, 64.

(Trust me to also carefully point out how elegant this one-liner is...)

Oh, BTW, haven't we seen this interviewer before? Right here in TDWTF?

Addendum (2012-09-19 20:57):Well, maybe. I think he's either interviewer or maybe the interviewee (not sure which) from "Riddled", A Most Wonderful Opportunity, Multiple Frustrations, and More.

I thought it sounded familiar.

I don't give a damn what he said - this the real WTF.

Clearly Anoldhacker, you were a Discrete Mathematician. All

REALMathematicians know root(x)=root(x) and that's the end of it. Just like pi = pi. None of this 3.1415... blasphemy.The whole point of a simplified toy examples is to allow to see the problem solving approach of candidates within a short interview.

Asking a carpenter how he would make a glueless joint for two pieces of wood is a natural question - it's not done in "production" nowadays since glue is usually simpler and sturdier, but any reasonable professional carpenter should either know or figure it out in 5 minutes.

Asking a programmer in how he would reimplement a simple function from scratch is a natural question - it's not commonly done in production, but any reasonable programmer should know or be able to figure it out in 5 minutes. Asking to build a more complex function than sqrt (one that wouldn't be in libraries) would simply require more time to see the same effect.

The exam showed: Candidate is able to reimplement well known techniques by looking up the details in a reference book or internet. Candidate is unable or unwilling to develop solutions independently even when requested to do so.

I have seen a couple of companies whose developers didn't have access to internet or books, so it is not unreasonable to infer that. Also, I remember one company where you couldn't use JOINs in stored procedures. There are many WTF companies out there.

English is not my native language, sorry for any mistakes.

Arethere any real programming languages without a square root function? I don't mean toy languages, I mean those in actual production use.I was thinking back over my programming history to see if I could spot one, and everything back to Applesoft Basic from the late 1970's on a 1 MHz 8-bit CPU had a square root implementation. Languages I learned later but which are older (C, Pascal, etc.) have had it from the beginning, too.

What I'm trying to get at is, is the interviewer's question anything more than an impossible hypothetical? Never mind that the context was Java. Is there even a snowball's chance someone would be required to do this?

Riffing on snowballs, here's a new hypothetical:

You're in Antarctica, a blizzard is blocking the satellite uplink to the Internet, and you have to fix a bug in an embedded system or Dooooom happens. The bug must be fixed in the next 2 hours, and the blizzard is expected to last another day. The embedded system is an 8-bit microcontroller with a toolchain you've never used before, but it uses a well-known programming language, and you have complete reference manuals for the toolchain and the language. You have no other reference material. It turns out that the bug fix requires a square root operation. The language entirely lacks what we'd call a math library today: so, no raising the number to a half power, no trickery with logarithms. You have to build the sqrt() implementation using nothing more than sixth-grade arithmetic.

Is that also an impossible hypothetical?

No multiplication? Multiplication "expensive"?

Use the "odd integer method" with proper scaling. I know of one computer system that did it that way.

Of course, you could always use n^(0.5) which also works.

If all else fails, try a slide rule!

Sure. A great many 8-bit CPUs (and microcontrollers) lack a hardware multiplier. High level languages for such systems typically provide a software multiplication implementation, but if it's general-purpose, its going to be hundreds of instructions long. If you're writing in assembly, you get to write (or swipe) the implementation yourself.

Even on systems with a hardware multiplier, multiplication may take many cycles, whereas an integer addition is typically the fastest sort of instruction.

You might not be aware of it, but there are still — today — more 8-bit CPUs sold than any other, by volume. There's even new code being written for 4-bit CPUs.

Here's such a CPU, still being sold, though Atmel recommends against using it in new designs. It's a 4-bit CPU with an instruction set optimized for a dialect of Forth. No hardware multiply instruction. The programming manual claims there is a software multiplier at the qForth level, but more reading suggests the only thing that actually works is

2*which is implemented in software as a shift-left operation.I guess this answers my question above, but I'd still appreciate more answers.

Sadly, most of you still seem to be missing the entire point, so let me illustrate...

Hypothetically, you are the interviewer, I am the candidate, and for the sake of argument, I am Mr. Math Wizard. You ask your question (in an intelligent way): We'd like to see how you think and go about problem solving; please explain how you might go about designing a method to compute a square root. As a shrewd interviewee, I ponder for a second, then respond with iterative approximation, perhaps mentioning some edge cases, negative numbers, numbers < 1, etc.

You probably think to yourself: Hey, this guy knows his stuff, and will probably use that as a significant portion of your hiring decision.

Epic Fail.

The only thing you have learned about me is if I can come up with a way to compute a square root. Unless the job entails figuring out new mathematical algorithms, or computing square roots, you have learned absolutely nothing about my ability to do the actual job.

It's actually worse than that, because you now have a false sense of positive security that I am a good fit. I may or may not actually be a good fit, but you don't know that based upon your question.

I, OTOH, know that you have chosen a question that fails to give you the sole piece of information it was designed to detect: Can I think?

In fact, that is not the complete question you wanted to answer. What you wanted to know was: Can he think in a way that helps him accomplish what we want to hire somebody to do?

A good question along those lines is: Our production environment looks like x. Every now and then, y happens with symptoms a, b and c. Given limited knowledge of the details, how might you go about diagnosing the problem and how might you proceed to solve it? This tells you whether I can think AND if I know how to do the job.

It's not that I have an attitude about answering questions; I get it; you have to play nice to get the job. It's just that I've learned over the decades that certain types of questions are red flags, and depending upon the tone/manner with which they are posed, I

mayplay along, or just accept it as a wasted trip and leave - because some jobs just aren't worth having.And I think that anyone who's wasting time to unnecessarily disassemble anything is a time waster and probably a bullshit programmer, too.

You're a heavy unit-test guy, aren't you?

I'll give you my salary for a month if you even copy it from another piece of paper in 10 seconds, let alone come up with even relatively accurate solution without anticipation or prior practice.

In other words, you're a dumbass.

No, dude - the interviewer is a plain old dumbass with no good intention at all. He simply couldn't think of any other good-quality question, so he thought of going down th what-if route. My child often does this to me, and the interviewer probably hasn't advanced much from that age.

I would not like to work for such a person either, because I would much rather work for someone who has the ability to make their expectations and needs clear.

It probably doesn't help matters that the first derivative of sqrt(x) contains a square root.

While yes, one can argue that the interviewer was almost certainly asking the person to describe how they would personally approach solving a new problem that they hadn't had to solve before, it would have probably been better if this particular question had been framed very differently, and the expectation that the interviewee should take some time to think about it had been clarified up front, instead of adding all these highly contrived "what ifs" after the question had already been posed, and an answer given.

I respectfully submit that you are also missing the point. I fall in the camp that thinks this is a reasonable interview question. I might consider using it in the future.

Your assumption that I would think "Hey, this guy knows his stuff, and will probably use that as a significant portion of your hiring decision" would be wrong. It's only 1 question. You don't know that the next question wouldn't have started with 'Our production environment looks like x...'. You judged the interviewer based on 1 question. I judge an interviewee based on answers to multiple questions.

I even like the approach the guy used of pulling the rug out from under you as you give the right answers. It's actually better than jumping straight to write a sqrt function from scratch.

Here's what would go through my mind as the interviewer in that scenario:

Interviewer: How would you calculate a square root (java)?

Me: Math.sqrt(double)

+5 for knowing the obvious solution without having to look it up.I: What if there were no square root function?

M: I'd Google for John Carmack's formula to calculate it.

+20 for being able to name an existing algorithm to solve the problem.+10 for knowing that Google is your friend here.+10 for knowing that this is a solved problem, no need to reinvent the wheel here.I: What if you couldn't use Google?

M: Assuming you mean no access to the internet, since I don't happen to know how to calculate a square root, I'd ask someone...

+10 for not being afraid to ask someone when you don't know the answer, rather than wasting hours trying to figure it out yourself.I: What if there were nobody to ask?

M: I'm not a math whiz; I'd drive to a bookstore and get a book on how to do it.

+5 for admitting you don't know everything.+5 for remembering that there were bookstores before there was Google.I: What if there were no bookstore?

M: Ok, so you want me to come up with a formula I've told you I don't know, in the next 10 seconds, without access to any of the usual reference sources?

Yes, I would like you to come up with an algorithm to solve the problem, even if it isn't a very good one. Take as much time as you would like. There is no 10 second time limit. Think about it while I check my email. Take your time. Use the whiteboard if you want.M: <Walks Out>

-1000. Too bad. He was doing fine at +65. But hiring this guy would have been an Epic Fail. When faced with a difficult challenge, he chooses flight over fight. Not what we need here.I have a feeling programmers at NASA, Spar, and maybe oil companies use those functions more.

Then you should just say "please give me a function" somewhere and totally sidestep this bullshit. It's the obvious and easy thing to do as an interviewer. YOU have to make your expectations clear so then it falls upon them to rise to meet them.

Although my main point still stands. It would have been better if the interviewer had framed the question more clearly with respect to what he was expecting.

I arrived prepared to tell them "It looks like you might have trouble here and here, and I propose this and this to cover yourselves while you fix it like this."

Instead, the interviewer wanted me to write some code to calculate prime numbers on the whiteboard.

So, now, they've hired their submissive puzzle solver, and I have a handful of vulnerabilities -- still not fixed -- that give me access to a major slice of e-commerce. Guess who (potentially) wins?

And, just to remind *you*, there *is* such a thing as exact with floating point numbers. IEEE754 can represent negative-powers of two quite nicely thank you very much. Things like 1/2, 1/4, 1/64 or any number that can be represented by summations of those (within the bounds of the bits available) are, to all intents and purposes, exactly representable.

It's only when you get outside the bounds of precision, or have a number like 0.1 which can't be represented as sums of 2^(-whatever).

Don't be a pedant on the net. There are so many of us around :-)

Use repeated addition? :-)

Then there is no concept of a square root?

Thus to "exactly" calculate sqrt(2), you'd only need to write a class to handle arbitrarily high precision decimal numbers (unless this already exists in Java) and implement your favorite iterative algorithm on it.

So the actual answer should have been "I'd give my mate Anoldhacker" a call and get him in to do the work".

Yes, I suppose you are right. Because that is how it works in the real world. Your boss always comes to you with requirements that are absolutely clear cut from the start, will never change, have no oddball restrictions, and no bullshit. That's because your boss got the requirements directly from Sales And Marketing, and they obviously always state the requirements clearly from the start. Why wouldn't they? They get the requirements directly from the customer. And not only does the customer know *exactly* what they want, they are also always right.

So, yes, you are right. Failing to give the programmer the precise requirements and restrictions from the start is my WTF. One that would never happen in the real world.

Thank you for pointing that out.

2. Successive approximation WILL give you an exact value.

That's impossible.

Most square root functions return an irrational number, i.e.: their digits repeat endlessly without a recurring pattern. There is no representation for the number in a digit-based system.[/quote]

Rubbish. In base sqrt(2), the square root of two is exactly 1 :-)

Option Explicit

Const ITERATIONS As Integer = 20

Sub SquareRootBitchez()

Dim num As Double

Dim i As Integer

Dim cntGuess As Double, cntGuessSquared As Double

Dim cntMin As Double, cntMax As Double

Dim isNeg As Boolean

num = InputBox("Enter Number")

If num < 0 Then

isNeg = True

num = Abs(num)

End If

If num > 1 Then

cntMin = 1

cntMax = num

Else

cntMin = num

cntMax = 1

End If

For i = 1 To ITERATIONS

cntGuess = (cntMax - cntMin) / 2 + cntMin

cntGuessSquared = cntGuess * cntGuess

If cntGuessSquared > num Then

cntMax = cntGuess

ElseIf cntGuessSquared < num Then

cntMin = cntGuess

Else

GoTo ExitFor

End If

Next

cntGuess = (cntMax - cntMin) / 2 + cntMin

ExitFor:

MsgBox cntGuess & IIf(isNeg, "i", "") & vbCrLf & "After " & i & " iterations"

End Sub

Ignore my last post :P

So thanks for responding to my point by being a smart ass. Let me retort though with a serious response:

If you're going to deliberately be a shit head when you're interviewing a candidate, then you're only going to hire people who are stupid enough to not see the red flag that you are yet another dumb shit employer.

Naturally, you're going to get a bunch of tool higher ups that won't give you good requirements. The smart man at least makes sure that he gets as few possible derps like that giving him orders. I don't think it's really strategic from a recruiting perspective to make yourself look like a dumb ass who can't even get his own interview questions straight. That's how you scare the competent people away.

Derp.

The point is, if my Boss isn't capable of giving coherent requirements for problems that he's making up himself without going to several iterations, why should I expect that he is going to come up with the requirements for a customers problem correctly? I imagine that Snoofle doesn't want to discover he's been wasting time working on the wrong problem because his boss is an idiot and didn't ask the right questions.

Asking questions that force the candidate into situations where they should try to gather requirements is a great strategy. Is the sqrt question a good way of doing that? I'd say it isn't. So I'm going to say your point is a touch moot and unrelated.

Unless of course you would use the sqrt question to look for requirement gathering skills, in which case God help you.

This is basically what I did when applying for a support position once with one of those "If you're lost in the woods and mysteriously have absolutely none of the items which people would normally carry into the woods, are then suddenly attacked by a velociraptor, and now need to cross a magma flow with only toothpaste, a ball of twine, and an Eagles 'Greatest Hits' LP..." questions.

"This question is stupid. What possible reason could I have for being in the woods without any weapons or survival gear?"

No, indeed. But i think he was judged by his refusal to do the technical test and fleeing from the area :) I mean he got in touch with Human ressources. Why not just say "er i'm lost in you place" ? I really think the bycicle what juste an excuse to leave when he learned about the written test :)

No, it isn't. 1 in any base is 1; in base sqrt(2), sqrt(2) is of course represented as 10.

I'd have gone with Newton-Rhaphson as well. But then, I have actually had to use Newton-Rhaphson in my job to derive iterative approximations we can use to solve intractable equations. For what it's worth, I also have to use exp() and log() functions in some of the data modelling I do.

For reference, I work in the financial industry, and the Newton-Rhaphson stuff comes into play when answering questions like "what is the maximum loan amount you can borrow in this scenario, given that as the loan amount changes a whole lot of other things change which affect your net serviceability amount?" These things are typically implemented by lenders as Excel spreadsheets with a button that calls the Solver (which internally does its own iterative approximation technique), and we have to replicate the results on our in-house system.

I haven't had to use these things often. But I certainly have had to use them.

I don't know if you are trolling or not, but for the record:

Use NOR gates.

Your computer does not have enough memory for an exact representation of sqrt(2).

Otherwise they're hypocrites.

Captcha: facilisi : Of course it is!

Captcha: haero : he who saves the day

OMG. I'd love to interview YOU... You must be a really acommodating worker, never questioning stupid situations and accepting anything you boss says:

Kasper, please, today I want you to write all your code without using the letter 'e'.

(Kasper thinks: what a sensible demand, of course some day my e key might break, and there will be no keyboard replacement, the chance to buy a new one in the shop down the street, use a colleague's keyboard, bring my portable from home... mmm. let's reinvent the while loop for starters... man I love my boss and this job!).

What I would learn from someone not leaving the room is:

1. This guy takes everthing!

2. This guy can be abused with silly demands

3. This guy goes for the complex, unneeded solution first and only (if ever) goes for the obvious, he must be very productive if/when we need to reinvent the wheel! (which of course is something we do every week).

4. This guys must be desperate for a job, I'll offer him less than what should the salay for this position!

5. Maybe he will bring a cup of coffee before the interviews ends...

6. Some little more mental abuse and he will call me "Lord"

7. Oh, and I can blame him for all that goes wrong, since he accepts so happily that everything goes wrong...

i) What range? integer, real, complex?

ii) What level of precision?

iii) What performance?

and to be pedantic iv) what error handling?

But yes, I agree with all the posters that any candidate who can't come up with some sort of algorithm off the top of their head is out of the door.

You are looking for roots to a function, in this case, if you look for sqrt(5), you want to find the root(s) of the function f(x) = x*x - 5. No sqrt in the function, none in the derivative.

1. Binary interpolation. I have seen a few solutions of this. This is O(precision) where precision is the number of bits of precision you require. Processing time will only use fast additions, subtractions and divisions by 2 (which are fast because they just shift the expononent by one in floating point).

2. Secant interpolation. Like binary interpolation, you need two values and you interpolate between them, but instead of picking the point halfway between them, you assume the "curve" between them is a straight line and pick the point that solves your equation. It can be a problem when you have a local maximum but not an issue with square roots as long as you deal only with positive roots as they are monotonic (i.e. sqrt(x) > sqrt(y) whenever x > y, which is monotonically increasing). The merge is usually quicker than binary interpolation I think O(log(precision)) actually. It does however require doing floating-point division per iteration.

3. Newton-Raphson. Unlike the other two methods above it does not use interpolation between two points. Instead you know the slope of the function (derivative) and assume the slope at your particular point remains constant. Thus you draw a line using just your one point. This can fail badly for non-monotonic functions too as you can head in the wrong direction but works for square-root. I recall this is marginally more efficient in number of iterations than secant but may require more complex calculations per iteration so may actually take more processing time. For square-root of y, I think x -> (x+(y/x))/2 is the correct iterative step, and you will alternate between numbers that are too high and too low.

4. Tables. Assuming we can split our number into an exponent and mantissa: actually we need always an even exponent, so the mantissa will have the range 1-3.999999 or 0.5 to 1.9999999. If we can store square-roots of these numbers to certain precision we already have a rough estimate. We can then interpolate the last few steps (probably with the secant method) but it gives us a head start. We could use tables of logarithms instead which means we can divide by two, but then we'll have to perform a "power" function back.

If I were writing an operating system kernel and a processor that had to be math-heavy and fast, there would probably be some cached tables.

Of course, an implementation detail is that as we will often be dealing with floating point approximations, we have to ensure we don't iterate forever even if we don't have a perfect solution. So we may need to store our last 2 solutions anyway to see if we meet the same one again.

Remember in Newton Raphson, that our value moves alternately below and above the correct answer? That means we might revisit the number we had 2 iterations ago, so we need to store it anyway.

they don't have log and exp? log, divide by 3, exp...

cube itself is monotonic but cubics in general are not.

"I'm in the forest so I grab two sticks off a tree and rub them together to make a fire then use that to scare off the bear"

I said "+NaN" but Akismet complained.

I: India has been vaporized by a nuclear blast. What do you do?

M: Ask for a raise.

for (i=2; i< int.max; i++)

if (i*i==operand) return i;

After you tried this (the square root is not an integer) consider approximating. I don't remember the code and while I have Google with me I'm not using it

1. Pick the highest integer such as "i*i < operand". (i+1)*(i+1) must be > operand

2. Pick a=i, b=i+1, c=(a+b)/2

3. If abs((c*c)-operand) < EPSILON return c

4. If (c*c)-operand<0 pick a=a, b=c, c=(a+b)/2, repeat 2

5. If (c*c)-operand>0 pick a=c, b=b, c=(a+b)/2, repeat 2

This algorithm has an exact scientific name but I currently don't remember it. More efficient methods include Newton's approximation but I don't remember the code and I'm voluntarily not using Google.

Can I consider myself hired?

Captcha: refoveo

As a reasonably intelligent person, I learned that certain actions on the part of the interviewer tell me that I DON'T WANT THAT JOB - that is why I walk out.

It's not that *I* fail the interview; it's that the INTERVIEWER has already failed MY interview.

Remember, interviewing is a two way street.

The answer is dead-simple once you realize that the problem is actually: how do you find number y for which y * y = x, where x is the number whose square root is being calculated?

Failing this, you showed the interviewer that you might be prone to getting confused when left to your own devices.

And the candidate cares about this why?

Everyone here seems to keep getting hung up on what the interviewer now thinks about the candidate, but the interviewer's opinion has become completely irrelevant. What is relevant is that the impression the interviewer has made on the candidate has led to the candidate rejecting the job.

Interviewers aren't the only decision-makers in an interview situation. They need to impress good candidates just as much as - if not sometimes more than - candidates need to impress them, and it's rather depressing that so many supposedly experienced people here seem not to know that.

What snoofle and others miss in their insistence "you're not learning anything useful about the candidate! but the interviewer's tone shows he's an idiot!" is the reverse is true too: the candidate's tone (including the quasi-hypothetical "that's neither funny nor relevant") derives the same conclusion.

Sure, you're not going to be required to code up square root functions, nor will you be limited to your choice of non-NAND gates. If you don't find inherent challenge or humor in such hypotheticals, if http://xkcd.com/505/ or http://ioccc.org/ don't intrigue you despite their obtuse irrelevance, you're not the droid we're looking for.

What's relevant is that this fact was not made anywhere close to clear in the dWTF article, until enough people piled on the candidate about how the allegedly WTF question was quite reasonable and the walking-out was the real WTF, then he backtracked hard and claimed the real WTF was the impression the interviewer made. The real WTF now is the bifurcation of this thread.

OK, fair enough. Certain questions, and methods of asking them, are red flags warning you it's not the job you want. Good. He asked a question suitable for screening a candidate for what he wants, you screen questions for whether you want to work there; you both concluded it wasn't a mutual fit, and you didn't waste his time any further (see prior dWTF discussions).

So what's the WTF?

Granted, even in this broader light HTML5 would not be great choice for data analysis, but it's not as bad an idea as the submitter portrayed.

I recently spent a

full dayin interviews during whichnobodymade the slightest attempt to convince me why I would want to work there. Nor did their highly scripted interview schedule allow time for my questions, unless they expected me to brazenly divert them off their script and demonstrate that I was determined to put my own interests first.If that's what it's like during the "sales pitch" can you imagine how it turns once you're locked in?

Your mind truly works in mysterious ways.

What is “a heavy unit-test guy”, and how is my being so (or not) relevant?

Come on, am I really a Mensa candidate for knowing this? This is basic problem solving, people.

FTFY

Incidentally you can also do a Taylor Series expansion here but for it to converge quickly you would need a close square number to start from. Still, our methods do give us some approximations which we square.

If we are going to reduce to numbers between 1 and 4, we can also split that range into squares e.g. 1-1.25, 1.25-1.5, 1.5-1.75, 1.75-2 squared, then factor down, and then employ our Taylor series.

[Test]

public void ShouldReturnTwoWhenPassedFour() {

Assert.AreEqual(2, NewMath.SqRoot(4));

}

[Test]

public void ShouldReturnThreeWhenPassedNine() {

Assert.AreEqual(3, NewMath.SqRoot(9));

}

double guess = (upper + lower) / 2 + lower;

?

On one occasion I have told off a manager. It wasn't my own manager, but another on the same level. I basically told him that's my decision to make, not yours. The next day he came to me and apologized for his behaviour, and thanked me for my effort.

I have never needed to speak to my own manager in such a voice, so nobody can say how I would have reacted in such a situation.

On some occasions you will find yourself in a situation, where sensible arguments won't work on otherwise sensible persons. In those cases it may be counter productive to keep arguing for a sensible solution. On a few occasions I have accepted to go with a solution, I knew to be a bad idea. If nothing else, that gave me opportunities to come back and say "told you so"

Nothing.

I have interviewed lots of people. Nobody ever left the room before time.

Good employers normally either ask you how you know a particular technology, let you talk about it and then judge if you know what you are talking about.

Some less technical people want to get a sense of your skills by asking you a questions such as "describe a situation where you solved a difficult task." ... you describe what the problem is, why it was difficult and how you went about solving it and what you have learned along the way.

The first answers snoofle gave were decent and fair answers to the questions, once the situation presented becomes so ridiculous that the situation isn't grounded in reality, then you know that your boss is most likely a bit of a dick ... and you don't want to work for them.

As someone who happens to be familiar with Newton's method of approximation, I can say that that is simply a silly criterion. How many mathematical formulas and theorems have been invented over the centuries? I'll bet you don't know 99.9% of them and probably wouldn't understand most of them if someone tried to explain them to you. But you would reject a candidate because he didn't know one particular formula off the top of his head? Maybe this one is more important and fundamental than most. But so what? Maybe the candidate has never had occassion to need it.

By the way, Newton's method of approximation does not use successive approximations as you indicate in your post. See, for example, http://www.math.wpi.edu/Course_Materials/MA1021C06/lin_approx/node1.html for an explanation of how it works. Apparently you do not know this method yourself. You fail your own test! :-)

And "it's blindingly obvious"? Than how come it took a genius like Newton to invent it? Why wasn't it invented 500 or 1000 years earlier? Maybe you re-invented it on your own with no hints whatsever when you were in third grade. But I suspect that it's only "obvious" now that someone else has explained it to you. I always get a laugh out of people who say that they could have made some great discovery or invention if only so-and-so hadn't done it first. Sure. Prove it by making some equally great discovery on your own now.

(I get an even bigger laugh out of people who ridicule a genius for wasting his time on an idea that was just obviously wrong. Like people who make fun of Galileo for trying to find a correspondance between the platonic solids and the orbits of the planets, or Newton for investigating alchemy. Sure, it's obvious NOW, after great geniuses spent decades investigating and demonstrating that these ideas don't work. But nobody would know that unless these men had done the work to prove it. Someone builds a boat and travels thousands of miles to discover a new continent, and then you proclaim that it was all a waste of time because you could have told him that continent was there without making the trip. Sure, but you only know that because HE made the trip. But I digress.)

The interviewer seemed to, at the time, be stuck in a train of thought and yes, he did not phrase the question optimally, but that makes him only human.

The fact that the interviewee misunderstood the question at first was also understandable.

nobody was particularly unreasonable UNTIL after, the interviewee understood that the interviewer wanted him to implement sqrt(), where he effectively said "fuck that" and stormed off.

But suppose he had asked the question in a way that made it clear what he wanted, like: "How would you calculate a square root if the language you are using does not have a square root function? Assume that you cannot ask anyone for help or use any reference material: you must come up with a solution yourself." I think that's a fair interview question. Sure, in real life a programmer probably won't have to come up with his own formula to find square roots. But he will have to come up with solutions to problems where there will be no handy answers available on the Internet, and he can't ask co-workers to do his work for him all the time.

Saying that this problem isn't relevant to the job is itself irrelevant. The real problems that would be relevant to the job would likely require hours, days, or even months of explanation of company business practices, existing systems, market conditions, etc etc. If a potential employer asked you to write a complete employee benefits system that would interface with the company's existing payroll system and the insurance company's system, and that handles all the benefits that the company presently offers, adjusting for recent changes in the law that may affect those benefits, and taking into account new benefits that the company is considering offerring ... Surely you would object that it is impossible to even collect all the requirements in the couple of hours available in an interview, never mind actually build such a system. Any problem that can be posed in an interview must, of practical necessity, be something abstract and probably generic.

When I was interviewing for my present job, they asked me to write a program that plays Bizz-Buzz. I didn't suppose that a company that develops web sites for hotels would often have occassion to need Bizz-Buzz programs. But I understood that the point was to see if I could write working code.

"I am deciding whether I want to work for them or not, and if he asks questions like this I don't want to work with them based on what I have heard hear and what I experienced before".

Yeah, "Siri for Data Analytics" isn't realistic....

http://www.dailytexanonline.com/university/2012/04/17/siri-technology-may-be-future-data-analytics

http://bioteam.net/2012/04/using-apple-siri-to-orchestrate-experiments-on-the-cloud/

I'm guessing those business guys saw the level of idiocracy amongs those CS students, and decided to not bother giving them a real pitch.

The interviewer was trying to weed out people like you.

The point of the question, although delivered terribly, was for you to think about what a square root is and how to get to it. If I was the interviewer, I would have rephrased with the following:

You do know the square root of A = B*B. How would you figure out B?

If you can't get past the FORMULA and get a better idea of what you're actually trying to do, you probably shouldn't be rebuidling legacy systems. Your ability to see the whole problem and solution is narrow.

Another big point in this situation is the interviewee's inability to accept someone elses reality. Instead of being curious, he was arrogant.

If the question was "how do you find the distance between two points?" You wouldn't agree with the interviewee. You're all caught up on "square roots are hard, waaaaa".

implement a natural logarithm function and exponential function if they not available (it can be implemented easily enough using their taylor series if they are not provided). After that it is easy enough to find the square point.

Otherwise, one can also use either fixed point iteration, or Newton Raphson to find square roots.

(I am not saying being able to answer this unrealistic question makes me more or less qualified for a programming position; technically I cheated, being a Maths student).

If I were the interviewer, I'd then ask you to go ahead derive the taylor series.

Also, I don't understand why everyone seems to be expecting "realistic" questions. If they were asking you to solve realistic actual job-related problems, those problems would take you all day.

If I were the interviewer, I'd then ask you to go ahead derive the taylor series.

Also, I don't understand why everyone seems to be expecting "realistic" questions. If they were asking you to solve realistic actual job-related problems, those problems would take you all day.

snoofledidn't understand what the interviewer wanted; it's that he recognized that the interviewer (who would probably have become his boss) was a bad communicator, and that was a red flag. I've worked with people like that, and I'd prefer never to again. If I were to glean such insight from interview questions, I'd end the interview as well.This. The core of the interview question in and of itself is in no way unreasonable, in my opinion. I think it's a fine candidate for a programming question. But it should be phrased as such right off the bat: "Please implement a function that calculates the square root of an integer without using a Math library." or whatever.

Going through a chain of "what if's" is 90% of the time irritating and petty UNLESS you are, in fact, trying to iron out an obscure problem and gather requirements. That is not the case here, however. And if you wanted to have such a question, it would be approached with "what if you had this input," or "what if there was this corner case" but probably not "what if you didn't have this basic technology that you might actually need to solve this problem effectively."

That said, anything where you want to have the candidate explore the problem needs to be designed that way right off the bat, and needs to be much more complex than "implement sqrt."

OK, snoofle. I won't be hiring

you.Actually, mine does because it represents numbers in base(sqrt(2)). It seems to have problems with numbers like "1", however.

Oh? So sqrt(0.789 * 0.789) is irrational?

OK, yes we know that interviewer wanted to find out how snoofle would approach a problem. However......

The BS of keep taking away valid answers is just stupid. Others have said it, the interviewer should have asked the question in a different way. If you ask the question that way because that's the only way you have heard it done, then it shows just how small minded the interviewer is.

And snoofle said it, he has seen what happens in job when they ask these types of questions, and he doesn't like it.

I wonder how many hours he will spend trying to find a design pattern for each and every small problem that comes at him. Would he even do any creative work?

Or maybe he just designs gui. I dont know.

I mean, he know what a square root is, doesnt he?

Ever see the code that people write when they really don't understand all the crypto issues? Better to take a WELL proven chunk of code and use it than reinvet the wheel with all kinds of security issues.

No, in sqrt(3^2 * 263^2 / 2^6 / 5^6), all the prime factors are to an even power.

It's really worth it to (re)learn Newton's method. Just to see if I can do this off the top of my head:

You're looking for a zero, right? So you're going to guess an x, calculate f(x), giving you a y. Then you want to draw a line tangent to the curve at that (x, y), and the zero of that line is your next guess.

Obviously, the slope of the tangent line is the derivative, and we're looking for is the solutions to x^2 - n = 0, where 'n' is the number we're taking the square root of.

The derivative of x^y (where y is constant) is the first rule you learned: y * x^(y-1). n is constant, so the derivative is just 2x

To find the tangent line from a point, expess it parametrically by setting the slope equal to itself:

m = (0 - Y) / (x - X)

x = X - Y/m

In python:

To make it more robust, you can pick some random number if 'm' turns out to be zero :-)

No, the correct answer to the Square root question is obviously: "Is this to be an empathy test?"

Doublethis.

Being asked "what if $REASONABLE_THING" is perfectly valid. But being asked "what if $DUMB_THING" is as redflagful as being asked to "code up a web 2.0 app to leverage our synergies going forward". Both should be treated accordingly.

Clearly the interviewer heard about this really cool interview techique and cant wait to try it out without actually understanding it at all. Of course, that may be his *only* fault. And unlike snoofle, others might be quite happy to take a chance on that being his only fault, and go to work for him anyway.

Indeed, I look forward to seeing some of their code on this very blog.

The derivatives of sqrt are powers of -.5, -1.5, -2.5 etc so you need the square root of the x. Therefore we start based on a squared number.

mod(a) should be < x for this and you should probably factor it down to make x==1 so divide the whole series by a constant so it ends up being that way.

If you want the square root of 29, for example, you would divide by 25 to get the square root of 1.16 so x = 1 and a = 0.16

If you want the square root of 47, you could divide by 49 (better than 36) and a would be negative.

Incidentally if x is rational then you would be able to store root(x) "exactly" in your memory as long as you don't store it in IEEE format but store it in a special class either as a square-root (algebraic number in general) or as a recurring continued fraction. Irrational square roots are always recurring continued fractions.

pi and e are transcendental (numbers that are real but not algebraic) but both are sums of an infinite series of rationals. pi/4 is atan(1) so usually pi is calculated as atan(1)*4.

Understanding Taylor series expansions, interpolation techniques and other solving problems may well be required in a programming job. Most of the equations you will be solving won't be square-roots and won't be solvable by a library function. Of course the interviewer may have said after the square root one, "ok now solve this" and give a function that has no library solution...

Incidentally I would normally only ask at interview something that either:

- was relevant for the job

or

- was something the user specified on their CV.

and usually the latter. So if the candidate doesn't want to be tested on it, they shouldn't put it on their CV.

I am seeing people use absolute epsilon which is faulty. Error is relative, not absolute.

IEEE numbers allow exponents of 2 to the power of something like 1023 so if you are asked to find the square root of 2 to the power of -1022, you can find it exactly, it will be 2 to the power of -511. Not approximately that, exactly that. No rounding errors. Similarly 9*pow(2,-1022) (yeah, 1.125*pow(2,-1019) has an exact square root of 3*pow(2,-511) (1.5*pow(2,-510)).

If it is 5*pow(2,-1022) there won't be an exact square root, of course, but have your answer out by 2 to the power of -15 and you are way out...

Conversely if we are going to find the square root of 5 * pow(2,1014) your epsilon will need to be a LOT higher...

The "error" needs to be in the square root, not in the square.

For me, the ability to ensure the algorithm terminates properly is more important than the fastest merging numerical method, so I would rather see a correctly-terminating binary interpolation algorithm than a faulty Newton-Raphson.

The weird way doubles are processed means that when you do reach the final destination, it won't neceesarily equate "equal" to either of your lower and upper bounds. (And actually I was not quite correct earlier. You won't always move between solutions too low and too high. You will for square root but not for functions in general).

Incidentally alternative interpolation methods are:

- Quadratic interpolation, although it requires you know how to calculate square-roots. Also assumes you know derivatives, but works in "general". You solve current value, last value and current slope (but not last scope).

- Cubic spline interpolation. For just 2 points you would use values and slopes at both points. The only issue is actually "solving" the cubic (which is solvable, Nicolo Tartaglia).

Normally used to interpolate when you don't have absolute values and usually done with multiple values, and the "slope" is not known at the key points but continual ranges are assumed to be continuous in slope at these points, which does give you a bit of scope at the end points.

These interpolations are worth using when the function you need to evaluate is very expensive compared to all else.

The development side should be trusted to the technical architects.

public static double sqrt(double val)

{

return 1; # accuracy increases as val -> 1

}

* it rhymes better

This.

"I wouldn't have time to be worrying about square roots, I would be with my family trying to find the nearest fallout shelter."

it is a numeric theory and algorithmic question, and the skills that you need to solve it can actually be very relevant to your job even if it might not seem so at first.

It's as though everyone expects you to be given actual problems from production when you go to an interview.

The skills to correctly solve it "in real life" are exactly the skills that have been shown by the author:

1.) Don't reinvent the wheel (badly). Know that it is a solved problem. Know what your platform provides.

2.) If your platform does not provide it, use a search engine to find out if it already has been solved by someone else (bonus points for knowing a good search term for this).

3.) If that still is insufficient, look up (scientific) literature about the problem. If others already have tackled the problem, chances are that they know about problems that you will run into with a "invent-it-myself-in-10-seconds" approach. (see sqrt(x) when x < 1)

CO: "Sailor, what would you do if a strong wind came up the port side?"

Sailor: "I'd drop an anchor off the port side, sir."

CO: "Then what would you do if there was a strong gust from starboard?"

Sailor: "I'd drop an anchor off the starboard side, sir."

CO: "But what if a wind came up from astern?"

Sailor: "I'd drop an anchor off the stern, sir."

CO: "Wait a minute, sailor. Where are you getting all of those anchors?"

Sailor: "The same place you're getting all of the wind, sir."

The first sign of a bad technical job is often a bad interviewer.

Shea

He did: "What if you couldn't use Google"

Leaving aside whether Google is "all information", the interviewee clearly understood it to mean "no internet". After all, the next suggestion wasn't to Bing it.

The solution to the problem is a simple - if slow - approach known as the bisection method. It's not unlike binary search (which you should be familiar with): given a range between a and b where the root should be present (for numbers larger than 1 this initial range will be between 1 and 1/2 x) and then check whether the number between a and b is within set precision from the root ( return it ), smaller than the root ( set a to this number, repeat ) or larger than the root ( set b to this number, repeat ).

This is literally something out of a beginner grade algorithms course, and a fairly reasonable way of finding out whether you can reason your way out of a wet paper bag. The problem is simple, practical and can be solved in a few minutes without bizzarro lateral logic.

Well the

interviewee understood! Severity One's point however was that theinterviewer did not understand his own questions- and that you have proven: He asked "What if you couldn't use Google?" when he should have asked "What if you couldn't access the internet?".norrelevant.Got it now?

While asking for something like implement sqrt may be a bit lacking in signal since it's very math oriented instead of cs oriented (though personally I'd expect most decent engineers to be able to come up with even a bad solution), asking interview candidates to try and solve problems that aren't in their comfort zone I do think can give you some good insights into the candidate. You do get to see how they *think* as opposed to how regurgitate patterns and solutions they've been repeating for years. God knows I've interviewed plenty of people who on paper were serious engineers but couldn't solve a basic problem like reverse-a-singly-linked-list w/o access to their precious sdks.

So many of you are missing the beauty of binary search which lays preceisly in the fact that it does not require you to know anything more about the function than if its argument is too large.

Recently I had to icompute number of weekes between two timestamp. After writing unit tests and considering for a moment precomputing for all possible inputs, I given the standard library a chance. Unfortuanately php's date_diff returned wrong number of weeks. But I knew that there is strtotime function which uses very robust linux library and I knew it had +n weeks functionality, so in a minute I hacked a simple binary search workaround for a buggy library.

Another example. I had a system in which I could access rows only by a key, yet I needed to know number of rows. Again, binary search came in handy.

Please, skip "trwtf is php" and "a man with a hammer sees only nails" comments, and admit it: the real wtf is not knowing binary search, and not recognizing theoretical question despite hints. I doubt the same attitide at school was helpful. If someone treats everything so literally he might have some troubles with abstract thinking whoch might be necessary to model parts of the reality in a program.

For every simple and effective Plan A you have, you may end up going through Plans B up to F when that plan meets reality.

Likewise, that there is an SDK, book, guide or implementation does not mean we have it on hand - or that we have time to obtain it.

In a practical scenario, I'd implement the bisection method as a temporary stopgap solution, leaving myself a note to redo it properly when I have access to my precious reference materials.

For which the answer should be "if you want me to solve your production issues you have to hire me first, or at least pay me a one-off consultancy fee of £500 (or whatever)".

There were many ways to handle this situation with dignity:

1. describe the root finding algo snoofle would have used to solve the equation x*x = y for given y

2. answer "I'm sorry, I don't know much about numerical programming"

3. if 2. would be false, attempt 1. but fail, and consider this a lesson learned

This was a valid question and I think snoofle's interviewer showed him much patience as things were.

Three points:

1.) TRWTF is PHP

2.) A man with a hammer sees only nails.

3.) The real real WTF is not knowing the limits of your silver bullet: binary search works if you have a monotonic function.

sqrt(x) is monotonic when x >= 1.

However for non-monotonic functions a binary search will fail.

I've gotten job offers out of interviews that were really, really easy, where I knew all the answers AND could come up with them in ten seconds. I've never taken one of those offers, though I certainly would if I had no other options and needed the paycheck - I'm not an idiot.

But if the interview was easy, then they don't KNOW I'm not an idiot. Which means that they don't know if my future co-workers or bosses were idiots when they hired THEM. Maybe they got really lucky, but idiots are really easy to find, especially at job interviews, so the odds aren't great.

And snoofle - leaving aside the whole issue of not figuring out the point of the question, even after many (admittedly coy & overly-"cute") hints - would you *really* drive to a bookstore and buy a book about square roots (that'd be some dry reading) rather than try to figure out your own solution? Even assuming a car parked nearby, no traffic, and no line at the checkout, that shouldn't be the fastest way to solve the problem.

There are all sorts of approaches to take to a "How would you solve this hypothetical problem?" question. Yours, repeatedly, was basically, "I'd look for somebody else's solution to it and copy that into my code and probably change some variable names until it compiled. That would be efficient, because I'd never have to waste time understanding the problem OR its solution." I've seen a depressingly large number of programmers who take that approach to their jobs, but few who actually admit to it in interviews.

1. Sqrt is monotone in whole domain of no negative real numbers

2. One should apply binary search to the inverse of the function(in this case squaring) and not to the function itself (in this case square root). Although i will admit that function is monotone iff its inverse is as well.

1. I did not claim contrary.

2. Binary search is still the wrong tool if the function is not monotone.

Would you rather the interviewer spend the time to invent an unsolved unconventional question, what would really serve no additional benefit other than the fact that you don't get smarmy answers from people like snoofle and you?

As he said, the interviewer was condescending. If you get a bad vibe from an interviewer or during any business deal, you have to trust your instincts.

In the square root case, the Newton iteration values will always be a upper bound to the root, to see why:

Let square root of y be z, and x is an upper estimate of it, we have

(x - z)^2 > 0

x^2 - 2xz + z^2 > 0

x^2 - 2xz + y > 0

x^2 + y > 2xz

x + y/x > 2z

Now we see the value of next iteration = (x+y/x)/2 > z and therefore is also another upper estimate of z.

That is critical because you can also compute a lower estimate of z by simply doing y/x and have an interval estimate of z - one can stop at any point the both estimate agree to the level of precision one is good enough.

I'll bet the interviewer would be happy even with a STUPID, SIMPLE, APPROXIMATED and SLOW solution (like computing squares of increasing numbers and comparing result with given number), but snoofle was too lazy to think.

Don't get me wrong, I do not thing that creating your own sqrt in java is important programmer's skill, I just think that while people who REFUSE to think may be good enough for some "generic" code monkey positions, they may not be good enough for position where you have to design and not just code.

- new,

- young,

- inexperienced,

- wants something other than a canned answer,

- want's a canned answer,

- is not going to be working on his team at all,

- will be working in his team and wants to see how he does under stress,

- does not represent the company at all,

any combination of above plus a gazillion other reasons this situation could've come up... who cares, snoofle already knows that this job is not for him, so he walks out. Good for him, good for the company he walked out on. It's a win-win, as far as I am concerned, in fact I think these kinds of questions should be used more often if nothing else just to weed out the snoofle types of people because from what I've read in the post and in the comments it doesn't look like he is a pleasant person to be working with, especially under pressure... of course I could be wrong, that is just an impression I got from reading this thread.

Most people don't really know how to do this, obviously. The interviewer might want somebody who's willing to take an earnest crack at something that they're pretty sure is impossible. Or maybe the interviewer's looking for somebody who is humble enough to say, "Unfortunately, I don't really have a good idea on that."

If I were the interviewer, I'd keep that question on the list to weed out people who couldn't accept that their job might push them past their reasonable limits.

Besides, I don't think it's that hard. "First, we're going to find the two integers that the square root is between. Let's take an example of sqrt(30). We can iterate though integers to find this, although if we weren't in an interview I might think of a better way of getting these. 1 goes to 1, 2 goes to 4, 3 goes to 9, 4 goes to sixteen, 5 goes to 20. Then, we'll iterate though 4.1 to 4.9 to determine the next digit. 4.4^2 is 19.36, 4.5^2 is 20.25. Then, we repeat the process to the desired precision. Eventually, we'd get 4.472."

There. I just answered the damn interview question in less than five minutes.

I still think storming out of an interview over a bad question might be a self-damaging habit. Having a mediocre job offer is better than having no job offer.

that is presentation not representation. The computer see's that as (U+221A) '2'. It can't use that value in a computation nor would it present it as the result of one, it will always present 1.141..

double sqrt(double d)

{

int n, invert, exponent;

double working;

/* Handle bad input */

if (d < 0.0) return -HUGE_VAL;

/* Handle 0.0 case */

if (d == 0.0) return d;

/* Invert any input less than 1.0 */

invert = (d < 1.0);

if (invert) d = 1.0 / d;

/*

* Normalize the input to 1.0 <= d < 2.0 by splitting it into a

* mantissa and exponent.

*/

d = frexp(d, &exponent);

/* Save the mantissa */

working = d;

/* Do a first approximation */

d = (d + 1.0) / 2.0;

/* Iterate using Newton's method */

for (n = 0; n < 4; n++)

{

d += working / d;

d /= 2.0;

}

/* Correct for odd exponents */

if (exponent & 1) d *= 1.414213562373095049;

/* Recombine the comp1.0nts */

d = ldexp(d, exponent / 2);

/* Invert if required */

if (invert) d = 1.0 / d;

return d;

}

Regardless of your talent or ability, I would have failed you based on your people skills. After reading your responses, it's increasingly apparent you're unable to get along with your peers.

You could be the 2nd coming of Sir Isaac Newton, but I would not recommend hiring you. You would only manage to piss off all our coworkers, clients, and customers. You would alienate our team within our company and make our work much more difficult to accomplish.

I think the only work environment suitable for you is a solitary office in Antarctica where your nearest coworker is several thousand miles away. Not to worry though. You'll receive drop shipments of supplies on the first day of every month. You can upload your completed work via file transfer over HAM radio.

However for non-monotonic functions a binary search will fail.[/quote]

I will fail you on two points.

Firstly sqrt is monotonic even for x < 1. It is strictly increasing as f(x) > f(y) whenver x > y. It doesn't matter that, below 1, sqrt(x) > x.

Incidentally, the derivative of sqrt(x) = 0.5/sqrt(x) which is always > 0 and therefore we know it is monotonic for x > 0.

The second point I will fail you on is that binary search will not work on a non-monotonic function. If you have two values a and b, and your function is continuous at all points between a and b, and f(a) < y and f(b) > y then there must be at least one point x between a and b such that f(x)=y. There might be more than one but there always must be at least one.

binary search won't work if you have two start points a and b such that f(a) and f(b) are both > y even if there happens to be a solution in between so if y is a (local) minima (or local maxima) there is no way to find it with binary search. Newton Raphson will possibly get you there, secant will also fail.

The point is that, when you take the halfway point between and b, you will either have hit a solution or you will still have a pair of values that wrap your target (a and (a+b)/2 or (a+b)/2 and b) even if your y-range is now bigger than it was before.

throw std::invalid_argument( \""Stupid\"" is not valid input for square root );

They were probably waiting to hear "Newton-Raphson iteration, with d(sqrt)/dx = 2x". My guess is they were testing whether you went to high school. Looks like you failed...

They would like to hear things like this:

* handling < 0

* handling 0

* normalizing for < 1

* simplifying the problem to 1 <= x < 2 by removing the exponent

* getting a first approximation

* using Newton's on x

* divide the exponent by two

* put the exponent back in

* correct for odd exponents

* undo any normalization for < 1

This is a complete procedure for the square root function in the real domain. Say stuff like this and they'll be impressed.

The correct answer would have been "I probably couldn't do it." r "I could come up with something but it wouldn't be pretty, brute force for example."

It seems like he was just trying to establish dominance by making you feel weak. With that kind of attitude what kind of programmers do you suppose he's able to retain? Certainly no one good. just a bunch of people who are trying to say "yes you're right, sir" all the time. And then that interviewer guy will wonder why they can't hire a good programmer and blame the programmers.

--

Furry cows moo and decompress.

--

Furry cows moo and decompress.

If a non-tech person shows up for an interview, they do their best to impress. When a tech person shows up, they all have entitlement issues and think they are infallible.

The normal procedure goes along the lines of the candidate trying to impress the interviewer and making them feel like this person belongs on the team.

The normal procedure when hiring a tech guy is trying to impress them and convince them they belong on the team.

This stuff takes time to get used to. Tech people are dangerous, because they control you assess and your access to them. But because there is such demand for skilled PC guys, they have the upper hand. Most of them seem to think they are better than what they actually are however.

"I'd reach down, grab a pile of poop and throw it at the bear."

"What if there were no poop?"

"Oh, there would be by this point..."

Ummm.... I appreciate the idea of seeing how someone thinks and can deconstruct a problem, but at some point, there *has* to be someone to ask - the client/manager/customer/user/someone.

If there's no one to ask, there's no one to verify if it's right or not, so I'll just return 0 or null and move on.

public static double findTheGoddamnSqrt(double num) {

int godamnAnswer = 0;

while (++godamnAnswer * godamnAnswer != num);

return godamnAnswer;

}

Concise and to the point and wastes a lot of time like the stupid question

M: I'd approximate the number one digit at a time.

I: What if you couldn't do that?

M: I'd, uh... guess randomly?

I: What if you had no random number generator?

M: I'd weep and cry out.

I: What if... you had no mouth?

However your "you might approximate but you won't get it exact" thing shows you know nothing about what that means.

The problem is hardly unrealistic. It's a trivial function everyone knows about and the question tests very simple computing ability.

def sqrt(x)

val = x

if (x >= 1)

while (val*val > x)

val = val - $eps

end

else

while (val*val < x)

val = val + $eps

end

end

return val

end

This is basically as exact as your computer can handle (accurate to a step maybe). It will take forever to calculate a single value, but will work nonetheless.