Epic Systems Interview Question
Analystsvoid main()
{
cin>>n;
cout<<fibo(n);
}
int fibo(int n){
if(n==0) return 0;
if(n==1) return 1;
else return(fibo(n-1)+fibo(n-2));
}
}
/*dynamic programming version,using cache O(n), here array's scope is [0,n-1]*/
int fib_one(int n,int *array){
int rs1,rs2;
if(n==0){
return 0;
}
else if(n==1){
return 1;
}
else{
rs1=array[n-1];
if(rs1==-1){
rs1=fib_one(n-1,array);
}
rs2=array[n-2];
if(rs2==-1){
rs2=fib_one(n-2,array);
}
return rs1+rs2;
}
}
<pre lang="" line="1" title="CodeMonkey52582" class="run-this">
#include <iostream>
#include <cstdio>
using namespace std;
int fib(int n){
unsigned long long fib1=1,fib2=1,fibr;
for(int i=2;i<=n;i++){
fibr= fib1+fib2;
fib1 = fib2;
fib2 = fibr;
}
return fibr;
}
int main(){
int n;
cin>>n;
cout<<fib(n)<<endl;
return 0;
}
</pre><pre title="CodeMonkey52582" input="yes">
</pre>
Python working code.
"""
8:29
@Python 2.7
write a code of fibonacci series.
- sonali on August 03, 2010 Report Duplicate | Flag
"""
class Fbi(object):
def __init__(self, n):
if n is None:
print 'invalid n'
raise SystemExit
self._n = n
def find(self, number = None):
if number is None:
number = self._n
if number == 0:
return 0
elif number == 1:
return 1
else:
return self.find(number-1) + self.find(number-2)
if __name__ == '__main__':
f = Fbi(30)
print f.find()
Another way is using divide and conquer algorithm,which in O(log n) running time.
- wei April 07, 2011+Tricky part is: for base_array[2][2]={{1,1},{1,0}}; => {{A2,A1},{A1,A0}} and for base_array^n, we can get {{An+1,An},{An,An-1}}, and simply return An is enough.
+Algorithm: (bottom to top) base_array=>base_array^2=>base_array^4=>....base_array^n, thus running time is O(log n).
The good part is the running time, but the code is a little bit more since need to calculate the matrix matrix multiplication and when compare to dynamic program, I still recommend dynamic programming method for its simplicity.