## Google Interview Question for Software Developers

• 0
of 2 votes

Country: United States
Interview Type: In-Person

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

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

``````long findFibCount(long n) {
if (n == 0)
return 0;
if (n == 1)
return 1;
double sqrtFive = Math.sqrt(5);
double fi = (1.0 + sqrtFive )/2.0;
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;

}``````

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

sqrt, pow and log are quite costly operations.

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

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

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

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;

}``````

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

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.

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

In this case time complexity becomes O(log(n)) and space complexity O(1)

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

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.

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

``````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.

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

really quite so.

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

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.

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

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;
}``````

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

it's approximately "log n" time complexity.

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

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

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

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)

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

Why Binary Search? The question just asks to get Fibonacci numbers.

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

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.

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

and your first solution is a bit unclear:
1) pregenerating fibbonachi numbers up to maximum value of n is O(1) space complexity,
2) why do binary search? it is unnecessary, because step#1 will already provide the final answer.

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

the question remains: can this be done faster than O(logn)?

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

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++;
}
}``````

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

``````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;
}``````

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

Forgot to remove the if(n==1) case as it's not necessary.

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

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.

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

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.

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

@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.

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

@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...

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

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.

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

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".

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

``````#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;
}``````

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

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;
}
}

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

#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;
}

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

#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;
}

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

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;
}``````

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

``````def num_fib_under_n(n):
if n <= 1:
return n
count = 2
a, b = 0, 1
while True:
a, b = b, a+b
if (b > n):
return count
count += 1

print(num_fib_under_n(6))``````

Add a Comment
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.

Learn More

### 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.

Learn More

### Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

### Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More