一亩三分地论坛

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

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

Facebook 11.2 intern一轮面试

[复制链接] |试试Instant~ |关注本帖
tkw1110 发表于 2016-11-3 02:44:22 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 实习@Facebook - 内推 -  |Otherfresh grad应届毕业生

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

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

x
来写一个新鲜面经了。最近要面Facebook,看了很多地里的题,也该来回报回报了!顺便攒人品求过!
面试官是一个非常nice的美国小哥。十分钟resume,然后两个算法题,最后五分钟question。
1.divide two intergers.鏈枃鍘熷垱鑷1point3acres璁哄潧
当时写的很快,解释+bug free大概10分钟。但是英语真的很渣,解释半天都没有说清楚,最后面试官估计无奈了就开了下一题。
2.convert binary tree to doubly linked list
这个题有一些改变,不能定义新的数据结构,也不能使用额外的空间。空间复杂度要求O(1).
一开始没听清要求,快速写完了。后来花了10多分钟才改过来bug free。
虽然两个题都bug free了,但是感觉写的有点磕磕绊绊,估计有点悬。
只能祈祷发面经求第二轮了,哎。

补充内容 (2016-11-4 12:47):. from: 1point3acres.com/bbs
好吧,真是奇怪的sad story,最后还是收到的拒信。难道是申请太晚了bar太高了吗?

评分

2

查看全部评分

graininear 发表于 2016-11-3 02:52:21 | 显示全部楼层
感谢分享,楼主加油
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-11-3 02:58:52 | 显示全部楼层
第二题空间复杂度指的不是revision memory stack的深度吧?
回复 支持 反对

使用道具 举报

wangyuesong2 发表于 2016-11-3 06:15:02 | 显示全部楼层
第二题递归或者栈的话的话不就需要memory了吗. more info on 1point3acres.com
楼主肯定稳了
回复 支持 反对

使用道具 举报

finerve 发表于 2016-11-3 06:29:22 | 显示全部楼层
第二题tree node本身是双向的node吗?否则不能定义新数据结构,又要doubly linked..
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-11-3 06:38:30 | 显示全部楼层
lz方便第2题,贴个代码么,非常感谢。
回复 支持 反对

使用道具 举报

Badger96 发表于 2016-11-3 06:57:33 | 显示全部楼层
也只有Morris Traversal能做到O(1)空间了吧。。
回复 支持 反对

使用道具 举报

 楼主| tkw1110 发表于 2016-11-3 11:29:08 | 显示全部楼层
wtcupup 发表于 2016-11-3 02:58
第二题空间复杂度指的不是revision memory stack的深度吧?

不是,就是说直接在TreenNode上做修改,不能开辟新的节点。
回复 支持 反对

使用道具 举报

 楼主| tkw1110 发表于 2016-11-3 11:29:44 | 显示全部楼层
wangyuesong2 发表于 2016-11-3 06:15
第二题递归或者栈的话的话不就需要memory了吗
楼主肯定稳了
. 1point 3acres 璁哄潧
应该是不允许用栈的,在原TreeNode上做修改
回复 支持 反对

使用道具 举报

 楼主| tkw1110 发表于 2016-11-3 11:30:14 | 显示全部楼层
finerve 发表于 2016-11-3 06:29
第二题tree node本身是双向的node吗?否则不能定义新数据结构,又要doubly linked..

对,相当于把left变成previous,right就是next
回复 支持 反对

使用道具 举报

 楼主| tkw1110 发表于 2016-11-3 11:32:10 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-11-3 06:38
lz方便第2题,贴个代码么,非常感谢。
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
void treeToDoublyList(Node *p, Node *& prev, Node *& head) {
  if (!p) return;
  treeToDoublyList(p->left, prev, head);
  p->left = prev;
  if (prev)
    prev->right = p;
  else
    head = p;
  Node *right = p->right;
  head->left = p;
. 1point3acres.com/bbs  p->right = head;
  prev = p;
  treeToDoublyList(right, prev, head);
}. From 1point 3acres bbs
. 1point3acres.com/bbs

Node* treeToDoublyList(Node *root) {
  Node *prev = NULL;
  Node *head = NULL;
  treeToDoublyList(root, prev, head);
  return head;
}

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| tkw1110 发表于 2016-11-3 11:32:34 | 显示全部楼层
Badger96 发表于 2016-11-3 06:57
也只有Morris Traversal能做到O(1)空间了吧。。
.1point3acres缃
其实就是convert in place
回复 支持 反对

使用道具 举报

Alice_koi 发表于 2016-11-3 11:40:46 | 显示全部楼层
tkw1110 发表于 2016-11-3 11:32.鐣欏璁哄潧-涓浜-涓夊垎鍦
其实就是convert in place

可是你这样递归不是用了stack space么?不算O(1)空间复杂度吧
回复 支持 反对

使用道具 举报

Badger96 发表于 2016-11-3 12:03:15 | 显示全部楼层
明白了,楼主的意思是要inplace修改成ddl,不过用递归并不是O(1)空间。。
回复 支持 反对

使用道具 举报

 楼主| tkw1110 发表于 2016-11-3 13:12:34 | 显示全部楼层
Badger96 发表于 2016-11-3 12:03
明白了,楼主的意思是要inplace修改成ddl,不过用递归并不是O(1)空间。。

嗯嗯,对。是我表达的问题,抱歉
回复 支持 反对

使用道具 举报

xxxxx56789 发表于 2016-11-3 14:37:59 | 显示全部楼层
geeksforgeeks.org/in-place-convert-a-given-binary-tree-to-doubly-linked-list/ 一样吧?
回复 支持 反对

使用道具 举报

 楼主| tkw1110 发表于 2016-11-4 12:49:16 | 显示全部楼层
xxxxx56789 发表于 2016-11-3 14:37
geeksforgeeks.org/in-place-convert-a-given-binary-tree-to-doubly-linked-list/ 一样吧?

对,就是这个
回复 支持 反对

使用道具 举报

honghunan 发表于 2016-11-4 23:51:15 | 显示全部楼层
他给你的估计是 据+很确定。所以你就被据了,和bar没什么关系。如果他给你一个过+不确定,你都可以继续下一轮的。当然这是我猜的,估计小哥比较心黑吧。
回复 支持 反对

使用道具 举报

 楼主| tkw1110 发表于 2016-11-5 02:00:00 | 显示全部楼层
honghunan 发表于 2016-11-4 23:51
他给你的估计是 据+很确定。所以你就被据了,和bar没什么关系。如果他给你一个过+不确定,你都可以继续下一 ...

哎,真不知道什么鬼,明明都bug free了。很不开心
回复 支持 反对

使用道具 举报

honghunan 发表于 2016-11-5 04:56:07 | 显示全部楼层
tkw1110 发表于 2016-11-5 02:00
哎,真不知道什么鬼,明明都bug free了。很不开心

表担心,好公司还很多呢!!加油!!勤奋会有回报的!
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 11:00

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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