The Daily WTF: Curious Perversions in Information Technology

2012-11-08 Reply Admin

I don't see the WTF in this. I was expecting a hate filled life threatening coffee disrupting termination mail reply. Instead all I got to see was a professional response.

2012-11-08 Reply Admin

Whats wrong with the code? Works for all my testcases.

2012-11-08 Reply Admin

It's his loss for not hiring such a brillant programmer as Boris.

2012-11-08 Reply Admin

Perhaps Float would have been better?

2012-11-08 Reply Admin

Clearly the WTF is to keep asking Boris to submit code when there is already more then enough to base a decision on. Right?

PedanticCurmudgeon · 2012-11-08 Reply Admin

Doctor_of_Ineptitude:
I don't see the WTF in this. I was expecting a hate filled life threatening coffee disrupting termination mail reply. Instead all I got to see was a professional response.

Actually, the WTF is Phil, whose take-home assignment only measures the candidate's ability to use google.

2012-11-08 Reply Admin

PedanticCurmudgeon:
Doctor_of_Ineptitude:
I don't see the WTF in this. I was expecting a hate filled life threatening coffee disrupting termination mail reply. Instead all I got to see was a professional response.
Actually, the WTF is Phil, whose take-home assignment only measures the candidate's ability to use google.

Maybe this story was from a time before Google?

Heck, how did people like Boris kept themselves from starving back then?

2012-11-08 Reply Admin

And if they fail to do that, is it really worth going on? It's not a bad test.

They don't use google and produce bad code. Fail.
They don't use google but manage to produce (potentially weak) code that solves the problem. Pass.
They use google and still produce bad code. Fail.
They use google and come up with a good solution. Pass.

You can then test them further if you want to, but it gives a good baseline of their ability to solve a problem. They either know the subject area already, or research it to find the solution. Either way, if they solve the problem with good code then they are on the right path.

PedanticCurmudgeon · 2012-11-08 Reply Admin

the beholder:
PedanticCurmudgeon:
Actually, the WTF is Phil, whose take-home assignment only measures the candidate's ability to use google.
Maybe this story was from a time before Google?
Heck, how did people like Boris kept themselves from starving back then?

Not sure if troll or comprehension fail.....

Remy Porter · 2012-11-08 Reply Admin

If someone gave me this "homework", the first thing I'd ask would be, "Do you just want a naive implementation, or should I use a more efficient algorithm? If you want the simple approach, I could rip that out right now."

dkf · 2012-11-08 Reply Admin

PedanticCurmudgeon:
Actually, the WTF is Phil, whose take-home assignment only measures the candidate's ability to use google.

Doesn't matter. It's worked perfectly in this case, in that while Boris's first attempt was just rather poor, his second band-aid around it was stunningly bad and a clear demonstration that he shouldn't be hired.

Except by whichever place maintains phpMyAdmin. Boris would definitely raise standards there.

2012-11-08 Reply Admin

PedanticCurmudgeon:
Doctor_of_Ineptitude:
I don't see the WTF in this. I was expecting a hate filled life threatening coffee disrupting termination mail reply. Instead all I got to see was a professional response.
Actually, the WTF is Phil, whose take-home assignment only measures the candidate's ability to use google.

You are right! That will be a massive problem when you hire him and he's not allowed an internet connection!

2012-11-08 Reply Admin

i can be simple and inefficient

function isPrime($val) {
	for ($i = 2; $i < $val; $i++) {
		if( $val % $i == 0 ) {
			return false;
		}
	}
	return true;	
}

Remy Porter · 2012-11-08 Reply Admin

You can make it slightly more efficient by breaking the loop at $val / 2, since you've already divided by 2 by the time you get there.

2012-11-08 Reply Admin

Remy Porter:
You can make it slightly more efficient by breaking the loop at $val / 2, since you've already divided by 2 by the time you get there.

Actually you only need to iterate to the squareroot of $val.

2012-11-08 Reply Admin

Remy Porter:
You can make it slightly more efficient by breaking the loop at $val / 2, since you've already divided by 2 by the time you get there.

