八八老东家Pinterest

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 6379|回复: 26
收起左侧

Facebook电面

[复制链接] |试试Instant~ |关注本帖
我的人缘0
月亮有心 发表于 2016-10-15 05:04:02 | 显示全部楼层 |阅读模式
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  79% (23)
 
 
20% (6)  踩

2017(10-12月) 码农类General 硕士 全职@Facebook - 内推 - 技术电面  | Other | fresh grad应届毕业生

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

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

x
刚刚面完5min就来写面经,感觉跪了。。。

小哥很准时地打来电话,先介绍了一下自己是什么组的,干嘛的,然后分配了一下时间,先说project,再写代码,留5min问问题。

感觉电话里的声音不是很清楚,project就问了简历里的一个。coderpad上写的,没有run,就自己跑了几个test

第一题就是给你一堆task和一个cooldown time,执行相同的task一定要过了cooldown time那么长的gap才可以,不需要reorder,求最后一共的时间。我用的hashmap,但是第一次电面太紧张,写了好久,run了两次testcase,还好他没发现啥bug,然后说一下时间空间复杂度,看看能不能优化。

第二题是第一题的follow up,可以reorder,求最短时间。时间不多了,只要我写一下思路。我一开始没反应过来,想用hashmap,然后说了半天发现应该用heap。。。把frequency排序。

最后5min让我随便问问题,小哥人还是很好的,但是感觉不是很想搭理我。。。
. from: 1point3acres
求人品!


补充内容 (2016-10-17 01:15):
拿到onsite邀请了

评分

参与人数 1大米 +40 收起 理由
阿童木 + 40 感谢分享!

查看全部评分


上一篇:Twitter coding challenge 面经
下一篇:请问最近有人面过亚麻家Marketplace/Sellers 组么?
我的人缘0
iPhD 发表于 2016-10-18 04:23:44 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
100% (1)   【踩】
全局: 顶  86% (60)
 
 
13% (9)  踩
月亮有心 发表于 2016-10-18 04:10
我觉得是,因为全是数字的话数组大小不好控制

LC上那题是字母,所以怎么扫都是常数时间。楼主能详细讲下怎么维护heap吗?就是如果下一个可以安排的task不是heap里频率最高的那个?怎么从heap里取出来和维护呢?如果有代码就更好啦!
回复

使用道具 举报

我的人缘0
iPhD 发表于 2016-10-15 05:16:25 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  86% (60)
 
 
13% (9)  踩
这题是面经里的老题了,follow up用LC 358 Rearrange String k Distance Apart的方法做
回复

使用道具 举报

我的人缘0
 楼主| 月亮有心 发表于 2016-10-15 05:45:17 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  79% (23)
 
 
20% (6)  踩
iPhD 发表于 2016-10-15 05:16
这题是面经里的老题了,follow up用LC 358 Rearrange String k Distance Apart的方法做
.留学论坛-一亩-三分地
唉,leetcode hard都没怎么刷,感觉我思路是对的,但是第一次电面还是太紧张了
回复

使用道具 举报

我的人缘0
 楼主| 月亮有心 发表于 2016-10-15 06:10:36 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  79% (23)
 
 
20% (6)  踩
iPhD 发表于 2016-10-15 05:16. 留学申请论坛-一亩三分地
这题是面经里的老题了,follow up用LC 358 Rearrange String k Distance Apart的方法做

刚刚写了下,用我跟他说的思路和heap能跑出来,不知道小哥最后会不会让我过
回复

使用道具 举报

我的人缘0
iPhD 发表于 2016-10-15 06:16:00 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  86% (60)
 
 
13% (9)  踩
月亮有心 发表于 2016-10-15 06:10
刚刚写了下,用我跟他说的思路和heap能跑出来,不知道小哥最后会不会让我过

嗯嗯,方便把代码贴出来看下不?祝楼主好运~
回复

使用道具 举报

我的人缘0
 楼主| 月亮有心 发表于 2016-10-15 06:29:56 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  79% (23)
 
 
20% (6)  踩
iPhD 发表于 2016-10-15 06:16
嗯嗯,方便把代码贴出来看下不?祝楼主好运~

我就是写的LC358,基本一样的,只不过facebook给的是integer序号,leetcode是字母
回复

使用道具 举报

我的人缘0
ben_viv 发表于 2016-10-18 01:43:48 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (19)
 
 
0% (0)  踩
请问楼主内推多久拿到回复呀?
Mobile Apps Category (English)728x90
回复

使用道具 举报

我的人缘0
iPhD 发表于 2016-10-18 01:51:46 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  86% (60)
 
 
13% (9)  踩
月亮有心 发表于 2016-10-15 06:29
我就是写的LC358,基本一样的,只不过facebook给的是integer序号,leetcode是字母

所以对于这题来说,如果是integer而不是字母,该用heap是最优解,不是像LC上的两个数组那样是最优解是吗?
回复

使用道具 举报

我的人缘0
 楼主| 月亮有心 发表于 2016-10-18 04:09:37 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  79% (23)
 
 
20% (6)  踩
ben_viv 发表于 2016-10-18 01:43. From 1point 3acres bbs
请问楼主内推多久拿到回复呀?

内推人很给力,一两天就收到Facebook的邮件了
回复

使用道具 举报

我的人缘0
 楼主| 月亮有心 发表于 2016-10-18 04:10:18 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  79% (23)
 
 
20% (6)  踩
iPhD 发表于 2016-10-18 01:51. 1point 3acres 论坛
所以对于这题来说,如果是integer而不是字母,该用heap是最优解,不是像LC上的两个数组那样是最优解是吗 ...

