Tusimple第一面

就在刚才面了图森第一面，简历随机网上投的。。。就做题一个，给一个list,维持一个k长的sublist，每次移动一位，然后求这个sublist去掉最大的10%数字，去掉最小的10%的数字之后的平均值，每次移动一位求一次平均数。。。。
大概就这样，最佳算法用树，我没想出来，具体怎么做求大家指教！！！
面试的小姐姐讲中文，特别友好！！
最近本身打算回国了，Onsite了三次都没过，还有几个公司电面都过了然后不招人了？？？气炸了！！！简历回复率也开始变低，有回复的公司都不支持签证，就在准备买机票时来了这个面试，还是有点开心的。。。。。
讲真随着面试真的能体会到自己的提高，从开始的题都做错，到最近一个多月从没做错过题，然后各种CS相关的知识也都全都能答出来，真的真的我都觉得自己很优秀，只是没有公司招我，真的想回国自己做一个app开始创业！！！！

没想到太好的办法，我想到的办法就是保存3个Treeset, 前10%，中间，和后10%。然后每次移动窗口的时候左边删除和右边添加都能LogK复杂度。所以总复杂度是NLogK？

juventusland 发表于 2019-4-20 08:56
没想到太好的办法，我想到的办法就是保存3个Treeset, 前10%，中间，和后10%。然后每次移动窗口的时候左边删 ...

我的想法是前10%用一个MaxHeap存，后10%用一个MinHeap存，这样可以O(1)知道两个边界是多少，中间平均值也可以O(1)算得，在heap里删或者加都是O(logk), 总共应该就是nlogk? 不知道有没有更好的方法

qqqzhouhk 发表于 2019-4-20 12:01
我的想法是前10%用一个MaxHeap存，后10%用一个MinHeap存，这样可以O(1)知道两个边界是多少，中间平均值也 ...

我开始想的也是用heap,但是Python的话要实现logk删除好像比较麻烦。。。至少python的heapq好像不提供logk删除非堆顶元素。所以还要实现logk删除复杂度还需要一个dict辅助记录每个node的index。

当然Python也不支持平衡二叉树，所以我用Python被问到这道题代码就难写了。。

juventusland 发表于 2019-4-20 12:54
我开始想的也是用heap,但是Python的话要实现logk删除好像比较麻烦。。。至少python的heapq好像不提供logk ...

啊啊啊我傻逼了，Java里面Heap删除应该也是O(k)的，那确实只能用Tree做了

juventusland 发表于 2019-4-20 12:54
我开始想的也是用heap,但是Python的话要实现logk删除好像比较麻烦。。。至少python的heapq好像不提供logk ...

Python如果调SortedList是可以用红黑树的，用红黑树实现的Python代码见：
https://app.gitbook.com/@complex ... code-480.-follow-up