You can make it FAR more efficient by using the square root. Anything larger than that would have to be multiplied by something smaller than that, which you would have already tested.

2012-11-08 Reply Admin

Before you star developers are all going to show us minor gods how it is done... i did what any sane programmer would do and searched the internet for an answer.

All i found was inefficient code. Well it is better than no code at all

2012-11-08 Reply Admin

Remy Porter:
You can make it slightly more efficient by breaking the loop at $val / 2, since you've already divided by 2 by the time you get there.

And by slightly, we mean REALLY slightly. The classic first improvement is to stop at sqrt($val). It starts to get more interesting after that.

2012-11-08 Reply Admin

urza9814:
Remy Porter:
You can make it slightly more efficient by breaking the loop at $val / 2, since you've already divided by 2 by the time you get there.

You can make it FAR more efficient by using the square root. Anything larger than that would have to be multiplied by something smaller than that, which you would have already tested.

Test the oddity and start 3 and add increase by 2 each time.

Or am I wrong with this? Should't it about double efficiency?

I'm just a noob though...

Cbuttius · 2012-11-08 Reply Admin

I think giving a programming exercise is a much better idea than judging by ability to answer well in an interview situation.

The real WTF is that the programming exercise was not the first step. There were probably many candidates who were rejected at the CV stage who would have passed that test easily.

Remy Porter · 2012-11-08 Reply Admin

Even better. I was napkinning in my head- the last time I wrote a prime number function was in high school. I've read up on some of the more interesting algorithms, but I couldn't implement one without further research.

Cbuttius · 2012-11-08 Reply Admin

why has nobody posted yet that the real WTF is PHP?

2012-11-08 Reply Admin

Cbuttius:
why has nobody posted yet that the real WTF is PHP?

Because that one is too obvious?

Still, PHP instead of C... Doctored CV?

Cbuttius · 2012-11-08 Reply Admin

And once when I wrote one, I tested if the number was greater than 5. Then tested divisbility only for numbers with mod 30 that were:

1, 7, 11, 13, 17, 19, 23, 29

so only 8 numbers out of every 30.

Incidentally I have my own formula for calcuating if numbers are prime, which I usually use for 4 digit numbers and it involves performing modulo arithmetic by certain numbers, then resolving as a difference of two squares. If the number can be resolved as such a way it is not prime, if it cannot then it is.

Example number 4769. We normally test divisibility first by 2, 3, 5, 7, 11 and 13. You can go a bit further with the normal method. In any case it is clear that the number is not divisible by 2, 3 or 5. With regards to the next 3 we can reduce with the 1001 rule, so we reduce to 765 which we can quickly deduce is not divisible by any of those 3.

Now we look at the modulo arithmetic of the number.

8 mod 9. That means it would be the difference of a number divisible by 9 and one whose square is 1 mod 9. In any case we normally look at the upper number in the difference, so we are looking for a number divisible by 3.
1 mod 8. So the upper number must be odd.
4 mod 5. Upper number may be divisible by 5, otherwise we can go further and say its 12 or 13 mod 25. Quite a reduction.
2 mod 7. Squares mod 7 are 0, 1, 2, 4 so the number must square to a 2 or a 4. That means it cannot be divisible by 7 or 1 or -1 mod 7.

Looking at the square root of the number we have, it's above 69.

The first number that passes all our tests is 75, then 87, then there are none until 135.

5625-4769 is 856 which isn't square. The square root of this value is around 29 so we can already say we've resolved all possibly prime factors up to 41.

87 squared is 8100-540+9 = 7569. Subtract 4769 and you get 2800 which isn't square either. Now we've got a bit further though, sqrt(2800) is approximately 53 so solved up to 34. Ok not much progress, only ruled out 37.

However our next effort is 135:

135 squared is 18225. Subtract 4769 is 13456, and we can actually work out this is 116 squared... So we've found the solution, 4769 is divisible by 19 (multiplied by 251, the sum of 135 and 116).

2012-11-08 Reply Admin

