Interview Question

Solutions Engineer Interview

-Houston, TX

Write a program which stores the results of the numbers in a Fibonancci sequence in an array

1

def fibRecr(n): if n==1 or n==2: return 1 return fibRecr(n-1)+fibRecr(n-2) # Eg, to 15, store the sequence in array f1 for i in range (1, 15): f1.append(fibR(i))

In Python on

0

I think the key here is to use memoization so that you don't do have to calculate same value again as again in intermediate steps. Eg. in above solution, if we say find all values till 10, you have to calculate fibR(5) for 6, 7, 8, 9, 10 and since its recursive call this will not finish for even small size of n. Here is a solution using DP/memoization #define n 10 map m; //caches the intermediate steps int fib(int x) { auto it = m.find(x); if(it!= m.end()) return it->second; if(x == 0) { m = 0; return 0; } if(x == 1) { m = 1; return 1; } int val = fib(x-1) + fib(x-2); m[x] = val; return val; } int main (int argc, char *argv[]) { int result[n+1]; m[n] = fib(n); for(map::iterator it2= m.begin(); it2!= m.end(); it2++) // just to convert answer in an array form as asked result[it2->first] = it2->second; return 0; }

0

I would write only the function and I assume that you will have to return the array: It goes as follows: long[] fib(int n){ long[] result= new long[n]; result=0; result=1; if(n<2) return result; for(int i=0;i

Anonymous on

0

I think this could be the answer (using iteration) void saveFib(int n){ int[] result = new int[n]; int a = 0, b=1 ,c =0; result=a; result=b for(int i=2;i

Anonymous on

0

isnt the question about returning an array? you dont need memoization // js let fibonacci = ((n) => { let arr = ; if(n > 0) arr = 1; if(n > 1){ let index = 2; while(index < n){ arr[index] = arr[index-1] + arr[index-2]; index++; } } return arr; }); console.log(fibonacci(5));

jonathan liu on

0

``` import java.util.ArrayList; public class Fib { private int maxKnown = 2; private ArrayList arr = new ArrayList(); Fib() { arr.add(0); arr.add(1); arr.add(1); } public int calculate(int n) { if (n <= maxKnown) { return arr.get(n); } for (int i = maxKnown + 1; i <= n; i++) { arr.add(arr.get(i - 1) + arr.get(i - 2)); } return arr.get(n); } public static void main(String[] args) { Fib fib = new Fib(); System.out.println(fib.calculate(10)); System.out.println(fib.arr); } } ```

here is a java solution (with arraylist) on