推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

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

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

facebook电面

[复制链接] |试试Instant~ |关注本帖
csy0609 发表于 2016-6-10 04:16:22 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 硕士 全职@Facebook - 网上海投 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
第一轮电面move zero https://leetcode.com/problems/move-zeroes/,问了complexity。
follow up: 如果只需要把非0的数移到左边,而不care右边是什么数要怎么做。举例 2,0,0,1,3,0,5,输出2,1,3,5,*,*,*,随便*输出什么都可以。

第二天接到二面通知,心里没底啊准备了好久面经结果碰到没见过的。给一个partial sorted的数组比如1,3,5,2,4,6,8,10,20,30,11,12,13,数组有N个数,分为M个segment,N>>>M,要求输出排序后的数组。第一反应就是merge k sorted list,按照那个写了下,问了问time 和space 的complexity,facebook家很喜欢问复杂度问题,而且需要解释清楚不是随便说个O就可以的。

跪求onsite!!
. From 1point 3acres bbs


评分

2

查看全部评分

forteller 发表于 2016-6-12 13:39:09 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
blackrose 发表于 2016-6-12 13:32. From 1point 3acres bbs
谢谢你的好心,我压根没说我不会,只不过说了句 code需要点时间。。。。。

就这样吧 在这帖子里跟你理论真没有什么意义 加油吧 能实现出来就好啊 写个解题报告 特别能帮你提高解决类似题目的效率
回复 支持 0 反对 3

使用道具 举报

forteller 发表于 2016-6-11 14:50:46 | 显示全部楼层
关注一亩三分地微博:
Warald
blackrose 发表于 2016-6-10 06:12
恩,就是这么写的,存下来M个start 和 end, 但是感觉这么些,半个小时写不完的样子。。。还不算压力情况 ...
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
你会用堆吗?
回复 支持 1 反对 1

使用道具 举报

blackrose 发表于 2016-6-10 04:25:20 | 显示全部楼层
二面那个题有意思。
回复 支持 反对

使用道具 举报

blackrose 发表于 2016-6-10 05:16:02 | 显示全部楼层
第二个题写了有一会儿,还写的很乱,楼主有代码没
回复 支持 反对

使用道具 举报

forteller 发表于 2016-6-10 05:28:55 | 显示全部楼层
blackrose 发表于 2016-6-10 05:16
第二个题写了有一会儿,还写的很乱,楼主有代码没

用M个指针存每个有序segment的起始位置,然后按照K路归并的思路
回复 支持 反对

使用道具 举报

blackrose 发表于 2016-6-10 06:12:23 | 显示全部楼层
forteller 发表于 2016-6-10 05:28. 1point3acres.com/bbs
用M个指针存每个有序segment的起始位置,然后按照K路归并的思路

恩,就是这么写的,存下来M个start 和 end, 但是感觉这么些,半个小时写不完的样子。。。还不算压力情况吓。。。。
回复 支持 反对

使用道具 举报

blackrose 发表于 2016-6-11 23:00:02 | 显示全部楼层

不明白 什么意思
回复 支持 反对

使用道具 举报

forteller 发表于 2016-6-12 04:34:39 | 显示全部楼层
blackrose 发表于 2016-6-11 23:00.鐣欏璁哄潧-涓浜-涓夊垎鍦
不明白 什么意思

max heap min heap知道吗
回复 支持 反对

使用道具 举报

blackrose 发表于 2016-6-12 04:55:28 | 显示全部楼层
forteller 发表于 2016-6-12 04:34
max heap min heap知道吗

即使知道也要code一阵阿。而且要先找出来M个断点。。。。我太挫,你是大神
回复 支持 反对

使用道具 举报

hkc593 发表于 2016-6-12 08:41:35 | 显示全部楼层
练习了一下第二问,跑了几个简单case,没有问题,不知道有没有bug。
  1. vector<int> sort(vector<int>& nums) {
  2.         int size = nums.size();
  3.         vector<int> res;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  4.         if (size == 0) return res;. more info on 1point3acres.com
  5.    .鐣欏璁哄潧-涓浜-涓夊垎鍦
  6.         //min heap, element is pair of <num, idx>
  7.         priority_queue<pair<int, int>, vector<pair<int, int>>, std::greater<pair<int,int>>> Q;
  8.         Q.push(make_pair(nums[0], 0));

  9.         //The next index of ending point
  10.         unordered_set<int> endIdx;
  11.         for(int i = 0; i < size - 1; ++i) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  12.                 //Find the boundary of sub-arrays
  13.                 if (nums[i] > nums[i+1]) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  14.                            endIdx.insert(i+1);
  15.                            //push the first element of the next sub-array to heap-google 1point3acres
  16.                            Q.push(make_pair(nums[i+1], i+1));      
  17.           }. 1point3acres.com/bbs
  18.      }
  19.      endIdx.insert(size);

  20.     while(res.size() < size) {. From 1point 3acres bbs
  21.               int val = Q.top().first;
  22.        int idx = Q.top().second;
  23.               Q.pop();
  24.               res.push_back(val);
  25.               ++idx; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  26.              //Check if we have reached the end of current sub array
  27.               if (endIdx.count(idx) == 0)
  28.                        Q.push(make_pair(nums[idx], idx));   
  29.        }
    .1point3acres缃
  30.         return res;
  31. }
