Google Interview Question
Web:
www.google.com
|
HQ:
Mountain View, CA
Overview |
| |
Salaries |
| |
Reviews |
| |
Interviews |
| |
Photos |
| |
Jobs |
| |
|
1,223 Interview Reviews |
Back to all Google Interview Questions & Reviews
Interview questions and reviews posted anonymously by interview candidates
Interview Question for Software Engineer at Google:
Aug 20, 2011
Helpful Question?
Yes |
No
Inappropriate?
Answers & Comments (3)
Jan 21, 2012
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));
}
}
}
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));
}
}
}
Helpful Answer?
Yes |
No
Inappropriate?
Jan 22, 2012
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<n ; ++j){
matRes = double_mat(matRes, mat);
}
if (matRes != null)
return matRes[0][1];
else
return mat[0][1];
}
public static int[][] double_mat(int[][] mat){
int[][] matRes = new int[2][2];
matRes[0][0] = mat[0][0]*mat[0][0] + mat[0][1]*mat[1][0];
matRes[0][1] = mat[0][0]*mat[0][1] + mat[0][1]*mat[1][1];
matRes[1][0] = mat[1][0]*mat[0][0] + mat[1][1]*mat[1][0];
matRes[1][1] = mat[1][0]*mat[0][1] + mat[1][1]*mat[1][1];
return matRes;
}
public static int[][] double_mat(int[][] mat,int[][] mat2){
int[][] matRes = new int[2][2];
matRes[0][0] = mat[0][0]*mat2[0][0] + mat[0][1]*mat2[1][0];
matRes[0][1] = mat[0][0]*mat2[0][1] + mat[0][1]*mat2[1][1];
matRes[1][0] = mat[1][0]*mat2[0][0] + mat[1][1]*mat2[1][0];
matRes[1][1] = mat[1][0]*mat2[0][1] + mat[1][1]*mat2[1][1];
return matRes;
}
public static void main(String[] args) {
for (int i=1; i<15; ++i){
System.out.println(fib_log(i));
}
}
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<n ; ++j){
matRes = double_mat(matRes, mat);
}
if (matRes != null)
return matRes[0][1];
else
return mat[0][1];
}
public static int[][] double_mat(int[][] mat){
int[][] matRes = new int[2][2];
matRes[0][0] = mat[0][0]*mat[0][0] + mat[0][1]*mat[1][0];
matRes[0][1] = mat[0][0]*mat[0][1] + mat[0][1]*mat[1][1];
matRes[1][0] = mat[1][0]*mat[0][0] + mat[1][1]*mat[1][0];
matRes[1][1] = mat[1][0]*mat[0][1] + mat[1][1]*mat[1][1];
return matRes;
}
public static int[][] double_mat(int[][] mat,int[][] mat2){
int[][] matRes = new int[2][2];
matRes[0][0] = mat[0][0]*mat2[0][0] + mat[0][1]*mat2[1][0];
matRes[0][1] = mat[0][0]*mat2[0][1] + mat[0][1]*mat2[1][1];
matRes[1][0] = mat[1][0]*mat2[0][0] + mat[1][1]*mat2[1][0];
matRes[1][1] = mat[1][0]*mat2[0][1] + mat[1][1]*mat2[1][1];
return matRes;
}
public static void main(String[] args) {
for (int i=1; i<15; ++i){
System.out.println(fib_log(i));
}
}
Helpful Answer?
Yes |
No
Inappropriate?
To comment on this
question,
Sign In with Facebook or
Sign Up
You might also be interested in: Interview Questions, Software Engineer Interview Questions, Google Interview
2 of 2 people found this helpful
by Vagrant: