DraftKings 二面

昨天面的,今天来发,面试总共一个小时,并非做算法题。面试官是个做前端的三叔,整个面试体验不太好,三叔感觉不在线都,问一个问题要好长时间对面才回答。内容如下:

有一个游戏,一个player可以选择多个lineup,每个lineup里面有很多的角色,一共要写四个函数
1.给定lineup,把这个lineup注册到相应的userid
2.如果一个角色的分数发生变化,更新相应的lineup总分数
3.算出各个玩家的总分
4.有一个排行榜,假如分数是[192,188,188,184,182]输出的排名是[1,2,2,4,5]
follow up: 分数总变,第四个函数还总被call,你有什么办法能避免频繁的sort或者插入优先队列吗。这个有点跪了。。感觉答得一般,三叔也没有任何提示,全程沉默,感觉预感不妙,挂的可能性大
我对前面的函数提出了一些优化,三叔表示还可以,但是没时间写了,不会跑代码,所以过不过全凭三叔一张嘴。

我觉得我写的很详细了

补充内容 (2018-10-14 11:14):
已挂,感觉跟三哥还是有很大关系

我觉得我写的很详细了,各位同学看过了麻烦加个米呗,加米不扣你们米的

学校Handshake投的

你好楼主 谢谢你的分享 我能详细问一下第一个function 和第二个吗

请问lineup是object吗 里边有什么gettotalscore 或者是getuser之类的method吗. From 1point 3acres bbs
第一个我打算用的是hashmap <user, List<Lineup>> 然后更新分数之后 每次便利hashmap 然后每个key 遍历list of lineup,然后check lineup里边有没有这个update的运动员 有的话就update这个lineup的总分 然后在和user 现在的分数对比 如果这个的总分大 则更新user的toalscore

我是这么写的,没问题,写的也很快,三哥说Cool,然后挂了。。。麻烦加个米呗

lineup是object,里面有运动员的id和total score,最后三哥会让加一个feature就是总分,然后开始那个有tie的排名

我能想到一个潜在的优化,就是类似搜索引擎的倒排索引,因为假如一个lineup没有出现在任何user的列表里,那就是白搜一遍了,时间复杂度还是蛮高的,三哥也会一直问时间复杂度,假如以lineup作为key, user作为value在list中时间复杂度可能会低一些

谢谢回复! 已经给您啦

优化怎么做bucket + cache?