## Interview Question for Software Engineer / Developers

Country: Russia
Interview Type: In-Person

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

Here is a hint:

Represent Fibonacci numbers in matrix form:
(F[n+1], F[n]
F[n], F[n-1])
= A^n, where
A =
((1,1),
(1,0))

Perform fast exponential (repeated squaring) to compute A^n.

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

revealing hint!

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

The solution is suppose to be O(1) space?? am I missing something ... can you give another example like fib of 8

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

yes, O(1) space, it means that you cannot use recursion, it should be iterative solution.

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

c# implementation.
O(logn) time.
O(1) space.

``````namespace FibonacciInLogNTime {

static class Program {

// time complexity O(log n)
static private long Fib( long n ) {
n--;
long[,] res = { { 1, 0 }, { 0, 1 } }; // Identity matrix (with ones on the main diagonal and zeros elsewhere)
long[,]  a  = { { 1, 1 }, { 1, 0 } }; // Identity matrix for Fibonacci seq { { F(n+1), F(n) }, { F(n), F(n-1) } }

while ( n > 0 ) {
if ( ( n & 1 ) == 1 ) {
res = res.Multiply( a );
}
n /= 2;
a = a.Multiply( a );
}
return res[ 0, 0 ];
}

private static long[,] Multiply ( this long[,] arrA, long[,] arrB ) {
return new [,] { {
( arrA[ 0, 0 ] * arrB[ 0, 0 ] + arrA[ 0, 1 ] * arrB[ 1, 0 ] ), // [0,0]
( arrA[ 0, 0 ] * arrB[ 0, 1 ] + arrA[ 0, 1 ] * arrB[ 1, 1 ] )  // [0,1]
},{
( arrA[ 1, 0 ] * arrB[ 0, 0 ] + arrA[ 1, 1 ] * arrB[ 1, 0 ] ), // [1,0]
( arrA[ 1, 0 ] * arrB[ 0, 1 ] + arrA[ 1, 1 ] * arrB[ 1, 1 ] )  // [1,1]
}
};
}

static void Main( string[] args ) {
var res = Fib( 5 );
}
}
}``````

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

why no answers? after the hint it is quite simple.

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

Use dynamic programming.
Store the previous fib numbers in an array
and access then at the next fib call

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

this is O(n) solution, but needed O(logn).

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

``````#include<stdio.h>
#include<stdlib.h>
#include <string.h>

int  check=1,temp =0;
int * array;
int fabonacii(int n)
{
if(check)
{
check=0;
array = (int *) malloc(sizeof(int) * (n+1));
memset(array,0,sizeof(int) * (n+1));
}

if (n==1)
{
array[n]=0;
return 0;
}
else if (n==2)
{
array[n]=1;
return 1;
}
else
{
if(array[n] !=0)
return (array[n]);
else
{
temp=fabonacii(n-2) + fabonacii(n-1);
array[n]=temp;
return temp;
}
}

}

int main(void)
{
printf("%d",fabonacii(100));
free(array);
return 0;
}``````

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

``````#include<stdio.h>
#include<stdlib.h>
#include <string.h>

int  check=1,temp =0;
int * array;
int fabonacii(int n)
{
if(check)
{
check=0;
array = (int *) malloc(sizeof(int) * (n+1));
memset(array,0,sizeof(int) * (n+1));
}

if (n==1)
{
array[n]=0;
return 0;
}
else if (n==2)
{
array[n]=1;
return 1;
}
else
{
if(array[n] !=0)
return (array[n]);
else
{
temp=fabonacii(n-2) + fabonacii(n-1);
array[n]=temp;
return temp;
}
}

}

int main(void)
{
printf("%d",fabonacii(100));
free(array);
return 0;
}``````

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

Fn = 1/sqrt(5) * pow(2,-n) * (pow(1+sqrt(5),n) - pow(1-sqrt(5),n))

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

Fn = 1/sqrt(5) * (1/2^n) * ( (1+sqrt(5))^n - (1-sqrt(5))^n)

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.