一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2482|回复: 22
收起左侧

Fackbook 下午刚电面的面筋

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

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

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

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

废话不多, 上题:

1. 写出 fib(n). 不是很难。
但是让一共写了三种方法, 注意 corner case。. more info on 1point3acres.com

2.写 divide operation  a / b .. 1point3acres.com/bbs
不能用  / 操作。
刚开始写了一个 o(n) 的 让改进成 o(log n)的。
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
3. 把二叉树 改成一个 循环双向链表。.1point3acres缃
no extra space. 把左右指针当成 pre , next 指针。
. visit 1point3acres.com for more.
求人品, 求大米。 谢谢大家~. 1point 3acres 璁哄潧


补充内容 (2015-1-30 11:36):
Fib 那个最终 解法是 o(log n)的running time. From 1point 3acres bbs

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

评分

3

查看全部评分

本帖被以下淘专辑推荐:

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

使用道具 举报

 楼主| cgdong2012 发表于 2015-1-31 01:45:13 | 显示全部楼层
pyemma 发表于 2015-1-31 00:45
Fib用logn的解法的话应该是用矩阵快速乘的那种方法吧

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.         if (n <= 1) return n;

  6.         int[][] result = {{1, 0}, {0, 1}};
  7.         int[][] fiboM = {{1, 1}, {1, 0}};. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

  8.         while (n > 0) {
  9.             if (n % 2 == 1) {
  10.                 multMatrix(result, fiboM);.鐣欏璁哄潧-涓浜-涓夊垎鍦
  11.             }.鏈枃鍘熷垱鑷1point3acres璁哄潧
  12.             n = n / 2;
  13.             multMatrix(fiboM, fiboM);
  14.         }

  15.         return result[1][0];
  16.     }

  17.     private void multMatrix(int[][] m, int [][] n) {
  18.         int a = m[0][0] * n[0][0] +  m[0][1] * n[1][0];. from: 1point3acres.com/bbs
  19.         int b = m[0][0] * n[0][1] +  m[0][1] * n[1][1];. Waral 鍗氬鏈夋洿澶氭枃绔,
  20.         int c = m[1][0] * n[0][0] +  m[1][1] * n[1][0];
  21.         int d = m[1][0] * n[0][1] +  m[1][1] * n[1][1];

  22.         m[0][0] = a;
  23.         m[0][1] = b;
  24.         m[1][0] = c;
  25.         m[1][1] = d;-google 1point3acres
  26.     }
复制代码
回复 支持 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){. 1point 3acres 璁哄潧
  2.     double sqrt_five=sqrt(5);.1point3acres缃
  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. }
复制代码
. from: 1point3acres.com/bbs
补充内容 (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
第三题能详细说下吗?
.鐣欏璁哄潧-涓浜-涓夊垎鍦
第三题就是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 {. 鍥磋鎴戜滑@1point 3 acres
  2.     public void solve(TreeNode root) {.1point3acres缃
  3.         if (root == null) {
  4.             return;
  5.         }
  6.         convertToDoubleLinkedList(root);           
  7.     }. 1point 3acres 璁哄潧
  8.     . From 1point 3acres bbs
  9.     public void convertToDoubleLinkedList(TreeNode root) {
  10.         if (root == null) {
  11.             return;. visit 1point3acres.com for more.
  12.         }
  13.         if (root.left != null) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  14.             TreeNode left = root.left;. 1point3acres.com/bbs
  15.             convertToDoubleLinkedList(left);
  16.             while (left.right != null) {
  17.                 left = left.right;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  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;. 1point3acres.com/bbs
  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) {. 1point 3acres 璁哄潧
  47.             a = a.left;
  48.         }
  49.         while (a != null) {
  50.             System.out.print(a.val + " ");. Waral 鍗氬鏈夋洿澶氭枃绔,
  51.             a = a.right;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  52.         }      
  53.     }
  54. }
复制代码
回复 支持 反对

使用道具 举报

北航小涵 发表于 2015-3-19 08:51:19 | 显示全部楼层
oops,没贴上
  1. public class SolutionConvert {. 1point 3acres 璁哄潧
  2.     public void solve(TreeNode root) {. 1point3acres.com/bbs
  3.         if (root == null) {
  4.             return;
  5.         }
  6.         convertToDoubleLinkedList(root);           . Waral 鍗氬鏈夋洿澶氭枃绔,
  7.     }
  8.    
  9.     public void convertToDoubleLinkedList(TreeNode root) {. From 1point 3acres bbs
  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;. Waral 鍗氬鏈夋洿澶氭枃绔,
  18.             }
  19.             left.right = root;. 鍥磋鎴戜滑@1point 3 acres
  20.             root.left = left;
  21.         }
  22.         if (root.right != null) {
  23.             TreeNode right = root.right;
  24.             convertToDoubleLinkedList(right);. 1point 3acres 璁哄潧
  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;. From 1point 3acres bbs
  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.         }.1point3acres缃
  49.         while (a != null) {
  50.             System.out.print(a.val + " ");
  51.             a = a.right;
  52.         }      
  53.     }
  54. }
复制代码
回复 支持 反对

使用道具 举报

yuruofeifei 发表于 2015-3-19 11:53:24 | 显示全部楼层
北航小涵 发表于 2015-3-19 08:51. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
oops,没贴上

谢谢啊!你从哪找的啊?
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

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

我的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;-google 1point3acres
      } else {
        TreeNode popped = st.pop();
        if (prev != null) {
          prev.right = popped;
          popped.left = prev;. Waral 鍗氬鏈夋洿澶氭枃绔,
        } else {
          head = popped;
        }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
        prev = popped;
        tail = popped;
        curr = popped.right;
      }
    }
    tail.right = head;
    head.left = tail;
    return head;
  }
回复 支持 反对

使用道具 举报

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

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-3 12:42

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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