bloomberg 马拉松设计题

第一个问题问的设计题，一个track上有很多runner，还有很多sensor，sensor可以检测到那个runner跑过了这个sensor
用这个系统生成一个dashboard显示runner现在的名次。

查之前的帖子，说有总结。但我没有找到。

有人能把总结的帖子发一下，或者说说这道题的想法么？

我提供一个思路
先看题，假设一共有n个runner，m个sensor，runner跑的时候经过连续的sensor（不会从sensor1直接到sensor3），而我们需要实现的方法有update（i, j），即runner i 刚刚经过 sensor j；以及getRank(k)获得当下前 k 个选手的名次。

solution 1：
1. 用一个2D array（int[][] ranking , m * n）记录runner跑到哪了，以及一个长 m 的array（int[] counter）记录已有多少个runner经过当前sensor。
2. 每次update（i，j），ranking[j-1][i] = 0, ranking[j][i] = counter[i]+1;
3. 每次getRank（k），从下往上遍历每个sensor，还需将每一行根据ranking[][]的大小排序，拿出前k个。

这用做也许在m，n都比较小的时候可以，但随着m，n增多很不方便。
主要问题是，如何保持每个sensor所“拥有”的runner有先后顺序（如queue），在先后顺序的前提下如何快速删除其中某一个runner（突然跑快了），并append到下一个sensor的队列中；为了取前k个runner，当sensor较多runner比较稀疏时，如何取了一部分后知道下一个有runner的sensor是谁。

solution 2：基于double linked list, hashmap
1. 建立一个HashMap<Runner, Node>, 每个runner对应一个node，O(1)时间找到这个此runner的位置
2. 每个sensor都建立double linked list，O(1)时间删除，且始终有序。删除后加入更新的sensor链尾即可，update时间O(1)
3. 建立另一个长 k 的 double linked list，每个node代表一个sensor，将稀疏的sensor连起来
4. getRank(k)时，依次将每个sensor node中选手按许倒出即可，O(k)

第一次回帖，只是提供思路，见谅，欢迎交流。

1. class LinkedList():
   
2.     def __init__(self, person):
   
3.         self.person = person
   
4.         self.next = None
   
5.         self.prev = None
   
6. 
   
7. class Marrathon():
   
8.     def __init__(self, numSensor):
   
9.         self.sensorsHead = [0] * numSensor
   
10.         self.sensorsTail = [0] * numSensor
    
11.         self.person2Node = dict()
    
12.         for i in range(numSensor):
    
13.             self.head = LinkedList(-1)
    
14.             self.tail = LinkedList(-1)
    
15.             self.head.next = self.tail
    
16.             self.tail.prev = self.head
    
17.             self.sensorsHead[i] = self.head
    
18.             self.sensorsTail[i] = self.tail
    
19.             
    
20.     def update(self, person, sensor):
    
21.         if person in self.person2Node:
    
22.             node = self.person2Node[person]
    
23.             self.removeNode(node)
    
24.             self.addNode(sensor, node)
    
25.         else: # person 1st time appear
    
26.             node = LinkedList(person)
    
27.             self.person2Node[person] = node
    
28.             self.addNode(sensor, node)
    
29.         
    
30.     def addNode(self, sensor, node):
    
31.         tail = self.sensorsTail[sensor]
    
32.         p = tail.prev
    
33.         p.next = node
    
34.         node.next = tail
    
35.         tail.prev = node
    
36.         node.prev = p
    
37.         
    
38.     def removeNode(self, node):
    
39.         p, n = node.prev, node.next
    
40.         p.next = n
    
41.         n.prev = p
    
42.         
    
43.     def topK(self, k):
    
44.         res = []
    
45. 
    
46.         for i in range(len(self.sensorsHead) - 1, -1, -1):
    
47.             if k == 0:
    
48.                 break
    
49.             candidate = self.sensorsHead[i].next
    
50.             while candidate.person != -1 and k > 0:
    
51.                 res.append(candidate.person)
    
52.                 k -= 1
    
53.                 candidate = candidate.next
    
54.         return res
    
55. 
    

复制代码

今天刚面到zhe这道题，超水平发挥了。基本上需要实现两个函数 passMilestone(runner), 以及printLeadBoard()打印出所有名次排名,
数据结构用一个hash table和一个doubly linked list，Node 包含runner id, 最后一个经过的milestone id, 经过milestone时候的rank，也就是第几个经过这个打卡点的,还有pre，next指针。注意passMilestone参数只有runner，没有打卡点id，所以hash table的key是runner id，值包含milestone id和rank，每次这个函数调用时候update milestone = milestone + 1，然后查看这个milestone之前几个人经过了得到rank。然后要把自己从doubly linked list中删除，然后找到正确的位置插入。诀窍在于只需要找到和自己milestone id，对每个milestone记住第一个经过的人，这样就可以把自己插入到第一个人之前。时间复杂度O（1）。print时间复杂度O（n）。希望可以帮助到大家。

我的一个主要疑问是，这道题的实时排名是如何实现的？  两个sensor之间的runner相对位置，我不知道如何得知。

看到了就进来随便说一句，可选的data structure有几种，别用heap，前年onsite挂在这上面了

这道题最早应该是出现在13年。。

第一次回帖，如果楼主把题目说全了。
sensor可以知道runner，那么每个runner设一个counter，任何sensor检测到经过，就给counter[runner_id]++，counter最高的那个就最前面的了吧？ 不太清楚相等的情况是不是按时间戳排序？如果是的话，每个sensor再有一个自己的sort就好

哩哩哩哩不消停 发表于 2017-2-8 14:41
我提供一个思路
先看题，假设一共有n个runner，m个sensor，runner跑的时候经过连续的sensor（不会从sensor ...

如果题目是：还要可以查询某个runer目前的名次，怎么求，时间复杂度是多少呢

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

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--;
            }
        }
    }
};