bloomberg 马拉松设计题

Liyukuang 发表于 2019-3-8 10:46
今天刚面到zhe这道题，超水平发挥了。基本上需要实现两个函数 passMilestone(runner), 以及printLeadBoard( ...

这个数rank的时间复杂度不是O（1）吧，因为和该经过milestone的人数有关。

BridgeHUHX 发表于 2019-3-8 22:46
这个数rank的时间复杂度不是O（1）吧，因为和该经过milestone的人数有关。

我当时读到的时候感觉是是笔误。应该是最后一个经过milestone的人。（即加入尾部）

明泉煮茶 发表于 2018-8-13 09:29
[mw_shl_code=python,true]class LinkedList():
    def __init__(self, person):
        self.person = ...

Topk的部分讀起來感覺像:
前k個sensor的最晚離開那位person

你的code中self.sensorHead裡面的index是代表sensors的編號 如果k>nums_of_sensor感覺會Error 如果不會error感覺也沒辦法解決如果第一名第二次經過sensor的問題  這樣跑第二快的選手會變成第一個因為第一名的選手會在一號sensor的最後面(你的addNode()是從list後端加入)

歡迎討論啊有錯誤請指正  這題解決會幫到很多人 一起來幫忙各位兄弟

YJ83Lee 发表于 2019-3-27 10:36
Topk的部分讀起來感覺像:
前k個sensor的最晚離開那位person

抱歉 馬拉松沒繞圈  沒有這幾個問題

好厉害，没想到还在用这道题...15年面的时候就面到这道题了

Liyukuang 发表于 2019-3-8 10:46
今天刚面到zhe这道题，超水平发挥了。基本上需要实现两个函数 passMilestone(runner), 以及printLeadBoard( ...

太谢谢啦！你过了吗？我有一个差不多的想法，也用ddl和hash table. ddl的node记录runner id 和last midestone,不需要记录这个人经过milesstone的rank. 一个hash table 记录最后经过第一个某milestone，并且在ddl上的runnder 的node, 所以每次插入的时候判断是否插入（比较最后一个node的milestone，需要新人的更大），如果需要（如果新人之前已经在node里面，找出来删除），然后如果新人的last milestone是m, 在第二个hash table找到m的最后一个node，插进去（如果新人之前不在node里面，删除最后一个node）。我怕自己没有想完整。你觉得这个对吗？

Liyukuang 发表于 2019-3-8 10:46
今天刚面到zhe这道题，超水平发挥了。基本上需要实现两个函数 passMilestone(runner), 以及printLeadBoard( ...

楼主是不是得再建个map来找到，来找到这个mielstone id 经历的人呀，谢谢

目测就是蠡口寺叁贰变种

14417335 发表于 2019-3-9 00:03
我当时读到的时候感觉是是笔误。应该是最后一个经过milestone的人。（即加入尾部）

我想记住前一轮的第一放在他前面也就是这一轮的最后。还在看。。。

补充内容 (2019-9-16 23:49):
如果前一轮的人都跑光，没有人了呢？

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

谢谢分享。请问solution 2第3步有什么快的办法吗？

”3. 建立另一个长 k 的 double linked list，每个node代表一个sensor，将稀疏的sensor连起来“

有了这个会很快，可是我觉得没有办法O（1）做出来。