## Google Interview Question

Software Developers**Country:**United States

**Interview Type:**In-Person

due to sqrt, pow and log, which are called several times, this is definitely is not O(1).

We could use bisection method to calculate sqrt(5) only one time - log (n) complexity , or we can declare sqrt(5) as precalculated constant - 2,23606, so we shoudn't calculate sqrt(5) . The same regards golden ration - we shall store constants only. Here is small modification :

```
long findFibCount(long n) {
if (n == 0)
return 0;
if (n == 1)
return 1;
double fi = 1. 618033;
doublde sqrtFive = 2.2360679
int index = (int) (Math.log(n * sqrtFive +0.5) / Math.log (fi));
int res = (int)((Math.pow(fi,index) /sqrtFive ) +0.5);
if (res != n) {
index +=1;
}
return index;
}
```

that's better, but we still have 2 log calls and 1 pow call, so complexity will depend on the cost of these remaining calls.

the cost to log operation is higher that the cost of division and multiplication.

The cost of multiplication is strictly higher than "n log n" (small omega notation should be used here).

So, looks like the complexity of the solution is at least "n log n" (or higher), but n is number of digits in input number.

```
public static int countValuesofFibonacci(int x){
if ( x <= 0){
return 0;
}
if ( x== 1){
return 1;
}
int a = 0;
int b = 1;
int count = 2;
int temp;
while (a+b < x){
count += 1;
temp = b;
b = a+b;
a = temp;
}
return count;
}
```

This takes appx. O (lgn) complexity.

brute force approach works here with approximate complexity "log n", so all the tricks are unneeded here.

Proof:

1) Given n = 1.000.

Brute force will find solution in 17 steps.

2) Given n = 1.000.000.

Brute force will find solution in 31 steps.

3) Given n = 1.000.000.000.

Brute force will find solution in 45 steps.

etc.

You can expand fib into a tail recursive function, and then from that into a simple iterative loop. From there it's pretty straightforward. O(n).

```
public static int fibTermsBeforeN(int n)
{
int val = 0;
int prev = 1;
int count = 0;
for(; val < n; ++count)
{
val = val + prev;
prev = val - prev;
}
return count;
}
```

```
// ZoomBA, showcasing iterator object creation.
// This is infinite iterator.
def FibGen :{ previous : [ 0, 1] ,
$next : def(){
cur = $.previous[0] + $.previous[1]
$.previous[0] = $.previous[1]
$.previous[1] = cur
}
}
fg = new ( FibGen )
n = 6
count = lfold ( fg, 2 ) -> { break( $.o >= n ) ; $.p += 1 }
println( count )
```

First thing is definitely ask about n, how large it can be.

first solution is to pregenerate fibbonachi numbers up to maximum value of n, the do binary search over it. O(N) - memory, O(logN) complexity

second solution is to binary search on n-th fibbonachi number. n-th fibbonachi can be found in O(logN) with power exponentiation so the complexity including binary search would be O(logN * logN)

does not work.

If n = 1.000.000.000 you will get overflow while trying to get n-th fibbonachi number.

Though the answer is simple: 44 fib numbers are less than 1.000.000.000.

It's just a basic addition of 2 numbers given the proper input and an upper limit.

```
void findFib(int n)
{
int fibNum = 0, prevFibNum = 1, count = 1;
while (fibNum < n) {
printf("Fibonacci number %d is: %d\n", count, fibNum);
fibNum += prevFibNum;
prevFibNum = fibNum-prevFibNum;
count++;
}
}
```

```
public int countFiboLessThan(int n)
{
if(n<=0)
{
return 0;
}
int a=0;
int b=1;
int count=2;
while(b<n)
{
int tmp=a;
a=b;
b=b+tmp;
count++;
}
return count-1;
}
```

Use fast exponential to calculate Fib(n), break when Fib(n) > input, climb down to Fib(n/2) and multiply until Fib(n/2 + x) < input. Return count.

does not work, you will not be able to count the exact number of preceding fib numbers.

Proof: while doing fast exponential, you don't know the exact quantity of fib numbers you skip.

