1、有1亿个浮点数,请找出其中最大的10000个。提示:假设每个浮点数占4个字节,1亿个浮点数就要站到相当大的空间,因此不能一次将全部读入内存进行排序。
2、有一篇英文文章(也就是说每个单词之间由空格分隔),请找出“csdn”着个单词出现的次数,要求效率最高,并写出算法的时间级。
3.假设有1kw个身份证号,以及他们对应的数据。身份证号可能重复,要求找出出现次数最多的身份证号。
4.百度每天都会接受数亿的查询请求, 如何在这么多的查询(Query)中找出高频的Query是一个不小的挑战. 而你的任务则更加艰巨, 你需要在极其有限的资源下来找出这些高频的Query.(使用内存不得多于1MB) 。输入文件是一行一个Query, 以文件结束符结尾。每个Query字节数L(一个汉字两个字节)满足:0
1.对于第一道题目可以发现如果一次读入那么机器的内存肯定是受不了的,因此我们只有想其他方法解决,解决方式为了高效还是得符合一定的该概率解决,结果并不一定准确,但是应该可以作对大部分的数据。
(1.我们可以把1亿个浮点数分组为100W个一组,这样就分为了100个组,第一次在每个组中找出最大的1W个数,第二次查询的时候就是100W个数中再找出最大的1W个数。
PS:100W个数中再找出最大的1W个数用类似快排的思想搞定。
2.第二道题目可以把单词看成一个N进制数,CSDN相当于('c'-'a')*N^3+('s'-'a')*N^2+('d'-'a')*N+('n'-'a'),然后查找这个数出现的次数就是答案,也可以建立一颗字典树,然后去计数!
PS:N可以取32,64等
3.简单进行hash搞定,O(n),如果数据量再扩大我就不知道怎么搞了,用磁盘的话,IO数据是接受不了的
4.hash,然后建立hash[103][100]的节点的表,每次找出出现次数最少的进行替换。
Tags - 海量数据 , 处理
*在处理海量数据时hash + 索引 + 倒排非常有用,在内存空间较小的情况下多通道排序也非常有用!另外,在遇到海量数据求高频问题时,还可以采用采样的手段来处理。
*对于第一道的思路一种更效率是: 1、读入的头10000个数,直接创建二叉排序树。O(1) 2、对以后每个读入的数,比较是否比前10000个数中最小的大。(N次比较)如果小的话接着读下面的数。O(N) 3、如果大,查找二叉排序树,找到应当插入的位置。 4、删除当前最小的结点。 5、重复步骤2,直到10亿个数全都读完。 6、按照中序遍历输出当前二叉排序树中的所有10000个数字。 基本上算法的时间复杂度是O(N)次比较 算法的空间复杂度是10000(常数)
分享到:
相关推荐
常用大数据量,海量数据处理方法,算法总结,非常好的书。
高级篇将从概念和应用的角度,深入剖析一些稍复杂的数据结构与算法,推演海量数据下的算法问题解决过程;帮你更加深入理解算法精髓,开拓视野,训练逻辑;真正带你升级算法思维,修炼深厚的编程内功。 实战篇将通过...
这个资源无疑是一个宝藏,它提供了海量的算法题目以及详尽的代码示例,覆盖了Java、C语言和C++等多种编程语言,为计算机专业的学生提供了一个极佳的课后实践平台。无论是初学者还是有一定编程基础的学生,都能从中...
中文文本相似度匹配算法 simHash 海明距离 IK分词 完整的可运行的示例代码 包含simHash 算法,使用IK 对中文文本进行分词处理
**JAVA基于遗传算法的中药药对挖掘系统的设计与实现(源代码+论文)** 本资源提供了一个基于遗传算法的中药药对挖掘系统的完整解决方案,包括源代码和详细的设计论文。该系统旨在通过先进的数据挖掘技术,结合中医...
从海量数据到大数据-数据挖掘算法、过程及应用案例,
Java核心知识点整理(包括Java基础、JVM、数据库、计算机网络、算法、操作系统、设计模式、系统设计、框架原理)。 > # 目录结构 > > | :--: | :----: | :--------: | :--: | :------: | :------: | :------: | :--...
数据挖掘出现之前,海量的数据只是被简单的存储,不能对隐含在其中的信息进行分析、利用与创造价值,数据挖掘由此出现。数据挖掘是新兴且前沿的技术,是信息领域和数据库领域热点之一。数据挖掘技术的快速发展,出现...
本文档为学术不端检测的方案文档,有多种算法结合的检测引擎方案
海量数据库的查询优化及分页算法方案-DAO-Java
java二叉树算法源码 项目对应 WebSIte: :pencil: 计算机基础 1. 计算机网络 2. 操作系统 3. 数据结构和算法 4. HTTP 5. Linux :hot_beverage: Java 1. Java 基础 2. Java 容器 3. Java 虚拟机 4. Java 并发 5. Java...
包含非常丰富的Java知识点和海量面试题,整理自“程序员乔戈里”,感谢原作者的辛苦付出,本资源作为搬运,是因为原作者的链接无法访问了,自己通过一些手段辛苦下载下来,希望能帮到大家! 搜集不易,请予以点滴...
java面试过程中遇到的问题及回答整理,包括Java基础,算法与数据结构,jvm,集合源码,JavaEE,海量数据处理,并发与多线程。希望可以帮助到你
java实现的SimHash算法,用于海量的网页去重和打拼量的文本相似度检测
本文实现了基于 Java 语言 的Adaptive Repalcement Cache缓存管理算法(ARC算法),并 提出改进的ARC算法, 以适应海量小文件中存在大量热点数据的情况。改进的 ARC 算法可以预测将会被 频繁访问的小文件并将其进行...
数据结构与算法 海量数据处理 SSM企业级应用(Spring+SpringMVC+Mybatis) SpringBoot+SpringCloud 需要完整版Java面试宝典的朋友,只需要关注我后[戳这里,暗号:CSDN](()即可。 [](()一、面试经验技巧篇 =...
算法设计与分析课内实验——贪心法求单源最短路径。文档很齐全,包括算法分析过程和源代码(java语言eclipse环境)
本书除了对传统的计算机相关知识(Java语言基础知识、Web基础知识、数据结构与算法、操作系统、计算机网络与通信、数据库、设计模式等)以及面试笔试真题进行分析与解答外,还根据当前计算机技术的发展潮流,对面试...
在本项目中采用的是基于用户的协同过滤的推荐算法来实现商品的推荐并在前台页面进行展示,我将会使用余弦相似度的度量方法来计算用户与用户之间相似性,最终将相似度较高的用户浏览的商品推荐给用户。 项目目标 商品...