|
Sex Bumbo posted:Yeah but... recursion is the wrong way to produce Fibonacci numbers. There's no reason to do it like that. Just put it in a loop and it's better code. I like being pedantic, so: this is not true, there are multiple ways to use recursion to calculate Fibonacci numbers in linear complexity. For example: fib_recursion (int n, a, b) = if n <= 0 then b else fib_recursion (n-1, b, a+b) call with fib_recursion(n, 1, 1)
|
#
¿
Apr 16, 2016 19:20
|
|
|
|
| # ¿ May 10, 2024 08:03 |
|
|
FamDav posted:Your solution is quadratic. Fibonacci numbers grow geometrically and bignum arithmetic is linear in the number of digits for addition. Unless you have access to an ALU that can do unbounded integer arithmetic in constant time? Ha, fair point, my example is wrong (but my claim that there are ways to calculate fibonacci in linear time is not). Either way I was just pointing out that when people say "solve fibo with recursion" you do not necessarily have to answer with fibo(n) = fibo(n-1) + fibo(n-2). Whether you use recursion or iteration shouldn't really change the time complexity (big O) of the optimal solution of any problem if you know what you're doing. That said, if I went to a job interview and somebody asked me the fibonacci question I'd be quite offended so I agree it's a silly interview problem.
|
|
#
¿
Apr 16, 2016 20:48
|
|
|
Hmm, I guess I should have done more research before making claims, serves me right for being pedantic. (I did indeed have the algorithm using matrix multiplication in mind) That said, I agree now even more that it's a bad interview question.
|
|
#
¿
Apr 16, 2016 21:53
|
|
|
Infinotize posted:Not FizzBuzz, but I have yet to find a candidate that could code up a bit counter*, in any language or even pseudocode, in the ~dozen interviews where I asked that question. Maybe I should be asking FizzBuzz first. That actually doesn't surprise me, because I've never learned about bitwise operators at all in my studies. Java, Haskell, Graph theory, advanced algorithmic datastructures, data analsysis, bio-informatics, etc, where all considered more important than bitwise operators by my university.
|
|
#
¿
Jun 19, 2016 13:10
|
|
|
feedmegin posted:Then your course sucked. They are the L in ALU. Bitwise instructions are one of the few fundamental things a CPU is for. Im amazed you can go to uni for comp sci and not be given a basic course in how a CPU actually works. Well, if I had had any interest in CPU's I could probably have taken a course about that, but as I never aimed for a job where I would need to know how a CPU worked I'm not too bothered about my uni not teaching me that. I actually didn't follow a traditional comp sci course either, mine was very focused on the mathematical sides of informatics (i.e. data analysis, bio-informatics, complex algoirthms using graph theory, numerical optimisation, neural networks, time series forecasting, etc). edit: to clarify, obviously I know what the operators and, or, xor, shift, etc mean in the context of bits. That's very simple. I just never saw the syntax and didn't know the >>= symbol (for left shift I assume?) posted in the code example above. Walh Hara fucked around with this message at 13:33 on Jun 19, 2016 |
|
#
¿
Jun 19, 2016 13:27
|
|