Grokking the Art of Recursion for Coding Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
Question and solution have different method signatures

Gaurav Rai Mazra

May 11, 2024

In question, it is asked to generate fibonacci series for n using memoization i.e.

public static List<Integer> fibonacci(int n);

whereas solution talks about generating n fibonacci using memoization i.e.

public static int fibonacci(int n);

The solution need to be updated as follows:

  • Base case:
    • n = 0
      • return List.of(0);
    • n = 1
      • return List.of(0, 1);
    • n > 1
      • add 0 and 1 in result and recursive call to fibonacci generation.
public static List<Integer> fibonacci(int n) { if (n == 0) return List.of(0); if (n == 1) return List.of(0, 1); List<Integer> result = new ArrayList<>(); result.add(0); result.add(1); Map<Integer, Integer> cache = new HashMap<>(); fib(result, cache, n); return result; } public static int fib(List<Integer> result, Map<Integer, Integer> cache, int n) { if (cache.containsKey(n)) return cache.get(n); if (n <= 1) { cache.put(n, n); return n; } int f = fib(result, cache, n - 1) + fib(result, cache, n - 2); result.add(f); cache.put(n, f); return f; }

5

0

Comments
Comments

On this page