腾讯
1.服务器内存 1G，有一个 2G 的文件，里面每行存着一个 QQ 号（5-10 位数），
怎么最快找出出现过最多次的 QQ 号。（此题与稍后下文的第 14 题重复，思路参考请
见下文第 14 题）。
首先你要注意到，数据存在服务器，存储不了（内存存不了），要想办法统计每一个qq出现的次数。
比如，因为内存是1g，首先 你用hash的方法，把qq分配到10个（这个数字可以变动，比较）文件（在硬盘中）。
相同的qq肯定在同一个文件中，然后对每一个文件，只要保证每一个文件少于1g的内存，
统计每个 qq 的次数，可以使用 hash_map(qq, qq_count)实现。
然后，记录每个文件的最大访问次数的qq，最后，从10个文件中找出一个最大，即为所有的最大。
那若面试官问有没有更高效率的解法之类的?
这时，你可以优化一下，但是这个速度很快，hash函数，速度很快，他肯定会问，你如何设计，用bitmap 也行。
2.如何求根号2的值，并且按照我的需要列出指定小数位，比如根号2是1.141，
我要列出1位小数就是1.1，2位就是1.14，1000位就是1.141......等；
方法1：二分逼近 ，解方程，用折中法或者直线法逼近
但是这种达不到很高的位数
方法2：用微积分函数展开，即将x^(1/2)展开
解：√(1+x)=(1+x)^(1/2)(按泰勒公式展开)
=1+(1/2)x+(1/2)[(1/2)-1]x^2)/2!+(1/2)[(1/2)-1][(1/2)-2]x^3)/3!+…+(1/2)[(1/2)-1][(1/2)-2]…[(1/2)-n+1](x^n)/n!+o(x^n)
=1+(x/2)-(x²/8)+(x³/16)-…+[(-1)^(n-1)](2n-3)!!(x^n)/(2n)!! +o(x^n)
(2n)!!=(2n)×(2n-2)×(2n-4)×…×4×2，即隔一个相乘，一直乘到能取到的最小正整数。
则√2=(1+1)^(1/2)
=1+(1/2)-(1/8)+(1/16)-…+[(-1)^(n-1)](2n-3)!!/(2n)!!+o(1)
如按前四项展开，则√2≈1+(1/2)-(1/8)+(1/16)=1.4375
十分位是精确值，取的项越多，近似程度越高。
//方法1：
#include<iostream>
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<string.h>
using namespace std;
double sqrtN(int n, int m)
{
double left=0;
double right=n*1.0;
double err=1,mid;
for(int i=0;i<m;i++)
err*=0.1;
while(fabs(left-right)>err)
{
mid=(left+right)/2;
if(mid*mid>(double)n)
right=mid;
else if(mid*mid<(double)n)
left=mid;
}
return left;
}
int main()
{
double res=sqrtN(2,8);
printf("%.8lf\n",res);
return 0;
}