一亩三分地论坛

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

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

Facebook last round phone interview

[复制链接] |试试Instant~ |关注本帖
wsnalice 发表于 2016-11-30 13:32:26 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 本科 实习@Facebook - 内推 - 技术电面 |Pass其他

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

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

x
昨天完成的最後一輪(也就是第二個。。)phone interview,今天收offer了,HR效率很高

題目:
1st round: given the in-order traversal list of a binary search tree, generate the tree
2nd round: given a list, generate all unique combinations of the elements 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

大米


补充内容 (2016-11-30 15:15):
1st round 的 in-order 應該是 pre-order。。

评分

2

查看全部评分

鼓頔娜夫 发表于 2016-11-30 16:36:52 | 显示全部楼层
wsnalice 发表于 2016-11-30 15:31
可以還原的,第一個node是root,之後的sublist分成前後兩部分,前面是都比root小的,後面是比它大的。主 ...

是的,用O(logn) space的话, 最优解可以做到O(n) time complexity
回复 支持 1 反对 0

使用道具 举报

darksteel 发表于 2016-11-30 14:05:18 | 显示全部楼层
恭喜楼主啊!请问第一题是要求generate出来的tree是balanced么?第二题是不是类似lc的subset
回复 支持 反对

使用道具 举报

yy318 发表于 2016-11-30 14:13:10 | 显示全部楼层
请问楼主两轮都是一道题嘛?
回复 支持 反对

使用道具 举报

yy318 发表于 2016-11-30 14:28:26 | 显示全部楼层
darksteel 发表于 2016-11-30 14:05
恭喜楼主啊!请问第一题是要求generate出来的tree是balanced么?第二题是不是类似lc的subset

虽然我第一感觉也被fb题库限制了觉得像subset,但后来看了看感觉是lc 46 permutation
回复 支持 反对

使用道具 举报

xuzhikun 发表于 2016-11-30 14:33:34 | 显示全部楼层
yy318 发表于 2016-11-29 22:28
虽然我第一感觉也被fb题库限制了觉得像subset,但后来看了看感觉是lc 46 permutation

第一题是LC108. Convert Sorted Array to Binary Search Tree  吧??
回复 支持 反对

使用道具 举报

yy318 发表于 2016-11-30 14:58:43 | 显示全部楼层
xuzhikun 发表于 2016-11-30 14:33
第一题是LC108. Convert Sorted Array to Binary Search Tree  吧??

虽然问法不一样,但是感觉就是一道题。。。。
回复 支持 反对

使用道具 举报

 楼主| wsnalice 发表于 2016-11-30 15:14:16 | 显示全部楼层
1st round 的 in-

补充内容 (2016-11-30 15:15):
1st round 的 in-order 應該是 pre-order。。
回复 支持 反对

使用道具 举报

 楼主| wsnalice 发表于 2016-11-30 15:17:45 | 显示全部楼层
darksteel 发表于 2016-11-30 14:05
恭喜楼主啊!请问第一题是要求generate出来的tree是balanced么?第二题是不是类似lc的subset

tree不一定是balanced的
第二題就是subset
回复 支持 反对

使用道具 举报

 楼主| wsnalice 发表于 2016-11-30 15:18:07 | 显示全部楼层
yy318 发表于 2016-11-30 14:13
请问楼主两轮都是一道题嘛?
-google 1point3acres
         是的
回复 支持 反对

使用道具 举报

BRYCEMENG 发表于 2016-11-30 15:18:17 | 显示全部楼层
lz能详细说下第二轮的题吗?谢谢
回复 支持 反对

使用道具 举报

 楼主| wsnalice 发表于 2016-11-30 15:19:32 | 显示全部楼层
BRYCEMENG 发表于 2016-11-30 15:18
lz能详细说下第二轮的题吗?谢谢
. visit 1point3acres.com for more.
就是lc的subset
回复 支持 反对

使用道具 举报

BRYCEMENG 发表于 2016-11-30 15:25:45 | 显示全部楼层
wsnalice 发表于 2016-11-30 15:19.1point3acres缃
就是lc的subset

谢谢,请问下第一题如果是pre order的话无法还原BST把,对最后的结果有什么要求吗?谢谢
回复 支持 反对

使用道具 举报

 楼主| wsnalice 发表于 2016-11-30 15:31:15 | 显示全部楼层
BRYCEMENG 发表于 2016-11-30 15:25
谢谢,请问下第一题如果是pre order的话无法还原BST把,对最后的结果有什么要求吗?谢谢

可以還原的,第一個node是root,之後的sublist分成前後兩部分,前面是都比root小的,後面是比它大的。主要是用binary search找partitioning index
回复 支持 反对

使用道具 举报

 楼主| wsnalice 发表于 2016-11-30 15:31:44 | 显示全部楼层
BRYCEMENG 发表于 2016-11-30 15:25
谢谢,请问下第一题如果是pre order的话无法还原BST把,对最后的结果有什么要求吗?谢谢

可以還原的,第一個node是root,之後的sublist分成前後兩部分,前面是都比root小的,後面是比它大的。主要是用binary search找partitioning index
回复 支持 反对

使用道具 举报

BRYCEMENG 发表于 2016-11-30 22:37:36 | 显示全部楼层
wsnalice 发表于 2016-11-30 15:31
可以還原的,第一個node是root,之後的sublist分成前後兩部分,前面是都比root小的,後面是比它大的。主 ...

对对对,是search tree。。。
回复 支持 反对

使用道具 举报

qqrcde 发表于 2016-11-30 22:49:06 | 显示全部楼层
哎,同样是电面,google总是DP。。。
回复 支持 反对

使用道具 举报

catinclay 发表于 2016-12-1 00:01:17 | 显示全部楼层
鼓頔娜夫 发表于 2016-11-30 16:36.鏈枃鍘熷垱鑷1point3acres璁哄潧
是的,用O(logn) space的话, 最优解可以做到O(n) time complexity

请问怎么做到O(n) complexity呢?

补充内容 (2016-12-1 00:02):
time complexity
回复 支持 反对

使用道具 举报

zhihaosun 发表于 2016-12-1 00:12:18 | 显示全部楼层
第一题用递归仔细做一下就差不多了吧,第二个先每个distinct element计个数再backtrack吧
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 15:11

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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