Phil here; the interview took place around 2000 so Google were around but not quite as pervasive as they are today. My expectation was that he would use Google or similar to discover what algorithms are out there and then implement one or more of them.

I actually had drawn on my own prior experience of a telephone interview where my prospective employer was in a different country. I was quite inexperienced and didn't have much to show as sample code so they asked me to submit an implementation of a test for primeness. I thought this was quite a good assignment as there is an easy solution (sieve of Eratosthenes) and then various more complex but efficient solutions.

In my case, I got an implementation of "sieve" working quite quickly and then got to work on another algorithm from Applied Cryptography (I don't remember the name). My submission included both implementations with an explanation of each including a reference to Applied Cryptography which I thought would impress them (it turned out the interviewer hadn't heard of Bruce Schneier despite being in the crypto field, wtf!)

In the end, they didn't offer me the job but I thought I'd keep it in mind as a good programming assignment to test if someone is:

capable of implementing a basic algorithm
inclined to do a bit of research (googling) to see if there is something better out there

Anyway, Boris failed miserably but I wanted to have a rock solid case against hiring him as others in the company were keen to get him in regardless so that's why I gave him a second chance. What's missing from the story is that after my response to his second submission, he asked if the work would be billable; that was when we asked him (nicely) to please go away.

2012-11-08 Reply Admin

Hum, you realize that making an efficient prime number detector for all possible values is currently impossible. The difficulty of finding prime numbers is what makes RSA secure after all... Okay, one guy claimed to have solved it, but his proof takes a hundred pages and is still under review :

http://www.scientificamerican.com/article.cfm?id=proof-claimed-for-deep-connection-between-prime-numbers

2012-11-08 Reply Admin

I though the real WTF was that his checkInteger implementation is O(n) (if I read the PHP correctly).

2012-11-08 Reply Admin

