• (disco) in reply to Ben
    Ben:
    Honestly if he couldn't even think of a binary search-type approach by checking the square (obviously not an efficient algorithm, but the interviewer didn't ask for one), I'd consider that a red flag.

    See, my issue with that reasoning is: "why not just ask for what you want?". I don't understand this whole "What if you don't have access to <basic resource>?" charade. If you want to know if I can make a decent stab at solving the problem, ask me to do that. Don't ask "How would you solve this easily-solvable problem under artificially constrained conditions?", just ask "Could you sketch out an algorithm for X?".

    Beating around the topic doesn't help anybody. And to be honest, questions like this are useless anyway. For my current job as a web developer, the technical portion of my interview was that I had to write a very simple web application using the technology that they used. In one go, they knew that I was not lying about my skill set, could get a sample of code to judge and could see that I could interpret basic requirements effectively.

  • (disco) in reply to Aatch
    Aatch:
    And to be honest, questions like this are useless anyway.

    The last time I had to use Newton-Raphson was probably in a Numerical Methods class, well over 25 years ago. I recognized the name when it was mentioned here, but even after a perusal of the Wikipedia article on it, I'm not sure I could remember it well enough to do it in an interview. The last (and only, AFAICR) time I ever actually calculated square roots by hand was in Junior High; I don't even want to think about how long ago that was. I would have been clueless had this been sprung on me cold.

  • (disco) in reply to s73v3r

    I wonder if I reply with midpoint subdivision algorithm, will it count as correct?

    Certainly it's not the most effective one, but it does give good enough answer by approximation up to X decimal places.

  • (disco) in reply to JBert
    JBert:
    1) The interviewer should then ask for it instead of playing a game of :moving_goal_post: . 2) He started out with Java which is known to possess such a function, so the goal post is immediately moved out of the field.

    Some people have no patience for peeling the onion.

    The "moving" goal posts actually measure the candidate's knowledge of high-level libraries, and their ability to engage with a novel problem at multiple levels, which a good programmer can do.

    At its core, the underlying problem (approximating square roots) can be solved with a real algorithm, as opposed to more ridiculous trick questions like estimating the tidal flow of an Unladen African River.

    Is it really true that @snoofle was the one who walked out of this interview?

  • (disco)

    Square root: How about the "odd integer method". It was used on a computer I worked on (it was a while ago). It has the feature that it doesn't use multiplication or division.

    Bonus points awarded for a nice program that uses this method.

  • (disco)

    https://en.wikipedia.org/wiki/Fast_inverse_square_root

    float Q_rsqrt( float number )
{
	long i;
	float x2, y;
	const float threehalfs = 1.5F;

	x2 = number * 0.5F;
	y  = number;
	i  = * ( long * ) &y;                       // evil floating point bit level hacking
	i  = 0x5f3759df - ( i >> 1 );               // what the fuck? 
	y  = * ( float * ) &i;
	y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration
//	y  = y * ( threehalfs - ( x2 * y * y ) );   // 2nd iteration, this can be removed

	return y;
}

    Just use this and then run pow(y, -1);. Simple.

  • (disco) in reply to ben_lubar

    Yes, that's the

    Google for John Carmack's formula

    from the article. Very good Ben, have a cookie. Or a cupcake.

  • (disco) in reply to another_sam

    Wait, @snoofle's next choice after "use Math.sqrt" was "use some code from Quake III for a purpose even less reasonable than what it was originally written for"?

  • (disco) in reply to ben_lubar

    Well, we don't know the purpose from what's written here. It seems that the interviewer never gave any purpose, and personally I think it's unlikely that the interviewer even had a purpose in mind outside the interview. So any approximation works as a first attempt until we find from better evidence that it's not appropriate.

  • (disco) in reply to another_sam

    Not sure how fast inverse square root is going to help you more than the part of it that actually computes a square root.

    https://en.wikipedia.org/wiki/Newton%27s_method#Square_root_of_a_number

  • (disco) in reply to dkf
    dkf:
    I've just tested that with sqrt(4.0) and it works wonderfully!

    Perhaps Microsoft should use it...

  • (disco) in reply to PJH

    What, you don't use zero-indexed months? :fire_engine:

  • (disco) in reply to aliceif
    aliceif:
    What, you don't use zero-indexed months?

    I did. It's when the user starts using them as well that causes problems...

  • (disco) in reply to kupfernigk
    kupfernigk:
    Preparation for real world exposure to "we don't really know what we want but we'll know it when we see it" clients?

    What if you don't have a client?

  • (disco) in reply to byteflush
    byteflush:
    Umm, isn't Math.pow(x, 0.5) the correct answer there?

    What if you don't have a 0.5?

  • (disco) in reply to boomzilla
    boomzilla:
    What if you don't have a 0.5?

    Interesting point. Is double n = 1.0; double y = Math.pow(x,n/2); good enough? We could play this game all day. Though as Java was specifically requested, the person above who asked "what if you don't have a compiler" was onto something.

  • (disco) in reply to kupfernigk
    kupfernigk:
    We could play this game all day.

    What if you don't have all day?

  • (disco) in reply to boomzilla
    boomzilla:
    What if you don't have all day?

    ...quickly checks for possible NEO collisions in the next hours...

  • (disco) in reply to kupfernigk
    kupfernigk:
    boomzilla:
    What if you don't have all day?

    ...quickly checks for possible NEO collisions in the next hours...

    [image]
  • (disco) in reply to Ben
    Ben:
    Sure, you'll never need to implement square root without looking it up, but there will be things you do need to implement without looking them up because they're domain-specific, so this is just a rough-and-ready way of simulating that in an interview with a simple problem.

    When it comes to domain-specific problems, "Ask someone handy" is always preferable to "wild-ass assumptions." That's as far as it should have gone.

    I'd have been more patient than notoriously snippy snoofle, but shooting down every idea I have in favor of the one the interviewer's already decided on is going to get me out the door in a hurry. That tells me exactly what working there will be like.

  • (disco) in reply to Crunger

    If it does, it does so in the most annoying and possibly disrespectful way possible. So much so that it likely doesn't even measure that very well, because the interviewee just gets frustrated and tired.

  • (disco) in reply to foxyshadis

    Whatever happened to snoofle?

  • (disco) in reply to blakeyrat

    Probably hates Discurse too much to post here. I think he still posts front page articles.

  • (disco) in reply to ben_lubar 
    float fasterInverseSquareRoot(float x) {
    return x * x;
}

    Easy!

  • (disco) in reply to FrostCat
    FrostCat:
    Probably hates Discurse too much to post here.

    He had petered out before Discourse. I suspect he got a new job (contract) that just wasn't as much WTF as his old one.

  • (disco) in reply to grkvlt

    I think you missed the Assert(2 == -0.5);

  • (disco) in reply to boomzilla
    boomzilla:
    I suspect he got a new job (contract) that just wasn't as much WTF as his old one.

    He said he was leaving WTF Central, I remember. I just assumed he didn't have any more awesome stories for us at his new place, but I figured he'd stick around in the comments.

  • (disco) in reply to ben_lubar

    fast

    java

  • (disco) in reply to kupfernigk
    kupfernigk:
    Though as Java was specifically requested, the person above who asked "what if you don't have a compiler" was onto something.

    FTFY…

  • (disco) in reply to dkf

    As the person who mentioned the compiler, I can neither confirm nor deny rumours about what substances I may or may not have been on. s However, I do find that when dealing with Java it helps to be on something

  • (disco) in reply to Jaloopa
    Jaloopa:
    However, I do find that when dealing with Java it helps to be on something

    I have found that my desk chair works quite well. <Looks like i picked the wrong week to stop sniffing chairs.

  • (disco) in reply to boomzilla
    boomzilla:
    He had petered out before Discourse. I suspect he got a new job (contract) that just wasn't as much WTF as his old one.

    Some quick research indicates that on a scale of @dhromed to @lucas, it's more the former than the latter

  • (disco) in reply to PJH
    PJH:
    boomzilla:
    He had petered out before Discourse. I suspect he got a new job (contract) that just wasn't as much WTF as his old one.

    Some quick research indicates that on a scale of @dhromed to @lucas, it's more the former than the latter

    I seem to remember him saying that he had a bunch of really outrageous :wtf:s that he was waiting until he was no longer working at WTF, Inc. to post, but I don't remember seeing those. If he's too busy with RL that's one thing, but his new job not being :wtf: is no excuse. Come on, @snoofle, post the good stuff you've been holding out!

  • (disco) in reply to ben_lubar
    ben_lubar:
    I think you missed the Assert(2 == -0.5);
    I think you missed that there are two possible meanings of "inverse".
  • (disco) in reply to Scarlet_Manuka

    Wiktionary only lists one for math. It's not the one that is implied by "fast inverse square root", but at least you're wrong about there being two of them.

  • (disco) in reply to ben_lubar
    ben_lubar:
    It's not the one that is implied by "fast inverse square root"
    Yes it is: "fast inverse square root" refers to the multiplicative inverse, which is covered by the Wiktionary definition and even features in the sample sentence.

    It's also the definition used in @grkvlt's post, but there it was used in reference to the square root operation.

    The Wiktionary definition is the general case, of which there are two more or less reasonable interpretations in the context of the term "inverse square root" (one, admittedly, somewhat more reasonable than the other).

    Really, though, it should have been called "fast reciprocal square root"; then there would be less scope for (creative) confusion.

  • (disco)

    When I started programming on ZX Specturm, there was no internet, no books (they were not alloweb into East Europe totalitarian countries), no people around. You have to figure everything out yourself. Some pirated games and programs from the black market and you could start trying. Later, on the first PC, there was still no internet, no books, no sources. And even with that, I was doing computer graphics and trying to do 3D seen in Doom! Today programmers? Just Google it. No Google? Get a book. No book? Impossible! Lazy stupid people, the interviewer was right! You can get good sqrt aproximation just with brute force numeric method, if everything else fails!

  • (disco) in reply to martin

    In Soviet Eastern Europe, sqrt() roots you!

    ... or something. I think I'm Doing It Wrong.

  • (disco) in reply to martin
    martin:
    When I started programming on ZX Specturm, there was no internet, no books (they were not alloweb into East Europe totalitarian countries), no people around.

    Did you at least have the Speccy's manual? That was actually a really good document. I wore mine out… :cry:

  • (disco) in reply to martin
    martin:
    You can get good sqrt aproximation just with brute force numeric method, if everything else fails!

    Heh.

    double sqrt(double val)
{
    double retVal = 0.0001;
    while (retVal * retVal < val)
    {
        retVal += 0.0001;
    }
    return retVal;
}
  • (disco) in reply to mott555
    martin:
    You can get good sqrt aproximation just with brute force numeric method, if everything else fails!
    mott555:
    Heh.

    Congratulations on a method which adds to the pile of fail. ;)

    Here's something which about works.

    float sqrt(float x) {
    float y = x /= 2;
    y -= y / 2 - x / y;
    y -= y / 2 - x / y;
    y -= y / 2 - x / y;
    y -= y / 2 - x / y;
    return y;
}

    TRWTF is the highlighter deciding that float isn't always a keyword, but that y sometimes is…

  • (disco) in reply to dkf

    So, the Newton-Raphson method people were hinting at? It looks elegant enough to work (i.e. simplified for stability and an initial guess which is well enough) but did you do it without looking up anything at all?

  • (disco) in reply to dkf

    This is like one of those math gotcha algorithms, that some genius mathematician invents and us grubby engineers / handymen just implement without asking too many questions.

    I did a binary search algorithm solution, but closed the fiddle before I realized this would turn into a coding epeen contest.

  • (disco) in reply to cartman82
    cartman82:
    before I realized this would turn into a coding epeen contest.

    YMBNH

  • (disco) in reply to JBert
    JBert:
    So, the Newton-Raphson method people were hinting at?

    It's simplified form of 5 rounds of Newton-Raphson with an initial guess of 1 (which makes the first round spit out x/2). It actually works pretty well because this particular sequence converges fast; I think it's several decimal digits per iteration, which is very zippy indeed. I forget where I read that it's a very fast convergence. :smiley:

    Each round is actually this: xn+1 = xn - (xn2 - y) / (2xn)

    That is, using a suitable function with a root at the value you want — in this case x2 - y — you get the next value in the sequence by subtracting the evaluation of the function divided by the evaluation of the first-order differential of the function. This particular form was known to Babylonians, but the generalisation was invented by Newton. Just how well things apply depends on a whole bunch of things: it gets complicated and you can jump down the Wikipedia rabbit hole yourself…

  • (disco) in reply to dkf
    dkf:
    float y = x /= 2;

    It's early-ish for us left-ponders...

    What in heck does that do?

    Looks for coffee..

    Filed under: That don't look like no FORTRAN to me, Pilgrim.

  • (disco) in reply to ijij
    ijij:
    What in heck does that do? 
    y = x;
x = x / 2;

    IIRC anyway.

  • (disco) in reply to accalia

    Other way round, at least in C#

    float x = 2;
float y = x /= 2;

Console.WriteLine("x = {0}", x);
Console.WriteLine("y = {0}", y);
Console.ReadKey();

    output:

    x = 1
y = 1

    Assign to y, the value of x/=2

  • (disco) in reply to Jaloopa
    Jaloopa:
    Other way round, at least in C#

    ah, so i missrememered.

  • (disco) in reply to accalia

    Either way, it's a horrible way to write it, due to exactly this confusion

Leave a comment on “Classic WTF: Trouble With Founders, the Lost Candidate, and More”

Log In or post as a guest

Replying to comment #:

Log Out

« Return to Article