Fibonacci numbers... haha.

Question

Vagrant · Accepted Answer

It can be done in O(logN) time is you are really clever.  O(n) is the standard iterative answer, if you cache the last two calculations.  If you gave the recursive answer, O(2^N), then that is why you failed.

Liron · Answer

public class Fibonacci {
	
	
	public static int fib(int n){
		if (n == 1){
			return 1;
		}
		if (n == 2){
			return 1;
		}
		int fib1 = 1;
		int fib2 =1;
		int temp;
		for (int i=3; i<=n; ++i){
			temp = fib1;
			fib1 = fib2;
			fib2 = temp + fib2;
		}
		return fib2;
	}
	
	
	
	public static int fib_rec(int n){
		if (n == 1){
			return 1;
		}
		if (n == 2){
			return 1;
		}
		
		return fib_rec(n-1)+fib_rec(n-2);
	}
	
	
	public static void main(String[] args) {
		for (int i=1; i<15; ++i){
			System.out.println(fib(i));
		}
		System.out.println("==========================");
		for (int i=1; i<15; ++i){
			System.out.println(fib_rec(i));
		}
	}

}

Liron · Answer

here is the O(logn) solution
public static int fib_log(int n){
		int[][] mat = new int[2][2];
		mat[0][0] = 1;mat[0][1] = 1;mat[1][0] = 1;mat[1][1] = 0;
		int i;
		int[][] matRes = mat;
		for (i=2; i<=n; i*=2){
			matRes = double_mat(matRes);
		}
		for (int j=(i/2); j

JJ · Answer

lol Why did Liron write so much code? Isn't the question just telling you to do fib # which keeps going? I created to take a int for how long you want it to go for.(Skipped over 0 as the first number, meh)

ArrayList Fib = new ArrayList;
public list Fibber (int n){
int k =0;
while (k

Google

Google Interview Question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches