6 ms·
I don't think trivializing the combinations with Python's builtins, looking up the fib primes with OEIS, or computing factors with Alpha is cheating. I hope, in
by dschoon 16y ago
I don't think trivializing the combinations with Python's builtins, looking up the fib primes with OEIS, or computing factors with Alpha is cheating. I hope, in fact, it's the whole point of the exercise: choose the right tools for the job. If you're writing code to test primeness or generate Fibonacci numbers, I sure as hell don't want to hire you.
- zmitri 16y agoCode to generate fibs is literally one line. Remember eigenvalues :)?
- shiven 16y agoSorry, couldn't help myself!! That approach is just so damn elegant. int((1/math.sqrt(5))*(math.pow(((1+math.sqrt(5))/2),fibonacci)-math.pow(((1-math.sqrt(5))/2),fibonacci))) Reference here: http://mathproofs.blogspot.com/2005/04/nth-term-of-fibonacci-sequence.html http://mathproofs.blogspot.com/2005/04/nth-term-of-fibonacci...
- btilly 16y agoElegant, but inefficient if you want to get exact values for large n. You're much better off using doubling operations. If you forget those, you can remember them from the matrix version. If fib(0) = 0. fib(1) = 1. etc. Then n [0 1] = [fib(n) fib(n+1)] [1 1] [fib(n+1) fib(n+2)] With repeated squarings, you can efficiently generate any Fibonacci number you want.
- kasterma 16y agoHere (where you have to search through Fibonacci numbers) I suspect memoization is rather the way to go: # memoized fibonacci function fibtable = {1:1, 0:1} def fib (n): global fibtable if n in fibtable.keys(): return fibtable [n] val = fib (n-1) + fib (n-2) fibtable [n] = val return val
- btilly 16y agoThere is no need to keep track of all previous values. last_fib = 0 fib = 1 while fib < 225000 or not is_prime(fib): last_fib, fib = fib, last_fib + fib
- dkarl 16y agoIf you're writing code to test primeness or generate Fibonacci numbers, I sure as hell don't want to hire you. Maybe you should have called it the "Greplin Challenge," then, instead of the "Greplin Programming Challenge." It's not a real task, after all; the reward comes from accepting a completely artificial challenge. I'm going to do the challenge before dinner tonight, and before I leave work I could get source code for the solutions from the guy down the hall from me who did the challenge as soon as it was posted -- and you certainly don't want to hire a guy who recodes other people's work for no reason, right?
- rwalker 16y agoMaybe we have a different hiring mindset than dschoon - we're equally happy with people who find the answers or create the answers. In a production system, we certainly wouldn't want hand-rolled primeness checking. But in a programming challenge, we think it's fun to write it for yourself.
- dkarl 16y agoOops; I wrote my comment under the assumption that dschoon was with greplin, and in retrospect I'm not sure why. Sorry about that.
- d0m 16y agoI tend to agree with dkarl here because if it was for real, I would just have looked here to find all the answers and maybe the passwords. It was way more fun to do it from scratch :D Thanks grepplin p.s. the csv was copied in my [] python list :)
- deleted 16y ago[deleted]
- extension 16y agoI wrote extremely naive Ruby algos from scratch that solved the problems in a couple seconds, or in the case of the last problem, a couple of minutes. I'm sure the whole challenge would have taken longer if I tried to use any dependencies.