求助大家两个场景题

1.假设一张表 500条万数据,通过 A 和  B 两个条件进行查询,A 条件可以过滤出 100万条数据,B 条件可以过滤出10 万条数据,那么这个索引应该怎么建。
2. 假设有一个10 G 的文件,你电脑只有 2 G 的内存,找出重复最多的数字
在别的地方看到这两个面试题,不知道怎么解决,网上也没找到比较好的答案,想问问大家有什么方法吗
#笔试题目#
全部评论
1. A B两个都是索引需要走树搜索,时间复杂度在log(M),由于有两个条件,其中一个条件选取完后,第二个条件进行树搜索的过程中需要,回来遍历第一个条件命中数据,时间复杂度为O(N), 让N为数据小的过滤条件,所以建立索引(B,A)。 2. 用分治+一致性hash的方法,如楼上所说,按10的模hash可分成10个文件,每个1G,每次排序任务统计频次需要最多额外1G的空间,然后排序算法最好用原地排序算法,加上我们只关心每个文件中的重复数最大值,用推排序比较合适,最后结果合并比较。
点赞 回复 分享
发布于 2020-03-06 18:18
第二题可以考虑分文件,比如先读入部分文件,然后在取模,(比如模5、模10),最后取值相同的都存入一个文件,然后每个文件统计再统计出现最多的数,合并比较。
点赞 回复 分享
发布于 2020-03-06 18:04

相关推荐

北漂的牛马人:211佬,包进的,可能是系统问题
点赞 评论 收藏
分享
评论
点赞
18
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务