## Interview Question for Developer Program Engineers

• 0

Country: India

Comment hidden because of low score. Click to expand.
1
of 1 vote

Can be done in O(log n) without big magic (by matrix multiplication method) or in constatn time with a lot of math magic (search for Binet's Formula) :)

Comment hidden because of low score. Click to expand.
0

Comment hidden because of low score. Click to expand.
2

Search on the geekforgeeks website for Program for Fibonacci numbers

Comment hidden because of low score. Click to expand.
1
of 1 vote

Hi this is written in C++ but will similarly work in Java also with few modifications....

#include <iostream>

using namespace std;

int main()
{

int t1,t2,t3,count;

t1=0;
t2=1;
count=1;

do
{
t3=t1+t2;
count++;
t1=t2;
t2=t3;
} while(count<=5000);

cout << "5000th element in fibonacci series is " << t3;

return 0;
}

5000th element in fibonacci series is 2020817954

Comment hidden because of low score. Click to expand.
0

hey the question does not permit you to output just the last 10 digits.
It should make use of 2 arrays to hold 2 big no.s and add 2nd to 1st.

Comment hidden because of low score. Click to expand.
1
of 1 vote

//finding the nth fibonacci number

//Time : O(logn)
//Space O(logn)

//All we need to do is multiply {1,1},{1,0} i.e {F(n+1),F(n)},{F(n),F(n-1)} 4999 times so that we get the 5000th fibonacci number

class Fibonacci{

private static void fib(int F[][],int n){
if(n==1)
return ;
//n/2 because if we multiply {1,1,1,0} with itself it becomes 2 times and that if we multiply by itself
//it becomes 4 times and if we multiply that by {1,1,1,0} it will becomes 3 times
int M[][]= {{1,1},{1,0}};
fib(F,n/2);
multiply(F,F);

if(n%2!=0)
multiply(F,M);

}

private static void multiply(int F[][],int M[][]){
int x=F[0][0]*M[0][0]+F[0][1]*M[1][0];
int y=F[0][0]*M[0][1]+F[0][1]*M[1][1];
int z=F[1][0]*M[0][0]+F[1][1]*M[1][0];
int w=F[1][0]*M[0][1]+F[1][1]*M[1][1];

F[0][0]=x;
F[0][1]=y;
F[1][0]=z;
F[1][1]=w;
}

public static void main(String args[]){
int F[][]= {{1,1},{1,0}};
int n=Integer.parseInt(args[0]);
fib(F,n-1);
System.out.println("Fib("+n+") = "+F[0][1]);
//0,1,1,2,3,5,8,13,21,34
}
}

//Input : javac career_cup.java ;java Fibonacci 9; // here 9 is the nth fibonacci number we need to find
//Output: Fib(9) = 21

Comment hidden because of low score. Click to expand.
0

Thank you :)

Comment hidden because of low score. Click to expand.
0

use long in place of int and call fib(F,n); instead of fib(F,n-1);

Comment hidden because of low score. Click to expand.
1
of 1 vote

You would need to use datatype like java.math.BigInteger

``````int i = 2;
BigInteger a = new BigInteger("1");
BigInteger b = new BigInteger("1");
BigInteger temp;
while (i != 5000) {
temp = b;
a = temp;
i++;
}
System.out.println("\n" + b);``````

Ans. 3878968454388325633701916308325905312082127714646245106160597214895550139044037097010822916462210669479293452858882973813483102008954982940361430156911478938364216563944106910214505634133706558656238254656700712525929903854933813928836378347518908762970712033337052923107693008518093849801803847813996748881765554653788291644268912980384613778969021502293082475666346224923071883324803280375039130352903304505842701147635242270210934637699104006714174883298422891491273104054328753298044273676822977244987749874555691907703880637046832794811358973739993110106219308149018570815397854379195305617510761053075688783766033667355445258844886241619210553457493675897849027988234351023599844663934853256411952221859563060475364645470760330902420806382584929156452876291575759142343809142302917491088984155209854432486594079793571316841692868039545309545388698114665082066862897420639323438488465240988742395873801976993820317174208932265468879364002630797780058759129671389634214252579116872755600360311370547754724604639987588046985178408674382863125

Comment hidden because of low score. Click to expand.
0
of 0 vote

I prepared this one with the TDD
Test Class

``````import org.junit.Test;

import static org.junit.Assert.assertEquals;

public class FibonTest {
@Test
public void return0WhenFibon0(){
assertEquals(0,Fibon.fibo(0));
}
@Test
public void return1WhenFibon1(){
assertEquals(1,Fibon.fibo(1));
}
@Test
public void return3WhenFibon2(){
assertEquals(3,Fibon.fibo(2));
}
@Test
public void return6WhenFibon3(){
assertEquals(6,Fibon.fibo(3));
}
@Test
public void return45WhenFibon9(){
assertEquals(45,Fibon.fibo(9));
}
}``````

Fibon

``````public class Fibon {
public static int fibo(int input) {
int result=0;
while(input>0){
result+=input--;
}
return result;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class Fibonacci {
public static void main(String[] args) {
long start1 = System.currentTimeMillis();
System.out.println(fib(5000));
long end1 = System.currentTimeMillis();
System.out.println((end1-start1));
}
public static long fib(int n){
int i=0;
long memo[] = new long[n+1];
for(;i<=n;i++)
memo[i]=-1;
memo[0]=0;
memo[1]=1;
return calcFib(n, memo);
}
public static long calcFib(int n, long memo[]){
if (memo[n]!=-1)
return memo[n];
memo[n] = calcFib(n-2,memo)+calcFib(n-1,memo);
return memo[n];
}
}``````

5000th number in the series is 535601498209671957

Comment hidden because of low score. Click to expand.
0
of 0 vote

Should use pascals triange to solve this. Not iteration.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````package Fibonacci5000th;

import java.math.BigInteger;

public class Fibonacci5000th {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
BigInteger[] fib = new BigInteger[5001];
fib[0] = new BigInteger("0");
fib[1] = new BigInteger("1");

for(int i = 2 ; i<5000 +1; i++){
}
System.out.println(fib[5000]);
}
}``````

does this give correct output?

Comment hidden because of low score. Click to expand.
0
of 0 vote

there is a formula given in Coremen to find 'i'th element of fibonacci series
F(i) = ((1 + √(5) / 2)^i) / √(5) + 0.5

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````long no1 =0, no2 =1
for (int i= 3;i<=500;i++ {
long newNow = no1 + no2;
no1 = no2;
no2 = newNow;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````fun(int n)
{
if(n==0)
return 0;
else if (n==1)
return 1;
else
return (fun(n-1)+fun(n-2));
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

void main
{
int n1,n2,n3,i=2;

{
n1=0;
n2=1;
printf("%d\n%d",n1,n2);
while(2<=5000)
{ n3=n2+n1;
printf("%d\n",n3);
n1=n2;
n2=n3;
i++;
}
}

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Generate Fibonacci numbers iteratively. Select the 5000th number.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.