• (cs) in reply to Ren
    Ren:
    DOA:
    <snip>

    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...

    Maybe I haven't been to enough interviews, but from what I understand the purpose of exercises like this is to see not only if the interviewee can solve basic problems (and let's face it, this is basic), but also if he can do it properly. What if he had to find a number divisible by every number from 1 to 1000? Would he copy-paste 1000+ lines? And let me clarify things before we get the inevitable flood of "you wont need to calculate this in real life"... no, this isn't a practical example, it's only a test to see HOW you structure your code.

  • Steve (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.

    That depends.

    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.

  • (cs) in reply to DOA
    DOA:
    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".
    Good attempt at an argument, with one problem. "What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?" is not a requirement, it is a question. This is a significant difference that you really should be able to recognise.
  • Vollhorst (unregistered)

    Should have bitch-slapped 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.

  • Mr^B (unregistered) in reply to Ren
    Ren:
    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...

    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 mind-set, 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.

    :)

  • Keith (unregistered) in reply to JimM

    While I agree that this is a middle-of-the-road 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 follow-up 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.

  • Addison (unregistered) in reply to the real wtf fool
    the real wtf fool:
    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.

    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 1-20. 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).

  • Mr^B (unregistered) in reply to JimM
    JimM:
    DOA:
    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".
    Good attempt at an argument, with one problem. "What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?" is not a requirement, it is a question. This is a significant difference that you really should be able to recognise.

    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...

  • Addison (unregistered)

    oops, I didn't know how to preserve the tabs- sorry.

  • (cs) in reply to mauve
    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.
    Um no, it demonstrates a wish to get the fastest solution. Quite understandable if you have 20 questions to solve. This kind of test doesn't really prove anything one way or the other -- except that the guy solved the issue at hand (many of the code examples given here do not), it compiles and has rudimentary optimization in it. You're not hiring someone to teach math, you're hiring someone who solves problems.
    mauve:
    If candidates cannot solve this problem using the GCD method then they fail the interview.
    I assume that you have a math-heavy application to develop/maintain, then. Otherwise, you fail as an interviewer.
  • Addison (unregistered) in reply to Addison
    Addison:
    oops, I didn't know how to preserve the tabs- sorry.
    aaaand I noticed a mistake :S. that last exit = false should be exit = true
  • MntlChaos (unregistered) in reply to mcwyrm
    mcwyrm:
    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?

    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.

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

    no:

    i	ans	mod(ans,i)
