Bloomberg经典面经题讨论

可能是我菜，欢迎纠正！
我不理解，为什么double-linkedlist里的删除/更新是O(1)? 不应该是先去search你要删除/更新的node(which takes O(n) time) 再去删除/更新吗？
如果是这样的话，第一和第二种解法唯一的区别就是，第一种是用treemap把不同sensor给sort连接起来，第二种是用一个linkedlist。个人觉得第一种比较好，毕竟treemap的搜索只需要O(logn)，先定位checkpoint，再更新对应的runner。我不太理解第二种怎么把linkedlist和linkedlist连接起来的……纯连的话，岂不是太长太慢了

huzhouwjj 发表于 2018-1-30 06:48
可能是我菜，欢迎纠正！
我不理解，为什么double-linkedlist里的删除/更新是O(1)? 不应该是先去search你要 ...

其实就是LFU的变种，每个checkpoint维护一个linkedhashset，插入删除就可以O(1)了。

写个我自己的思考，还请大神指点一下

1. sensor/check_pointer那用一个list记录当前sensor有多少个runners；并且有个hashmap记录每个runner_id 和 runner_list的iterator
2. sensor 写一个deleteRunner() ；根据提供的runnerid把当前list和hashmap上的runner_id删除 //  这个runner已经从这个sensor到了另外一个
3. MarathonBoard 的 update( runner_id, sensor_id ) 主要有2步
  3.1） 先根据runner_id 从他之前sensor list里删除
  3.2）再把这个runner_id 放到现在这个sensor_id 里的runner_list 后面去  // 假设每个新的runner都是在这个sensor的runner_list的最后

4. 最后打印top K, 假设sensor都是按先后顺序排好的（如果不是，可以把list改成multiset然后写个compartor），直接把每个sensor上的runner都打印出来就是的了







class Sensor
{
    int s_id;
    int s_distance;
    list<int> runner_list;   // a list of runner_id at this sensor/check_pointer
    unordered_map<int, list<int>::iterator> runner_m_sensor;    // {runner_id : list<runner_id>::iterator}
public:
    Sensor(int id, int dist):s_id(id), s_distance(dist){ }

    void deleteRunner(int runner_id){
        auto it = runner_m_sensor.find(runner_id);
        if (it == runner_m_sensor.end()) return;

        runner_list.erase( runner_m_sensor[runner_id] );
        runner_m_sensor.erase(runner_id);
    }
};

class MarathonBoard{
    list<Sensor> sensor_list;

    unordered_map<int, list<Sensor>::iterator> sensor_m; // {sensor_id: sensor_list::iterator}
    unordered_map<int, int> runner_m;   // {runner_id: sensor_id}

public:
    MarathonBoard(){}
    void update(int runner_id, int sensor_id){
        // 1. delete the runner from his/her previous sensor's runner list      
        int old_sensor_id = runner_m[runner_id];
        auto old_sensor_it = sensor_m[old_sensor_id];
        // delete it from previous runner list
        old_sensor_it->deleteRunner(runner_id);

        // 2. push_back(runner_id) at current sensor's runner list
        // update it to current sensor
        sensor_m[sensor_id]->runner_list.push_back(runner_id);
    }

    void printTopK(int k){
        for (auto &s : sensor_list)
        {
            for (auto &r : s.runner_list)
            {
                if (k >= 0)
                    cout << "Runner id: " << r << endl;
                k--;
            }
        }
    }
};

感谢楼主的分享谢谢

这个题目不就是LFU吗....每次过checkpoint就是过相当于增加了一个频率，没看出来哪儿不一样，求大神指点

您好！
本帖隐藏的内容需要积分高于 110 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 110 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies