一亩三分地论坛

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

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

Facebook电面

[复制链接] |试试Instant~ |关注本帖
姐姐不吃糖 发表于 2016-11-23 03:16:17 | 显示全部楼层 |阅读模式

2017(1-3月) 码农类 硕士 全职@Facebook - Other - 技术电面 |Other在职跳槽

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

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

x
10mins前刚刚结束的Facebook电面。准备的面经题竟然都没用上。。。

一个印度小哥准时打来电话,听说话人还比较nice。简单介绍了一下他在Facebook做的东西,然后问了我一些当前工作的一些问题以及为什么想去Facebook等等。。
然后打开coderpad开始做题。小哥只给了一道题,感觉特别虚。。。
题目是给一个array,然后根据这个input array建一颗binary tree,同时要满足minheap property和inorder traversal preserve original order of the array。
一上来有点儿懵,跑了两个sample大概有了点儿思路就开始做题。思路大概是先要sort一个array但是要记录sort前在array中的index,我用的map。然后每次取出最小的insert到tree里面,insert只要按index以建bst的方式插入就行了。这样inorder就preserve了之前的顺序。大概就是这样。。求好运!求过!

评分

1

查看全部评分

catinclay 发表于 2016-11-23 03:43:52 | 显示全部楼层
挺有趣的题目...楼主思考好快 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

一直想问问, 这种sort之后还想让index信息被保留有没有什么特别好的方法? 好像有一个方法是类似作merge sort 但先创造一个index array, 并且同时对index array作同样的操作的方法

或是把原本的data用
class Element{
   int index;
   int val
}
的方法储存再override comparater...不知道有没有其他思路
回复 支持 反对

使用道具 举报

 楼主| 姐姐不吃糖 发表于 2016-11-23 03:50:08 | 显示全部楼层
catinclay 发表于 2016-11-23 03:43
挺有趣的题目...楼主思考好快 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

一直想问问, 这种sort之后还想让index信息被保留有没有什么特别好的方法?  ...

我就用的map<pair<int, int>> //<val, index>
回复 支持 反对

使用道具 举报

清水翔太 发表于 2016-11-23 04:03:00 | 显示全部楼层
不太理解为什么需要排序,这里min-heap只是需要把最小值放在root吧?这样按照最小值分割也就能够把保证inorder的顺序了,不知道是不是我理解错了
  1. public TreeNode(int[] input) {
  2.   return sol(input, 0, input.length-1);
  3. }
  4. public TreeNode sol(int[] input, int l, int r) {
  5.   if(l>r) return null;
  6.   else if(l==r) return new TreeNode(input[l]);
  7.   int min = l;. more info on 1point3acres.com
  8.   for(int i=l; i<=r; i++) {
  9.     if(input[min]>input[i]) min = i;
  10.   }
  11.   TreeNode root = new TreeNode(input[min]);
  12.   root.left = sol(input, l, min-1);
  13.   root.right = sol(input, min+1, right);
    . 1point3acres.com/bbs
  14.   return root;. visit 1point3acres.com for more.
  15. }
复制代码
回复 支持 反对

使用道具 举报

Alice_koi 发表于 2016-11-23 04:12:53 | 显示全部楼层
可以构建 vector<pair<int, int>>,如果内容没有重复直接排序就可以,如果有重复的话看要不要求stable,正反,视情况考虑直接排序或者自己写个comp functor
回复 支持 反对

使用道具 举报

hxf 发表于 2016-11-29 02:55:40 | 显示全部楼层
lz 有结果了嘛?
回复 支持 反对

使用道具 举报

 楼主| 姐姐不吃糖 发表于 2016-11-30 04:54:35 | 显示全部楼层
很奇怪,一周没有音讯,感觉是挂了的。今天HR突然发邮件说他今天下午2点会受到result,问题什么时候有时间可以联系我。。。只是一个电面而已,为什么看起来这么奇葩。而且 感觉上来讲不是什么好结果
回复 支持 反对

使用道具 举报

Alice_koi 发表于 2016-11-30 05:38:53 | 显示全部楼层
姐姐不吃糖 发表于 2016-11-30 04:54
很奇怪,一周没有音讯,感觉是挂了的。今天HR突然发邮件说他今天下午2点会受到result,问题什么时候有时间 ...

打电话据说是发offer的啊!!.鏈枃鍘熷垱鑷1point3acres璁哄潧

为什么我还没消息……
回复 支持 反对

使用道具 举报

nbodqujd 发表于 6 天前 | 显示全部楼层
清水翔太 发表于 2016-11-23 04:03
不太理解为什么需要排序,这里min-heap只是需要把最小值放在root吧?这样按照最小值分割也就能够把保证inor ...

我也是这么理解的
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 16:17

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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