Runner & Monitor Design

来源：Bloomberg onsite

原帖：在bb的面经出现多次，以后考察时补上相应链接。

题目：
我面bb onsite 的时候遇到的题目。题目是在跑道上存在不同位置的monitor,监控runner的位置。提供当一个运动员路过一个monitor的时候，update运动员的位置void update(runnerID, monitorID)；查询运动员的位置(就是monitor的位置)int getMonitorID(runnerID)；查询排名前k的运动员的函数vector<int> getTopK(k).
方法：使用hash + vector<list<>>; 不同的monitor可以看做一个bucket

代码：

  // hashmap stores <runnerID, list<Data>::iterator>  
  // update: 使用hash变更链表，插入新的位置  
  // topk: 遍历数组  
  class Record {  
  public:  
      Record(int num_p, int num_m) : data(num_m) {  
          for (int i = 0; i < num_p; ++i) {  
              data[0].push_front(Data(i,0));  
              map[i] = data[0].begin();  
          }  
      }  
    
      int getMonitorID(int personID) const {  
          return map[personID]->mID;  
      }  
    
      void update(int personID, int monitorID) {  
          int pre_mID = map[personID]->mID;  
          data[monitorID].splice(data[monitorID].begin(), data[pre_mID], map[personID]);  
      }  
    
      // return top-k person ID from data;  
      vector<int> getTopK(int k) {  
          vector<int> res;  
          for (int i = data.size()-1; i >= 0 && res.size() < k; --i) {  
          if (data[i].empty()) continue;  
          for (auto it = data[i].rbegin(); it != data[i].rend() && res.size() < k; ++it) {  
              res.push_back(it->pID);  
          }  
      }  
          return res;  
      }  
    
  private:  
      struct Data {  
          int pID;  
          int mID;  
          Data(int p, int m) : pID(p), mID(m) {}  
      };  
      vector<list<Data> > data;  
      unordered_map<int, list<Data>::iterator> map;   
  };  
    
  int main() {  
      int num_p = 10; // 0, 1, 2, ..., 9  
      int num_m = 3; // 0, 1, 2.  
    
      Record r(num_p, num_m);  
      cout << r.getMonitorID(1) << endl;  
      r.update(1, 1);  
      r.update(2, 1);  
      r.update(6, 1);  
      r.update(2, 2);  
      r.update(7, 1);  
      vector res = r.getTopK(3);   
      for (auto i : res) cout << i << " ";  
          cout << endl;  
          return 0;  
      }  
  }