Expedia Interview Question
Software Engineer in TestsCountry: United States
This is nice solution but you are using space for stack as recursive calls. Below program is written as iterative approach.
public int sumFibo(int n){
int n0=0;
int n1=1;
int n2;
int sum=1;
int i=0;
while(i<=n){
n2=n0+n1;
sum+=n2;
n0=n1;
n1=n2;
i++;
}
return sum;
}
#include <iostream>
#include <vector>
using namespace std;
int fibSum(int pos_);
int main()
{
int pos = 5;
int result = fibSum(pos);
cout << result;
return 0;
}
int fibSum(int pos_){
if(pos_ == 1){
return 0;
}
else if(pos_ == 2){
return 1;
}
else{
return (fibSum(pos_-1) + fibSum(pos_-2) + 1);
}
}
We should not confuse 'position' with 'value' at position. ie. check if
pos == 1
then return 0 (value at position 1). I think this could be a solution.
basically fibonacci series looks like 1, 1, 2, 3, 5, 8... not starting from 0.
#include<stdio.h>
#include<conio.h>
int main()
{
int f=0, s=0, t=1, sunm = 0;
for(int i=0, i<n,i++)
{
f = s; s = t;
sum = sum + s;
t = s + f;
}
printf("Sum: %d", sum);
getch();
return 0;
}
public static void printSeries(int sum, int previousSum, int newSum)
{
if (sum != newSum)
{
if (sum >= 1 && previousSum < 1)
{
Console.WriteLine(0);
Console.WriteLine(1);
Console.WriteLine(1);
previousSum = 1;
newSum = 1;
printSeries(sum, previousSum, newSum);
}
else if (sum >= 1 && previousSum >= 1)
{
int temp = newSum;
newSum = previousSum + newSum;
previousSum = temp;
Console.WriteLine(newSum);
printSeries(sum, previousSum, newSum);
}
}
return;
}
Obviously things could be must easlier if you do this using iteration, but sometimes interviewer doesn't want easy solution, they want to test your skills, and believe me if it not that easy using recursion.
Requires some time of yours and it is when interviewer check your approach to some triky problems. And that is the whole idea of taking interviews. :)
You didn't answer my q's...can you tell me what you mean by If you are given 5 Sum= (0+1+1+2+3)=7
if n =5 it should return the sum of the first 5 fibonacci no.
I have clearly written (0+1+1+2+3)=7, don't know why you couldn't understand
static int fib(int f)
{
if (f == 1 || f == 0)
return f;
return fib(f - 1) + fib(f - 2);
}
#include <stdio.h>
int main()
{
int c=0;int d=1;int n;
printf("Enter the range of the series: ");
scanf("%d", &n);
int i;int sum;
for(i=0;i<n;i++)
{
int z;int a[n];
if(i==0)
{
z=c;
a[i]=z;
sum=z;
}
if(i==1)
{
z=d;
a[i]=z;
sum=sum+z;
}
if(i>1)
{
z=a[i-1]+a[i-2];
a[i]=z;
sum=sum+z;
}
printf("The value of the series is: %d\n", z);
}
printf("The sum of the given Fibonacci series is: %d\n", sum);
return 0;
}
import java.math.BigInteger;
import java.util.ArrayList;
public class FibonacciMemoized {
// Memoization cache
private static ArrayList<BigInteger> fibCache = new ArrayList<BigInteger>();
static {
fibCache.add(BigInteger.ZERO);
fibCache.add(BigInteger.ONE);
}
public static BigInteger fib(int n) {
if (n >= fibCache.size()) {
fibCache.add(n, fib(n-1).add(fib(n-2)));
}
return fibCache.get(n);
}
public static void main(String[] args) {
for (int i=0; i<=Integer.parseInt(args[0]); i++)
System.out.print(fib(i)+", ");
}
}
static int fibonacci(int n) {
if (n == 0)
return 0;
else if (n == 1)
return 1;
else
return (fibonacci(n - 1) + fibonacci(n - 2) + (1));
}
private static int GetFibonacciSum(out int first, out int second, int count){
if (count < 1){
throw new ArgumentException("count has to be > 0");
}
if (count == 1){
first = 0; second = 0;
return 0;
}
if (count == 2){
first = 0; second = 1;
return 1;
}
int firstSub; int secondSub;
int sum = GetFibonacciSum(out firstSub, out secondSub, count - 1);
second = firstSub + secondSub;
first = secondSub;
return sum + second;
}
First let's define the solution. Suppose we want the sum of fibonacci numbers up to position 14. The answer can be defined recursively as: FibSum(14) = FibNumber(14) + FibSum(13).
To generalize, the fibonacci sum at any given position is the fibonacci VALUE at that position, plus the fibonacci sum at all prior position.
public static int Fib(int p) {
if (p == 1 || p == 2)
return p - 1;
return Fib(p-1) + Fib(p-2);
}
public static int Sum(int p) {
if (p == 0)
return 0;
return Fib(p) + Sum(p-1);
}
import java.util.Scanner;
public class SumOfFibonacciSeries {
static int sum=0;
public static void main(String[] args) {
System.out.println("Enter the Range for Fibonacci Series : ");
Scanner sc = new Scanner(System.in);
int range = sc.nextInt();
System.out.print("Fibonacci Series : ");
SumOfFibonacci(0, 1,range);
System.out.println("\nSum of Fibonacci Series of first "+ range+" Numbers : "+sum);
}
public static void SumOfFibonacci(int previous, int next, int range){
if(range<1){
return;
}else{
System.out.print(previous + " ");
sum = sum + previous;
SumOfFibonacci(next, previous+next, --range);
}
}
}
- supratim.sengupta October 31, 2012