 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
 Sponsor Post
 Tales from the Interview
 The Daily WTF: Live
 Virtudyne
Admin
Admin
The real WTF is using PHP :)
Admin
Apart from using two loops rather than one loop and lots of ifs, should you do it another way?
Admin
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...
Admin
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.
Admin
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. Bruteforce is faster than coding a more intelligent algorithm.
Admin
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
Admin
Go, go Haskell!
Admin
Nothing could be more wrong than that.
Admin
I'd probably do something like this instead:
Even prettier would be to make a function that takes N (=20 or whatever) as an argument, but it seems rather pointless.Admin
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.
Admin
#!/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.
Admin
That (usually) gets me off the hook.
Admin
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.
Admin
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.
Admin
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
Admin
Shouldn't this article be green?
Admin
Generic answer;
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
2^43^257111317*19 = 232792560
A slightly simpler solution to code might be to multiply the primes together (=9699690), then multiply that answer by 1M 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.
Admin
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.
Admin
But some programmers solve puzzles at work; e.g. when they're too much bored with their work.
Admin
This is what you call simple programming task?
Admin
Yes.
Admin
at least it's indented properly
Admin
I give the coder points for artistic value. Why, if you squint a little, it looks like a formation of geese flying south.
Admin
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 120, the smallest number is not going to be anything smaller than 2520 ><
Admin
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!
Admin
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.
Admin
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,000100,000 requests come through at once?
Last time I checked reducing processing requirements by 1000 fold was a good thing.
Admin
"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.
Admin
$ perl MMath::BigInt=blcm E 'say blcm(1..20)' 232792560
Go Perl!
Admin
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.
Admin
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.
Admin
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.
Admin
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?
Admin
He starts at 20, not 1. ;)
Admin
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 optimizationjunkie or "could should read like a book" advocate, that's where the halfbaked answers come from...
Admin
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 1M'? That would give 9699690*(124) = 223092870 as your answer.
Admin
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 150". 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.
Admin
Honestly, I'd do it this way as well.
That's probably why I don't write code for a living =P
Admin
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.
Admin
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 bruteforce 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 nonUK residents). So let's remember that just because we think a solution is poor, that doesn't mean that it is.
Admin
OK… TopCoder was funny. The people in this thread are way too obvious.
Admin
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...
Admin
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.
Admin
Try 12252240
Admin
Not divisible by 19.
Admin
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?
Admin
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!)
Admin
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.
Admin
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.