《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 4077|回复: 15
收起左侧

Facebook电面

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

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

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

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

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

评分

1

查看全部评分

本帖被以下淘专辑推荐:

清水翔太 发表于 2016-11-23 04:03:00 | 显示全部楼层
不太理解为什么需要排序,这里min-heap只是需要把最小值放在root吧?这样按照最小值分割也就能够把保证inorder的顺序了,不知道是不是我理解错了
  1. public TreeNode(int[] input) {
  2.   return sol(input, 0, input.length-1);
  3. }. Waral 鍗氬鏈夋洿澶氭枃绔,
  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;
  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);.1point3acres缃
  13.   root.right = sol(input, min+1, right);. from: 1point3acres.com/bbs
  14.   return root;
  15. }
复制代码

评分

1

查看全部评分

回复 支持 4 反对 0

使用道具 举报

wangxinbo1123 发表于 2017-1-23 08:47:56 | 显示全部楼层
  1. Node* buildTree(Iter start, Iter end) {
  2.         if(start == end) return NULL;
  3.         if(start == end - 1) return new Node(*start);
  4.         auto minPos = min_element(start, end);. visit 1point3acres.com for more.
  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

使用道具 举报

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
挺有趣的题目...楼主思考好快
. more info on 1point3acres.com
一直想问问, 这种sort之后还想让index信息被保留有没有什么特别好的方法?  ...

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

使用道具 举报

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的啊!!. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

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

使用道具 举报

nbodqujd 发表于 2016-12-5 11:05:11 | 显示全部楼层
清水翔太 发表于 2016-11-23 04:03. Waral 鍗氬鏈夋洿澶氭枃绔,
不太理解为什么需要排序,这里min-heap只是需要把最小值放在root吧?这样按照最小值分割也就能够把保证inor ...

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

使用道具 举报

AndrewFish 发表于 2017-1-9 04:32:47 | 显示全部楼层
其实, sort的complexity是nlg(n),  在每一个subarray里找最小index的话总complexity也是nlg(n),这么看来不sort直接找每个subtree的root更便捷。
回复 支持 反对

使用道具 举报

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

使用道具 举报

吃啥才算成熟 发表于 2017-1-12 06:13:39 | 显示全部楼层
  1. public class Solution6 {. from: 1point3acres.com/bbs
  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);. Waral 鍗氬鏈夋洿澶氭枃绔,
  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.             }
  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();. 1point3acres.com/bbs
  28.     }
  29.     private void inorderHelper(TreeNode node, List<Integer> nums){
  30.         if(node.left!=null) inorderHelper(node.left, nums);
  31.         nums.add(node.val);
  32.         if(node.right!=null) inorderHelper(node.right, nums);
  33.     }. From 1point 3acres bbs
  34. }
复制代码
回复 支持 反对

使用道具 举报

wangxinbo1123 发表于 2017-1-23 08:46:53 | 显示全部楼层
C++ version:

补充内容 (2017-1-23 08:47):
Node* buildTree(Iter start, Iter end) {. 1point3acres.com/bbs
        if(start == end) return NULL;
        if(start == end - 1) return new Node(*start); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
        auto minPos = min_element(start, end);
        Node* node = new Node(*minPos);
        node-...
回复 支持 反对

使用道具 举报

lhh_NJU 发表于 2017-2-20 12:39:09 | 显示全部楼层

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

使用道具 举报

bigbearlake 发表于 2017-3-1 13:38:37 | 显示全部楼层
  1. public class Array2Minheap {. more info on 1point3acres.com
  2.     class TreeNode {
  3.         int val;. 1point 3acres 璁哄潧
  4.         TreeNode left, right;
  5.         public TreeNode(int v) {
  6.             val = v;
  7.         }
  8.     }. from: 1point3acres.com/bbs

  9.     public TreeNode getMinheap(int[] arr) {
  10.         return helper(arr, 0, arr.length - 1);.鏈枃鍘熷垱鑷1point3acres璁哄潧
  11.     }

  12.     public TreeNode helper(int[] arr, int start, int end) {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  13.         if (start > end) {
  14.             return null;
  15.         } else if (start == end) {
  16.             return new TreeNode(arr[start]);
  17.         }
  18.         int min = start; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  19.         for (int i = start; i <= end; i++) {
  20.             if (arr[i] < arr[min]) {
  21.                 min = i;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  22.             }
    . 1point3acres.com/bbs
  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) {. Waral 鍗氬鏈夋洿澶氭枃绔,
  31.             return;
  32.         }
  33.         inorder(root.left);
  34.         System.out.println(root.val + " ");
  35.         inorder(root.right);. Waral 鍗氬鏈夋洿澶氭枃绔,
  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. }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-11-21 20:27

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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