要回国了,写个简单的总结吧。

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
把贵司招聘信息放这里
查看: 4380|回复: 15
收起左侧

Facebook电面

[复制链接] |试试Instant~ |关注本帖
我的人缘0
姐姐不吃糖 发表于 2016-11-23 03:16:17 | 显示全部楼层 |阅读模式
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】

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

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

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

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

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

评分

1

查看全部评分


上一篇:fb london和us intern面试共享题库吗?
下一篇:linkedin一面

本帖被以下淘专辑推荐:

我的人缘0
清水翔太 发表于 2016-11-23 04:03:00 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
不太理解为什么需要排序,这里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) {. visit 1point3acres for more.
  5.   if(l>r) return null;
  6.   else if(l==r) return new TreeNode(input[l]);. 1point3acres
  7.   int min = l;. Waral 博客有更多文章,
  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);. 牛人云集,一亩三分地
  14.   return root;
  15. }
复制代码

评分

1

查看全部评分

回复 支持 4 反对 0

使用道具 举报

我的人缘0
wangxinbo1123 发表于 2017-1-23 08:47:56 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
  1. Node* buildTree(Iter start, Iter end) {
  2.         if(start == end) return NULL;. visit 1point3acres for more.
  3.         if(start == end - 1) return new Node(*start);
  4.         auto minPos = min_element(start, end);
  5.         Node* node = new Node(*minPos);
  6.         node->left = buildTree(start, minPos);
  7.         node->right = buildTree(minPos+1, end);
  8.         return node;
  9. }
复制代码
回复 支持 1 反对 0

使用道具 举报

我的人缘0
catinclay 发表于 2016-11-23 03:43:52 | 显示全部楼层
挺有趣的题目...楼主思考好快

一直想问问, 这种sort之后还想让index信息被保留有没有什么特别好的方法? 好像有一个方法是类似作merge sort 但先创造一个index array, 并且同时对index array作同样的操作的方法
.本文原创自1point3acres论坛
或是把原本的data用
class Element{
   int index;.留学论坛-一亩-三分地
   int val.留学论坛-一亩-三分地
}. more info on 1point3acres
的方法储存再override comparater...不知道有没有其他思路
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| 姐姐不吃糖 发表于 2016-11-23 03:50:08 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
catinclay 发表于 2016-11-23 03:43
挺有趣的题目...楼主思考好快

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

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

使用道具 举报

我的人缘0
Alice_koi 发表于 2016-11-23 04:12:53 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
可以构建 vector<pair<int, int>>,如果内容没有重复直接排序就可以,如果有重复的话看要不要求stable,正反,视情况考虑直接排序或者自己写个comp functor
回复 支持 反对

使用道具 举报

我的人缘0
hxf 发表于 2016-11-29 02:55:40 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
lz 有结果了嘛?
回复 支持 反对

使用道具 举报

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

使用道具 举报

我的人缘0
Alice_koi 发表于 2016-11-30 05:38:53 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
姐姐不吃糖 发表于 2016-11-30 04:54
很奇怪,一周没有音讯,感觉是挂了的。今天HR突然发邮件说他今天下午2点会受到result,问题什么时候有时间 ...

打电话据说是发offer的啊!!
-google 1point3acres
为什么我还没消息……
回复 支持 反对

使用道具 举报

我的人缘0
nbodqujd 发表于 2016-12-5 11:05:11 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
清水翔太 发表于 2016-11-23 04:03
不太理解为什么需要排序,这里min-heap只是需要把最小值放在root吧?这样按照最小值分割也就能够把保证inor ...
. from: 1point3acres
我也是这么理解的
回复 支持 反对

使用道具 举报

我的人缘0
AndrewFish 发表于 2017-1-9 04:32:47 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
其实, sort的complexity是nlg(n),  在每一个subarray里找最小index的话总complexity也是nlg(n),这么看来不sort直接找每个subtree的root更便捷。
回复 支持 反对

使用道具 举报

头像被屏蔽
我的人缘0
timeforce 发表于 2017-1-10 00:26:41 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

