 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
Not all jobs are alike.
Some folks work in more of a research and development environment where the work involves coming up with solutions to all sorts of "puzzles"; i.e., research problems which may not have been solved before. Having a grasp of numerical methods, including decomposing composite numbers down to their prime factors, could actually be useful. If you're writing physics engines for a game company, you'd better know your math.
Having said that, I'd never give someone a test like that. . . as someone else pointed out, it basically just shows how good someone is at taking tests.
What I usually ask for is a couple of pages of code they've written, just to see what their coding style looks like. If that looks good, I ask them to explain to me what they've written.
But mostly we talk about the actual problems they're being hired to solve.
Depending upon the level at which we're hiring, we might ask the applicant to give a short seminar or talk on a relevant topic of their own choosing.
That separates the duds from the winners in a hurry.
Admin
Admin
Should have bitchslapped the interviewer. Why the fuck should anyone write code to calculate one fucking static number in an efficient way when it can be done this way in less than a minute? With such requirements the result will be hard coded anyway. Or is he "calculating" Pi every time he uses it? Damn nerds...
Programmers shouldn't care about such stuff. That is what the other nerds are for in the company.
Admin
No, sorry, the problem is simple enough to not be a distraction from the test, which is actually about coding style more than anything else. It's nowhere near enough to say "it works", a lot of development still happens like that due to hiring people LIKE THAT  and the worst thing is that they don't see any problem with the code "it works doesn't it? What more do you want."
No, people don't use prime numbers every day, nor the mod function, but I don't think it's unreasonable for a developer to have a basic grasp of:
a) mathematics b) code structures c) well designed code
When I interview people, I expect them to be in EXACTLY the right mindset, they're under pressure to deliver, but have to deliver something of acceptable quality. This is EXACTLY how they will be coding in the workplace, to deadlines and with quality constraints.
I fail to see how the Boeing weight problem is anything to do with this. It's a really simple straightforward coding challenge, and if you can't produce, or even attempt the 15 lines of code in 20 minutes then, sorry, maybe development isn't for you.
I'm still counting the WTFs on that code. Apart from the Alpine nesting (code smell), why multiply the iterator by 20? Just start the iterator at 20 and add 20 each time, no need for that confusing $num variable in there at all. What if the answer is greater than 99999999999? What if the business change their minds and want not divisible by 1..50 or 1..100?
TRWTF is that apparently some people out there think that it isn't.
:)
Admin
While I agree that this is a middleoftheroad math problem, there is no reason the interviewee couldn't AT A MINIMUM write a loop instead of nesting all of the test numbers. Like someone similarly said before, what if the followup question was "Now produce the results for the lowest common denominator of 1 through 50". The same guy would nest 30 more times instead of simply updating the maximum loop value.
Admin
ok, so it took me 15 minutes to write it. It only took me 2 minutes to come up with it though:
short[] divisables = {1, 2, 3, 5, 7, 9, 11, 13, 17, 19};
int divisibleNumber = 2520; bool exit = false; int i = 0;
while (i <= divisables[].length){ exit = false; while (exit == false){ if !(divisibleNumber % divisables[i] = 0){ divisibleNumber++; exit = true; i = 0; } else{ i++; exit = false; } } } /divisibleNumber is now the lowest number divisible by all the number 120. display however you like/
Keep in mind I don't write C very often and I've only had a coding job for < 6 months. But I think that fulfills the requirements nicely, if you ignore any stupid mistakes I may have made :P (which an interviewer is likely to do he's looking for ability, not absolute correctness).
Admin
bzz No, sorry wrong it's both a requirement and a question.
Can I have a report detailing the daily NAV for our top 30 funds?
^ that's both too.
"Can I have a report detailing the daily NAV for our top 300 funds?"
^ that's now changed.
Just because it's a requirement phrased as a question doesn't mean it can't be changed.
And, frankly, if I saw that code the FIRST thing I would say is "OK, so now modify it for numbers 1 to 500" and see if they rethink how to do it...
Admin
oops, I didn't know how to preserve the tabs sorry.
Admin
Admin
Admin
If it was obvious, it would be right, which it isn't. For max=10, ans starts at 1, then goes to 10, 90, 720, and finally 5040, when the correct answer is 2520. Either you do way more tests than necessary, or you do prime factorization.
Psuedocode: Find all primes <= max, create a map mapping prime>count. Start each of these counts at 1. For i: 1..max: for each prime determine the maximum power of that prime that divides i, update that prime's count if its greater. Multiply together prime^count for all of the primes.
Admin
no:
1860480/7=265782.8571
Admin
Are you serious? Very well, let's do it your way: Then a few monts go by and he'll come by your desk... "A few weeks ago I asked you to work out the smalest number that is evenly divisible by all the numbers from 1 to 20. Can you quickly tell me what the smallest one for 1 to 50 is?
Admin
Alright, everybody raise your hand if you could write a function to calculate a least common multiple without looking it up the definition?
No takers? Honestly, your average Joe Schmoe has forgotten everything they ever learned fifth grade math class, and if they aren't in a field that requires solving math problems like this on a regular basis, they're going to solve it using the embarrassing brute force method instead.
If you have a PHP programmer with 10 years of experience, ask him a question relevant to the kinds of problems he solves everyday. For example, show him a simple database schema and ask him to join two or three tables, ask him the difference between a singleton and a static method, find out if he's familiar with xpath or regex, etc.
Admin
My solution (about 510 mins)
Admin
I'm going to have to come out with the "it works in a reasonable time frame, what more do you want?" crowd.
If the result were to be used in an actual web page, I'd run the offthetopofmyhead10secondstowrite code, then simply
#define LOWEST_COMMON_MULTIPLE_1_20 [whatever the actual number is]
Why recalculate at all?
If the interviewer had wanted a generic LCM algorithm, he should have asked for one.
Admin
OMG WTF...your right, with such a simple solution youd have to 'Refactor' it to meet the new requirements.....well Im with you...id toss my cookies as well....
of course to ensure that I wouldnt be caught with having to refactor my code Id probably propse a writing the function to take any range of numbers, any mathematical operation, and some sort of Trinary boolean to indicate what result type is needed....but thats just me.
Admin
Admin
On retrospect, I kinda agree on your take on the stressful situation. But still, basic problems deserve basic answers, and the original problem feels a lot more like a high school/college programming assignment than an interview question. Feel free to look up my answer earlier in the comments and find the WTFs in that (I'm sure there are some).
That's not in the scope of the question. You're given a simple programming/mathematical exercise to solve, but you also have an opportunity to try to work with your (hopefully) future boss.Personally, if I'd give a problem like this in an actual interview situation, I'd be vying for a dialog with the interviewee. "Would I be solving these on a regular basis" is a fair question, and one that deserves an answer. "Will this be used in other context than 1..20" is another. Again, this is an extremely simple problem. If you know that the code will need later renovation that's a whole another issue.
First solution vs reasonable solution vs best solution. IE fast, cheap or good. Pick any two ;)
Admin
Also likely to get the wrong result (not proven, just a hunch).
Probably chokes on something like 8 % 16 = 8, but 8 * 16 = 128, not 16
Admin
East.
Admin
Because often the people asking the questions in your job won't KNOW what they actually want. That's why we have things like design patterns and that's why we try and write code that is flexible/extensible and all the stuff that developers SHOULD be taught about code. Rather than the "oh, it works, just stick it in" and then it becomes someone else's problem. "Technical Debt" is the term.
Admin
No, no, no, no.
It's not a loop optimization question. As noted by other posters, after a moment or two of thought, you just write down the answer as an expression (223*......). So it's a really stupid interview question because it's not a programming question.
Admin
I then write a function that takes a low and high number and calculates the LCM of the integer range (potentially I'll even google up a better solution than "guess and test"), because now I've been asked to solve a similar problem twice I figure there's a real posibility that my boss is a dick and will keep asking me to solve trivial mathematical problems when I'm trying to restructure a webapp written by a business graduate with a limited grasp of programming and develop a new allsinging alldancing data visualisation tool (you know, those actually being my job).
Of course, if the main business area of the company is solving trivial mathematics problems then either a) I wouldn't have applied in the first place, as I don't have a strong mathematical background, or b) I would probably have coded something generic in the first place because I would've had the mathematical background to easily create a reusable solution...
Admin
Sure, but I'm looking up at them and I am facing east.
Admin
LMAO!
Best. Comment. Ever
You sir, have made my day!
Admin
First of all, I do not write code for a living, but I can write simple programs in Delphi or Pascal.
I do not see any problem with bruteforce if it does not take a long time. To solve the problem 5 you need maths knowledge and not a programming skill, because you first need to come up with a formula that can produce the answer and only then you would need to code it. If you do not have good maths knowledge you will not be able to come up with a solution that is not a bruteforce. Yes, in my opinion it was possible to optimize the code a bit by starting from 234567891011121314151617181920 and then subtracting 20 every time (instead of adding 1 and then multiplying by 20)
This reminds me of one time when one of my friends asked me for help with a school assignment. http://img142.imageshack.us/img142/5115/50994158by2.jpg
For those who do not understand anything: you have to write a program that finds all possible numbers that can be written in place of * so that the multiplication is correct (each * can hold a different number). One result should be three numbers so that x*y=z and you have to output all results. Running time  less than 1 minute.
I found out that doing a bruteforce search gets all the answers in about 35 seconds on a Cyrix MediaGX 233MHz CPU provided that you write output to file. Hoping that the school does not use 486s for testing I told him to do a bruteforce and write the results to file. It worked.
Admin
Less than a minute for a human with a calculator: 25202111317*19=232792560
but as an (generic) algorithm it's pretty hard.
Admin
Highlighted in red. I think you must have been coding in a language that actually gives you some high level features as C doesn't have length...
But you've given pretty much a neatened up version of the WTF code. It is even less efficient as you missed the +=20 optimisation. Also it is not flexible enough to be easily extended to greater values of n  the array must be changed by hand.
It's still the brute force approach  something you said you were spending the 2 minutes to avoid.
Personally I would be more concerned with the code structure. Having the loop condition named just exit, then having it changed in 2 different places feels very error prone and reduces readability, and there's no need to set it to false in the 2nd branch. You've also missed the outer loop. And having 1 in the divisables array is unnecessary.
So I don't really think that this is such a 2 minute question after all.
[ code ] ... [ /code ] will do thatAdmin
OK, I truly don't see the WTF here. Sure, if this was live code destined for production then this expensive "brute force" technique is utterly inappropriate. But from my understanding, this was an interview question for a programming position and the coder had to provide a working answer there and then. Well, he did provide a working answer and he did so within the tight restrictions of an interview scenario (no internet, no text books, just "give me the answer now!"). If the interviewer wanted a working answer that minimised CPU cycles then he should have stipulated that when he posed the question. As is, the coder fulfilled all the requirements of the question and had no reason to consider any further refinements since an interview question is hardly going to be reworked at a later date due to new requirements!
A raised eyebrow is about as much of a response as this tale warrants. Exclaiming "WTF?" is inappropriate, in my humble opinion.
Admin
Wouldn't the answer to that question be 1?
Admin
Did he get the jog?
Admin
No, no it wouldn't.
Admin
I'm going to assume that I'm now being trolled and exit quietly (stage east, with the geese).
Admin
There. Next. :)
Admin
Maybe it's just me, but when I ask (or when I'm asked) a programming question on an interview, I expect the answer to be both elegant and efficient.
It's fine to start out with "well, the naive way would be to loop over all numbers and see which one is divisible by 120", etc.
But if anyone thought an answer like this is the "right" one, I definitely do not want to be working with them.
It's amazing that so many people miss the point of these "puzzle" questions. It's not to get the right answer  it's to show how you think and how you go about solving a problem. The fact that something like this would rarely be required on the job is irrelevant.
Admin
Cute. My turn...(Common Lisp)
User time = 0.000 System time = 0.000 Elapsed time = 0.000 Allocation = 252 bytes 0 Page faults 232792560
Admin
Admin
Personally, the WTF here isn't about not remembering GCD/LCM or any mathematical optimization  it's doing a halfassed job at optimization.
I mean, the guy already removed 1, 2, 5, and 10 because he had an idea those would be covered somewhere along the way. So why didn't he remove the 3, 6, etc?
Either way, I'd still take a guy who would use a bruteforce 2 nested loop approach over a guy who would decide it's better go wild with copypaste.
Admin
But it doesnt matter cos the result would be in the cache by then. Either that or I'd move it into a stored procedure on the db.
Admin
sorry, I wrote it in notepad assuming C++, which has .length (or something similar).
I only noticed the fact that I didn't need 1 in the divisibles array, or the second exit= line after I posted it. I did miss the +20 optimization though. And changing the requirements simply means adding more prime numbers to the array. Easily doable with a second function that finds the prime numbers within a given number and assigns them to the array. Though then it might be better to use a linked list. . . :p. Joking!
in reality the best answer is: "long variable = 25202111317*19;" then display it.
while mine was still brute force as it was a programming interview I thought I one line basic math answer would be insufficient. And otherwise it's just brute force.
Admin
Fair enough. Only now run your stored procedure 100,000 times and tell me what happens. Nothing good, considering 25202111317*19 will do the same thing.
Admin
Admin
Or this way:
int GetLeastCommonMultiple(int n) { int result = 1; for(int i = 2; i <= n; i++) { if(IsPrime(i)) { result *= GetHighestPowerSmallerThan(i,n); } } return result; }
int GetHighestPowerSmallerThan(int i, int n) { int tmp = i; int result = i; while(tmp *= i <= n) { result = tmp; } return result; }
bool IsPrime(int i) { //I don't want to start another war, //so I refuse to implement it }
Admin
I would have hired him. His code does the job, and his work was efficient: He found a working solution to the problem in little time.
About 90% of all volunteers would end with no or a wrong solution.
Admin
No offense. But anybody who writes 14 nested if statements, and don't think: "Surely there must be a better way to do this." is not someone I want to work with.
Captcha: genitus
Admin
Admin
If you think this is really a WTF, then YOU are the real WTF (while the opposite holds true in Soviet Russia). Let's examine the facts:
Seriously, get a dose of reality people. I also wager that alot the people coming up with their ohso elegant solutions are also CRUD developers who just WISH they actually programmed software with cutting edge algorithms.
Admin
Typical. Not picking any one response, but time to chime. "What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?"
Had to jump in to try to solve it. First, 120. Note that some numbers (such as 20) eliminate others (2 & 10) because of common factors (if it's divisible by 20, it's divisible by 2 & 10). Other numbers (like 16) share some factors with others (20 & 16 share 4, but not 4 & 5), so instead of 16, I DO need 4.
The proposed solution is 4791113171920. 4 is there because of 16 (420=80, which is 0 mod 16), 9 is there because of 18. I could have broken 20 into 4 * 5, or 225, but it helps to keep it handy.
The product is 232792560, which is a proposed solution. A simple fornext loop testing mod i will show it to be a product of each number. Division of the solution by any factor (2,3,5, which are parts of our composites) results in numbers that ARE relatively prime to our problem set. So 232792560 is the answer.
I don't give a rat's ass how easy or hard a problem or a solution is. The critical part is recognizing the problem, devising a workable solution, and implementing it. Sometimes an idiot loop is reasonable, sometimes not.
The given solution is stupid. Why? Because it started at 1. At the very least, start at 2520. Better would be the least multiple of all the primes < 20. Stop at the 20! mark (2432902008176640000) or somewhere that the compiler blows up. Leave out 10, 15 & 20 maybe. It would work, but it's not elegant at all, and it's wasteful.
The language is irrelevant. Good code can be written in any language, as can bad code. It's what you do with what's available that counts.
By the way, I just reread the post I'm quoting. "Bitchslapped"? I'm that kind of nerd. That's the kind of mental exercise that keeps the mind nimble and able to function after working on the same problem set for months at a time. Indeed.