What a fibonacci function which return N th position number both in recursive and loop, also give the explanation on both implementation on their time efficiency.

Question

What a fibonacci function which return N th position number both in recursive and loop, also give the explanation on both implementation on their  time efficiency.

python recursive version · Accepted Answer

def fib(n):
    if n <= 1:
        return n
    else:
        return fib3(n - 1) + fib3(n - 2)

print(fib(35))

python loop version · Answer

def fib(n):
    if n = 2:
        a, b = b, a + b
        n -= 1
    return b

print(fib(35))

python correct loop version · Answer

def fib2(n):
    if n = 2:
        a, b = b, a + b
        n -= 1
    return b

print(fib(35))

vlados · Answer

Time complexity is 2^n

Tasneem · Answer

In Recursion it takes O(2^n) i.e. exponential complexity and with some caching your can achieve this in logN.

Huabing Zhao · Answer

We need a HashMap to cache the result and reduce duplicated calculations.

public class Fibonacci {
    //Key n, value Fibonacci of n
    static Map cache = new HashMap();

    public static long fibonacci(int n) {
        cache.put(1, 1L);
        cache.put(2, 1L);
        return fib(n);
    }

    private static long fib(int n) {
        if (cache.containsKey(n)) {
            return cache.get(n);
        }

        long result = fib(n - 1) + fib(n - 2);
        cache.put(n, result);
        return result;
    }

    public static void main(String[] args) {
        System.out.println("Fibonacci 5000: " + Fibonacci.fibonacci(5000));
    }
}

Booking.com

Pergunta de entrevista da empresa Booking.com

Respostas da entrevista

Empresas seguidas

Buscas de vagas