推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 3789|回复: 22
收起左侧

Fackbook 下午刚电面的面筋

[复制链接] |试试Instant~ |关注本帖
cgdong2012 发表于 2015-1-30 10:45:48 | 显示全部楼层 |阅读模式

2015(1-3月) 码农类 硕士 全职@Facebook - 网上海投 - 技术电面 |Other

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

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

废话不多, 上题:
. from: 1point3acres.com/bbs
1. 写出 fib(n). 不是很难。
但是让一共写了三种方法, 注意 corner case。

2.写 divide operation  a / b .
不能用  / 操作。
刚开始写了一个 o(n) 的 让改进成 o(log n)的。

3. 把二叉树 改成一个 循环双向链表。
no extra space. 把左右指针当成 pre , next 指针。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
求人品, 求大米。 谢谢大家~

. 1point 3acres 璁哄潧
补充内容 (2015-1-30 11:36):. 1point3acres.com/bbs
Fib 那个最终 解法是 o(log n)的running time.鏈枃鍘熷垱鑷1point3acres璁哄潧

补充内容 (2015-1-31 01:48):
昨天面完, 今天早晨9点多就收到邮件, 要第二次 screen interview 了。
请问是不是我表现不太好或者background 不强才会进行第二面的呀,看地里大部分同学都是只有一面。
望筒子们解答一下。

评分

3

查看全部评分

本帖被以下淘专辑推荐:

ronaldo17 发表于 2015-3-12 22:52:33 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
第三题no extra space是要求必须用morris traversal?
回复 支持 1 反对 0

使用道具 举报

 楼主| cgdong2012 发表于 2015-1-31 01:45:13 | 显示全部楼层
关注一亩三分地微博:
Warald
pyemma 发表于 2015-1-31 00:45
Fib用logn的解法的话应该是用矩阵快速乘的那种方法吧
. more info on 1point3acres.com
fib 的 log  n 算法肯定和 数学有关, 和算法关系不大了, 我也就是临时写一下。
不要太在意这个啦。
回复 支持 1 反对 0

使用道具 举报

mhbkb 发表于 2015-1-31 03:33:46 | 显示全部楼层
  1. public int getNthfibo(int n) {
  2.         if (n < 0) {
  3.             throw new IllegalArgumentException("n cannot be negative");
  4.         }
  5. . From 1point 3acres bbs
  6.         if (n <= 1) return n;
  7. . Waral 鍗氬鏈夋洿澶氭枃绔,
  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);.鏈枃鍘熷垱鑷1point3acres璁哄潧
  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];. more info on 1point3acres.com

  27.         m[0][0] = a;
  28.         m[0][1] = b;. 1point 3acres 璁哄潧
  29.         m[1][0] = c;
  30.         m[1][1] = d;. 1point 3acres 璁哄潧
  31.     }
复制代码
回复 支持 1 反对 0

使用道具 举报

pyemma 发表于 2015-1-31 00:45:25 | 显示全部楼层
Fib用logn的解法的话应该是用矩阵快速乘的那种方法吧
回复 支持 反对

使用道具 举报

houqingniao 发表于 2015-1-31 03:21:07 | 显示全部楼层
logn 的fib怎么写
回复 支持 反对

使用道具 举报

 楼主| cgdong2012 发表于 2015-2-1 01:22:55 | 显示全部楼层

二楼哥们儿贴出来了
回复 支持 反对

使用道具 举报

ysong1pt3ac 发表于 2015-2-1 02:05:32 | 显示全部楼层

用通项公式 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
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):
假设不需考虑输入异常和溢出
回复 支持 反对

使用道具 举报

csstudyup234 发表于 2015-2-1 03:08:38 | 显示全部楼层
如果用通项公式的话不应该是O(1)吗?
回复 支持 反对

使用道具 举报

douya 发表于 2015-3-12 11:24:36 | 显示全部楼层
多谢楼主!
logn 一般人想不到啊。**能想到的有2个. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
1. dp
2. recusive
3 还与啥呢?
回复 支持 反对

使用道具 举报

douya 发表于 2015-3-12 11:32:06 | 显示全部楼层
第三题能详细说下吗?
回复 支持 反对

使用道具 举报