我觉得是,因为全是数字的话数组大小不好控制
回复

使用道具 举报

我的人缘0
 楼主| 月亮有心 发表于 2016-10-18 04:32:25 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  79% (23)
 
 
20% (6)  踩
iPhD 发表于 2016-10-18 04:23
LC上那题是字母,所以怎么扫都是常数时间。楼主能详细讲下怎么维护heap吗?就是如果下一个可以安排的task ...

怎么会不是频率最高的那个呢,heap就是按频率大小来排的,下一个可以安排的task肯定就是heap顶部的那个,如果cooldown时间不够,就hold住,等时间够了再执行。
回复

使用道具 举报

我的人缘0
iPhD 发表于 2016-10-18 04:40:44 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  86% (60)
 
 
13% (9)  踩
月亮有心 发表于 2016-10-18 04:32
怎么会不是频率最高的那个呢,heap就是按频率大小来排的,下一个可以安排的task肯定就是heap顶部的那个, ...
. Waral 博客有更多文章,
多谢,我问的是follow-up那个可以reorder,那样子第一个选出频率最高的,第二次如果要选出频率第二高的,这个怎么选?
回复

使用道具 举报

我的人缘0
 楼主| 月亮有心 发表于 2016-10-18 04:43:43 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  79% (23)
 
 
20% (6)  踩
iPhD 发表于 2016-10-18 04:40
多谢,我问的是follow-up那个可以reorder,那样子第一个选出频率最高的,第二次如果要选出频率第二高的, ...

为什么第二次要选出频率第二高的?第一问用不到heap的,然后reorder的目的是优化时间,并没有要求一定要先执行哪个
回复

使用道具 举报

我的人缘0
iPhD 发表于 2016-10-18 04:49:25 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  86% (60)
 
 
13% (9)  踩
月亮有心 发表于 2016-10-18 04:43
为什么第二次要选出频率第二高的?第一问用不到heap的,然后reorder的目的是优化时间,并没有要求一定要 ...
. more info on 1point3acres
不是有cooldown吗?比如cool down = 3, 如果task 1频率为10,task 2频率为5,那样子第一次选出task 1后,第二次因为cool down的原因,不能再选task 1了,得选频率第二高的task 2了?但在heap里最大的还是task 1
回复

使用道具 举报

我的人缘0
西法的洛 发表于 2016-10-18 06:21:45 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (163)
 
 
2% (4)  踩
iPhD 发表于 2016-10-18 04:49
不是有cooldown吗?比如cool down = 3, 如果task 1频率为10,task 2频率为5,那样子第一次选出task 1后, ...

去看lc358的discussion, 那个题目你理解了,这个你也能做了。
回复

使用道具 举报

我的人缘0
 楼主| 月亮有心 发表于 2016-10-18 07:51:18 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  79% (23)
 
 
20% (6)  踩
iPhD 发表于 2016-10-18 04:49
不是有cooldown吗?比如cool down = 3, 如果task 1频率为10,task 2频率为5,那样子第一次选出task 1后, ...

看来你没懂这个heap是怎么操作的。。。你还是听楼上的去看discussion吧
回复

使用道具 举报

我的人缘0
zhangyanuuuuu 发表于 2016-10-21 11:40:15 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (7)
 
 
0% (0)  踩
iPhD 发表于 2016-10-18 04:49
不是有cooldown吗?比如cool down = 3, 如果task 1频率为10,task 2频率为5,那样子第一次选出task 1后, ...

如果照你的说法,1212121212,出现了5个1和5个2之后怎么办?不是还得连续的5个一么,跟一开始放5个1也没区别吧
回复

使用道具 举报

我的人缘0
zhangyanuuuuu 发表于 2016-10-21 12:19:35 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (7)
 
 
0% (0)  踩
但是感觉单纯用heap还是不行,毕竟比如12233这种cooldown是3的话,选完23之后要选1,需要保证在相同frequency的数字之间选一个离左边最远的,这个在lc358那里是个invalid的情况,但在这里还是要考虑,写了一下代码,欢迎指正.本文原创自1point3acres论坛

int arrangeTask(vector<int>& tasks, int cooldown) {
        unordered_map<int, int> count;
        for (auto task : tasks) {
.本文原创自1point3acres论坛                count[task]++;
        }
        unordered_map<int, int> lastPos;
        for (auto ele : count) {
                lastPos[ele.first] = -1;
        }.1point3acres网
        auto comp = [&lastPos](pair<int, int> p1, pair<int, int> p2) {
                if (p1.first != p2.first) {
                        return p1.first < p2.first;
                }
                else {
                        return lastPos[p1.second] > lastPos[p2.second];.留学论坛-一亩-三分地
                }
        };
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(comp)> queue(comp);
        for (auto ele : count) {
                queue.emplace(ele.second, ele.first);
        }
        int currPos = 0; 来源一亩.三分地论坛.
        while (!queue.empty()) {. 1point3acres
                auto ele = queue.top();.1point3acres网
                int fre = ele.first, num = ele.second;
                queue.pop();
                if (lastPos[num] != -1 && currPos - lastPos[num] - 1 < cooldown) {
                        currPos += cooldown - (currPos - lastPos[num] - 1);
                }
                lastPos[num] = currPos++;
                if (--fre > 0) {
                        queue.emplace(fre, num);
                }
        }
        return currPos;
}
回复

使用道具 举报

我的人缘0
xfxjw9381 发表于 2016-10-21 12:40:42 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (7)
 
 
0% (0)  踩
经典面经题
回复

使用道具 举报

游客
请先登录

本版积分规则

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

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

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

custom counter

GMT+8, 2018-7-19 02:23

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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