Fackbook 下午刚电面的面筋

下午刚面的， 面试的是个search 组的白人小哥。人很nice。 赶紧发个面经攒攒人品。

废话不多， 上题：

1. 写出 fib(n). 不是很难。
但是让一共写了三种方法， 注意 corner case。

2.写 divide operatio

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

nterview 了。
请问是不是我表现不太好或者background 不强才会进行第二面的呀，看地里大部分同学都是只有一面。
望筒子们解答一下。

oops，没贴上

1. public class SolutionConvert {
   
2.     public void solve(TreeNode root) {
   
3.         if (root == null) {
   
4.             return;
   
5.         }
   
6.         convertToDoubleLinkedList(root);           
   
7.     }
   
8.    
   
9.     public void convertToDoubleLinkedList(TreeNode root) {
   
10.         if (root == null) {
    
11.             return;
    
12.         }
    
13.         if (root.left != null) {
    
14.             TreeNode left = root.left;
    
15.             convertToDoubleLinkedList(left);
    
16.             while (left.right != null) {
    
17.                 left = left.right;
    
18.             }
    
19.             left.right = root;
    
20.             root.left = left;
    
21.         }
    
22.         if (root.right != null) {
    
23.             TreeNode right = root.right;
    
24.             convertToDoubleLinkedList(right);
    
25.             while (right.left != null) {
    
26.                 right = right.left;
    
27.             }
    
28.             right.left = root;
    
29.             root.right = right;
    
30.         }
    
31.     }
    
32.    
    
33.     public void test(String[] args) {
    
34.         TreeNode a = new TreeNode("10");
    
35.         TreeNode b = new TreeNode("12");
    
36.         TreeNode c = new TreeNode("15");
    
37.         TreeNode d = new TreeNode("25");
    
38.         TreeNode e = new TreeNode("30");
    
39.         TreeNode f = new TreeNode("36");
    
40.         a.left = b;
    
41.         a.right = c;
    
42.         b.left = d;
    
43.         b.right = e;
    
44.         c.left = f;
    
45.         solve(a);
    
46.         while (a.left != null) {
    
47.             a = a.left;
    
48.         }
    
49.         while (a != null) {
    
50.             System.out.print(a.val + " ");
    
51.             a = a.right;
    
52.         }      
    
53.     }
    
54. }

复制代码

第三题no extra space是要求必须用morris traversal?

1. public int getNthfibo(int n) {
   
2.         if (n < 0) {
   
3.             throw new IllegalArgumentException("n cannot be negative");
   
4.         }
   
5. 
   
6.         if (n <= 1) return n;
   
7. 
   
8.         int[][] result = {{1, 0}, {0, 1}};
   
9.         int[][] fiboM = {{1, 1}, {1, 0}};
   
10. 
    
11.         while (n > 0) {
    
12.             if (n % 2 == 1) {
    
13.                 multMatrix(result, fiboM);
    
14.             }
    
15.             n = n / 2;
    
16.             multMatrix(fiboM, fiboM);
    
17.         }
    
18. 
    
19.         return result[1][0];
    
20.     }
    
21. 
    
22.     private void multMatrix(int[][] m, int [][] n) {
    
23.         int a = m[0][0] * n[0][0] +  m[0][1] * n[1][0];
    
24.         int b = m[0][0] * n[0][1] +  m[0][1] * n[1][1];
    
25.         int c = m[1][0] * n[0][0] +  m[1][1] * n[1][0];
    
26.         int d = m[1][0] * n[0][1] +  m[1][1] * n[1][1];
    
27. 
    
28.         m[0][0] = a;
    
29.         m[0][1] = b;
    
30.         m[1][0] = c;
    
31.         m[1][1] = d;
    
32.     }

复制代码

Fib用logn的解法的话应该是用矩阵快速乘的那种方法吧

pyemma 发表于 2015-1-31 00:45
Fib用logn的解法的话应该是用矩阵快速乘的那种方法吧

fib 的 log  n 算法肯定和 数学有关， 和算法关系不大了， 我也就是临时写一下。
不要太在意这个啦。

logn 的fib怎么写

houqingniao 发表于 2015-1-31 03:21
logn 的fib怎么写

二楼哥们儿贴出来了

houqingniao 发表于 2015-1-31 03:21
logn 的fib怎么写

用通项公式
http://en.wikipedia.org/wiki/Fibonacci_number

1. int fib(n){
   
2.     double sqrt_five=sqrt(5);
   
3.     double fib_n = floor((pow((1+sqrt_five)/2.0, n) - pow((1-sqrt_five)/2.0,n) ) / sqrt_five ) ;
   
4.     return (int) fib_n;
   
5. }

复制代码

补充内容 (2015-2-1 02:08):
假设不需考虑输入异常和溢出

如果用通项公式的话不应该是O（1）吗？

多谢楼主！
logn 一般人想不到啊。**能想到的有2个
1. dp
2. recusive
3 还与啥呢？

第三题能详细说下吗？