• (cs)
    if (this) {
       if (is) {
          if (a) {
             if (comment) {
                post();
             }
          }
       }
    }
    
  • (cs)

    The real WTF is using PHP :)

  • Max (unregistered)

    Apart from using two loops rather than one loop and lots of ifs, should you do it another way?

  • illtiz (unregistered)

    The most obviousest REAL WTF is that he multiplied by 20 instead of testing for the original number having a modulo of 0 when dividing, as he did with the rest of the numbers. But then that may be a brillant optimization of this algorithm...

  • ideo (unregistered)

    Oh, my, where to start?

    OK... if it divides by 18, it divides by 9 and 6, and thus by 3 as well. Similar for 16 and 8.

  • DaStoned (unregistered)

    It's a puzzle. Programmers don't solve puzzles for work.

    I'd solve it similarly. I don't give a crap about puzzles and solving them. The computer does all the work, gives me the answer and we can all continue with more pressing matters. Brute-force is faster than coding a more intelligent algorithm.

  • Chris (unregistered)

    At least he was smart enough to not write an if to test mod 10, 5, 4, and 2, but for some reason he still tests mod 9, 8, 7, 6, and 3 which are covered by earlier cases. :P

  • sjogren (unregistered)
    foldr1 lcm [1..20]

    Go, go Haskell!

  • (cs)

    Nothing could be more wrong than that.

  • Carl T (unregistered)
    Matt:
    232792560

    First!

    Well... if that's your PHP program then you fail because there was nothing in the specifications about printing "First!". There's also the issue of maintainability - your program would need to be rewritten from scratch if the problem were changed to, say, "What is the smallest number that is evenly divisible by all of the numbers from 1 to 25?"

    I'd probably do something like this instead:

    <?php echo 2*2*2*2*3*3*5*7*11*13*17*19 ?>
    Even prettier would be to make a function that takes N (=20 or whatever) as an argument, but it seems rather pointless.

  • (cs)
    public static int LcmBetween(int start, int end) {
        int common = 1;
        for (int i = start; i <= end; i++) {
            common = Lcm(common, i);
        }
        return common;
    }
    public static int Lcm(int a, int b) {
        return a / Gcd(a, b) * b;
    }
    public static int Gcd(int a, int b) {
        return b != 0 ? Gcd(b, a % b) : a;
    }
    static int Main(string[] args) {
        Console.WriteLine(LcmBetween(1, 20));
        return 0;
    }
    

    This is not PHP, but the code should work in Java, C and others with some adjustments, and int will work for numbers between 1 and 20.

  • (cs)

    #!/usr/bin/perl $max = 201918171615141312*11; print "Max: $max\n"; $starttime = time(); LOOP: while($i+=20) { for(11..19) { next LOOP if($i%$_); } print "Min: $i\nRunning time: ".(time()-$starttime)." seconds\n"; exit(0); }

    End result:

    ~$ ./asd.pl Max: 670442572800 Min: 232792560 Running time: 6 seconds

    Reposting from the Side Bar. In an interview, I'd solve the problem 10 times out of 10 like this. Why? It's easy, readable and reliable. Also very quick to code in a stressful situation.

    Personally I don't think much of problems like this, especially if what you're looking for is magic with prime numbers. I can honestly say that in our product group we do not have a single application of prime numbers (well, I haven't read through all of the 10 million lines of code, but I'm pretty sure ;) ). Last time I used prime numbers was years back in high school. Oh, once after that when I had to talk a friend out of storing flags with primes ("Use binary!" "No, primes!"). After that I've run into primes in programming solutions and through my spouse (who's currently teaching high school math and finishing some uni courses). In general, my familiarity with primes ends with "what, 1 isn't a prime?" If I really need a prime solution (pun intended), I'll use my advanced google skills and find a nice formula which I'll test and then apply.

    I'd be interested in hearing the rest of the 20 questions (which the applicant had to answer, according to the original post) and how many of those involved prime numbers. And, of course, what applications prime numbers have in the position he was being interviewed.

  • (cs) in reply to DaStoned
    DaStoned:
    It's a puzzle. Programmers don't solve puzzles for work.

    I'd solve it similarly. I don't give a crap about puzzles and solving them. The computer does all the work, gives me the answer and we can all continue with more pressing matters. Brute-force is faster than coding a more intelligent algorithm.

    I'm terrible at solving riddles, yet I can solve fairly complex business problems (depending upon the time of day and coffee previously consumed). While perusing the problem, I usually casually ask: is this typical of the types of problems that need to be solved here?

    That (usually) gets me off the hook.

  • Stephen (unregistered) in reply to DaStoned

    Agreed... And remember interviews are stressful and artificial situations where the candidate is often wondering if the answer is simple and he/she has just failed to see it or clever - but the answer just escapes them because of nerves.

    The real WTF is that anyone would give this problem to a programmer at an interview.

  • Jirah (unregistered)

    guiltily raises hand

    Yeah, I solved it that way too (neatly nested if and mods in PHP)

    It's not elegant, but it took all of 90 seconds to type.

  • NShadeIV (unregistered)

    function f(n) { define h as hashtable for i = 2 -> n { break i into a product of primes for each prime in product { h[prime] = max(power, h[prime]) } }

    answer = 1 for each prime -> power in h { answer *= prime^power } }

    // f(20) = 232792560

  • (cs)

    Shouldn't this article be green?

  • complete looney (unregistered)

    Generic answer;

    1. find the prime factors of each number from 1-N

    2 = 2 3 = 3 4 = 2^2 5 = 5 6 = 23 7 = 7 8 = 2^3 9 = 3^2 10 = 25 11 = 11 12 = 2^23 13 = 13 14 = 27 15 = 35 16 = 2^4 17 = 17 18 = 3^22 19 = 19 20 = 2^2*5

    1. count the maximum number of times each prime appears in each factorization
    2. raise each prime to the power of that maximum number and multiply the answers together

    2^43^257111317*19 = 232792560

    A slightly simpler solution to code might be to multiply the primes together (=9699690), then multiply that answer by 1-M until you found a result that had no remainder (in this case M=24). But for a large value of N that might take a while.

  • JoeSmoe (unregistered)

    What kind of stupid interview question is this? How does this help test that the person truly has 10 years of PHP? What business application does this have? Unless the person is interviewing for a job that requires common use of prime number calculation, the real WTF was the interview question rather than the answer.

  • (cs) in reply to DaStoned
    DaStoned:
    It's a puzzle. Programmers don't solve puzzles for work.

    But some programmers solve puzzles at work; e.g. when they're too much bored with their work.

  • Anonymous (unregistered)

    This is what you call simple programming task?

  • (cs) in reply to Anonymous
    Anonymous:
    This is what you call simple programming task?

    Yes.

  • James (unregistered)

    at least it's indented properly

  • jDeepBeep (unregistered)

    I give the coder points for artistic value. Why, if you squint a little, it looks like a formation of geese flying south.

  • Anonymous (unregistered)

    I think TRWTF is that the guy started his program from 1, instead of 2520 when the problem clearly states:

    "2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder."

    Obviously, when considering 1-20, the smallest number is not going to be anything smaller than 2520 ><

  • (cs) in reply to jDeepBeep
    jDeepBeep:
    I give the coder points for artistic value. Why, if you squint a little, it looks like a formation of geese flying south.

    And if you turn this way and squint a little, you'll see my brown eye throwing up all over this problem. Riddles, puzzles, etc. only measure a small portion of what a coder can really do. They never measure how resourceful you are!

  • jDeepBeep (unregistered) in reply to jwenting
    jwenting:
    The real WTF is using PHP :)

    It's not clear, but most likely this was for a php position, so.... not really a wtf. Sooner or later, someone would have posted the same flamebait as you, so we might as well get it over with.

  • Addison (unregistered) in reply to DaStoned
    DaStoned:
    It's a puzzle. Programmers don't solve puzzles for work.

    I'd solve it similarly. I don't give a crap about puzzles and solving them. The computer does all the work, gives me the answer and we can all continue with more pressing matters. Brute-force is faster than coding a more intelligent algorithm.

    Why hello TopCod3r.

    Jokes aside, let's say you were making a web application (it was a PHP interview after all). You use brute force instead of taking 2 minutes to come up with something better (it's not a hard question). What happens to your server when 10,000-100,000 requests come through at once?

    Last time I checked reducing processing requirements by 1000 fold was a good thing.

  • BLEEE (unregistered)

    "Yeah, it works, but..."

    But what, exactly? I fail to the the WTF here other than the fact that there's a bunch of nested ifs and a load of magic numbers.

    So it's pretty brute forced. Did you specify in the question that the solution had to be optimised for speed? No? Oh. Well why waste time prematurely optimising then?

    Oh, magic numbers are a problem? Well you specified the question with a magic number, so what did you expect? Maybe if you has asked the right question you would have got the answer you were looking for, e.g:

    Write a function with input n that calculates the smallest number that is evenly divisible by all of the numbers from 1 to n.

    The real WTF is the interviewer.

  • mscha (unregistered)

    $ perl -MMath::BigInt=blcm -E 'say blcm(1..20)' 232792560

    Go Perl!

    • Michael
  • TomW (unregistered)

    A simple test, huh? And this is to see if someone has the ability to engineer software systems? I would have walked out of your interview.

  • Zap Brannigan (unregistered)

    I don't know PHP, but I've seen that 'onion' structure in COBOL programs. I guess you would call this the brute force approach.

  • (cs) in reply to Addison
    Addison:
    Jokes aside, let's say you were making a web application (it was a PHP interview after all). You use brute force instead of taking 2 minutes to come up with something better (it's not a hard question).

    If it is so easy to come up with a better solution in 2 minutes why didn't you? Remember no googling is allowed as this is an interview, and if you already knew an approach to finding LCDs then it has become a test of interviewee knowledge rather than skill and so worthless.

  • (cs)

    This article is really versatile. It could be any of these: "Best of the sidebar", a "CodeSOD", a "Tales of the Interview" and obviously "Featured Article" too.

    Can we swap MFD for these stories?

  • (cs) in reply to Anonymous
    Anonymous:
    I think TRWTF is that the guy started his program from 1, instead of 2520*snip*

    He starts at 20, not 1. ;)

  • Azeroth (unregistered)

    If interviewer wanted to see more optimized or more elegantly written solution, why not just ask extra question "could you offer another solution that's optimized for speed/readibility/whatever?". At least that's the right thing to do in inteview if you want to get the answer that you like from the candidate. If I'm a candidate, I can't guess whether my interviewer is optimization-junkie or "could should read like a book" advocate, that's where the half-baked answers come from...

  • (cs) in reply to complete looney
    complete looney:
    A slightly simpler solution to code might be to multiply the primes together (=9699690), then multiply that answer by 1-M until you found a result that had no remainder (in this case M=24). But for a large value of N that might take a while.

    If someone came up with the generic answer you gave I would then want to see a derivation to show where they got the method from rather than knowing it.

    For your second solution, what is M? I don't think you can have meant to type 'multiply by 1-M'? That would give 9699690*(1-24) = -223092870 as your answer.

  • (cs)

    This is exactly the kind of braindead code a colleague of mine produces. "it fulfills the requirements" he'd say, "what more do you want". Sad part is that's exactly what the boss thinks too. You can explain best practices to him all you want and he'll just give you a blank look. Then a few months go by and he'll come by your desk... "There was a change in requirements. We want it to be divisible by all numbers from 1-50". And now you have to a) copy paste like an idiot or b) rewrite it they way your retarded colleague should have written it in the first place.

  • Overlord (unregistered)

    Honestly, I'd do it this way as well.

    That's probably why I don't write code for a living =P

  • K&T (unregistered) in reply to TomW
    A simple test, huh? And this is to see if someone has the ability to engineer software systems? I would have walked out of your interview.

    Good, i like to know upfront when potential employees are going to throw a temper tantrums when they get requirements they don't like. It makes hiring people so much easier.

    At any rate, how would you determine if someone can write code? Do you just hire them based off their resume and have them design production systems for a few months? Sort of like a 2 month long (paid?) interview?

    Seriously, I've had tons of candidates that can tell me all the book definitions but when it came time to actually use those definitions in real code, they couldn't hack it. One guy event told me how cool recursion is, but when it came time to white board a method to search a file directory (and i gave him the needed classes and methods) he couldn't figure it out.

  • (cs) in reply to Anonymous
    Anonymous:
    This is what you call simple programming task?
    The programming task is simple. The most straight-forward, get-it-out-the-door-now solution is actually the one that is being paraded as a WTF - which is a WTF in itself.

    Yes, there are more elegant solutions, some of which have been proposed here, but they require a certain amount of mathematical knowledge - in fact they strike me as the solutions of people who have formally trained in maths and computer science. They are academically pleasing, but have no practical advantage given that any reasonable hardware will be able to brute-force mash the numbers in an acceptable timeframe (I'd guess you're looking at a few seconds at most).

    Assuming the interview is for a php developer and not a maths tutor, there's nothing wrong with this solution as a first pop in a pressurised interview situation. It's certainly the route I would've gone down, as I'm not a mathematician. Yes, it could do with some refining, but in practical terms it will determine the correct answer. I suspect that even taking the time to write the code into account I would get the correct answer faster by this method than by trying to work out a more elegant algorithm.

    So, TRWTF is using a Project Euler problem in a coding interview, given that: "Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems." (from the Project Euler homepage).

    The whole point of those problems is to first test mathematical knowledge; and then test your ability to code the mathematical principles. Just because someone has ten years of PHP experience doesn't mean they must be a mathematical genius - I have more than ten years of development experience but never studied maths beyond GCSE (that's tests at age 16 for the non-UK residents). So let's remember that just because we think a solution is poor, that doesn't mean that it is.

  • More (unregistered) in reply to BLEEE
    BLEEE:
    "Yeah, it works, but..."

    But what, exactly? I fail to the the WTF here other than the fact that there's a bunch of nested ifs and a load of magic numbers.

    So it's pretty brute forced. Did you specify in the question that the solution had to be optimised for speed? No? Oh. Well why waste time prematurely optimising then?

    Oh, magic numbers are a problem? Well you specified the question with a magic number, so what did you expect? Maybe if you has asked the right question you would have got the answer you were looking for, e.g:

    Write a function with input n that calculates the smallest number that is evenly divisible by all of the numbers from 1 to n.

    The real WTF is the interviewer.

    OK… TopCoder was funny. The people in this thread are way too obvious.

  • (cs) in reply to DOA
    DOA:
    This is exactly the kind of braindead code a colleague of mine produces. "it fulfills the requirements" he'd say, "what more do you want". Sad part is that's exactly what the boss thinks too. You can explain best practices to him all you want and he'll just give you a blank look. Then a few months go by and he'll come by your desk... "There was a change in requirements. We want it to be divisible by all numbers from 1-50". And now you have to a) copy paste like an idiot or b) rewrite it they way your retarded colleague should have written it in the first place.

    There's a difference between solving problems like this in the time given to you by the interview and actually having to produce upkeepable code. Do you use prime numbers every day/week/month to solve common problems in your environments? I don't. If you're in an interview and are given 20 questions to answer, will you REALLY be in the exact mindset you are in your everyday work? Especially if they're stupid puzzles like this, or in the range of how much a Boeing weighs? If yes, then I wonder about your workplace...

  • Gparent (unregistered)
    int main()
    {
        int number = 20;
        do
        {
            number += 2;
        }
        while ((number % 11 != 0) || (number % 12 != 0) || (number % 13 != 0) || (number % 14 != 0) || (number % 15 != 0) || (number % 16 != 0) || (number % 17 != 0) || (number % 18 != 0) || (number % 19 != 0) || (number % 20 != 0));
    
        std::cout << number;
        return 0;
    }

    Took under 60 seconds to write, and took under 2 to run. If the interviewer didn't suck, he would've asked a better question.

  • Scott (unregistered)

    Try 12252240

  • (cs) in reply to Scott
    Scott:
    Try 12252240

    Not divisible by 19.

  • mcwyrm (unregistered)

    Wow.

    max = 20 ans = 1

    for i = max to 1{ if mod(ans, i) != 0 then ans *= i }

    return ans

    Faster to type than your nested loops, and really - the obvious way to do it, no?

  • RiF (unregistered)

    I've asked similar questions to this and there are often several ways to solve the problem, what I'm really interested in is which approach the candidate took and why?

    Better than giving them a b&w printout containing 200 lines of badly formattted code and asking why it wouldn't compile....especially when the reason is you've inserted a deliberate typo in a variable name...twice! (you know who you are!)

  • Tony (unregistered) in reply to JoeSmoe
    JoeSmoe:
    What kind of stupid interview question is this? How does this help test that the person truly has 10 years of PHP? What business application does this have? Unless the person is interviewing for a job that requires common use of prime number calculation, the real WTF was the interview question rather than the answer.

    It's testing whether someone understands loop optimization. You only need a basic knowledge of arithmetic to solve it, so it's not really about the math, it's just about how many steps you take. Testing for divisibility is like doing a SELECT statement. If you have a PHP page that's hitting the database over and over again during a loop, when it could be caching results and avoiding redundant SELECTs, your service isn't going to scale very well, is it? You need someone who knows why.

  • mauve (unregistered)

    If candidates cannot solve this problem using the GCD method then they fail the interview. If I was interviewing, I'd prod them in the right direction and judge them on how much effort it took to get there.

    The product of primes method is elegant mathematically but not in code, though I'd be impressed if someone produced it.

    Brute forcing it or ridiculing the question demonstrates an inability to program algorithms. 90% of business code may just be workflows and database CRUD, but it's always the "clever" algorithms that make an application really stand out.

Leave a comment on “Out of All the Possible Answers...”

Log In or post as a guest

Replying to comment #:

« Return to Article