银河里的星星
大数据量的问题是很多面试笔试中经常出现的问题，比如baidu google 腾讯 这样的一些涉及到海量数据的公司经常会问到。
下面的方法是我对海量数据的处理方法进行了一个一般性的总结，当然这些方法可能并不能完全覆盖所有的问题，但是这样的一些方法也基本可以处理绝大多数遇到的问题。下面的一些问题基本直接来源于公司的面试笔试题目，方法不一定最优，如果你有更好的处理方法，欢迎与我讨论。 read more
1. 给你A,B两个文件，各存放50亿条URL，每条URL占用64字节，内存限制是4G，让你找出A,B文件共同的URL。
2. 有10个文件，每个文件1G， 每个文件的每一行都存放的是用户的query，每个文件的query都可能重复。要你按照query的频度排序
3. 有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16个字节，内存限制大小是1M。返回频数最高的100个词 read more
转载请注明作者：phylips@bmy 出处：http://duanple.blog.163.com/blog/static/7097176720098283597120/
对于通常的尾递归很容易转换成循环。通过手工模拟我们基本上就可以确定如何进行转换。实际上尾递归的转换也可以看成是下面这种模式的特殊情况，在这种模式下，尾递归只是一个这样的递归树。 read more
转载请注明作者：phylips@bmy 出处：http://duanple.blog.163.com/blog/static/70971767200982584340501/
1.求最长回文子串。
[解法]：
将整个字 符串反过来写在原字符串后面，中间用一个特殊的字符隔开。这样就把问题变为了
求这个新的字符串的某两个后缀的最长公共前缀。而某两个后缀的lcs的计算利用后缀数组，可以O(1),这样总的复杂度就可以降为O(n)。
eg：aabebf —-> aabebf&fbebaa read more
涉及到字符串的问题，无外乎这样一些算法和数据结构：自动机 KMP算法 Extend-KMP 后缀树 后缀数组 trie树 trie图及其应用。当然这些都是比较高级的数据结构和算法，而这里面最常用和最熟悉的大概是kmp，即使如此还是有相当一部分人也不理解kmp，更别说其他的了。当然一般的字符串问题中，我们只要用简单的暴力算法就可以解决了，然后如果暴力效率太低，就用个hash。当然hash也是一个面试中经常被用到的方法。这样看来，这样的一些算法和数据结构实际上很少会被问到，不过如果使用它们一般可以得到很好的线性复杂度的算法。 read more
1.将字符串转换成整数，将整数转换为字符串，浮点数与字符串的转换(atoi itoa)
int atoi(const char *str){
int res = 0;
int sign;
assert(str != NULL);
if(str[0] == ‘-‘) sign = -1;
else if(str[0] == ‘+’) sign =1;
else if(isdigit(str[0])){sign = 1;res=str[0] – ‘0’;} read more
转载请注明作者：phylips@bmy 出处：http://duanple.blog.163.com/blog/static/7097176720098311658625/
RSA加密系统，实际上基于这样一个基本事实。大数的素性测试要比因子分解简单的多，因子分解是一个难问题。
素数测试
如何测试一个数n是不是素数呢？简单的办法就是试一下它能否整除比它小的那些数，当然可以优化只检测小于sqare(n),但是无论如何优化，需要检测的数的个数都将不会小于小于sqare(n)的素数的个数。根据拉格朗日定理，小于n的素数的个数大概=n/ln(n)，也就是说这个数目很大，数量级上很接近n了。所以这个路子实际上很难降低复杂度。 read more
转载请注明作者：phylips@bmy 出处：http://duanple.blog.163.com/blog/static/7097176720098210128972/
欧几里德算法
用来求两个数的最大公约数的算法。具体如下
int gcd(int a,int b){
if(b == 0) return a;
return gcd(b,a%b);
}
首先看正确性证明，实际上需要证明gcd(a,b)=gcd(b,a%b),我们只要证明gcd(a,b)=gcd(a-b,b)即可，因为可以由此逐步扩展为gcd(a,b) = gcd(a-k*b,b),而 gcd(a-k*b,b)=gcd(a%b,b)。
因为a,b的公约数必然是a-b,b的公约数故 gcd(a,b) <= gcd(a-b,b);另a-b b的公约数也必然是a b的公约数，gcd(a,b) >= gcd(a-b,b).所以gcd(a,b) = gcd(a-b,b)。证明完毕。 read more
转载请注明作者：phylips@bmy 出处：http://duanple.blog.163.com/blog/static/70971767200953105952749/
对于字符串处理，常用的有这么几个工具，kmp，trie树，trie图，后缀树，后缀数组，正则表达式，DFA，NFA。下面就这些算法，数据结果及模型进行下简要的说明，并研究下它们之间的联系。 read more
转载请注明作者：phylips@bmy 出处：http://duanple.blog.163.com/blog/static/7097176720094279641210/
有关各种排序问题的稳定性，时间复杂度，比较次数大概是最经常问到的问题了。另外对于某些公司，对于大数据量的排序问题也会涉及，这样就可能牵扯到外排序。所以这里一并将外排序一般归并过程中所使用的败者树和胜者树，以及置换选择排序大概的描述一下。 read more
1.枚举int值，统计二进制bit中1的个数
1.1记忆化统计1的个数，x^(x-1)直接统计
//enum int comb
int count(unsigned int x){
int i = 0;
while(x != 0){
x = x&(x-1);
i++;
}
return i;
}
void enumComb(int N,int M){
int one[1<<15];
for(int i = 0 ; i < (1 << (N+1)/2) ; i++){
one[i] = count(i);
}
int half = N/2;
for(int i = 1 ; i < (1 << half) ; i++){
for(int j = 1 ; j < (1 << N-half) ; j++){
if(one[i] + one[j] == M){
cout << i << " " << j << endl;
}
}
}
} read more
转载请注明作者：phylps@bmy
出处：http://duanple.blog.163.com/blog/static/70971767200922110494318/
第一层次
线段树的本质在于将一条线段区间分成一些小的子段，树状数组可以看成一种线段树。对于该区间内的一些线段便可以用这样的一些子段来表示，同时有这样的定理。任何一个长为L的线段都可以用不超过2*logL个子段表示。这样对于插入一个线段便可以在logn时间内解决。而线段树，则是通过这样的使用线段子段的组合，来表示现在出现的线段，而具体的方式则是通过对于一个子段的cout计数来表示的。同时一条线段在树中，只会被真实的表达一次，即只有真正组成它的那些子段会被计数，而当子段已经计数，就可以结束，而子段下的子段不会被重复计数。 read more
近来忙着挑战杯的项目，还有异构编程的，没有多少时间来做题，不过偶尔也会把题目记在心里，走路吃饭睡觉的时候那么想想。有时候也会有了一些新的看法和思考，感觉这样的思考方式倒是挺安静也挺深刻的，不会拘泥于做题中对数量的追求。 read more
线段树就像树状数组一样，通过将一个长为n的段落，划分为O(logn)个子段落，这样就可以通过维护子段落的属性，来求得整个段落的属性。可以证明，任何一个子段在一颗线段树上不会被划分为超过2logn个子段。
一个典型的线段树如下： read more
历史上，Knuth在其<<Sorting and Searching>>一书的第6.2.1节指出：尽管第一个二分搜索算法于1946年就出现，然而第一个完全正确的二分搜索算法直到1962年才出现。
而不经仔细斟酌而写出的一个二分查找经常遭遇off by one或者无限循环的错误。下面将讨论二分查找的理论基础，实现应用，及如何采用何种技术保证写出一个正确的二分程序，让我们免于思考麻烦的边界及结束判断问题。 read more