胖子Jeffwan 发表于 2015-3-12 12:41:08 | 显示全部楼层
douya 发表于 2015-3-12 11:32. 鍥磋鎴戜滑@1point 3 acres
第三题能详细说下吗?

第三题就是BST转成一个循环的linkedlist,用left right 当prev next 的指针了,上网搜一下,都有的
回复 支持 反对

使用道具 举报

douch 发表于 2015-3-12 14:24:04 | 显示全部楼层
fib 的log n的事先没看过现场能想出来那也太牛x了吧
回复 支持 反对

使用道具 举报

北航小涵 发表于 2015-3-19 08:50:13 | 显示全部楼层
  1. //这是二叉树转双向链表的程序,测试通过。
复制代码
回复 支持 反对

使用道具 举报

北航小涵 发表于 2015-3-19 08:51:10 | 显示全部楼层
oops,没贴上
  1. public class SolutionConvert {
  2.     public void solve(TreeNode root) {
  3.         if (root == null) {
  4.             return;
  5.         }
  6.         convertToDoubleLinkedList(root);           
  7.     }. 1point 3acres 璁哄潧
  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;. Waral 鍗氬鏈夋洿澶氭枃绔,
  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.         }. 1point3acres.com/bbs
  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. }
复制代码
回复 支持 反对

使用道具 举报

北航小涵 发表于 2015-3-19 08:51:19 | 显示全部楼层
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;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  15.             convertToDoubleLinkedList(left);
  16.             while (left.right != null) {
  17.                 left = left.right;. 1point3acres.com/bbs
  18.             }
    . 1point3acres.com/bbs
  19.             left.right = root;
  20.             root.left = left;
  21.         }. From 1point 3acres bbs
  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.         }.1point3acres缃
  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");. visit 1point3acres.com for more.
  38.         TreeNode e = new TreeNode("30");
  39.         TreeNode f = new TreeNode("36");. 1point 3acres 璁哄潧
  40.         a.left = b;
  41.         a.right = c;. from: 1point3acres.com/bbs
  42.         b.left = d;
  43.         b.right = e;
  44.         c.left = f;
  45.         solve(a);
  46.         while (a.left != null) {
  47.             a = a.left;-google 1point3acres
  48.         }
  49.         while (a != null) {
  50.             System.out.print(a.val + " ");
  51.             a = a.right;
  52.         }      
  53.     }. From 1point 3acres bbs
  54. }
复制代码
回复 支持 反对

使用道具 举报

yuruofeifei 发表于 2015-3-19 11:53:24 | 显示全部楼层
. 1point 3acres 璁哄潧
谢谢啊!你从哪找的啊?
回复 支持 反对

使用道具 举报

北航小涵 发表于 2015-3-19 19:24:21 | 显示全部楼层
yuruofeifei 发表于 2015-3-18 22:53
谢谢啊!你从哪找的啊?

自己写的。。
回复 支持 反对

使用道具 举报

yanggao1119 发表于 2016-2-19 09:52:37 | 显示全部楼层
个人感觉,楼上解法mix了recursive solution,和iterative solution,不够简明。

我的iterative solution with stack,其实就是一个中序遍历:
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  public TreeNode BT2CircularDLL(TreeNode root) {
    if (root == null) {
      return root;
    }
    Stack<TreeNode> st = new Stack<>();
    TreeNode curr = root;
    TreeNode head = null;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
    TreeNode tail = null;
    TreeNode prev = null;
    while (curr != null || !st.isEmpty()) {
      if (curr != null) {
        st.push(curr);
        curr = curr.left;
      } else {
        TreeNode popped = st.pop();
        if (prev != null) {
          prev.right = popped;
          popped.left = prev;
        } else {
          head = popped;
        }
        prev = popped;
        tail = popped;
        curr = popped.right;
      }
    }.鏈枃鍘熷垱鑷1point3acres璁哄潧
    tail.right = head;
    head.left = tail;
    return head;
  }
回复 支持 反对

使用道具 举报

linlin1990 发表于 2016-2-20 11:21:52 | 显示全部楼层
你面的是intern还是fulltime呀?intern和full time的题目可能会一样吗?
回复 支持 反对

使用道具 举报

本版积分规则

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-7-28 22:55

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表