 Feature Articles

CodeSOD
 Most Recent Articles
 A Caught Return
 Free From Space
 Zero Failures
 Lines of Code
 Limited Space
 Constant Adventure
 Mapro
 Shift Sign Off
 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
Actually, since the answer is a constant, there's no use in calculating it more than once.
const int ANSWER_TO_POINTLESS_QUESTION = 232792560;
Admin
There are two good answers that would work:
Admin
Another shortcut (of many) is that the result for LCM(1..20) will be a multiple of LCM(1..10).
Admin
Admin
I think not  we are looking for the LCM. This would not give us that number. It would multiply 2019181716 which is already wrong(it contains 2 to the power of 7 and the LCM has 2 to the power of 4)
Admin
Another 10 years of PHP experience and he won't even be able to write Hello World. :)
Admin
if he can write that code with 10 years of experience, i can not imagine what he would write had he say 20 years of such experience
Admin
When I interview, I never test. Testing people is pretty meaningless in the pressurized interview atmosphere, since it has little to do with real work. Because I may eventually have to work with whoever I hire, part of my job as an interviewer is to also sell myself to them as someone they would value as a colleague  not someone they have to fear. I much prefer to ask potential candidates to bring me samples of whatever they consider to be their most interesting work and be prepared to discuss what they found interesting about the task. That way, not only do I get a decent reading on their skill level, I also get and idea about how passionate they will be on the job.
Admin
Well, at least he knew that every problem in computer science can be solved by a search algorithm.
Admin
Actually as a generic algorithm it's straight forward. You only have to inductively apply the insight you already demonstrate. I don't know PHP, so I'll just use pseudocode:
leastCommonMultiple :: int > long leastCommonMultiple n = fold * 1 (minSpanningPrimes n)
minSpanningPrimes :: int > List int minSpanningPrimes n where n < 2 = [] minSpanningPrimes n = generateSPrimes n (minSpanningPrimes (n  1)) where generateSPrimes x primeList = foldl condDiv x primeList where condDiv n d where n % d == 0 = n / d condDiv n d where n % d != 0 = n
My initial answer in response to the question was:
leastCommonMultiple :: int > long leastCommonMultiple n = fold * 1 (minSpanningPrimes n)
minSpanningPrimes n where n == 20 = [2,2,2,2,3,3,5,7,11,13,17,19] minSpanningPrimes n where n != 20 = throw error "Calculating spanning Primes unimplemented"
As an interview question it is fine. You really are testing if the person can write code at all (which the WTF answer satisfied perfectly well)  and also how they approach problem solving. Do they think iteratively or inductively? If they take a bruteforce approach, do they show any discomfort at it? Do they consider doing some manual work offline to simplify the online calcuation? Do they (as in my solution), include indications of how a bruteforce/manual solution might be generalised/improved?
Anyone commenting on this question as if it was a simple pass/fail simply doesn't have the experience necessary to be considered for an interviewing position. That this is a question likely to be outside the comfortable, daytoday experience, of an applicant is actually a good thing.
Admin
Yeah, there is a smarter way. Faster, anyway. This particular algorithm takes forever. Sure, it's shorter to write out when not done stupidly (10 lines of Python for the naive algorithm, 19 for the one I'm about to show you), but it takes forever: I'm running the version in the post above while I write this. The algorithm I've given here runs in much faster time, and can be readily generalized.
The set of prime factors for a number divisible by all numbers n such that 2 <= n <= 20 will contain only the prime numbers <= 20, illud est 2, 3, 5, 7, 11, 13, 17, and 19.
In addition, we shall need the highest power of each of those numbers that is less than 20. Since 5 ^ 2 == 25, we're only looking at powers of 2 and 3. The highest power of 2 < 20 is 16 (2^4), and the highest power of 3 < 30 is 9. Thus, we need to do some multiplication: 16 * 9 * 5 * 7 * 11 * 13 * 17 * 19 = 232,792,560, the smallest number divisible by all integers between 1 and 20, inclusive.
Admin
I thought so too, but it turned out that 2520 wasn't divisible by 16. I wonder what the right way to do it is...
Admin
I don't know how can anyone call haskell pseudocode. Pseudocode is supposed to be readable and englishlike!
Anyway, I don't like any answer here. I lie. I like the suggestion of using lcm(1..10) as an increment, because it was given, and I like the suggestions that use lcm. The programmer yielding the faster, cleaner and less error prone code will be the one using lcm from a library.
That said, my solution:
#!/usr/bin/perl
our @primes; our @factors;
foreach $number (2..$ARGV[0]) { if(grep {$number % $_ == 0} (@primes)) { @factors = map { ($number%($primes[$]$factors[$_]) == 0) ? $primes[$_]$factors[$] : $factors[$_] } (0..$#factors); } else { push @primes, $number; push @factors, $number; } }
print eval join("*", @factors), "\n";
Admin
Well, to make it divisible by all evens from 12 thru 20 (in addition to all ints from 1 thru ten), just double it. Then you have to factor the remaining odd composites: 15=3×5 (so if it's a multiple of both those numbers, which it is, it should be a multiple of 15) No other odd composites remain! Now all we have left to do is account for intervening primes, and the only way to do that is to multiply by them. Thus, my answer would be: 2520×2×11×13×17×19=232,792,560 (digit separator:',') see also http://www.google.com/search?q=2520%C3%972%C3%9711%C3%9713%C3%9717%C3%9719
Now maybe I missed a trick there and it isn't the smallest, but it's the smallest you can get at without reaching for any electronic device other than a 4 function calculator at the end (or Google :), and it's well thought out. In other words, I did this without Perl, Python, Java, C++, or anything of that nature.
Admin
self reply, for those with encoding problems: The char I used is the unicode multiplication sign or U+00D7. It's supposed to look vaguely like 'x'
Admin
Brute force Java.
Admin
If 10,000100,000 requests come through for this information and it's not all being memoized and cached, yes, this is a problem.
If you figure this out bruteforce and make the answer a static result in a lookup table, no harm is done.
Admin
int isprime(int n){ int i; for(i = 2; i < n; i++) if( n % i == 0 ) return 0; return 1; }
int main(int argc, char **argv){ int *primes = NULL; int count = 0;
}
Admin
And its wrong. The result being. $ bc 23257231113217 12252240 ^D $ echo WTF
Admin
Admin
except your solution would be wrong.
It will not find the lowest common multiple. Just a multiple.
Admin
Well this guy... lacks not only programming skills but common sense... you can find this answer without writing one line of code, using the Windows Calculator and write: 23257231113217*19
I wonder if this is a more efficient solution XD...
Cheers
Admin
I haven't found this approach while looking through the comments:
Felix
Admin
increment x by 20 instead of 1, 20 times less loopage
Admin
Admin
Surely there is a better way! (Not sure if this qualifies as PHP, though...)
Admin
My best guess, tbh, is that if you're terrible at solving 'puzzles' such as this  extremely simple 'puzzles' , then you're terrible at solving any 'business problems', even fairly simple ones. Business problems are ill defined enough and the complexity is not ranked in any way other than by yourself  and this lets the DunningKruger effect protect your ego.
Admin
Very elegant, but it doesn't produce the correct answer.
Admin
I must ask: Would you consider it a good, bad, or neutral thing if a candidate got this question and said "Just gimme a pencil, paper, and a calculator; I don't need a fullfledged computer for this" and proceeded to get a perfectly good solution in a couple minutes that way?
Admin
I would've done it this way. Sure, it may not be the fastest, but it's the easiest and most obvious solution that I immediately thought of.
//warning. Java below
Anything wrong with that?