[zz]大数据量，海量数据 处理方法总结

大数据量的问题是很多面试笔试中经常出现的问题，比如baidu google 腾讯 这样的一些涉及到海量数据的公司经常会问到。

下面的方法是我对海量数据的处理方法进行了一个一般性的总结，当然这些方法可能并不能完全覆盖所有的问题，但是这样的一些方法也基本可以处理绝大多数遇到的问题。下面的一些问题基本直接来源于公司的面试笔试题目，方法不一定最优，如果你有更好的处理方法，欢迎与我讨论。

1.Bloom filter

适用范围：可以用来实现数据字典，进行数据的判重，或者集合求交集

基本原理及要点：
对 于原理来说很简单，位数组+k个独立hash函数。将hash函数对应的值的位数组置1，查找时如果发现所有hash函数对应位都是1说明存在，很明显这 个过程并不保证查找的结果是100%正确的。同时也不支持删除一个已经插入的关键字，因为该关键字对应的位会牵动到其他的关键字。所以一个简单的改进就是 counting Bloom filter，用一个counter数组代替位数组，就可以支持删除了。

还有一个比较重要的问题，如 何根据输入元素个数n，确定位数组m的大小及hash函数个数。当hash函数个数k=(ln2)*(m/n)时错误率最小。在错误率不大于E的情况 下，m至少要等于n*lg(1/E)才能表示任意n个元素的集合。但m还应该更大些，因为还要保证bit数组里至少一半为0，则m应 该>=nlg(1/E)*lge 大概就是nlg(1/E)1.44倍(lg表示以2为底的对数)。

举个例子我们假设错误率为0.01，则此时m应大概是n的13倍。这样k大概是8个。

[zz]计算机算法和竞赛教材介绍

现在公认最好的入门书籍是“白书”《算法竞赛入门经典》（建议每位队员都应该要买这本书），之后应该就是《算法导论》和《算法艺术与信息学竞赛》了，另外《组合数学》和《离散数学》也是值得学习的，这个对训练逻辑思维、数学思维有很大的好处，比如东欧强队都非常注重这方面的训练，而国内注重的是算法训练。

关于题目的好书有：《ACM国际大学生程序设计竞赛题解(1) 》《ACM国际大学生程序设计竞赛题解(2)》《ACM国际大学生程序设计竞赛亚洲区预选赛真题题解》

关于OJ做题的好书有《挑战编程:程序设计竞赛训练手册》，另外一本国内的《程序设计导引及在线实践》

以下来自网络转载：

acm算法书籍收藏推荐

我常感叹到，学计算机的人是幸福的，因为在这个领域中有如此多的通俗易懂（相对来说）的经典好书，你需要做的只是坚持把它们一本一本读下去而已。学力学就没有这样的好事了（抱怨一下），除了论文就是论文，满篇公式，晦涩坚深，真不是给人看的（虽然我也没看过几篇）。在这里列出一些我看过或者准备看的算法书籍，以供参考。

[zz]数据结构+算法面试100题~~~摘自CSDN，作者July

Also see these 2 links:

https://apollozhao.wordpress.com/2011/05/20/zz%E5%90%84%E5%A4%A7%E5%85%AC%E5%8F%B8%EF%BC%88google%EF%BC%8Cmicrosoft%EF%BC%8Cbaidu%EF%BC%8C-microsoft-research-asia-etc-%EF%BC%89%E5%AE%9E%E4%B9%A0%E7%94%9F%E9%9D%A2%E8%AF%95%E9%A2%98%E6%80%BB/

https://apollozhao.wordpress.com/2012/03/31/zz%E9%87%8D%E7%A3%85%E5%88%86%E4%BA%AB%EF%BC%9A%E5%BE%AE%E8%BD%AF%E7%AD%89%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%AE%97%E6%B3%95%E9%9D%A2%E8%AF%95100%E9%A2%98%E5%85%A8%E9%83%A8%E7%AD%94%E6%A1%88/

This post has something more at the end.

——

1.把二元查找树转变成排序的双向链表（树）
题目：
输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。
要求不能创建任何新的结点，只调整指针的指向。
10
/ /
6  14
/ / / /
4  8 12 16
转换成双向链表
4=6=8=10=12=14=16。

首先我们定义的二元查找树 节点的数据结构如下：
struct BSTreeNode
{
int m_nValue; // value of node
BSTreeNode *m_pLeft; // left child of node
BSTreeNode *m_pRight; // right child of node
};
2.设计包含min函数的栈（栈）
定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。
要求函数min、push以及pop的时间复杂度都是O(1)。
3.求子数组的最大和（数组）
题目：
输入一个整形数组，数组里有正数也有负数。
数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。
求所有子数组的和的最大值。要求时间复杂度为O(n)。

[zz]APL — The God’s Language 上帝的编程语言

There are three things a man must do
Before his life is done;
Write two lines in APL,
And make the buggers run.

— Stan Kelly-Bootle, The Devil’s DP Dictionary, 1981

