 Feature Articles
 CodeSOD
 Error'd
 Forums

Other Articles
 Random Article
 Other Series
 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
 Tales from the Interview
 The Daily WTF: Live
 Virtudyne
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.
Admin
Whats wrong with the code? Works for all my testcases.
Admin
It's his loss for not hiring such a brillant programmer as Boris.
Admin
Perhaps Float would have been better?
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?
Admin
Admin
Heck, how did people like Boris kept themselves from starving back then?
Admin
And if they fail to do that, is it really worth going on? It's not a bad test.
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.
Admin
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."
Admin
Except by whichever place maintains phpMyAdmin. Boris would definitely raise standards there.
Admin
You are right! That will be a massive problem when you hire him and he's not allowed an internet connection!
Admin
i can be simple and inefficient
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.
Admin
Admin
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.
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
Admin
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.
Admin
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...
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.
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.
Admin
why has nobody posted yet that the real WTF is PHP?
Admin
Because that one is too obvious?
Still, PHP instead of C... Doctored CV?
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.
56254769 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 8100540+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).
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:
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.
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=proofclaimedfordeepconnectionbetweenprimenumbers
Admin
I though the real WTF was that his checkInteger implementation is O(n) (if I read the PHP correctly).
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.
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 neighon impossible. Determining if any given number is a prime is very much possible.
Admin
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.
Admin
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:
or
or
or
...
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.
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.
Admin
This smacks of someone who had too much math and not enough sense. The "beauty" of integers is that you can define an almostinfinite 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.
Admin
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?
Admin
Hey, if it passes the test cases it's production code. Ship it!
Any postlaunch issues can be dealt with by the bug fixers. We could probably even charge extra for the performance upgrade.
Admin
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");
Admin
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.
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 N1 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 nonprime 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.
Admin
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.
Admin
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.
Admin
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.
Admin
Admin
I got to code some C so I obfuscate my comments ;D Just use preprocessor to remove why ;D
Admin
checkDouble(0.5) .. thinking ...
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.
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 online 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.
Admin
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.
Admin
Or I might get as far as 1297 and discover that it is not prime. (1297 * 77101)