我是家长,妈妈一枚,突然想写点什么(不太会写)

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推多家公司面试
[Google级团队]:实时大数据分析领域践行者
北京/深圳-大数据/搜索/机器学习职位
日志易机器大数据行业践行者Web/大数据/机器学习等职位-北京or深圳
把贵司招聘信息放这里
查看: 3356|回复: 19
收起左侧

Facebook 11.2 intern一轮面试

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

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

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

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

x
来写一个新鲜面经了。最近要面Facebook,看了很多地里的题,也该来回报回报了!顺便攒人品求过!
面试官是一个非常nice的美国小哥。十分钟resume,然后两个算法题,最后五分钟question。
1.divide two intergers
当时写的很快,解释+bug free大概10分钟。但是英语真的很渣,解释半天都没有说清楚,最后面试官估计无奈了就开了下一题。. 1point3acres.com/bbs
2.convert binary tree to doubly linked list
这个题有一些改变,不能定义新的数据结构,也不能使用额外的空间。空间复杂度要求O(1).
一开始没听清要求,快速写完了。后来花了10多分钟才改过来bug free。
虽然两个题都bug free了,但是感觉写的有点磕磕绊绊,估计有点悬。
只能祈祷发面经求第二轮了,哎。
. more info on 1point3acres.com
补充内容 (2016-11-4 12:47):
好吧,真是奇怪的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了吗
楼主肯定稳了
回复 支持 反对

使用道具 举报

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的深度吧?
-google 1point3acres
不是,就是说直接在TreenNode上做修改,不能开辟新的节点。
回复 支持 反对

使用道具 举报

 楼主| tkw1110 发表于 2016-11-3 11:29:44 | 显示全部楼层
wangyuesong2 发表于 2016-11-3 06:15
第二题递归或者栈的话的话不就需要memory了吗
楼主肯定稳了

应该是不允许用栈的,在原TreeNode上做修改
回复 支持 反对

使用道具 举报

 楼主| tkw1110 发表于 2016-11-3 11:30:14 | 显示全部楼层
finerve 发表于 2016-11-3 06:29
第二题tree node本身是双向的node吗?否则不能定义新数据结构,又要doubly linked..
. 1point3acres.com/bbs
对,相当于把left变成previous,right就是next
回复 支持 反对

使用道具 举报

 楼主| tkw1110 发表于 2016-11-3 11:32:10 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-11-3 06:38. more info on 1point3acres.com
lz方便第2题,贴个代码么,非常感谢。

void treeToDoublyList(Node *p, Node *& prev, Node *& head) {
  if (!p) return;
  treeToDoublyList(p->left, prev, head);
  p->left = prev;. Waral 鍗氬鏈夋洿澶氭枃绔,
  if (prev). Waral 鍗氬鏈夋洿澶氭枃绔,
    prev->right = p;
  else
    head = p; . Waral 鍗氬鏈夋洿澶氭枃绔,
  Node *right = p->right;
  head->left = p;
  p->right = head;
  prev = p;
  treeToDoublyList(right, prev, head);
}


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)空间了吧。。

其实就是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了。很不开心

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2018-4-24 14:53

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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