Open wtysos11 opened 3 years ago
这个是字节跳动三面的时候被问到的问题,其实还挺麻烦的。当时面试官给的问题是一亿个数字的第100大,我想了三个思路,一个是直接原地排序;一个是直接随机选关键字进行快速分桶,全部分完之后在桶内进行排序;一个是如果知道数据的大致分布的话可以参考基数排序的思想(按最高几位进行分桶);一个是维护一个最大堆,然后扫描一遍。 从效果上我觉得类基数排序的分桶速度上应该是最快的,桶甚至都不用往内存里面放,并行化支持也挺好的。分完桶之后并行对包含前100个数字的桶进行排序,然后找到即可。(这里应该要讲一下时间复杂度,分析执行代价之类的,当时忘记讲了) 二面的时候有一个类似的问题,不过数字的大小变为了一千亿个数字,没有特殊处理基本是不可能在现代计算机中放进去(每个4B,可以快速估算出来是400个十亿,大约是400G的量级),当时就是口述了一下多路归并和分桶两个想法。
而且第k大数字和分位数算法又有些不太一样,我觉得还是需要好好想一下。还是算法题做的不够多。 https://caorong.github.io/2020/08/03/quartile-%20algorithm/
这个是字节跳动三面的时候被问到的问题,其实还挺麻烦的。当时面试官给的问题是一亿个数字的第100大,我想了三个思路,一个是直接原地排序;一个是直接随机选关键字进行快速分桶,全部分完之后在桶内进行排序;一个是如果知道数据的大致分布的话可以参考基数排序的思想(按最高几位进行分桶);一个是维护一个最大堆,然后扫描一遍。 从效果上我觉得类基数排序的分桶速度上应该是最快的,桶甚至都不用往内存里面放,并行化支持也挺好的。分完桶之后并行对包含前100个数字的桶进行排序,然后找到即可。(这里应该要讲一下时间复杂度,分析执行代价之类的,当时忘记讲了) 二面的时候有一个类似的问题,不过数字的大小变为了一千亿个数字,没有特殊处理基本是不可能在现代计算机中放进去(每个4B,可以快速估算出来是400个十亿,大约是400G的量级),当时就是口述了一下多路归并和分桶两个想法。
而且第k大数字和分位数算法又有些不太一样,我觉得还是需要好好想一下。还是算法题做的不够多。 https://caorong.github.io/2020/08/03/quartile-%20algorithm/