一亩三分地论坛

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

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

facebook电面

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

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

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

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

x
第一轮电面move zero https://leetcode.com/problems/move-zeroes/,问了complexity。.1point3acres缃
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!!



评分

2

查看全部评分

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

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

使用道具 举报

forteller 发表于 2016-6-11 14:50:46 | 显示全部楼层
blackrose 发表于 2016-6-10 06:12
恩,就是这么写的,存下来M个start 和 end, 但是感觉这么些,半个小时写不完的样子。。。还不算压力情况 ...
. From 1point 3acres bbs
你会用堆吗?
回复 支持 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. Waral 鍗氬鏈夋洿澶氭枃绔,
第二个题写了有一会儿,还写的很乱,楼主有代码没

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

使用道具 举报

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

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

使用道具 举报

blackrose 发表于 2016-6-11 23:00:02 | 显示全部楼层
forteller 发表于 2016-6-11 14:50.鏈枃鍘熷垱鑷1point3acres璁哄潧
你会用堆吗?
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
不明白 什么意思
回复 支持 反对

使用道具 举报

forteller 发表于 2016-6-12 04:34:39 | 显示全部楼层

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();. visit 1point3acres.com for more.
  3.         vector<int> res;
  4.         if (size == 0) return res;
  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. . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  10.         //The next index of ending point
  11.         unordered_set<int> endIdx;. more info on 1point3acres.com
  12.         for(int i = 0; i < size - 1; ++i) {
  13.                 //Find the boundary of sub-arrays
  14.                 if (nums[i] > nums[i+1]) {
  15.                            endIdx.insert(i+1);
  16.                            //push the first element of the next sub-array to heap
  17.                            Q.push(make_pair(nums[i+1], i+1));      
  18.           }
  19.      }
  20.      endIdx.insert(size);

  21.     while(res.size() < size) {
  22.               int val = Q.top().first;
  23.        int idx = Q.top().second;
  24.               Q.pop();
  25.               res.push_back(val);
  26.               ++idx;
  27.              //Check if we have reached the end of current sub array
  28.               if (endIdx.count(idx) == 0). Waral 鍗氬鏈夋洿澶氭枃绔,
  29.                        Q.push(make_pair(nums[idx], idx));   
  30.        }
  31.         return res;
  32. }
复制代码
回复 支持 反对

使用道具 举报

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
算我多事。好心想帮你梳理思路 也不知道你k路归并懂不懂 用一个堆 实现的快点 是一个比较不错的解法。又 ...

谢谢你的好心,我压根没说我不会,只不过说了句 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. 1point3acres.com/bbs
请问fb一次店面只问一道题吗?是内推么?

应该是楼主太水了
回复 支持 反对

使用道具 举报

 楼主| csy0609 发表于 2016-6-13 01:18:40 | 显示全部楼层
hkc593 发表于 2016-6-12 08:41.鏈枃鍘熷垱鑷1point3acres璁哄潧
练习了一下第二问,跑了几个简单case,没有问题,不知道有没有bug。

多谢分享!!
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 18:14

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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