Bloomberg经典面经题讨论

StellaYue00 发表于 2017-10-25 14:12
就是用的一个double linkedlist + Hashmap~

楼主的意思是每一个cursor是一个DoubleLinkedListNode, 然后每一个cursor自己也是一连串的DoubkelinkedListNode 形成的LIST,请问你说的只需要一个所有运动员排序的linkedlist是什么意思呢？是省略了那一部分？

StellaYue00 发表于 2017-10-23 01:31
我使用的第二种方法，然后过了

补充内容 (2017-10-23 01:33):

感觉楼主没有说明白sensor 怎么工作的,感觉层主的意思是不是只有一个sensor, 每次经过sensor 就删原来的位置然后在队尾加入他, 直到最后跑完才显示前k个, 比如一个两个人 A, B, 2个sensor, 每人都要经过2个sensor, 假设A 先经过第一个sensor , linkedlist 状态为 head - A-tail, 接着B再经过: head-A-B-tail, 然后B 先经过第二个sensor: head - A -B-tail, 最后A经过第二个sensor 结束: head - B -A -tail,结果为: Ｂ－Ａ，　是这样的吗，　不是实时的吗？我的意思是只要经过ｓｅｎｓｏｒ就更新，　不管是第几个ｓｅｎｓｏｒ，　但是不是实时获取前ｋ个．必须大家都跑完才行，　是这个意思吗？

那个hashmap＋linkedlist是不是有点类似LFU那种了

我觉得第二种就是挺好的结果，楼主是要去onsite了么

kate8528577 发表于 2017-10-26 03:43
我觉得第二种就是挺好的结果，楼主是要去onsite了么

嗯  你也要onsite吗

westcoastboy 发表于 2017-10-26 04:31
嗯  你也要onsite吗

组个队吧，还可以讨论

我按照对于第二种方法的解读写了一下代码，不知道对不对，请各位帮忙看看？不过，，我还是不能理解用linkedlist直接存runner顺序的方法，哪位大神能不能详细解释一下。
还有sensor 的情况应该是一开始就给出的吧？如果没有理解错的话！
#include <iostream>

class runner
{
  public:
    int id;
    int name;
    runner(int id,int name)
    {
        this->id=id;
        this->name=name;
    }
};
class sensor
{
  public:
    int id;
    int dis;
    list<int> runner;
    sensor(int id,int dis)
    {
        this->id=id;
        this->dis=dis;
    }
};
class solution
{
public:
  vector<sensor*> collection;
  unordered_map<int,int> sensorposition;
  unordered_map<int,pair<int,list<int>::iterator>> position;
  unordered_map<int,sensor*> mappingsensor;
  unordered_map<int,runner*> mappingrunner;
  static bool cmp(sensor* a,sensor* b)
  {
      return a->dis<b->dis;
  }
  solution(vector<sensor*>& sens)
  {
      sort(sens.begin(),sens.end(),cmp); //sort according to distance to destination
  }
  void update(int runnerid,int sensorid)
  {
      if(position.find(runnerid)==position.end())
      {
          mappingsensor[sensorid]->runner.push_back(runnerid);
          position[runnerid]=make_pair(sensorid,mappingsensor[sensorid]->runner.begin());
      }
      else
      {
          auto s=position[runnerid].first;
          auto index=position[runnerid].second;
          mappingsensor[s]->runner.erase(index);
          mappingsensor[sensorid]->runner.push_back(runnerid);
          position[runnerid].first=sensorid;
          position[runnerid].second=--mappingsensor[sensorid]->runner.end();
      }
  }
  vector<int> topk()
  {
      vector<int> ans;
      for(int i=0;i<collection.size();i++)
      {
          if(collection[i]->runner.size()>0)
          {
              list<int>::iterator it;
              for(it=collection[i]->runner.begin();it!=collection[i]->runner.end()&&ans.size()<10;it++)
              {
                  ans.push_back(*it);
              }
          }
      }
      return ans;
  }
};

我想说的是第二种方法里的2的删除时间复杂程度应该不是O（1）也， 因为从hashmap可以知道选手最新经过的sensor是哪一个，但并不知道选手在sensor的double linked list里的第几位，还是要遍历找到才可以删除也，插入确实是O（1）倒是

luyuzhuangdeyez 发表于 2018-1-6 07:26
我想说的是第二种方法里的2的删除时间复杂程度应该不是O（1）也， 因为从hashmap可以知道选手最新经过的sen ...

删除是通过hashmap找到node在哪儿，所以也是O（1）吧？

这个为什么不是LFU，一个runner，经过越多checkpoint，证明ranking越高，每经过一个checkpoint，相当于frequency加一，假如同样frequency的情况，按先后经过最新一个checkpoint的顺序？