[八我司] 介绍一下Uber tech stack和各个大组的情况

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 5439|回复: 16
收起左侧

FB fresh grad 电面

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

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

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

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

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

第二题,逆序输出一个单链表,要求空间复杂度为O(lgn),不能修改链表结构(也就是不可以reverse链表,然后再reverse回去),可以适当牺牲时间负责度(其实就是O(nlgn)的意思)。
. 围观我们@1point 3 acres
第二题想了有好几分钟,和他还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)
    {
. visit 1point3acres for more.        if (head == null) return; 来源一亩.三分地论坛.

        // print list of head node
. 围观我们@1point 3 acres        printReverse(head.next);

        // After everything else is printed
        System.out.print(head.data+" ");. visit 1point3acres for more.
    }
回复 支持 反对

使用道具 举报

 楼主| 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.本文原创自1point3acres论坛
楼主提到自己会C语言了所有才会问那个问题么?

来源一亩.三分地论坛. 没有,我面试用python。
回复 支持 反对

使用道具 举报

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

使用道具 举报

何打发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){
  2.                 int len = 0;
  3.                 ListNode node = head;. Waral 博客有更多文章,
  4.                 while(node != null){
  5.                         node = node.next;
  6.                         len++;
  7.                 }
  8.                 print(head, len);
  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;
  18.                 }
  19.                 ListNode node = head;. 留学申请论坛-一亩三分地
  20.                 int count = 0;
  21.                 while(node != null && count < len / 2){.留学论坛-一亩-三分地
  22.                         node = node.next;
  23.                         count++;
  24.                 }
  25.                 print(node, len - count); 来源一亩.三分地论坛.
  26.                 print(head, count);
  27.         }
复制代码
. visit 1point3acres for more.

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

使用道具 举报

wxl3691 发表于 2016-10-10 00:45:55 | 显示全部楼层
111180611 发表于 2016-10-10 00:33. visit 1point3acres for more.
我用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)

嗯嗯对,我差不多就是这么做的…
回复 支持 反对

使用道具 举报

 楼主| LumiG 发表于 2016-10-10 04:54:55 | 显示全部楼层
forestwn 发表于 2016-10-10 01:11
请问lz第一题是怎么做的?...

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 | 显示全部楼层
特来膜拜谷神
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

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

custom counter

GMT+8, 2018-5-25 19:28

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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