Questions d'entretien

Entretien pour Solutions Engineer

-

Meta

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

Répondre

Réponses aux questions d'entretien

6 réponse(s)

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 le

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] = 0; return 0; } if(x == 1) { m[1] = 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; }

Adi le

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]=0; result[1]=1; if(n<2) return result; for(int i=0;i

Utilisateur anonyme le

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[0]=a; result[1]=b for(int i=2;i

Utilisateur anonyme le

0

isnt the question about returning an array? you dont need memoization // js let fibonacci = ((n) => { let arr = [0]; if(n > 0) arr[1] = 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 le

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) le

Ajouter des réponses ou des commentaires

Pour commenter ceci, connectez-vous ou inscrivez-vous.