近期论坛无法登录的解决方案


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 2938|回复: 19
收起左侧

Facebook 11.2 intern一轮面试

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

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

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

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

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

评分

2

查看全部评分

graininear 发表于 2016-11-3 02:52:21 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
感谢分享,楼主加油
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-11-3 02:58:52 | 显示全部楼层
关注一亩三分地微博:
Warald
第二题空间复杂度指的不是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的深度吧?

不是,就是说直接在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..

. 1point 3acres 璁哄潧对,相当于把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) {. 1point3acres.com/bbs
  if (!p) return;. visit 1point3acres.com for more.
  treeToDoublyList(p->left, prev, head);.鐣欏璁哄潧-涓浜-涓夊垎鍦
  p->left = prev;. 1point3acres.com/bbs
  if (prev)
    prev->right = p;
  else
    head = p;
  Node *right = p->right;
  head->left = p;
  p->right = head;
  prev = p;
  treeToDoublyList(right, prev, head);
}


Node* treeToDoublyList(Node *root) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  Node *prev = NULL;-google 1point3acres
  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

. 1point 3acres 璁哄潧可是你这样递归不是用了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)空间。。
. 1point 3acres 璁哄潧
嗯嗯,对。是我表达的问题,抱歉
回复 支持 反对

使用道具 举报

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了。很不开心

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-6-29 14:00

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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