复制代码
回复 支持 反对

使用道具 举报

iejr 发表于 2016-6-12 09:47:13 | 显示全部楼层
二面的merge sort那题,我在想这个思路是不是会在面试时写的容易些:
    1. 从左向右扫,发现一个元素x,比左边的数小,那么这个是分割点了
    2. 上一步得到的分割点两侧分别递归
    3. 左右两边排好后,再merge  
    如果第一步找不到x,那么数组已有序,直接返回  
感觉效率不如k路归并高,不过题意说N>>>M,所以我估计差别不大吧
回复 支持 反对

使用道具 举报

forteller 发表于 2016-6-12 10:31:51 | 显示全部楼层
blackrose 发表于 2016-6-12 04:55
即使知道也要code一阵阿。而且要先找出来M个断点。。。。我太挫,你是大神

你不用实现一个heap。这个你知道吧。你有库文件/头文件。你可以调用已经实现了的堆 进行增删查改的操作。这个确实是难的不会会的不难。
回复 支持 反对

使用道具 举报

blackrose 发表于 2016-6-12 12:51:05 | 显示全部楼层
forteller 发表于 2016-6-12 10:31
你不用实现一个heap。这个你知道吧。你有库文件/头文件。你可以调用已经实现了的堆 进行增删查改的操作。 ...
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
呵呵呵呵呵呵,那的多谢您的指点
回复 支持 反对

使用道具 举报

forteller 发表于 2016-6-12 13:30:45 | 显示全部楼层
blackrose 发表于 2016-6-12 12:51
呵呵呵呵呵呵,那的多谢您的指点

算我多事。好心想帮你梳理思路 也不知道你k路归并懂不懂 用一个堆 实现的快点 是一个比较不错的解法。又没有看不起你的意思。干嘛这种语气说话。问问你知不知道堆 就是max heap 大根堆 min heap小根堆 你要是会就好啦 不会又不丢人 呵呵呵呵呵是干什么。好心当成驴肝肺
回复 支持 反对

使用道具 举报

blackrose 发表于 2016-6-12 13:32:12 | 显示全部楼层
forteller 发表于 2016-6-12 13:30
. 鍥磋鎴戜滑@1point 3 acres算我多事。好心想帮你梳理思路 也不知道你k路归并懂不懂 用一个堆 实现的快点 是一个比较不错的解法。又 ...
. 鍥磋鎴戜滑@1point 3 acres
谢谢你的好心,我压根没说我不会,只不过说了句 code需要点时间。。。。。
回复 支持 反对

使用道具 举报

forteller 发表于 2016-6-12 13:35:59 | 显示全部楼层
blackrose 发表于 2016-6-12 13:32
谢谢你的好心,我压根没说我不会,只不过说了句 code需要点时间。。。。。

.鐣欏璁哄潧-涓浜-涓夊垎鍦你上面自己说的“不明白 什么意思” 你可以看看 我还怕你不知道堆 就跟你说heap。我以为你没用堆去实现k路归并 用的比较朴素的那个想法 这样才慢的 所以想给你提个醒 用下堆这个数据结构会好很多
回复 支持 反对

使用道具 举报

hijkstra 发表于 2016-6-12 22:19:55 | 显示全部楼层
请问fb一次店面只问一道题吗?是内推么?
回复 支持 反对

使用道具 举报

 楼主| csy0609 发表于 2016-6-13 01:18:11 | 显示全部楼层
hijkstra 发表于 2016-6-12 22:19
请问fb一次店面只问一道题吗?是内推么?
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
应该是楼主太水了
回复 支持 反对

使用道具 举报

 楼主| csy0609 发表于 2016-6-13 01:18:40 | 显示全部楼层
hkc593 发表于 2016-6-12 08:41. From 1point 3acres bbs
练习了一下第二问,跑了几个简单case,没有问题,不知道有没有bug。
. 1point3acres.com/bbs
多谢分享!!
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-8-16 21:51

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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