• captcha:augue (unregistered)

    So you got experience with C and embedded systems? Great, you're the perfect candidate for our PHP job!

    The other way around would be a much bigger WTF of course, but it's still a waste of a low-level programmer.

  • (cs) in reply to neminem
    neminem:
    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.

    Roman numerals give you fun problems anyway. There's never been a formal way of writing them; clocks, for example, tend to use IIII for 4, whereas people will tend to write it as IV.

  • Tim (unregistered)

    Well obviously he should have called out to a web service using XML. There must be one somewhere that can tell you if a given number is prime.

    Just hope it isn't encrypted over https. Because in setting up the crypto you'll probably need some prime numbers! Recursion lurks wherever you look. If you don't see it at first, look closer.

  • Caesar (unregistered) in reply to hikari
    hikari:
    Roman numerals give you fun problems anyway. There's never been a formal way of writing them; clocks, for example, tend to use IIII for 4, whereas people will tend to write it as IV.
    Roman numerals were invented by people who had to chisel them in stone. There's no way you'd chop away at "IIII" when you could simply do "IV".
  • David F. Skoll (unregistered)

    When asked to prove that all odd numbers greather than two are prime:

    The mathematician said: "3 is prime, 5 is prime, 7 is prime, ... and so on."

    The engineer said: "3 is prime, 5 is prime, 7 is prime, 9 is experimental error, 11 is prime..."

    The arts major said: "What does 'prime' mean?"

  • (cs)

    Man, why are we fiddling with all this Mersenne stuff?! According to him we can have 100,000 digit primes just by checking MOD 2, 3, 5 and 7!

  • Joe (unregistered) in reply to hikari
    hikari:
    Roman numerals give you fun problems anyway. There's never been a formal way of writing them; clocks, for example, tend to use IIII for 4, whereas people will tend to write it as IV.
    Yes, which is why I write all my algorithms to accept input in "Simplified Roman Numerals"-- None of this "VXLCM" nonsense, just give me "IIIIIIIIIIII" for 12.

    It also has the benefit of making those pesky NP-hard problems run in polynomial time (of the length of the input)

    --Joe

  • (cs) in reply to JC
    JC:
    No, factorizing* prime numbers is what is neigh-on impossible.

    No, factorising prime numbers is very easy ... by definition, the sole factor is the number itself. It's factorising large NON-prime numbers that gets tricky, and that's the bit that's needed for breaking public-key crypto systems like RSA.

  • (cs)

    PHP is an extendable language. Knowledge of C would be good because you can write your extensions in it.

  • (cs)

    At least he was honest. His crap code DOES represent his work very well.

  • (cs) 
    boolean isPrime(long val) {
     return BigInteger.valueOf(val).isProbablePrime(1000);
}

    Done?

  • Mike (unregistered)

    I think everyone is missing the point.

    It doesn't really matter if the prime test is correct. This is an interview to see if the guy can code. So judge the code, not the algorithm. There is plenty of evidence in the first sample (which worked for a small set of numbers) that the coding is sloppy and misguided.

    Only if the code is good should you even consider looking at if the algorithm is good.

    My other thought was, even if they guy's code was great, would you hire him after such a bad interview? If his code was great, and you turned him down, you could be in a whole lot of bother if he challenged the decision any the grounds of any form of discrimination he chooses as your only hard evidence is a good piece of code!

  • verisimilidude (unregistered)

    if (($Number > 0) AND ($Number < 1)) { return (FALSE) } else { return (TRUE) }

    I see his level of expertise right there. If he can't do

    return ($Number > 0) AND ($Number < 1)

    then his code it too wordy for consideration.

  • JJ (unregistered) in reply to JC
    JC:
    No, factorizing* prime numbers is what is neigh-on impossible.
    Said the horse.
  • Not Badinoff (unregistered) in reply to PedanticCurmudgeon
    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.
    And yet, somehow, Boris failed even by those anemic standards.

    The real WTF is the apparent lack of WTF punchline. I mean, Boris' "homework" answer approaches CodeSOD levels, but it was rejected along with Boris, yielding an uncharacteristically happy ending for everyone except Boris.

    WTF?

  • minimus (unregistered) in reply to verisimilidude
    verisimilidude:
    if (($Number > 0) AND ($Number < 1)) { return (FALSE) } else { return (TRUE) }

    I see his level of expertise right there. If he can't do

    return ($Number > 0) AND ($Number < 1)

    then his code it too wordy for consideration.

    And we see yours...

  • Daniel (unregistered)

    I was looking at some code I wrote a few years ago and testing for 2, 3, 5 & 7 are sufficient... if your using SPRP (Strong Probable Prime) instead of modulus.

    If n < 25,000,000,000 is a 2, 3, 5 and 7-SPRP, then either n = 3,215,031,751 or n is prime. This covers all unsigned 32 bit integers.

    int Prime (unsigned n) { if (n == 3215031751) return FALSE; if (n <= 10) { return (n == 2) || (n == 3) || (n == 5) || (n == 7); } if ((n % 2) == 0) return FALSE; return b_SPRP (n,2) && b_SPRP (n,3) && b_SPRP (n,5) && b_SPRP (n,7); }

    Sources: http://primes.utm.edu/prove/prove2_3.html http://www.olivierlanglois.net/archive/prime_cpp.htm

    And yes, I am the Daniel fixed a bug in the second link.

  • (cs) in reply to hire me
    hire me:
    i can be simple and inefficient 
    function isPrime($val) {
	for ($i = 2; $i < $val; $i++) {
		if( $val % $i == 0 ) {
			return false;
		}
	}
	return true;	
}
    Way too long.

    % R

    library(gmp) isprime(37) 1 isprime(100) 0

  • (cs)

    TRWTF is interviewing Boris instead of Natasha.

  • lmm (unregistered) in reply to cellocgw
    cellocgw:
    TRWTF is interviewing Boris instead of Natasha.
    ITYM Nataliya.
  • (cs) in reply to lmm
    lmm:
    cellocgw:
    TRWTF is interviewing Boris instead of Natasha.
    ITYM Nataliya.
    Ya not familiar with Moose and Squirrel?
  • (cs) in reply to DCRoss
    DCRoss:
    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.

    The tough part is that you get into recursion checking if the number is prime inside the loop. More efficient to just run the modulus test.

  • (cs) in reply to cellocgw
    cellocgw:
    TRWTF is interviewing Boris instead of Natasha.

    Doris?

  • Elron the Fantastic (unregistered) in reply to Anonymous

    99999997 is not prime.

    1297 * 77101 = 99999997

    You sir, fail at prime numbers.

  • (cs) in reply to Not Badinoff
    Not Badinoff:
    The real WTF is the apparent lack of WTF punchline. I mean, Boris' "homework" answer approaches CodeSOD levels, but it was rejected along with Boris, yielding an uncharacteristically happy ending for everyone except Boris.

    WTF?

    But imagine if Boris had enough google skills to find an implementation and copy it. He would have been hired despite his obvious inability to code his way out of a paper bag.

    Actually, the real WTF was given by Phil in one of his comments. Phil's colleagues wanted to hire Boris anyway.

  • (cs) in reply to Elron the Fantastic
    Elron the Fantastic:
    99999997 is not prime.

    1297 * 77101 = 99999997

    You sir, fail at prime numbers.

    I had already pointed that one out at the end of page 1.

  • C-Derb (unregistered)

    TRWTF was Boris being "eager to gain experience in" PHP.

  • Elron the Fantastic (unregistered) in reply to Cbuttius

    Well, that's what I get for not refreshing the comments page...

    Captcha: abico. I abico any responsibility for my failure to properly read all comments.

  • instigator (unregistered) in reply to the beholder

    Presentation matters. A bad programmer can still get a job(depending on who's hiring). And, companies without engineering talent can succeed if they have presentation skills (obviously by ripping their customers off).

  • (cs) in reply to Elron the Fantastic
    Elron the Fantastic:
    Well, that's what I get for not refreshing the comments page...

    Captcha: abico. I abico any responsibility for my failure to properly read all comments.

    This is why, if there are 40+ comments, I wait until there are 50 to add mine. Posts don't exist if they're below the fold.

  • (cs) in reply to chubertdev
    chubertdev:
    Posts don't exist if they're below the fold.

    You can fold your monitor?

  • jay (unregistered)

    When I was in high school, we once had a programming contest where the problem was to write a program that would produce a list of all the prime numbers less than 100. Entries were to be judged based on accuracy, conciseness and efficiency. Namely, any programs that produced incorrect results failed. Working programs were then scored by multiplying the number of lines of code (excluding comments) by the run-time, and low score wins. (Which, by the way, I think is an excellent scoring system.)

    A friend of mine submitted a program that looked basically like this (I don't have the original listing, but this was the basic idea):

    10 PRINT "2,3,5,7,11,13,17,19,23,29,31,37,41,43,47" 20 PRINT "53,59,61,67,71,73,79,83,89,97"

    His entry had the fewest lines of code and the fastest run-time, so under the rules, he should have won. He also commented that he thought the algorithm was very easy to understand and so the program was highly maintainable. But the teachers disqualified him.

  • jay (unregistered) in reply to JC
    JC:
    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.

    I can write a function to factor a prime number very easily.

    int[] factorsOfPrime(int prime)
{
  /* Note: This function assumes that "prime" is, indeed,
  a prime number. */
  int[] factors=new int[2];
  factors[0]=1;
  factors[1]=prime;
  return factors;
}

    Perhaps you meant that factoring a composite number is very difficult? It's certainly not conceptually difficult -- you can always do it with the simple "loop through successive integers attempting to divide" method and when you get a hit, pass the quotient back in to the same function recursively. e.g. say you start with 455. Divide by 2? No. 3? No. 5? Yes, quotient is 91. So first factor is 5. Now repeat process using 91. Divide by 5? (Note we can start with the divisor that last succeeded, as we already know it's not divisible by smaller numbers.) Anyway, divide by 5? No. 7? Yes. Quotient is 13. So add 7 to list of factors. Now work on 13. We start at 7, we're already past the square root, so we're done. 13 is the last factor. Prime factorization is therefore 5713.

    Perhaps you meant that finding prime factors of very large composites in some reasonable amount of time is difficult.

  • jMerliN (unregistered) in reply to JC
    JC:
    "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.

    I don't think that's quite right. You see, if it's trivial to determine if a number N is prime, that necessarily means you know at least one factor: 1 < F < N. If this is the case, then recursively apply this test to N/F and you've trivially factored N. But because factoring N is nontrivial, it seems that this wouldn't be possible.

    This is similar to the reason why it's impossible to create a general compression algorithm that can compress N bits into N-1 bits without loss. Recursive application necessarily yields a contradiction.

  • Sam I am (unregistered)

    I am constantly amazed by how many commenters here are unable to conceive of a brute-force algorithm to solve a well-defined problem.

  • Some Guy (unregistered) in reply to Anonymous Paranoiac
    Anonymous Paranoiac:
    function checkInteger( $num ) {
  return ((int) $num === num);
}

    BAD! NO! I know that PHP is TRWTF, but you should at least know why your suggestion is wrong before you make the claim.

    A PHP variable, under the hood, is a struct that stores the base type, and the typed representations of the variable for each base type. (Yes, for each of the 6 base types: int, float, string, bool, object, and reference. The WTF is strong with PHP.)

    When you test a variable using the == operator, it evaluates the type of the lvalue to find the correctly-typed internal value of the rvalue to compare against the lvalue.

    When you test a variable using the === operator, it evaluates the type of the lvalue against the type of the rvalue, and if that matches, it then evaluates the value of the lvalue against the value of the rvalue.

    The reason your third checkInteger fails is because it coerces the type of the lvalue. When you cast (int)$num, it's creating a copy of $num, but setting its type to int. Then you're comparing type-for-type against an uncoerced $num. If $num is anything but an int already, this implementation of checkInteger will fail.

    A correctly idiot-proofed PHP function should always treat "1" the same as 1. If a PHP-hack-claiming-to-be-a-dev called checkInteger("1"), it should work correctly and return true.

    But wait! There's another WTF buried here. Since the (int)$num takes the internal integer representation from $num and makes it the "real" value of that instance of $num, then compares it to the original $num's internal integer instance, this function effectively proves nothing but identity.

    Think of PHP variables as a struct:

    struct PHPVar {
  int typeEnum;
  int intVar;
  float floatVar;
  string stringVar;
  bool boolVar;
  object objectVar;
  int* refVar;
}

    If you have one that's set up like so:

    PHPVar1 {
  typeEnum = 3; // 3 = string, for this exercise
  intVar = 1;
  floatVar = 1.0;
  stringVar = "1";
  boolVar = true;
  objectVar = null; // because a constant isn't an object
  refVar = null; // because a constant isn't a reference either
}

    When you cast it to an int, you get this:

    PHPVar2 {
  typeEnum = 1; // 1 = int, for this exercise
  intVar = 1;
  floatVar = 1.0;
  stringVar = "1";
  boolVar = true;
  objectVar = null; // because a constant isn't an object
  refVar = null; // because a constant isn't a reference either
}

    So when you compare PHPVar1->intVar == PHPVar2->intVar, you always get true, regardless of the value of either ones typeEnum.

    Repeat after me: PHP is TRWTF.

  • (cs) in reply to KattMan
    KattMan:
    chubertdev:
    Posts don't exist if they're below the fold.

    You can fold your monitor?

    Yeah, I'm pretty buff.

  • foo (unregistered) in reply to David F. Skoll
    David F. Skoll:
    When asked to prove that all odd numbers greather than two are prime:

    The mathematician said: "3 is prime, 5 is prime, 7 is prime, ... and so on."

    The engineer said: "3 is prime, 5 is prime, 7 is prime, 9 is experimental error, 11 is prime..."

    The arts major said: "What does 'prime' mean?"

    Boris said: "3 is ... an integer (and prime), 5 is ..... an integer (and prime), 7 is ....... an integer, 9 is ......... an integer. -0.5 is ............................." (and he starved)

  • foo (unregistered) in reply to Some Guy
    Some Guy:
    A PHP variable, under the hood, is a struct that stores the base type, and the typed representations of the variable for each base type. (Yes, for each of the 6 base types: int, float, string, bool, object, and reference. The WTF is strong with PHP.)
    You mean every value is converted to 5 other types (99.9% of which conversions are never used)? Please tell me that's not true! I knew PHP was a big WTF, but that beats everything. A great way to waste both memory and runtime simultaneously, and at such a fundamental level.
  • Ken B (unregistered) in reply to urza9814
    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.
    And you only need to check for divisible by 2, and then by odd numbers 3 and up. (No need to check for divisibility by even numbers other than 2.)

    I did that (mumble, mumble) years ago in junior high school.

  • Vlad Patryshev (unregistered)

    CCD, Can't Code Disease.

    Regarding foreigners and phone interviews, one of my favorite phone questions is "can you write a regex that checks if parentheses are correct in an arithmetic expression?" - and I know the right candidate when they start laughing. Mostly it happens if you call a candidate in Poland; they have an excellent education there. (Disclaimer: I've never even been to Poland.)

  • foo (unregistered) in reply to captcha:augue
    captcha:augue:
    So you got experience with C and embedded systems? Great, you're the perfect candidate for our PHP job!

    The other way around would be a much bigger WTF of course, but it's still a waste of a low-level programmer.

    Actually, by hiring him and putting him to work on a dummy PHP project that will never see the light of day, they could have done humanity a big favour. Think about it: Now Boris may go on to work on a life-support, traffic-control, airplane, nuclear-safety, etc. system that your life may one day depend on ...

    (And no, it's not possible that Boris may just be a great C/embedded programmer. Even though he won't have to checkInteger in C, there's plenty of WTFs in those code samples to make this absolutely certain.)

  • foo (unregistered) in reply to Matt
    Matt:
    This smacks of someone who had too much math and not enough sense.
    Last time I checked, math included the definition of prime numbers greater than 7.

    No, to me it smacks of someone who has much too big an ego (billable code, what?) and not enough clue of anything.

  • (cs)

    I had an interview where I had to write a prime number algorithm on a white board, in C#. Didn't do too bad at it, but not too good either. So I felt challenged, and that afternoon I went back to the drawing board.

    I wrote a single linq statement that correctly calculated the prime numbers up to some arbitrary number.

    var cnt=1000000;

    var query = (from two in Enumerable.Range(2,1) select two) .Union (from candidate in Enumerable.Range(3, cnt-2).Where(p => p % 2 != 0) select candidate).AsParallel() .Except ((from candidate in Enumerable.Range(3, cnt-2).Where(p => p % 2 != 0).AsParallel() from q1 in Enumerable.Range(3, (int)Math.Sqrt(candidate)).Where(p => p % 2 != 0).AsParallel() where q1 < candidate && candidate % q1 == 0 select candidate) .Distinct()).OrderBy(x => x);

    foreach (int i in query) Console.WriteLine(i);

  • (cs) in reply to Rnd(
    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...

    (1) Test last digit for even/odd. (2) Test last digit to determine whether divisible by 5. (3) Starting with 3, test for divisibility by numbers ending in 3, 7, 9, or 1.

    I just knocked about another 20% off your execution time. You're welcome.

  • (cs)

    ...why is nobody commenting on the fact that checkInteger and checkDouble are exactly identical.

    Boris was not just an idiot, he was a liar.

  • Computer Scientist (unregistered)

    An engineer, physicist and Computer Scientist we're asked to show whether all odd numbers were prime.

    The engineer (a bit miffed that we was being bothered with such an irrelevant problem) suggested that until someone (not him) could offer a counter example of an odd number that was not prime, we should accept that all odd numbers might be prime.

    The physicist chose some odd numbers, 3,5,7,11 and concluded that as all of these were prime, it might be a reasonable hypothesis that all odd numbers should be prime.

    The Computer Scientist (possibly Boris) went away and laboured on a a complex algorithm to determine whether a given input was Prime. He tested it extensively before declaring that all odd numbers must be prime: 3....PRIME 3....PRIME 3....PRIME 3....PRIME 3....PRIME ...

  • Jim (unregistered) in reply to PedanticCurmudgeon
    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.
    Not really. I've given similar assignments to candidates and made it clear to them that I'm happy for them to use any resources available (hell, when I don't know how to do something at work, I use Google).

    As a preliminary exercise it filters out some of the useless - and a few questions (at a subsequent interview) about how their solution works and obstacles they found in creating their program usually exposes those who understand what their program does (irrespective of whether they wrote it or copied it) and those who definitely copied it without understanding how it works. Of those who can explain how it works, it doesn't really bother me whether they made it themselves or copied someone else's directly (the fact they understand the workings is reasonable assurance that they won't blindly copy stuff that doesn't work - and may be more inclined to use in-built API's than the gung-ho developer who believes they can make a good Calendar/Date class).

    Do you want a candidate who has a limited amount of skill that will never develop, or one that is happy to teach themselves by googling for ideas?

  • Jr (unregistered) in reply to Cbuttius
    Cbuttius:
    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).

    The real WTF is working out Primes on the fly like that for each Prime.

    You use these sort of algorithms to create look-up tables. If you need to find whether a number beyond your list is prime, you can always extend it (using the same formula).

    Startup: calculate primes to 19 Eg: Test if 9 is Prime - Lookup. Test if 25 is prime - better extend list to 29 and lookup Test if 23 is prime - lookup test if 34 is prime - extend list to 37 and lookup etc....

    of course if it's a one off (or a trivial case (%2) then it might be overkill) - but in the real world nothing is ever a one-off.

  • Jack 27 (unregistered) in reply to PedanticCurmudgeon

    But the candidate failed, so score one for that assignment.

    I'd say "ability to use google" is necessary but not sufficient for most programming jobs.

    Anyway, you could use this assignment also to check coding and documentation style, unless they just copy it directly from the internet (which you should be able to discover if you also know how to use google).

Leave a comment on “The Prime Candidate”

Log In or post as a guest

Replying to comment #:

Log Out

« Return to Article