If I remember correctly, the algorithm in Applied Cryptography is a fast way of getting what is probably the right answer as long as you can stand a few false negatives (so it might tell you that your prime number isn't prime but not vice versa). I could be wrong, it's a long time ago and I have never had to look at it since.

2012-11-08 Reply Admin

"Hum, you realize that making an efficient prime number detector for all possible values is currently impossible."

No, factorizing* prime numbers is what is neigh-on impossible. Determining if any given number is a prime is very much possible.

"Prime Factorization" is finding which prime numbers multiply together to make the original number.

2012-11-08 Reply Admin

Rnd(:
urza9814:
Remy Porter:
You can make it slightly more efficient by breaking the loop at $val / 2, since you've already divided by 2 by the time you get there.

You can make it FAR more efficient by using the square root. Anything larger than that would have to be multiplied by something smaller than that, which you would have already tested.

Test the oddity and start 3 and add increase by 2 each time.

Or am I wrong with this? Should't it about double efficiency?

I'm just a noob though...

Using square root of the number as a limit makes a big difference when the prime candidates starts to grow.

Take the number 99999997 as an example. Say you only check odd number until you reach number/2. You have now tested about 25 million numbers and you know you found a prime! However, if you use square root as a limit you only need to test about 10000 numbers. Of course you only need to check the odd ones so then you are down to 5000.

2012-11-08 Reply Admin

b_russel:
I though the real WTF was that his checkInteger implementation is O(n) (if I read the PHP correctly).

Yeah, I was about to say that just his checkInteger() function should have been more than enough to disqualify him as it is possibly the least efficient way of calculating it. Even if you ignore native PHP methods for determining type (is_int() comes to mind), you could write an integer checker much more simply by just doing this:

function checkInteger( $num ) {
  return ($num % 1 === 0);
}

or

function checkInteger( $num ) {
  return (floor($num) === $num);
}

or

function checkInteger( $num ) {
  return ((int) $num === num);
}

or

...

2012-11-08 Reply Admin

The nice thing about recursion is that you get to use recursion.

I, too, was recently given the prime number test during an interview. Well the last time I did that was 32 years ago in Fortran. And I usually don't write code on a whiteboard with someone watching me. I'll stub out the structure (loops etc.) then go back and fill in the details.

So, anyway, I didn't get the job. Never mind that I could have helped them secure their website, and the guy they hired apparently can't, because it is still penetrable. At least he could rattle off an algorithm during an interview.

Claxon · 2012-11-08 Reply Admin

It makes you wonder how people can avoid thinking "Hmmm, determining if a number is an integer. I wonder if anyone has done this before?"

He could have HALVED the amount of code just by using PHP's is_int() function.

That's enough of a reason to stop reading and fail his test right there.

2012-11-08 Reply Admin

This smacks of someone who had too much math and not enough sense. The "beauty" of integers is that you can define an almost-infinite sequence of them recursively with only the postulates of "one" and "plus". So, naturally, that's how he tested whether the input was a member of the set of integers.

2012-11-08 Reply Admin

Anonymous:
Rnd(:
urza9814:
Remy Porter:
You can make it slightly more efficient by breaking the loop at $val / 2, since you've already divided by 2 by the time you get there.

You can make it FAR more efficient by using the square root. Anything larger than that would have to be multiplied by something smaller than that, which you would have already tested.

Test the oddity and start 3 and add increase by 2 each time.

Or am I wrong with this? Should't it about double efficiency?

I'm just a noob though...

Using square root of the number as a limit makes a big difference when the prime candidates starts to grow.

Take the number 99999997 as an example. Say you only check odd number until you reach number/2. You have now tested about 25 million numbers and you know you found a prime! However, if you use square root as a limit you only need to test about 10000 numbers. Of course you only need to check the odd ones so then you are down to 5000.

Pretty much meant further optimisation. There is a why more tricks I think, but at some point it's better to move to some more specialised algorithms.

Anyway anyone got prime test which uses no extra memory or minimal amount of it?

2012-11-08 Reply Admin

Hey, if it passes the test cases it's production code. Ship it!

Any post-launch issues can be dealt with by the bug fixers. We could probably even charge extra for the performance upgrade.

2012-11-08 Reply Admin

Rnd(:
Pretty much meant further optimisation. There is a why more tricks I think

Some speak confuse not born country language maybe translation google mud said him meant?

2012-11-08 Reply Admin

He may still be learning indentation but at least he's consistent with his use of:

} else {

Now if I could only figured out what he hoped to accomplish with:

" \n");

2012-11-08 Reply Admin

Phil:
What's missing from the story is that after my response to his second submission, he asked if the work would be billable; that was when we asked him (nicely) to please go away.

Ah, Boris was actually demonstrating his ability to do consulting in the real world. On the 3rd or 4th time upgrading this function, after much time billed and wasted, he would then give you something that worked. I bet Boris went far.

Cbuttius · 2012-11-08 Reply Admin

A lot depends on whether you want to test just one number of primeness or build a machine that will test the primeness of many numbers.

To do the latter, build a prime number table.

To build a prime number table up to N, mark every cell with itself. You can of course make the table size N-1 as we don't test 0 or 1 for primeness.

Take the first prime number which is 2. You now mark every product of 2 with the number 2. Next is 3: You know this is prime because it's still marked with a 3. You jump to its square and mark every 3rd number that currently has itself as the value with a 3.

4 is marked as non-prime so continue with 5.

Once we get to a value where the square is beyond N we stop and we have our prime number table. Then constant time to check if a number it contains is prime or not.

If we want to check the primeness of a number beyond the table, we at least know what the primes are so we know what values to try modding it by, so more efficient in those numbers too.

2012-11-08 Reply Admin

Phil:
If I remember correctly, the algorithm in Applied Cryptography is a fast way of getting what is probably the right answer as long as you can stand a few false negatives (so it might tell you that your prime number isn't prime but not vice versa). I could be wrong, it's a long time ago and I have never had to look at it since.

So, you check if Fermat's Little Theorem holds for the possible prime with a few candidates. If not, it fails. If so, then it starts to look like it might be prime.... http://en.wikipedia.org/wiki/Primality_test

In crypto, you are usually just looking for SOME prime number, not a definite statement about a particular number. In that case, a false negative usually not a problem.

2012-11-08 Reply Admin

Claxon:
He could have HALVED the amount of code just by using PHP's is_int() function.

Bear in mind that the candidate proclaimed to have little or no knowledge of PHP, and was only using that language to expand his programming abilities; a very commendable effort in and of itself.

Not to mention, this was 2000; PHP 4 (which first included is_int() and is_numeric()) was released only halfway through that year, so he may have well used PHP 3.

Last but not least: those of us working with PHP for a long time know that the language can do pretty much anything for you, natively. But people used to languages like C start of with the assumption that by default your language has about two tools, and everything else needs to be loaded from libraries. After a while, a PHP's programmer first instinct when faced with a new problem will be to search if there is a default function available to do that, but it takes time before that mindset is achieved.

2012-11-08 Reply Admin

Remy Porter:
If someone gave me this "homework", the first thing I'd ask would be, "Do you just want a naive implementation, or should I use a more efficient algorithm? If you want the simple approach, I could rip that out right now."

That's a very important thing to do. I have a friend that when asked to do the Fibonacci Sequence, proceeded to quickly work out the closed form expression and coded that. This confused the interviewers to no end.

PedanticCurmudgeon · 2012-11-08 Reply Admin

Phil:
Anyway, Boris failed miserably but I wanted to have a rock solid case against hiring him as others in the company were keen to get him in regardless so that's why I gave him a second chance.

So TRWTF was left out of the article entirely. How typical.

2012-11-08 Reply Admin

Tom:
Rnd(:
Pretty much meant further optimisation. There is a why more tricks I think
Some speak confuse not born country language maybe translation google mud said him meant?

I got to code some C so I obfuscate my comments ;D Just use preprocessor to remove why ;D

2012-11-08 Reply Admin

checkDouble(-0.5) .. thinking ...

2012-11-08 Reply Admin

For the job I'm at, I had a similar experience - after the usual silly discussion questions, they gave me a couple really small programming questions, that I think I did a decent job of. Then they asked me a larger one - convert an int to its roman numeral expansion (or possibly the reverse, I forget, it was a while ago). That is the sort of problem domain I would not have had any reason to be an expert in before being asked to solve it, and my first response in a real scenario would clearly be visiting wikipedia for what the full rules of roman numerals even were. I had to ask a bunch of questions. So they said just go home, write it and email it. Interview ended at around 5 PM, I had it to them by 8 the next morning. It definitely would not have been nearly such a nice experience if I'd had to do the whole thing writing on a whiteboard with no internet.

Giving a whole week seems needlessly nice, though.

hikari · 2012-11-08 Reply Admin

I don't mind questions like this, so long as they're not "and do it right now in the interview" ones.

I think I would have just gone and looked up an algorithm on-line or in one of my books - one of them is bound to have one in - and then implemented it.

I have a similar reaction to interviews as the candidate in the story; I end up talking in a muted whisper, sweating, and shaking. Sometimes in life I get lucky and interview with people who can see through this (like my current employers). Having people who are willing to make effort to interview people like us makes me really rather appreciative.

DCRoss · 2012-11-08 Reply Admin

Anonymous:
Take the number 99999997 as an example. Say you only check odd number until you reach number/2. You have now tested about 25 million numbers and you know you found a prime! However, if you use square root as a limit you only need to test about 10000 numbers. Of course you only need to check the odd ones so then you are down to 5000.

If you want to get picky, you only need to check the factors which are prime themselves. As long as you have a fresh supply of interview candidates and undergrad students to provide you with lists of primes that cuts it down further to just over 1000.

Cbuttius · 2012-11-08 Reply Admin

Anonymous:
Take the number 99999997 as an example. Say you only check odd number until you reach number/2. You have now tested about 25 million numbers and you know you found a prime! However, if you use square root as a limit you only need to test about 10000 numbers. Of course you only need to check the odd ones so then you are down to 5000.

Or I might get as far as 1297 and discover that it is not prime. (1297 * 77101)

The Prime Candidate

Leave a comment on “The Prime Candidate”