Bloomberg LP Interview Question
Software Engineer / DevelopersTeam: Price history
Country: United States
Interview Type: In-Person
int main()
{
int n, i;
printf("Enter the number of elements in the sequence");
scanf("%d", &n);
for( i=0 ;i<n;i++)
{
printf("%d",fibo(i));
}
}
int fibo(int n) {
if ( n == 0)
return 0;
else if (n ==1)
return 1;
else
return fibo(n-1) + fibo(n-2);
}
Java Solution:
public static void main(String[] args) {
System.out.println("Enter the no of elements");
Scanner sc1 = new Scanner(System.in);
int n = sc1.nextInt();
System.out.println(displayFibonacci(n).toString());
}
private static StringBuffer displayFibonacci(int n){
StringBuffer buffer = new StringBuffer();
List<Integer> list = new ArrayList<Integer>();
for(int i=0; i < n; i++){
if(i == 0){
list.add(0);
buffer.append(String.valueOf(0));
}
if (i == 1 || i == 2){
list.add(1);
buffer.append(",");
buffer.append(String.valueOf(1));
}
if(i > 2){
list.add(list.get(i-1) + list.get(i-2));
buffer.append(",");
buffer.append(list.get(i-1) + list.get(i-2));
}
}
return buffer;
}
import java.util.ArrayList;
import java.util.Scanner;
public class Fibonacci {
public void fib(int size, int firstNum) {
int previous = 0;
int current = firstNum;
ArrayList<Integer> list = new ArrayList<Integer>();
list.add(current);
for(int i = 1 ; i<size ; i++) {
int temp = current;
current = previous + temp;
previous = temp ;
list.add(current);
}
System.out.println("The fibonnaci series is :");
System.out.println(list);
}
public static void main(String [] args) {
Scanner scanner = new Scanner(System.in);
System.out.println("Enter the first element");
int firstNum = scanner.nextInt();
System.out.println("Enter the size of the Fibonacci Series");
int size = scanner.nextInt();
Fibonacci object = new Fibonacci();
object.fib(size,firstNum);
}
}
Dynamic Programming Approach:
Avoid the repeated work done (By recursion method) by storing the Fibonacci numbers calculated so far.
This can even further optimized the space by storing the previous 2 numbers only because that is all we need to get the next Fibonnaci number in series.
int fibo ( int Num ) {
int prev1 = 0, prev2 = 1, next ;
if( 0 == Num )
return prev1 ;
for (int i = 2; i <= num; i++ ) {
next = prev1 + prev2 ;
prev1 = prev2 ;
prev2 = next ;
}
return prev2;
}
Time Complexity: O(N)
Space Complexity: O(1)
- RajKP August 26, 2014