Facebook电面

谢谢楼主面经，写了一下第一题，祝楼主onsite一切顺利
string scheduleTaskWithCooldown(string s, int k)
{
        map<char, int> m;
        map<char, int> lastIdx;
        string res;
        for (int i = 0; i < s.size(); i++)
        {
                if (lastIdx.find(s[i]) == lastIdx.end())
                {
                        res.push_back(s[i]);
                        lastIdx[s[i]] = res.size() - 1;
                }
                else
                {
                        while (lastIdx[s[i]] + k > res.size() - 1)
                        {
                                res += " ";
                        }
                        res.push_back(s[i]);
                        lastIdx[s[i]] = res.size() - 1;
                }
        }
        return res;
}

zhangyanuuuuu 发表于 2016-10-21 12:19
但是感觉单纯用heap还是不行，毕竟比如12233这种cooldown是3的话，选完23之后要选1，需要保证在相同frequen ...

我是这么实现的，先建了个类，存着task number和freq，然后heap的排序是先freq降序，如果freq一样，那就按task数字大小升序排。如果heap.size大于等于cool down，是不需要考虑你说的情况的。为了最后heap.size小于cool down的情况，用hashtable来存储最近一轮输出的结果和位置，然后最后一轮才需要填充cool down。
给楼主的代码一个小建议，lastpos初始化值可以说-cooldown-1，这样后面可以少一个if的情况

mingzhou1987 发表于 2016-10-21 13:16
谢谢楼主面经，写了一下第一题，祝楼主onsite一切顺利
string scheduleTaskWithCooldown(string s, int k) ...

不需要最终的输出序列的，只要总时间就可以了

月亮有心 发表于 2016-10-21 16:11
我是这么实现的，先建了个类，存着task number和freq，然后heap的排序是先freq降序，如果freq一样，那就 ...

哦哦，初始化确实，我也觉得写的有点ugly，多谢！
不过对于你说的最后一轮才需要填充cooldown不是很理解，这个没法保证吧，比如1112223333这种cooldown是10的话，怎么样每轮都得cooldown，heap的size一上来就可以小于cooldown不是么

对啊，所以这样子就要动用hashtable了啊

zhangyanuuuuu 发表于 2016-10-22 00:35
哦哦，初始化确实，我也觉得写的有点ugly，多谢！
不过对于你说的最后一轮才需要填充cooldown不是很理解 ...

对啊，所以这样子要用hashtable了，其实和你思路差不多，总之是要记录位置的

月亮有心 发表于 2016-10-22 03:22
对啊，所以这样子要用hashtable了，其实和你思路差不多，总之是要记录位置的

懂你的意思了，基本上还是跟lc那个题的解法比较像，就是多加了一个记录上次位置，写了一下
int rearrangeTask(vector<int>& tasks, int cooldown) {
        unordered_map<int, int> fre;
        for (auto task : tasks) {
                fre[task]++;
        }
        priority_queue<pair<int, int>> queue;
        for (auto ele : fre) {
                queue.emplace(ele.second, ele.first);
        }
        unordered_map<int, int> lastPos;
        for (auto ele : fre) {
                lastPos[ele.first] = -1 - cooldown;
        }
        int curr = 0;
        while (!queue.empty()) {
                int len = queue.size();
                auto ele = queue.top();
                if (curr - lastPos[ele.second] - 1 < cooldown) {
                        curr += cooldown - (curr - lastPos[ele.second] - 1);
                }
                vector<pair<int, int>> cache;
                for (int i = 0; i < min(len, cooldown); i++) {
                        auto ele = queue.top();
                        queue.pop();
                        lastPos[ele.second] = curr++;
                        if (--ele.first > 0) {
                                cache.push_back(ele);
                        }
                }
                for (auto ele : cache) {
                        queue.push(ele);
                }
        }
        return curr;
}