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)
今天刚面到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）。希望可以帮助到大家。
我当时读到的时候感觉是是笔误。应该是最后一个经过milestone的人。（即加入尾部）
Topk的部分讀起來感覺像:
前k個sensor的最晚離開那位person
你的code中self.sensorHead裡面的index是代表sensors的編號 如果k>nums_of_sensor感覺會Error 如果不會error感覺也沒辦法解決如果第一名第二次經過sensor的問題 這樣跑第二快的選手會變成第一個因為第一名的選手會在一號sensor的最後面(你的addNode()是從list後端加入)
歡迎討論啊有錯誤請指正 這題解決會幫到很多人 一起來幫忙各位兄弟
写个我自己的思考，还请大神指点一下
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--;
}
}
}
};
第一个问题问的设计题，一个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)
今天刚面到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）。希望可以帮助到大家。
我当时读到的时候感觉是是笔误。应该是最后一个经过milestone的人。（即加入尾部）
抱歉 馬拉松沒繞圈 沒有這幾個問題
前k個sensor的最晚離開那位person
你的code中self.sensorHead裡面的index是代表sensors的編號 如果k>nums_of_sensor感覺會Error 如果不會error感覺也沒辦法解決如果第一名第二次經過sensor的問題 這樣跑第二快的選手會變成第一個因為第一名的選手會在一號sensor的最後面(你的addNode()是從list後端加入)
歡迎討論啊有錯誤請指正 這題解決會幫到很多人 一起來幫忙各位兄弟
class LinkedList(): def __init__(self, person): self.person = person self.next = None self.prev = Noneclass Marrathon(): def __init__(self, numSensor): self.sensorsHead = [0] * numSensor self.sensorsTail = [0] * numSensor self.person2Node = dict() for i in range(numSensor): self.head = LinkedList(-1) self.tail = LinkedList(-1) self.head.next = self.tail self.tail.prev = self.head self.sensorsHead[i] = self.head self.sensorsTail[i] = self.tail def update(self, person, sensor): if person in self.person2Node: node = self.person2Node[person] self.removeNode(node) self.addNode(sensor, node) else: # person 1st time appear node = LinkedList(person) self.person2Node[person] = node self.addNode(sensor, node) def addNode(self, sensor, node): tail = self.sensorsTail[sensor] p = tail.prev p.next = node node.next = tail tail.prev = node node.prev = p def removeNode(self, node): p, n = node.prev, node.next p.next = n n.prev = p def topK(self, k): res = [] for i in range(len(self.sensorsHead) - 1, -1, -1): if k == 0: break candidate = self.sensorsHead[i].next while candidate.person != -1 and k > 0: res.append(candidate.person) k -= 1 candidate = candidate.next return res写个我自己的思考，还请大神指点一下
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--;
}
}
}
};
