Bloomberg LP Interview Question Software Engineer / Developers
This one is iterative.'num' is the number of numbers you want to generate.
public static void fibonacci(int num){
int result = 0;
int lastOne = 1;
int lastSecond = 0;
for(int i=0;i<num;i++){
result = lastOne + lastSecond;
lastSecond = lastOne;
lastOne = result;
System.out.print(result + ",");
}
}
This one is recursive, 'count' is the number of numbers you want to generate, and first = 0 and second = 1.
public static void fibonacciR(int first,int second, int count){
if(count == 0){
return;
}
int temp = first;
first = second;
second = second + temp;
count--;
System.out.print(second + ",");
fibonacciR(first, second, count);
}
This one is iterative.'num' is the number of numbers you want to generate.
public static void fibonacci(int num){
int result = 0;
int lastOne = 1;
int lastSecond = 0;
for(int i=0;i<num;i++){
result = lastOne + lastSecond;
lastSecond = lastOne;
lastOne = result;
System.out.print(result + ",");
}
}
This one is recursive, 'count' is the number of numbers you want to generate, and first = 0 and second = 1.
public static void fibonacciR(int first,int second, int count){
if(count == 0){
return;
}
int temp = first;
first = second;
second = second + temp;
count--;
System.out.print(second + ",");
fibonacciR(first, second, count);
}
int m[4] = {1,0,0,1};
int a[4] = {1,1,1,0};
int tmp[4] = {0,0,0,0};
void matrixmul(int a[], int b[])
{
tmp[0] = a[0]*b[0] + a[1]*b[2];
tmp[1] = a[0]*b[1] + a[1]*b[3];
tmp[2] = a[2]*b[0] + a[3]*b[2];
tmp[3] = a[2]*b[1] + a[3]*b[3];
}
void assignmatrix(int a[], int b[])
{
a[0] = b[0];
a[1] = b[1];
a[2] = b[2];
a[3] = b[3];
}
void matpow(int n)
{
if(n > 1)
{
matpow(n/2);
matrixmul(m,m);
::assignmatrix(m,tmp);
}
if ( n%2 == 1)
{
::matrixmul(m,a);
::assignmatrix(m,tmp);
}
}
void clearm()
{ m[0] = 1; m[1]=m[2] = 0;m[3] = 1;}
int fib(int n)
{
matpow(n-1);
return m[0];
}
int main()
{
for (int i = 1; i < 10; i++)
{
cout<<fib(i)<<endl;
clearm();
}
return 0;
}
#include <stdio.h>
int fib1(int n){
if(n<0){
printf("\nInvalid Number : ");
return n;
}
if(n==1 || n==2){
return 1;
}
return (fib1(n-1) + fib1(n-2));
}
int fib2(int n){
if(n<0){
printf("\nInvalid Number : ");
return n;
}
if(n==1 || n==2){
return 1;
}
int prev = 1;
int curr = 1;
int next = 0;
while(next<n){
next = prev+curr;
prev = curr;
curr = next;
}
return next;
}
int main(){
printf("%d",fib1(-8));
printf("\n%d",fib2(6));
return 0;
}
<pre lang="" line="1" title="CodeMonkey27041" class="run-this">/* The class name doesn't have to be Main, as long as the class is not public. */
class Main
{
public static void main (String[] args) throws java.lang.Exception
{
java.io.BufferedReader r = new java.io.BufferedReader (new java.io.InputStreamReader (System.in));
String s;
while (!(s=r.readLine()).startsWith("42")) System.out.println(s);
}
}
</pre><pre title="CodeMonkey27041" input="yes">
void fib(int n){
int fib1 = 0, fib2 = 1;
for(int i=0; i<n; ++i){
cout<<fib1<<"\t";
int temp = fib1;
fib1 = fib1 + fib2;
fib2 = temp;
}
}
void fibRecursive(int &n, int fib1 = 0, int fib2 = 1){
if(n==0)
return;
cout<<fib1<<"\t";
n--;
fibRecursive(n, fib1+fib2, fib1);
}</pre>
I assumed we have the Fibonacci series starting with 1 (1,1,2,3,5,...)
So if the user type 3 the program returns 2.
I used function pointer here and call both version of the implementation (iterative and recursive)
#include<stdio.h>
int fibo_rec(int);
int fibo_iterative(int);
int (*fptr)(int);
int main()
{
int test;
printf("type the number to calculate its fibonacci series\n");
scanf("%d",&test);
fptr=fibo_rec;
printf("The result of recursive fibo_%d is %d\n",test,fptr(test-1));
fptr=fibo_iterative;
printf("The result of iterative fibo_%d is %d\n",test,fptr(test-1));
scanf("%d",&test);
return 0;
}
int fibo_rec(int x)
{
if (x==0|| x==1)
return 1;
else
return fibo_rec(x-1)+ fibo_rec(x-2);
}
int fibo_iterative(int x)
{
int i;
int tmp=1;
int tmp1=1;
int tmp2=1;
for (i=1;i<x;i++)
{
tmp=tmp1+tmp2;
tmp2=tmp1;
tmp1=tmp;
}
return tmp;
}
Easy
- Anonymous January 11, 2010