📣 VIP通行证夏日特惠 限时立减$68
楼主: 月亮有心
跳转到指定楼层
上一主题 下一主题
收起左侧

Facebook电面

🔗
iPhD 2016-10-18 04:23:44 | 只看该作者
全局:
月亮有心 发表于 2016-10-18 04:10
我觉得是,因为全是数字的话数组大小不好控制

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);
                }
        }
        return currPos;
}
回复

使用道具 举报

🔗
xfxjw9381 2016-10-21 12:40:42 | 只看该作者
全局:
经典面经题
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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