这几天大师兄没来实验室，问了下老板才发现是参加ICFP比赛去了(一个关于functional programming language的比赛)。说到FP，老板饶有兴致地向我们介绍了APL这门语言。APL的全称就叫A Programming Language， 一般一个传奇性的东西名字都普通得不能再普通，就好比武侠小说里一把牛逼的宝剑上刻的名字是“无名”这种情况。当时看了下wiki百科，瞬间就被震到了， 因为这是一门比lisp,scheme都还要再high-level的语言，我老板称它为”The God’s Language”。当你看到下面的介绍时，就会发现用这种语言写程序的人，要么是天才，要么是疯子。

每种程序语言都会吹嘘这门语言和其他语言在哪些方面上有多么多么不同，但是当你看到一个APL程序的时候，你会发现这尼玛才是真正的不同！一个APL程序根本就长得很怪异，像一些代数公式一样。当你想要写APL程序的时候，还需要准备一个专门的APL键盘，这种键盘长得下面这个样子：

[zz]UIUC某童鞋收集的代码合集，大赞啊！

https://netfiles.uiuc.edu/jbhuang1/www/resources/vision/index.html

Computer Vision Resources

Maintained by Jia-Bin Huang

Submit resource links here

Lastest Update: July 4, 2011

算法和数据结构的可视化演示

做的非常好。

见此链接：

http://www.cs.usfca.edu/~galles/visualization/Algorithms.html

[zz]各大公司（Google，Microsoft，Baidu， Microsoft Research Asia etc.）实习生面试题总汇

from: http://blog.renren.com/share/228066793/6584972503

1.把二元查找树转变成排序的双向链表（树）

题目：

输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。

要求不能创建任何新的结点，只调整指针的指向。

10

/ \

6  14

/ \ / \

4  8 12 16

转换成双向链表

4=6=8=10=12=14=16。

首先我们定义的二元查找树 节点的数据结构如下：

struct BSTreeNode

{

int m_nValue; // value of node

BSTreeNode *m_pLeft; // left child of node

BSTreeNode *m_pRight; // right child of node

};

[zz]可视化数据结构和算法

from: http://blog.renren.com/share/1780465771/6408297826

友情提示，一下链接，建议用chrome浏览器打开！

还记得之前发布过的那个关于可视化排序的文章吗？在网上又看到了一个旧金山大学David Galles做的各种可视化的数据结构和基本算法的主页，网址在这里，大家可以看看。我把这个页面的目录列在下面并翻译了一下，大家可以直接点击了。

不知道国内的教育有没有相关的教学课件，至少在我大学的时候是没有的。

基础

• Stack栈: 数组实现
• Stack栈: 链表实现
• Queues队列: 数组实现
• Queues队列: 链表实现
• Lists列表: 数组实现( java 版演示)
• Lists列表: 链表实现( java 版演示)

索引

[zz]最大公约数(Gcd)两种算法(Euclid && Stein) [整理]

from: http://www.cnblogs.com/drizzlecrj/archive/2007/09/14/892340.html

很老的东东了，其实也没啥好整理的，网上很多资料了，就当备用把:-)

1. 欧几里德算法和扩展欧几里德算法

欧几里德算法
欧几里德算法又称辗转相除法，用于计算两个整数a,b的最大公约数。其计算原理依赖于下面的定理：

定理：gcd(a,b) = gcd(b,a mod b)

证明：a可以表示成a = kb + r，则r = a mod b
假设d是a,b的一个公约数，则有
d|a, d|b，而r = a – kb，因此d|r
因此d是(b,a mod b)的公约数

假设d 是(b,a mod b)的公约数，则
d | b , d |r ，但是a = kb +r
因此d也是(a,b)的公约数

因此(a,b)和(b,a mod b)的公约数是一样的，其最大公约数也必然相等，得证

[zz]深入学习算法的一点拙见

from: http://blog.csdn.net/midgard/archive/2009/04/16/4084884.aspx

今天实在是头脑不听使唤了，没力气看书，写代码了。写点总结吧。

都说算法是内功，究竟练到什么程度才算修成了呢？

为什么要学习，强化算法？

首先强调的是，下面的原因均是建立在算法熟练到一定程度后的效果。不熟的话，未见得能达到效果。这些原因很现实。但很多程序员却不知道或不以为然。

1. 比较世俗的方面，顶级软件公司笔试，面试会问到。别说你不想去谷歌，百度，微软，如果真的没想过，我希望你能想想自己是否具备进入的实力。如果还是没兴趣想，那就忘了这条，看看下面的原因吧。
2. 如果算法熟练，能显著提高看代码的速度，越是工作久了，越会发现很多时候是在读别人写的代码，然后在其基础上追加功能，或修改bug。所以这是很现实的技能。
3. 算法操练上手快，注意只是快，但不见得容易。因为练习省去了界面等操作，只利用编译器最基本的功能，非常适合初学者，编程环境不十分熟练的人来学习，别小看这一点，这能让你不论在家，在同学的电脑上，甚至在网吧，只要你想操练都是能迅速找到办法写程序实现的。