Bloomberg经典面经题讨论

经典高频的马拉松问题：

一个 track 上有很多 runners(runner 已经给的属性有 id 和 name)，还有很多 check points(已给属 性为 distance:距离终点的距离，和 id)，che

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

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

inkedlist， 有谁知道这种解法是什么意思吗？

欢迎大神们来讨论！！感谢！！




补充内容 (2017-10-23 00:28):
或者建一个checkpoint的array,然后每有一个runner过了当前checkpoint，就将runner从上一个checkpoint删除，然后加入到当前checkpoint.  显示排名的时候，就从array的后面开始找top K ？

我按照对于第二种方法的解读写了一下代码，不知道对不对，请各位帮忙看看？不过，，我还是不能理解用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;
  }
};

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

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

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

讨论有加米！ 欢迎讨论！！！

我使用的第二种方法，然后过了

补充内容 (2017-10-23 01:33):
咦。。。看错了。。。不用每个sensor都维护一个linkedlist吧 只需要从头到尾 所有运动员排序的一个linkedlist就可以了吧~

这是LRU的变形吧，double linked list不断更新当前的runner顺序即可

EddieZ 发表于 2017-10-23 02:06
这是LRU的变形吧，double linked list不断更新当前的runner顺序即可

能再详细讲一下吗？比如一个runner先后过了checkpoint 1和checkpoint 2，应该怎么办呢？  而且top K是从后端开始找吗

用Heap不行么？

EddieZ 发表于 2017-10-23 02:06
这是LRU的变形吧，double linked list不断更新当前的runner顺序即可

嗯嗯  差不多就这个思路！

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

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

您的意思是 一个doubly linkedlist + 一个排序Linkedlist？

tabrisjayson 发表于 2017-10-24 23:40
用Heap不行么？

heap好像不是面试官想要的答案

westcoastboy 发表于 2017-10-25 01:51
您的意思是 一个doubly linkedlist + 一个排序Linkedlist？

就是用的一个double linkedlist + Hashmap~