求助大家两个场景题

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

相关推荐

头像 会员标识
10-31 12:32
已编辑
南京技师学院 Java
说明:这篇文章纯纯碎碎念,别的地方不好发就发这里了。    从上家离职到现在也差不多一个半月了,至今仍是0大厂offer,自己真的好菜呀。    其实上家的实习体验还是挺好的,带我的mentor就是之前的学长,leader也不push我,问了组内几个校招生,也都能开到30左右,可惜了遇到的时机不对,公司业务偏小众化,title不够,只希望我就待两个月别拉黑我,我秋招还是很想回老东家的。    在这一个半月内,大大小小的面试也累计将近30场,国内收我简历的中大厂像唯品会、哈啰、快手、网易、滴滴、美团、字节也面了个遍,剩下的小厂面的不计其数。也越发的让我意识到面试真的是一场运气的较量,在面这些大厂之前,我反复看牛客上的面经,看到大部分都是八股的拷打+简历上项目实现的难点,但到我这就是各种场景题,有时候真的要被面试官天马行空的问题震惊到。像面字节的时候,直接问我Lion这个中间价的底层实现原理,还试图让我手搓一个线程池(不是ThreadPoolExecutor这种传参数就行,要从底层进行实现),这我面个鬼,面试官还是老学长,真的让我泪目。    在经历了唯品会,哈啰的kpi面,网易给太少拒了,快手一面挂,字节一面挂,美团排序挂,滴滴现在应该也在排序(过了也不一定去,需要转go,而且base北京,一趟来回直接三天白干)。 现在已经面麻木了,也对面试失去了热情,现在在面试的前半个小时,我还可以安心的刷抖音,到面试前10分钟,在老板直骗上重新勾搭几个新目标,这样如果这场面试不过也还有下次机会。    马上11月份了,终于有一家大厂hr加了微信要了学信网证明,目前进行offer审批了,希望不要出问题吧,许愿     update:团子发offer了,团孝子启动!!!#26届实习##美团##字节##滴滴##实习##滴滴##大厂##面试#
投递快手等公司10个岗位
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
11-02 19:30
点赞 评论 收藏
分享
评论
点赞
16
分享
牛客网
牛客企业服务