一亩三分地论坛

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

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

FB fresh grad 电面

[复制链接] |试试Instant~ |关注本帖
LumiG 发表于 2016-10-7 06:28:52 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 全职@Facebook - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
刚面的FB,电面,不过因为人现在正在湾区,HR说可以onsite,还是45min一轮,当做电面,就人过去了。居然碰到了面经以外的题,所以来发个帖给以后攒个人品。。. 1point 3acres 璁哄潧
第一题是那个BST转双向链表的,很简单。

第二题,逆序输出一个单链表,要求空间复杂度为O(lgn),不能修改链表结构(也就是不可以reverse链表,然后再reverse回去),可以适当牺牲时间负责度(其实就是O(nlgn)的意思)。

第二题想了有好几分钟,和他还confirm了好几次。。最后做的大概就是每次走到终点,递归右半段,然后再递归左半段,最后给他画颗递归树证明下复杂度就行了,他也认可了。不过看起来这个做法相对奇葩一点,他看我画的还想了一会,似乎这不是他原来设想的方案吧,但也确实没毛病。
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

补充内容 (2016-10-7 06:44):
第一题期间还问了一下C语言怎么实现一个栈,说下用array和链表大概怎么做的就行了。然后array每次应该分配多大的空间,我说考虑cache line大小,他说可以。其实还挺奇怪的,FB会问这种东西……

评分

2

查看全部评分

wtcupup 发表于 2016-10-7 06:38:27 | 显示全部楼层
这样的话,空间是O(N) ?
void printReverse(Node head)
    {
        if (head == null) return;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

        // print list of head node. 1point3acres.com/bbs
        printReverse(head.next);.鐣欏璁哄潧-涓浜-涓夊垎鍦
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
        // After everything else is printed
        System.out.print(head.data+" ");
    }
回复 支持 反对

使用道具 举报

 楼主| LumiG 发表于 2016-10-7 06:42:37 | 显示全部楼层
wtcupup 发表于 2016-10-7 06:38
这样的话,空间是O(N) ?
void printReverse(Node head)
    {

对,这个是O(N)的,递归深度为N。所以要改一下函数签名,void(Node head, int length)这样,每次找到mid = lenght/2的那个节点,然后递归右半段,再递归左半段。这样每次压栈的常数复杂度空间,递归树深度是lgn的,宽度是n。所以空间lgn,时间nlgn
回复 支持 反对

使用道具 举报

cwjade 发表于 2016-10-7 06:46:02 | 显示全部楼层
请问LZ什么时候内推的啊?
回复 支持 反对

使用道具 举报

 楼主| LumiG 发表于 2016-10-7 06:49:28 | 显示全部楼层
八月份,但是CMU凡是不着急面试的都给压到这两周电面了……

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

steveguang 发表于 2016-10-7 11:52:43 | 显示全部楼层
楼主提到自己会C语言了所有才会问那个问题么?
回复 支持 反对

使用道具 举报

 楼主| LumiG 发表于 2016-10-7 13:32:17 | 显示全部楼层
steveguang 发表于 2016-10-7 11:52
楼主提到自己会C语言了所有才会问那个问题么?

没有,我面试用python。
回复 支持 反对

使用道具 举报

celtspirit 发表于 2016-10-9 23:09:37 | 显示全部楼层
麻烦描述一下第一题可以么,纯粹的把BST转换成double linked list?
回复 支持 反对

使用道具 举报

何打发123 发表于 2016-10-9 23:53:37 | 显示全部楼层
LumiG 发表于 2016-10-7 06:42. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
对,这个是O(N)的,递归深度为N。所以要改一下函数签名,void(Node head, int length)这样,每次找到mid  ...

感谢楼主分享~~~  不过没懂啊 T T。。 啥叫做先递归右半边啊 T T 能贴个代码嘛?~
回复 支持 反对

使用道具 举报

111180611 发表于 2016-10-10 00:33:17 | 显示全部楼层
  1. public static void printReverse(ListNode head){.鏈枃鍘熷垱鑷1point3acres璁哄潧
  2.                 int len = 0;
  3.                 ListNode node = head;
  4.                 while(node != null){. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  5.                         node = node.next;
  6.                         len++;
  7.                 }
  8.                 print(head, len);.鏈枃鍘熷垱鑷1point3acres璁哄潧
  9.         }
  10.        
  11.         public static void print(ListNode head, int len){
  12.                 if(head == null){
  13.                         return;
  14.                 }
  15.                 if(len == 1){
  16.                         System.out.println(head.val);
  17.                         return;. From 1point 3acres bbs
  18.                 }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  19.                 ListNode node = head;
  20.                 int count = 0;
  21.                 while(node != null && count < len / 2){ 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  22.                         node = node.next;
  23.                         count++;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  24.                 }
  25.                 print(node, len - count);
  26.                 print(head, count);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  27.         }
复制代码


我用java写的 , 楼主看看是这个意思嘛? 这复杂度应该是O(nlogn)
回复 支持 反对

使用道具 举报

wxl3691 发表于 2016-10-10 00:45:55 | 显示全部楼层
111180611 发表于 2016-10-10 00:33
我用java写的 , 楼主看看是这个意思嘛? 这复杂度应该是O(nlogn)

感觉是对的
回复 支持 反对

使用道具 举报

forestwn 发表于 2016-10-10 01:11:44 | 显示全部楼层
请问lz第一题是怎么做的?...
回复 支持 反对

使用道具 举报

 楼主| LumiG 发表于 2016-10-10 04:51:27 | 显示全部楼层
111180611 发表于 2016-10-10 00:33
我用java写的 , 楼主看看是这个意思嘛? 这复杂度应该是O(nlogn)
. From 1point 3acres bbs
嗯嗯对,我差不多就是这么做的…
回复 支持 反对

使用道具 举报

 楼主| LumiG 发表于 2016-10-10 04:54:55 | 显示全部楼层
forestwn 发表于 2016-10-10 01:11
请问lz第一题是怎么做的?...
.鏈枃鍘熷垱鑷1point3acres璁哄潧
LC114,双链表单链表没有区别,连成circle只要找好tail就是了。 面试的时候我是拿个stack写中序遍历的。不过我有小伙伴面试的时候碰到同一个题,被面试官要求用常数空间复杂度来写的,我的面试官倒是没说,直接让做下一题了。可以看下线索二叉树遍历的那个方法……
回复 支持 反对

使用道具 举报

wcyz666 发表于 2016-10-10 04:59:47 | 显示全部楼层
特地来膜一下谷神
回复 支持 反对

使用道具 举报

 楼主| LumiG 发表于 2016-10-10 05:29:35 | 显示全部楼层
wcyz666 发表于 2016-10-10 04:59
特地来膜一下谷神

成神不黑……但凡你随便分我一个offer。。我还在这刷什么面经……
回复 支持 反对

使用道具 举报

木子星 发表于 2016-10-13 07:20:34 | 显示全部楼层
特来膜拜谷神
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 20:09

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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