@zz.roman: does too, as far as I can tell. Once fast exponential has exceeded the input, climb down to n/2, and multiply until Fib(n/2 + x) < input. Like so: say the input number is 25000; find n where F(n) < 25000; using fast exponential: n = 32 (that's 5 cycles); climb down to n/2=16, and multiply until n = 22 (Fib(22) = 28657); total cycles is 11, compared with 21 using the traditional method.

@zr.roman: I thought you would know this one "Represent Fibonacci numbers in matrix form:

(F[n+1], F[n]

F[n], F[n-1])

= A^n, where

A =

((1,1),

(1,0))", no? If A^n is Fib(n+1), the rest is simple math. Fast exponential until A^n > input. A^n was obtained by doing A^(n/2) * A^(n/2). So, take A^(n/2) and multiply by A until A^(n/2 +x) > input; n/2 + x is the number of Fibonacci numbers smaller than the input. I tried it and it works...

I also tried, and it occurred to be unstable: i.e. sometimes it works, but sometimes it does not, depending on input.

Please, provide here your solution, I'll test it on some input values.

I tried submitting the code here 3 days ago, and I have no idea where it went. Posting comments here is weird, as there's no feedback given to the user. Anyway, there's nothing special about my code, it does exactly what I have described above. Maybe the missing piece is that when you use the matrix A described above, the [0,0] element in A pow n is the n+1 element in the Fibonacci sequence, so then "you will be able to count the exact number of preceding fib numbers".

```
#include <iostream>
#include <vector>
using namespace std;
class FiboExist{
public :
int fibo(int n){
int ans = 0;
if(n <= 1){
ans = n;
}else{
int a = 0, b = 1;
ans=1;
while(b < n){
int c = a;
a = b;
b = a+c;
ans++;
}
}
return ans;
}
};
int main(){
FiboExist fb;
cout<<fb.fibo(3)<<endl;
return 0;
}
```

import java.util.*;

import java.lang.*;

import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */

class Ideone

{

public static void main (String[] args) throws java.lang.Exception

{

Ideone fibtest = new Ideone();

System.out.println(fibtest.fibCount(2));

}

public int fibCount(int target) {

if (target == 0) return 0;

if (target == 1) return 1;

ArrayList<Integer> fibs = new ArrayList<>();

fibs.add(0);

fibs.add(1);

int count = 2;

while (fibs.get(count-1) < target) {

fibs.add(fibs.get(count-1) + fibs.get(count-2));

if (fibs.get(count) >= target) return count;

++count;

}

return count;

}

}

#include<stdio.h>

int main()

{

int count=0;

int n;

printf("enter the number:=> ");

scanf("%d",&n);

int i,fibo=0;

int previous2=1,previous1=-1;

for(i=0;fibo<n;i++)

{

fibo=previous1+previous2;

if(fibo<=n)

{

count++;

printf("%d ",fibo);

}

else

break;

previous1=previous2;

previous2=fibo;

}

printf("\n");

printf(" the no of term in fibonacii series is :=>:%d",count);

return 0;

}

#include <iostream>

#include <vector>

using namespace std;

vector<int> fibo(int range);

int main()

{

vector<int> sum;

int range;

cout<<"Enter the number range: "<<endl;

cin>>range;

sum = fibo(range);

cout<<"Output : ";

for(unsigned int i=0 ; i<sum.size() ; i++){

cout<<sum[i]<<" ";

}

return 0;

}

vector<int> fibo(int range) {

vector<int> temp;

temp.push_back(0);

temp.push_back(1);

int i=0;

while(temp.size() < range) {

temp.push_back(temp[i+1]+temp[i]);

i++;

}

return temp;

}

how about this solution

```
#include <stdio.h>
#include <stdlib.h>
#define SIZE 6
int fib(int n, int arr[]){
if (n == 0 || n == 1){
arr[n] = n;
return n;
}
return arr[n] = (fib(n - 1, arr) + fib(n - 2, arr));
}
int main(){
int *arr = (int*)calloc(sizeof(int)* SIZE, 1);
fib(SIZE, arr);
for (int i = 0; i < SIZE; i++)
printf("%d ", arr[i]);
return 0;
}
```

We could use Binet's formula for finding the n- th fibonachi number. Actually Fibonachi numbers are very famous numbers because of their golden rule ratio. O(1) time and memory complexity

- EPavlova January 13, 2016