我的人缘0
吃啥才算成熟 发表于 2017-1-12 06:13:39 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
  1. public class Solution6 {
  2.     public TreeNode solve(int[] nums){
  3.         if(nums==null||nums.length==0) return null;
  4.         return build(nums, 0, nums.length-1);
  5.     }
  6.     private TreeNode build(int[] nums, int s, int e){
  7.         if(s>e) return null;. 一亩-三分-地,独家发布
  8.         int min = getMin(nums, s, e);
  9.         TreeNode node = new TreeNode(nums[min]);
  10.         node.left = build(nums, s, min-1);
  11.         node.right = build(nums, min+1, e);
  12.         return node;
  13.     } 来源一亩.三分地论坛.

  14.     private int getMin(int[] nums, int s, int e){
  15.         int min = -1;
  16.         for(int i = s; i<=e; i++){
  17.             if(min==-1 || nums[i]<nums[min]){
  18.                 min = i;
  19.             }. visit 1point3acres for more.
  20.         }
  21.         return min;
  22.     }

  23.     //verification
  24.     public int[] inorder(TreeNode root) {
  25.         List<Integer> nums = new LinkedList<>();
  26.         inorderHelper(root, nums);
  27.         return nums.stream().mapToInt(i->i).toArray();
  28.     }.本文原创自1point3acres论坛
  29.     private void inorderHelper(TreeNode node, List<Integer> nums){. 留学申请论坛-一亩三分地
  30.         if(node.left!=null) inorderHelper(node.left, nums);. 1point 3acres 论坛
  31.         nums.add(node.val);. 1point 3acres 论坛
  32.         if(node.right!=null) inorderHelper(node.right, nums);
  33.     }
  34. }
复制代码
回复 支持 反对

使用道具 举报

我的人缘0
wangxinbo1123 发表于 2017-1-23 08:46:53 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
C++ version:. from: 1point3acres

补充内容 (2017-1-23 08:47):
Node* buildTree(Iter start, Iter end) {
        if(start == end) return NULL;
        if(start == end - 1) return new Node(*start);
        auto minPos = min_element(start, end);.1point3acres网
        Node* node = new Node(*minPos);
        node-...
回复 支持 反对

使用道具 举报

我的人缘0
lhh_NJU 发表于 2017-2-20 12:39:09 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】

我后来也想了这个方法, 比较简单易懂. 楼主的思路也可行不过实现起来好麻烦呢..
回复 支持 反对

使用道具 举报

我的人缘0
bigbearlake 发表于 2017-3-1 13:38:37 | 显示全部楼层
  1. public class Array2Minheap {
  2.     class TreeNode {
  3.         int val;. From 1point 3acres bbs
  4.         TreeNode left, right;
  5.         public TreeNode(int v) {
  6.             val = v;
  7.         }. 1point 3acres 论坛
  8.     }

  9.     public TreeNode getMinheap(int[] arr) {-google 1point3acres
  10.         return helper(arr, 0, arr.length - 1);
  11.     }

  12.     public TreeNode helper(int[] arr, int start, int end) {
  13.         if (start > end) {
  14.             return null;. Waral 博客有更多文章,
  15.         } else if (start == end) {
  16.             return new TreeNode(arr[start]);. more info on 1point3acres
  17.         }
  18.         int min = start;
  19.         for (int i = start; i <= end; i++) {.留学论坛-一亩-三分地
  20.             if (arr[i] < arr[min]) {. 留学申请论坛-一亩三分地
  21.                 min = i;
  22.             }
  23.         }
  24.         TreeNode root = new TreeNode(arr[min]);
  25.         root.left = helper(arr, start, min - 1);
  26.         root.right = helper(arr, min + 1, end);
  27.         return root;
  28.     }

  29.     public void inorder(TreeNode root) {
  30.         if (root == null) {
  31.             return;
  32.         }
  33.         inorder(root.left);
  34.         System.out.println(root.val + " ");
  35.         inorder(root.right);
  36.     }

  37.     public static void main(String[] args) {
  38.         int[] arr = {5, 9, 4, 10, 1, 8, 11, 6};
  39.         Array2Minheap a = new Array2Minheap();
  40.         a.inorder(a.getMinheap(arr));
  41.     }
  42. }
复制代码
回复 支持 反对

使用道具 举报

游客
请先登录

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2018-5-27 17:21

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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