十亿手机号排序问题

tx面试官问十亿手机号要排序,然后我回答说用mapreduce,先分区排,再归并。然后面试官问我reduce怎么实现,我就跟他说最正常的归并排序算法,然后面试官说给我两个提示,一个是手机号都是十一位,还有一个是指针偏移量,最后没想出来,想问问大家面试官想听到什么回答。
全部评论
基数排序O(n)。先根据第11位排序(计数排序或者桶排序),再根据第10位排序,依次类推,最后一次是根据第一位重新排序。
1 回复 分享
发布于 2020-08-21 17:05
我感觉是位图?遍历一遍手机号,对应位置一就行
点赞 回复 分享
发布于 2020-08-21 16:44
手机号码的区间就是00000000000 - 99999999999,弄一个100000000000的区间,把数放到对应的地址位上,在按顺序取出来?
点赞 回复 分享
发布于 2020-08-21 16:56
用一个哈希函数,计算每个电话号码的hash值,然后对1000取余,这样可以把10 亿的电话号码分为1000分,存到1000个文件里面去,然后每个文件里面有100万数据,直接进行排序,然后用小根堆,相当于对多个排序好的链表进行排序。
点赞 回复 分享
发布于 2020-08-21 18:15
面试官明显想听到位图排序
点赞 回复 分享
发布于 2020-08-21 18:20

相关推荐

HNU_fsq:建议直接出国,这简历太6了。自愧不如
点赞 评论 收藏
分享
躺尸修仙中:因为很多92的也去卷中小厂,反正投递简历不要钱,面试不要钱,时间冲突就推,不冲突就面试积累经验
点赞 评论 收藏
分享
点赞 6 评论
分享
牛客网
牛客企业服务