一亩三分地论坛

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

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

Facebook电面

[复制链接] |试试Instant~ |关注本帖
月亮有心 发表于 2016-10-15 05:04:02 | 显示全部楼层 |阅读模式

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

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

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

x
刚刚面完5min就来写面经,感觉跪了。。。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

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

感觉电话里的声音不是很清楚,project就问了简历里的一个。coderpad上写的,没有run,就自己跑了几个test
. Waral 鍗氬鏈夋洿澶氭枃绔,
第一题就是给你一堆task和一个cooldown time,执行相同的task一定要过了cooldown time那么长的gap才可以,不需要reorder,求最后一共的时间。我用的hashmap,但是第一次电面太紧张,写了好久,run了两次testcase,还好他没发现啥bug,然后说一下时间空间复杂度,看看能不能优化。

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

最后5min让我随便问问题,小哥人还是很好的,但是感觉不是很想搭理我。。。.鐣欏璁哄潧-涓浜-涓夊垎鍦

求人品!


补充内容 (2016-10-17 01:15):
.鏈枃鍘熷垱鑷1point3acres璁哄潧拿到onsite邀请了

评分

1

查看全部评分

iPhD 发表于 2016-10-15 05:16:25 | 显示全部楼层
这题是面经里的老题了,follow up用LC 358 Rearrange String k Distance Apart的方法做
回复 支持 反对

使用道具 举报

 楼主| 月亮有心 发表于 2016-10-15 05:45:17 | 显示全部楼层
iPhD 发表于 2016-10-15 05:16
这题是面经里的老题了,follow up用LC 358 Rearrange String k Distance Apart的方法做

唉,leetcode hard都没怎么刷,感觉我思路是对的,但是第一次电面还是太紧张了
回复 支持 反对

使用道具 举报

 楼主| 月亮有心 发表于 2016-10-15 06:10:36 | 显示全部楼层
iPhD 发表于 2016-10-15 05:16. 1point 3acres 璁哄潧
这题是面经里的老题了,follow up用LC 358 Rearrange String k Distance Apart的方法做

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

使用道具 举报

iPhD 发表于 2016-10-15 06:16:00 | 显示全部楼层
月亮有心 发表于 2016-10-15 06:10.鐣欏璁哄潧-涓浜-涓夊垎鍦
刚刚写了下,用我跟他说的思路和heap能跑出来,不知道小哥最后会不会让我过

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

使用道具 举报

 楼主| 月亮有心 发表于 2016-10-15 06:29:56 | 显示全部楼层
iPhD 发表于 2016-10-15 06:16
嗯嗯,方便把代码贴出来看下不?祝楼主好运~

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

使用道具 举报

ben_viv 发表于 2016-10-18 01:43:48 | 显示全部楼层
请问楼主内推多久拿到回复呀?
回复 支持 反对

使用道具 举报

iPhD 发表于 2016-10-18 01:51:46 | 显示全部楼层
月亮有心 发表于 2016-10-15 06:29
我就是写的LC358,基本一样的,只不过facebook给的是integer序号,leetcode是字母

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

使用道具 举报

 楼主| 月亮有心 发表于 2016-10-18 04:09:37 | 显示全部楼层
ben_viv 发表于 2016-10-18 01:43
请问楼主内推多久拿到回复呀?

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

使用道具 举报

 楼主| 月亮有心 发表于 2016-10-18 04:10:18 | 显示全部楼层
iPhD 发表于 2016-10-18 01:51-google 1point3acres
所以对于这题来说,如果是integer而不是字母,该用heap是最优解,不是像LC上的两个数组那样是最优解是吗 ...
. 1point 3acres 璁哄潧
我觉得是,因为全是数字的话数组大小不好控制
回复 支持 反对

使用道具 举报

iPhD 发表于 2016-10-18 04:23:44 | 显示全部楼层
月亮有心 发表于 2016-10-18 04:10.1point3acres缃
我觉得是,因为全是数字的话数组大小不好控制
-google 1point3acres
LC上那题是字母,所以怎么扫都是常数时间。楼主能详细讲下怎么维护heap吗?就是如果下一个可以安排的task不是heap里频率最高的那个?怎么从heap里取出来和维护呢?如果有代码就更好啦!
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

iPhD 发表于 2016-10-18 04:40:44 | 显示全部楼层
月亮有心 发表于 2016-10-18 04:32
怎么会不是频率最高的那个呢,heap就是按频率大小来排的,下一个可以安排的task肯定就是heap顶部的那个, ...
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
多谢,我问的是follow-up那个可以reorder,那样子第一个选出频率最高的,第二次如果要选出频率第二高的,这个怎么选?
回复 支持 反对

使用道具 举报

 楼主| 月亮有心 发表于 2016-10-18 04:43:43 | 显示全部楼层
iPhD 发表于 2016-10-18 04:40
多谢,我问的是follow-up那个可以reorder,那样子第一个选出频率最高的,第二次如果要选出频率第二高的, ...

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

使用道具 举报

iPhD 发表于 2016-10-18 04:49:25 | 显示全部楼层
月亮有心 发表于 2016-10-18 04:43
为什么第二次要选出频率第二高的?第一问用不到heap的,然后reorder的目的是优化时间,并没有要求一定要 ...

不是有cooldown吗?比如cool down = 3, 如果task 1频率为10,task 2频率为5,那样子第一次选出task 1后,第二次因为cool down的原因,不能再选task 1了,得选频率第二高的task 2了?但在heap里最大的还是task 1
回复 支持 反对

使用道具 举报

西法的洛 发表于 2016-10-18 06:21:45 | 显示全部楼层
iPhD 发表于 2016-10-18 04:49
不是有cooldown吗?比如cool down = 3, 如果task 1频率为10,task 2频率为5,那样子第一次选出task 1后, ...

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

使用道具 举报

 楼主| 月亮有心 发表于 2016-10-18 07:51:18 | 显示全部楼层
iPhD 发表于 2016-10-18 04:49
不是有cooldown吗?比如cool down = 3, 如果task 1频率为10,task 2频率为5,那样子第一次选出task 1后, ...

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

使用道具 举报

zhangyanuuuuu 发表于 2016-10-21 11:40:15 | 显示全部楼层
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也没区别吧
回复 支持 反对

使用道具 举报

zhangyanuuuuu 发表于 2016-10-21 12:19:35 | 显示全部楼层
但是感觉单纯用heap还是不行,毕竟比如12233这种cooldown是3的话,选完23之后要选1,需要保证在相同frequency的数字之间选一个离左边最远的,这个在lc358那里是个invalid的情况,但在这里还是要考虑,写了一下代码,欢迎指正

int arrangeTask(vector<int>& tasks, int cooldown) {
        unordered_map<int, int> count;
        for (auto task : tasks) {
                count[task]++;
        }
        unordered_map<int, int> lastPos;
        for (auto ele : count) {
                lastPos[ele.first] = -1;
        }
        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()) {
                auto ele = queue.top();
                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);.鏈枃鍘熷垱鑷1point3acres璁哄潧
                }
        }
        return currPos;. Waral 鍗氬鏈夋洿澶氭枃绔,
}
回复 支持 反对

使用道具 举报

xfxjw9381 发表于 2016-10-21 12:40:42 | 显示全部楼层
经典面经题
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 22:58

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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