20	1	1
19	20	1
18	380	2
17	6840	6
16	116280	8
15	1860480	0

    1860480/7=265782.8571

  • More (unregistered) in reply to JimM
    JimM:
    DOA:
    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".
    Good attempt at an argument, with one problem. "What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?" is not a requirement, it is a question. This is a significant difference that you really should be able to recognise.

    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?

  • Anon (unregistered)

    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.

  • Migala (unregistered)

    My solution (about 5-10 mins)

    public class EulerTest {
	public static void main(String[] args) {
		long result = 1;
		for (int i = 1; i <= 20; i++)
			result *= i / gcd(result, i);
		System.out.println(result);
	}

	private static long gcd(long num, long div) {
		return num % div == 0 ? div : gcd(div, num % div);
	}
}
  • ThingGuy McGuyThing (unregistered)

    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 off-the-top-of-my-head-10-seconds-to-write 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.

  • Paula Bean (unregistered) in reply to DOA
    DOA:
    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.

    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.

  • (cs) in reply to Mr^B
    Mr^B:
    I don't think it's unreasonable for a developer to have a basic grasp of:

    a) mathematics

    mauve:
    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.
    How basic? Or rather, how complicated? Yes, I'm sure I learnt clever ways to do this at school, but that was 16 years ago, and surprisingly I've forgotten a lot of that in deference to useful work-based knowledge and other life experiences (I really couldn't tell you what the GCD method would involve). As a solution to the stated problem I don't have any issues with the approach of incrementing a guess and testing against the stated condition.
    Mr^B:
    What if the business change their minds and want not divisible by 1..50 or 1..100?
    JimM:
    Good attempt at an argument, with one problem. "What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?" is not a requirement, it is a question. This is a significant difference that you really should be able to recognise.
  • (cs) in reply to Mr^B
    Mr^B:
    No, people don't use prime numbers every day, nor the mod function*snip*
    I use the mod function at least weekly...
    When I interview people, I expect them to be in EXACTLY the right mind-set, 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.
    So how much of your codebase is basic math?
    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.
    The Boeing problem is relevant in that it's designed use is nowhere near the actual use. With the Boeing problem you're trying to get a bit of insight to the inner workings of the interviewee's mind, and if he's willing/able to work in uncommon circumstances. What you get from usage is people going "no, that won't do", "google isn't the answer" and "I don't know about that, so that won't work.". IE they're trying to find the ONE answer.

    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).

    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?
    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 ;)

  • Terra (unregistered) in reply to mcwyrm

    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

  • anoncow (unregistered) 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.

    East.

  • Mr^B (unregistered) in reply to ThingGuy McGuyThing
    ThingGuy McGuyThing:
    If the interviewer had wanted a generic LCM algorithm, he should have asked for one.

    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.

  • SeaDrive (unregistered) in reply to Tony

    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.

  • (cs) in reply to More
    More:
    JimM:
    DOA:
    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".
    Good attempt at an argument, with one problem. "What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?" is not a requirement, it is a question. This is a significant difference that you really should be able to recognise.
    Are you serious? Yes! - JimM Very well, let's do it your way: Then a few months 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?" Weeks? Months? Which is? You decide...
    "It'll take me about 10 minutes - I'll email it to you."

    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 all-singing all-dancing 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...

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

    East.

    Sure, but I'm looking up at them and I am facing east.

  • Endo808 (unregistered) in reply to jwenting

    LMAO!

    Best. Comment. Ever

    You sir, have made my day!

  • Pentium100 (unregistered)

    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.

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

    Yes.

    Less than a minute for a human with a calculator: 25202111317*19=232792560

    but as an (generic) algorithm it's pretty hard.

  • (cs) in reply to Addison
    Addison:
    the real wtf fool:
    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.

    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+=20;
			exit = true;
			i = 0;
		}
		else{
			i++;
			exit = false;
		}
	}
}

    OK this is n /divisibleNumber is now the lowest number divisible by all the number 1-20. 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).

    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.

    oops, I didn't know how to preserve the tabs- sorry.
    [ code ] ... [ /code ] will do that
  • JR (unregistered)

    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.

  • Ryan Neufeld (unregistered)

    Wouldn't the answer to that question be 1?

  • p (unregistered)

    Did he get the jog?

  • Mr^B (unregistered) in reply to Ryan Neufeld
    Ryan Neufeld:
    Wouldn't the answer to that question be 1?

    No, no it wouldn't.

  • Mr^B (unregistered) in reply to JR
    JR:
    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.

    I'm going to assume that I'm now being trolled and exit quietly (stage east, with the geese).

  • Paul (unregistered)
    <?php echo '232792560'; ?>

    There. Next. :)

  • Bobo (unregistered)

    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 1-20", 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.

  • Geoff (unregistered)

    Cute. My turn...(Common Lisp)

    (defun foo(n) (reduce #'lcm (loop for i from 1 to n collect i))) FOO

    (compile 'foo) FOO

    (time (foo 20)) Timing the evaluation of (FOO 20)

    User time = 0.000 System time = 0.000 Elapsed time = 0.000 Allocation = 252 bytes 0 Page faults 232792560

  • (cs) in reply to Mr^B
    Mr^B:
    JR:
    <snip>
    I'm going to assume that I'm now being trolled and exit quietly (stage east, with the geese).
    No, no - we all genuinely believe that in a one-off interview situation there is no problem solving this with brute-force code.
  • sudo make me a sandwich (unregistered)

    Personally, the WTF here isn't about not remembering GCD/LCM or any mathematical optimization - it's doing a half-assed 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 brute-force 2 nested loop approach over a guy who would decide it's better go wild with copy-paste.

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

    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.

  • Addison (unregistered) in reply to the real wtf fool
    the real wtf fool:
    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.

    oops, I didn't know how to preserve the tabs- sorry.
    [ code ] ... [ /code ] will do that

    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.

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

    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.

    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.

  • JR (unregistered) in reply to JimM
    JimM:
    Mr^B:
    JR:
    <snip>
    I'm going to assume that I'm now being trolled and exit quietly (stage east, with the geese).
    No, no - we all genuinely believe that in a one-off interview situation there is no problem solving this with brute-force code.
    Exactly what JimM said! I'm not trying to troll anyone, I thought my post was concise and to the point and highlighted exactly why this is not such a terrible solution for a one-off interview scenario. Mr^B, I got to this party a little late but I've gone back and read some of your posts and your main argument for why this is so bad seems to be "what if the requirements change?". Well, please re-read my post and try to remember this was an interview question! How exactly are the requirements going to change for an interview question?! The solution satisfied the scenario, plain and simple.
  • Anonymous (unregistered) in reply to Anonymous
    Anonymous:
    Ren:
    Anonymous:
    This is what you call simple programming task?

    Yes.

    Less than a minute for a human with a calculator: 25202111317*19=232792560

    but as an (generic) algorithm it's pretty hard.

    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 }

  • titrat (unregistered)

    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.

  • More (unregistered) in reply to JR
    JR:
    JimM:
    Mr^B:
    JR:
    <snip>
    I'm going to assume that I'm now being trolled and exit quietly (stage east, with the geese).
    No, no - we all genuinely believe that in a one-off interview situation there is no problem solving this with brute-force code.
    Exactly what JimM said! I'm not trying to troll anyone, I thought my post was concise and to the point and highlighted exactly why this is not such a terrible solution for a one-off interview scenario. Mr^B, I got to this party a little late but I've gone back and read some of your posts and your main argument for why this is so bad seems to be "what if the requirements change?". Well, please re-read my post and try to remember this was an interview question! How exactly are the requirements going to change for an interview question?! The solution satisfied the scenario, plain and simple.

    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

  • (cs) in reply to Mr^B
    Mr^B:
    JimM:
    Good attempt at an argument, with one problem. "What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?" is not a requirement, it is a question. This is a significant difference that you really should be able to recognise.
    *bzz* No, sorry wrong it's both a requirement and a question.
    Sorry, but how can *anything* that starts "What is..." be a requirement? "What is your name? No, I've changed the requirement, I need the names of all your immediate family." See, doesn't work. "What is..." cannot be a requirement - it expects a discreet and fixed answer.
    Mr^B:
    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.
    Yes, I agree with you on this one. But the question here is "Can I have..." and the requirement is "a report detailing the daily NAV of funds" (whatever that is). The answer to the question is "Yes" or "No" in both cases. This situation is not analogous to the discussion at hand. The report is not going to have a discreet fixed answer, it's going to change on a daily basis, so it has to be written flexibly. The answer to the Euler Project question is not going to change. Ever.
    Mr^B:
    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...
    That's fair enough - it shows that you're interested in how someone thinks. And I strongly suspect that if you'd asked this candidate that he would've taken a few seconds to think and then written something that has a couple of loops, one to increment the guess, and one to mod by all numbers between the required number and 2. However, again this point is not relevant to the discussion, because we have no evidence that either of these things (the asking and the modifying) took place. We've simply been asked to laugh at a piece of code that provides a clunky, yet workable, solution to a single question. And I'm disinclined to acquiesce to the request...
  • I walked the dinosaur (unregistered)

    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:

    1. PHP, used almost exclusively for CRUD web front-ends (other uses are most likely "doin it rong")
    2. As such, PHP attracts the most amateur developers as well as the developers who don't have a formal math/science degrees
    3. Per 1 and 2, it's obvious that both the actual job doesn't involve any kind of mathematical knowledge (prime factors are NOT basic math knowledge, sorry guys)
    4. Per 1, 2, and 3, it is obvious that the interviewer was obviously asking the question to try and be "clever" by asking such a "clever" question

    Seriously, get a dose of reality people. I also wager that alot the people coming up with their oh-so elegant solutions are also CRUD developers who just WISH they actually programmed software with cutting edge algorithms.

  • (cs) in reply to Vollhorst
    Vollhorst:
    Should have bitch-slapped 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.

    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, 1-20. 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 for-next 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. "Bitch-slapped"? 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.

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

Log In or post as a guest

Replying to comment #:

Log Out

« Return to Article