- Feature Articles
- CodeSOD
- Error'd
-
Forums
-
Other Articles
- Random Article
- Alex's Soapbox
- Announcements
- Best of…
- Best of Email
- Best of the Sidebar
- Bring Your Own Code
- Coded Smorgasbord
- Mandatory Fun Day
- Off Topic
- Representative Line
- News Roundup
- Editor's Soapbox
- Software on the Rocks
- Souvenir Potpourri
- Sponsor Post
- Tales from the Interview
- The Daily WTF: Live
- Virtudyne
Admin
I don't know if you are trolling or not, but for the record:
Use NOR gates.
Admin
Admin
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.
Admin
You do know that square roots tend to be irrational, yes?
Admin
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!
Admin
Yucks, I forgot toe mention this in my previous comment...
Captcha: haero : he who saves the day
Admin
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:
Admin
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.
Admin
Admin
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.
Admin
How horrifying, he asked a developer to compose an algorithm! What will be next - telling that there are no method WebSite.CreateEnterpriseWebSiteWithDatabaseAndEverytnig()
Admin
Ok, we have 4 solutions to get the square root.
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).
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.
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.
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.
Admin
they don't have log and exp? log, divide by 3, exp...
cube itself is monotonic but cubics in general are not.
Admin
"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"
Admin
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).
Admin
+NaN
I said "+NaN" but Akismet complained.
Admin
Admin
Admin
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
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
Admin
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.
Admin
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.
Admin
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.
Admin
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.
Admin
asm { FSQRT }
Admin
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.
Admin
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?
Admin
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.
Admin
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?
Admin
At present this has generated the most comments since 10 July when this: Just A Warm Up was the WTF of the day.
Admin
Your mind truly works in mysterious ways.
What is “a heavy unit-test guy”, and how is my being so (or not) relevant?
Admin
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.
Admin
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.
Admin
FTFY
Admin
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.
Admin
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)); }
Admin
Quit being so irrational!
Admin
Shouldn't that be: double guess = (upper + lower) / 2 + lower; ?
Admin
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.
Admin
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.
Admin
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.
Admin
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.)
Admin
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.
Admin
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.
Admin
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".
Admin
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....
http://www.dailytexanonline.com/university/2012/04/17/siri-technology-may-be-future-data-analytics
Admin
Yeah mannn. No one would ever use Siri for Data Analytics mannnnn.
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.
Admin
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".
Admin
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).
Admin
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.
Admin
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.