百度人搜，阿里巴巴，腾讯华为笔试面试题汇总（2）

接上一篇百度人搜，阿里巴巴，腾讯华为笔试面试题汇总（1）





10月13日，百度移动开发笔试题
一、 1、什么是RISC；
2、通过后序、中xu求前序
3、重写与重载的区别
二、
1、反转链表
2、判断两个数组中是否有相同的数字
3、1000瓶水中找 出有毒的那瓶，毒性一周后发作，一周内最少需要多少只老鼠
三、系统设计 email客户端，支持多账户和pop3等协议
  1、请写出可能的至少5个用例；
  2、使用sqlite存储帐户、已收信息、已发信息、附件、草稿，请设计合理的表结构
  3、pop3等协议等接口已完成，请给出email客户端的模块设计图。
10月13日，人搜2013 校招北京站部分笔试题（读者回忆+照片）：

1，二重歌德巴赫猜想
所有大于等于6的偶数都可以表示成两个（奇）素数之和。
给定1-10000，找到可以用两个素数之和表示每一个偶数的两个素数，然后输出这两个素数，如果有多对，则只需要输出其中之一对即可。
要求：复杂度较低，代码可运行。
2，城市遍历
某人家住北京，想去青海玩，可能会经过许多城市，
现已知地图上的城市连接，求经过M个城市到达青海的路线种类。
城市可以多次到达的，比如去了天津又回到北京，再去天津，即为3次。北京出发不算1次。
输入：
N  M  S
    N为城市总数，北京为0，青海为N-1；
    M为经过的城市数目；
    S为之后有S行
i  j
    表示第i个城市可以去第j个城市，是有方向的。
输出：
N
    表示路径种类。
3，分布式系统设计
有1000亿个URL，其中大约有5亿个site。每天的更新大约2%-5%。设计一个系统来解决存储和计算下面三个问题。可用分布式系统。
URL：http///site[port]*(key==?;key==?)
site:.domain
  URL：http://www.baidu.com/baidu?word= ... 2%E4%BC%9A&ie=utf-8
  site：：www.baidu.com
domain：：baidu.com
key=baidu?word
    a>检测每个域名下的site数目，以及每个site下的URL数目，输出site变化超过一定阈值的域名以及URL数目变化剧烈的site。找出泛域。
泛域：该域下的site数目超过500个，且每个site下的URL数目超过100个。
    b>提取URL中key的特征，对site进行聚类；
(每个site下面有多个URL，这些URL中有许多key，可以获取这些key作为site的特征，对site进行聚类，不过这应该是多机器联合的)
    c>对于给定的domain，输出该domain下的所有site。
10月13日，创新工场笔试：
第一个，快排最坏情况下是O(n^2)，问如何优化？
第二个，怎么样求一个数的根号
点评：你是不是会想到一系列有关数学的东西，什么泰勒级数啊，什么牛顿法啊，具体编程可以如下代码所示：
static void Main(string[] args)  
{  
    double k = 5;  
    double n = 2,  m = k;  
  
    while (n != m)  
    {  
        m = k / n;  
        n = (m + n) / 2;  
    }  
}  

链接：http://www.51nod.com/question/index.html#!questionId=660。
第三个，4个数字，用四则元素求结果能否为24。写出这个判断的函数。

10月14日，思科网讯旗下公司笔试题：
1、海量数据中，寻找最小的k个数。
请分情况，给出时间复杂度最优，或空间复杂度最优的方案，或时间复杂度/空间复杂度综合考虑的可行方案。
点评：参见：第三章、寻找最小的k个数。
2、有两座桥，其中一座可能是坏的，两个守桥人分别守在这两座桥的入口。他们一个总是会说实话，一个总是说谎话。
你现在需要找出哪一座桥可以通过。
1)，请问最少需要问守桥人几个问题，可以找出可以通过的桥？如何问？
2)，请编程解决。

10月14日，腾讯杭州站笔试题：

1、http服务器会在用户访问某一个文件的时候，记录下该文件被访问的日志，网 站管理员都会去统计每天每文件被访问的次数。写一个小程序，来遍历整个日志 文件，计算出每个文件被访问的访问次数
    1）请问这个管理员设计这个算法
    2）该网站管理员后来加入腾讯从事运维工作，在腾讯，单台http服务器不够用的 ，同样的内容，会分布在全国各地上百台服务器上。每台服务器上的日志数量， 都是之前的10倍之多，每天服务器的性能更好，之前他用的是单核cpu，现在用的 是8核的，管理员发现在这种的海量的分布式服务器，基本没法使用了，请重新设计一个算法。
2、腾讯的qq游戏当中，最多人玩的游戏就是斗地主了，每一句游戏开始时，服务 器端都要洗牌，以保证发牌的时每个人拿的牌都是随机的，假设用1-54来表示54 张不同的拍，请你写一个洗牌算法，保证54张牌能随机打散！
选择题：
1）、下列RAID技术无法提高可靠性的是：
A：RAID0   B：RAID1  C：RAID10  D：RAID5
2）、长度为1的线段，随机在其上选择两点，将线段分为三段，问这3个字段能组成一 个三角形的概率是：
1/2,1/3,1/4,1/8
3）、下面那种标记的包不会在三次握手的过程中出现（）
A：SYN B：PSH C：ACK D:RST

10月14日，搜狗2013 校招笔试题：



1、有n*n个格子，每个格子里有正数或者0，从最左上角往最右下角走，只能向下和向右，一共走两次（即从左上角走到右下角走两趟），把所有经过的格子的数加起来，求最大值SUM，且两次如果经过同一个格子，则最后总和SUM中该格子的计数只加一次。
点评：@西芹_new，一共搜（2n-2）步，每一步有四种走法，考虑不相交等条件可以剪去很多枝，代码如下「http://blog.csdn.net/huangxy10/article/details/8071242」：
西芹_new<huangxy10@qq.com>  0:55:40  
// 10_15.cpp : 定义控制台应用程序的入口点。  
//  
  
#include "stdafx.h"  
#include <iostream>  
using namespace std;  
  
#define N 5  
int map[5][5]={  
    {2,0,8,0,2},  
    {0,0,0,0,0},  
    {0,3,2,0,0},  
    {0,0,0,0,0},  
    {2,0,8,0,2}};  
int sumMax=0;  
int p1x=0;  
int p1y=0;  
int p2x=0;  
int p2y=0;  
int curMax=0;  
  
void dfs( int index){  
    if( index == 2*N-2){  
        if( curMax>sumMax)  
            sumMax = curMax;  
        return;  
    }  
  
    if( !(p1x==0 && p1y==0) && !(p2x==N-1 && p2y==N-1))  
    {  
        if( p1x>= p2x && p1y >= p2y )  
            return;  
    }  
  
    //right right  
    if( p1x+1<N && p2x+1<N ){  
        p1x++;p2x++;  
        int sum = map[p1x][p1y]+map[p2x][p2y];  
        curMax += sum;  
        dfs(index+1);  
        curMax -= sum;  
        p1x--;p2x--;  
    }  
  
    //down down  
    if( p1y+1<N && p2y+1<N ){  
        p1y++;p2y++;  
        int sum = map[p1x][p1y]+map[p2x][p2y];  
        curMax += sum;  
        dfs(index+1);  
        curMax -= sum;  
        p1y--;p2y--;  
    }  
  
    //rd  
    if( p1x+1<N && p2y+1<N ) {  
        p1x++;p2y++;  
        int sum = map[p1x][p1y]+map[p2x][p2y];  
        curMax += sum;  
        dfs(index+1);  
        curMax -= sum;  
        p1x--;p2y--;  
    }  
  
    //dr  
    if( p1y+1<N && p2x+1<N ) {  
        p1y++;p2x++;  
        int sum = map[p1x][p1y]+map[p2x][p2y];  
        curMax += sum;  
        dfs(index+1);  
        curMax -= sum;  
        p1y--;p2x--;  
    }  
}  
  
int _tmain(int argc, _TCHAR* argv[])  
{  
    curMax = map[0][0];  
    dfs(0);  
    cout <<sumMax-map[N-1][N-1]<<endl;  
    return 0;  
}  

@绿色夹克衫：跟这个问题：[size=+0]http://www.51nod.com/question/index.html#!questionId=487 ，是同一个问题。
  1、用动态规划可以求解，大概思路就是同时DP 2次所走的状态。先来分析一下这个问题，为了方便讨论，先对矩阵做一个编号，且以5*5的矩阵为例（给这个矩阵起个名字叫M1）：
M1
0 1 2 3 4
1 2 3 4 5
2 3 4 5 6
3 4 5 6 7
4 5 6 7 8
  从左上(0)走到右下(8)共需要走8步（2*5-2）。为了方便讨论，我们设所走的步数为s。因为限定了只能向右和向下走，因此无论如何走，经过8步后（s = 8)都将走到右下。而DP的状态也是依据所走的步数来记录的。
  再来分析一下经过其他s步后所处的位置，根据上面的讨论，可以知道经过8步后，一定处于右下角(8)，那么经过5步后(s = 5)，肯定会处于编号为5的位置。3步后肯定处于编号为3的位置......。s = 4的时候，处于编号为4的位置，对于方格中，共有5（相当于n）个不同的位置，也是所有编号中最多的。推广来说n*n的方格，总共需要走2n - 2步，当s = n - 1时，编号为n个，也是编号最多的。
  如果用DP[s,i,j]来记录2次所走的状态获得的最大值，其中s表示走s步，i表示s步后第1次走所处的位置，j表示s步后第2次走所处的位置。
为了方便讨论，再对矩阵做一个编号（给这个矩阵起个名字叫M2）：
M2
0 0 0 0 0
1 1 1 1 1
2 2 2 2 2
3 3 3 3 3
4 4 4 4 4
M1
0 1 2 3 4
1 2 3 4 5
2 3 4 5 6
3 4 5 6 7
4 5 6 7 8
  经过6步后，肯定处于M1中编号为6的位置。共有3个编号为6的，分别对应M2中的2 3 4。假设第1次经过6步走到了M2中的2，第2次经过6步走到了M2中的4，DP[s,i,j] 则对应 DP[6,2,4]。由于s = 2n - 2,0 <= i<= <= j <= n，所以这个DP共有O(n^3)个状态。
M1
0 1 2 3 4
1 2 3 4 5
2 3 4 5 6
3 4 5 6 7
4 5 6 7 8
  再来分析一下状态转移，以DP[6,2,3]为例(就是上面M1中加粗的部分)，可以到达DP[6,2,3]的状态包括DP[5,1,2]，DP[5,1,3]，DP[5,2,2]，DP[5,2,3]，加粗表示位置DP[5,1,2]    DP[5,1,3]    DP[5,2,2]    DP[5,2,3] （加红表示要达到的状态DP[6,2,3]）
0 1 2 3 4    0 1 2 3 4    0 1 2 3 4    0 1 2 3 4
1 2 3 4 5    1 2 3 4 5    1 2 3 4 5    1 2 3 4 5
2 3 4 5 6    2 3 4 5 6    2 3 4 5 6    2 3 4 5 6
3 4 5 6 7    3 4 5 6 7    3 4 5 6 7    3 4 5 6 7
4 5 6 7 8    4 5 6 7 8    4 5 6 7 8    4 5 6 7 8
  因此，DP[6,2,3] = Max(DP[5,1,2] ，DP[5,1,3]，DP[5,2,2]，DP[5,2,3]) + 6,2和6,3格子中对应的数值    （式一）
  2、上面（式一）所示的这个递推看起来没有涉及：“如果两次经过同一个格子，那么该数只加一次的这个条件”，讨论这个条件需要换一个例子，以DP[6,2,2]为例。
  DP[6,2,2]可以由DP[5,1,1]，DP[5,1,2]，DP[5,2,2]到达，但由于i = j，也就是2次走到同一个格子，那么数值只能加1次。
  所以当i = j时，DP[6,2,2] = Max(DP[5,1,1]，DP[5,1,2]，DP[5,2,2]) + 6,2格子中对应的数值                    （式二）
  3、故，综合上述的（式一），（式二）最后的递推式就是
if(i != j)
    DP[s, i ,j] = Max(DP[s - 1, i - 1, j - 1], DP[s - 1, i - 1, j], DP[s - 1, i, j - 1], DP[s - 1, i, j]) + W[s,i] + W[s,j]
else
    DP[s, i ,j] = Max(DP[s - 1, i - 1, j - 1], DP[s - 1, i - 1, j], DP[s - 1, i, j]) + W[s,i]
    其中W[s,i]表示经过s步后，处于i位置，位置i对应的方格中的数字。
  复杂度分析：状态转移最多需要统计4个变量的情况，看做是O(1)的。共有O(n^3)个状态，所以总的时间复杂度是O(n^3)的。空间上可以利用滚动数组优化，由于每一步的递推只跟上1步的情况有关，因此可以循环利用数组，将空间复杂度降为O(n^2)。
    OK，上述这个方法可能不算最优解法，但相对比较容易想一些。希望大家能够提供更好的想法，也欢迎大家补充程序。链接：http://www.51nod.com/answer/index.html#!answerId=598。
2、N个整数（数的大小为0-255）的序列，把它们加密为K个整数（数的大小为0-255）.再将K个整数顺序随机打乱，使得可以从这乱序的K个整数中解码出原序列。设计加密解密算法,且要求K<=15*N.
如果是：
1，N<=16,要求K<=16*N.
2，N<=16,要求K<=10*N.
3，N<=64,要求K<=15*N.
点评：http://www.51nod.com/question/index.html#!questionId=659。

人人网面试，只面一道题，要求5分钟出思路，10分钟出代码
面试题是：
两个无序数组分别叫A和B，长度分别是m和n，求中位数，要求时间复杂度O(m+n)，空间复杂度O(1) 。

10月15日，网新恒天笔试题
1.不要使用库函数，写出void *memcpy(void *dst, const void *src, size_t count)，其中dst是目标地址，src是源地址。
点评：下面是nwpulei写的代码：
void* memcpy(void *dst, const void *src, size_t count)   
{   
    assert(dst != NULL);   
    assert(src != NULL);   
    unsigned char *pdst = (unsigned char *)dst;   
    const unsigned char *psrc = (const unsigned char *)src;   
   
    assert(!(psrc<=pdst && pdst<psrc+count));   
    assert(!(pdst<=psrc && psrc<pdst+count));   
   
    while(count--)   
    {   
        *pdst = *psrc;   
        pdst++;   
        psrc++;   
    }   
    return dst;   
}  
链接：http://blog.csdn.net/nwpulei/article/details/8090136。
2.给定一个字符串，统计一下哪个字符出现次数最大。
3.我们不知道Object类型的变量里面会出现什么内容，请写个函数把Object类型转换为int类型。

10月15日，Google 2013 校招全套笔试题：










1.写一个函数，输出前N个素数，函数原型：void print_prime(int N); 不需要考虑整数的溢出问题，也不需要使用大数处理算法。
2.长度为N的数组乱序存放着0带N-1.现在只能进行0与其他数的swap操作，请设计并实现排序，必须通过交换实现排序。
3.给定一个源串和目标串，能够对源串进行如下操作：
   1.在给定位置上插入一个字符
   2.替换任意字符
   3.删除任意字符
写一个程序，返回最小操作数，使得对源串进行这些操作后等于目标串，源串和目标串的长度都小于2000。
点评：
1、此题反复出现，如上文第38题第4小题9月26日百度一二面试题，10月9日腾讯面试题第1小题，及上面第69题10月13日百度2013校招北京站笔试题第二大道题第3小题，同时，还可以看下这个链接：http://www.51nod.com/question/index.html#!questionId=662。
//动态规划：  
  
//f[i,j]表示s[0...i]与t[0...j]的最小编辑距离。  
f[i,j] = min { f[i-1,j]+1,  f[i,j-1]+1,  f[i-1,j-1]+(s==t[j]?0:1) }  
  
//分别表示：添加1个，删除1个，替换1个（相同就不用替换）。  

2、补充：上述问题类似于编程之美上的下述一题「以下内容摘自编程之美第3.3节」：
许多程序会大量使用字符串。对于不同的字符串，我们希望能够有办法判断其相似程度。我们定义了一套操作方法来把两个不相同的字符串变得相同，具体的操作方法为：
1. 修改一个字符（如把“a”替换为“b”）；
2. 增加一个字符（如把“abdd ”变为“aebdd ”）；
3. 删除一个字符（如把“travelling”变为“traveling”）。
比如，对于“abcdefg”和“abcdef ”两个字符串来说，我们认为可以通过增加/减少一个“g”的方式来达到目的。上面的两种方案，都仅需要一次操作。把这个操作所需要的次数定义为两个字符串的距离，而相似度等于“距离+1”的倒数。也就是说，“abcdefg”和“abcdef”的距离为1，相似度为1 / 2 = 0.5。
给定任意两个字符串，你是否能写出一个算法来计算出它们的相似度呢？




这样，很快就可以完成一个递归程序，如下所示：
Int CalculateStringDistance(string strA, int pABegin, int pAEnd,  
   string strB, int pBBegin, int pBEnd)   
{  
     if(pABegin > pAEnd)  
     {  
          if(pBBegin > pBEnd)  
               return 0;   
          else  
   
               return pBEnd – pBBegin + 1;  
     }  
  
     if(pBBegin > pBEnd)  
     {  
          if(pABegin > pAEnd)  
               return 0;  
          else  
               return pAEnd – pABegin + 1;  
     }  
  
     if(strA[pABegin] == strB[pBBegin])  
     {  
          return CalculateStringDistance(strA, pABegin + 1, pAEnd,  
            strB, pBBegin + 1, pBEnd);  
     }  
     else  
     {  
          int t1 = CalculateStringDistance(strA, pABegin, pAEnd, strB,   
            pBBegin + 1, pBEnd);  
          int t2 = CalculateStringDistance(strA, pABegin + 1, pAEnd,   
            strB,pBBegin, pBEnd);  
          int t3 = CalculateStringDistance(strA, pABegin + 1, pAEnd,  
            strB,pBBegin + 1, pBEnd);  
          return minValue(t1,t2,t3) + 1;  
     }  
}  

上面的递归程序，有什么地方需要改进呢？在递归的过程中，有些数据被重复计算了。比如，如果开始我们调用CalculateStringDistance(strA,1, 2, strB, 1, 2)，下图是部分展开的递归调用。




可以看到，圈中的两个子问题被重复计算了。为了避免这种不必要的重复计算，可以把子问题计算后的解存储起来。如何修改递归程序呢？还是DP！请看此链接：http://www.cnblogs.com/yujunyong/articles/2004724.html。

3、此外，关于这个“编辑距离”问题的应用：搜索引擎关键字查询中拼写错误的提示，可以看下这篇文章：http://www.ruanyifeng.com/blog/2012/10/spelling_corrector.html。「关于什么是“编辑距离”：一个快速、高效的Levenshtein算法实现，这个是计算两个字符串的算法，Levenshtein距离又称为“编辑距离”，是指两个字符串之间，由一个转换成另一个所需的最少编辑操作次数。当然，次数越小越相似。这里有一个BT树的数据结构，挺有意思的：http://blog.notdot.net/2007/4/Da ... hms-Part-1-BK-Trees」
最后，Lucene中也有这个算法的实现（我想，一般的搜索引擎一般都应该会有此项拼写错误检查功能的实现）：http://www.bjwilly.com/archives/395.html。
4、扩展：面试官还可以继续问下去：那么，请问，如何设计一个比较两篇文章相似性的算法？（这个问题的讨论可以看看这里：http://t.cn/zl82CAH）
BTW，群友braveheart89也整理了这套笔试题：http://blog.csdn.net/braveheart89/article/details/8074657。


10月16日，UC的笔试题目：
1、有个长度为2n的数组{a1,a2,a3,...,an,b1,b2,b3,...,bn}，希望排序后{a1,b1,a2,b2,....,an,bn}，要求时间复杂度o(n),空间复杂度0(1)。
点评：@绿色夹克衫：完美洗牌问题「关于洗牌算法：http://blog.csdn.net/gogdizzy/article/details/4917488」，解决这个问题的关键在于如何解决置换群中的环。方法是微软员工那篇论文中写的：http://user.qzone.qq.com/4143533 ... resh&pos=1243343118，大概意思是，用3的幂来弄：

@方程：
int index = arr.length / 2;  
int temp = arr[index];  
while(index != 1){  
    int tempIndex = (index + (index % 2) * (arr.length - 1)) / 2;  
    arr[index] = arr[tempIndex];  
    index = tempIndex;  
}  
arr[1] = temp;  

链接：1，http://www.51nod.com/question/index.html#!questionId=278；2、这里也有一参考答案：http://blog.csdn.net/yuan8080/article/details/5705567。

10月17日，创新工场电话面试：
1，如何删除一个搜索二叉树的结点；
2，如何找到一个数组中的两个数，他们的和为0；
3，如何判断两条二维平面上的线段是否相交。
网易2013 校招笔试题：


10月19日，百度研发三面题：
百度地图里的路线查询：给定两个站点，如果没有直达的路线，如何找到换乘次数最少的路线？
点评：蚂蚁算法？还是广搜，或A*算法？
10月20日，baidu广州站笔试算法题：
1. 有一箱苹果，3个一包还剩2个，5个一包还剩3个，7个一包还剩2个，求N个满足以上条件的苹果个数。
2. 用递归算法写一个函数，求字符串最长连续字符的长度，比如aaaabbcc的长度为4，aabb的长度为2，ab的长度为1。
3. 假设一个大小为100亿个数据的数组，该数组是从小到大排好序的，现在该数组分成若干段，每个段的数据长度小于20「也就是说：题目并没有说每段数据的size 相同，只是说每个段的 size < 20 而已」，然后将每段的数据进行乱序（即：段内数据乱序），形成一个新数组。请写一个算法，将所有数据从小到大进行排序，并说明时间复杂度。
点评：
思路一、如@四万万网友所说：维护一个20个元素大小的小根堆，然后排序，每次pop取出小根堆上最小的一个元素（log20），然后继续遍历原始数组后续的(N-20)个元素，总共pop (N-20)次20个元素小根堆的log20的调整操作。
思路二@飘零虾、如果原数组是a[]，那么a[i+20]>=a恒成立（因为每段乱序区间都是小于20的，那么向后取20，必然是更大的区间的元素）。
第一个数组：取第0、20、40、60、80...
第二个数组：取第1、21、41、61、81...
...
第20个数组：取第19、39、59、79...     （上述每个数组100亿/20 个元素）
共计20个数组，每个数组100亿/20 个元素「注：这5亿个元素已经有序，不需要再排序」，且这20个数组都是有序的，然后对这20个数组进行归并，每次归并20个元素。时间复杂度跟上述思路一一样，也是N*logK（N=100亿，K=20）。
此外，读者@木叶漂舟直接按每组20个排序,将排好的20个与前20个调整拼接,调整两端接头处的元素,写了个简单地demo： http://t.cn/zlELAzs。不过，复杂度有点高，目前来说中规中矩的思路还是如上文中@四万万网友 所说思路一「@张玮-marihees按照思路一：http://weibo.com/1580904460/z1v5jxJ9P，写了一份代码：http://codepad.org/T5jIUFPG，欢迎查看」。

10月21日，完美笔试算法题
1. 请设计一个算法，当给出在2D平面中某个三角形ABC的顶点坐标时能输出位于该三角形内的一个随机点(需要满足三角形内均匀随机)，无需写出实现，只要能清楚地描述算法即可。
2. 请自己用双向链表实现一个队列，队列里节点内存的值为int，要求实现入队，出队和查找指定节点的三个功能。
3. 实现一个无符号任意大整数的类，实现两个无符号超大整数的乘法。


10月22日，CSR掌微电子笔试题：
5.给定两个字符串s1和s2，要求判定s2是否能够被通过s1做循环移位（rotate）得到字符串包含。例如，S1=AABCD和s2=CDAA，返回true；给定s1=ABCD和s2=ACBD，返回false。用伪代码或流程图叙述解法。
点评：老题，类似：http://blog.csdn.net/v_JULY_v/article/details/6322882。其余题目见：http://blog.sina.com.cn/s/blog_3eb9f72801016llt.html。


10月23日，去哪儿网笔试：
1.将IPV4转换成整数
2.定义一个栈的数据结构，实现min函数，要求push,pop,min时间复杂度是0(1);
点评：这是2010年整理的微软100题的第2题，http://blog.csdn.net/v_JULY_v/article/details/6057286，答案见此文第2题：http://blog.csdn.net/v_JULY_v/article/details/6126406。
3.数组a[n]里存有1到n的所有树，除了一个数removed，找出这个missing的树。
4.找出字符串中的最长子串，要求子串不含重复字符，并分析时间复杂度。

10月28日，微软三面题
找一个点集中与给定点距离最近的点，同时，给定的二维点集都是固定的，查询可能有很多次，时间复杂度O(n)无法接受，请设计数据结构和相应的算法。
类似于@陈利人：附近地点搜索，就是搜索用户附近有哪些地点。随着GPS和带有GPS功能的移动设备的普及，附近地点搜索也变得炙手可热。在庞大的地理数据库中搜索地点，索引是很重要的。但是，我们的需求是搜索附近地点，例如，坐标(39.91, 116.37)附近500米内有什么餐馆，那么让你来设计，该怎么做？
点评：R树「从B树、B+树、B*树谈到R 树」还是KD树「从K近邻算法、距离度量谈到KD树、SIFT+BBF算法」？


11月10日，百度笔试题：
1、20个排序好的数组，每个数组500个数，按照降序排序好的，让找出500个最大的数。
2、一在线推送服务，同时为10万个用户提供服务，对于每个用户服务从10万首歌的曲库中为他们随机选择一首，同一用户不能推送重复的，设计方案，内存尽可能小，写出数据结构与算法。

谢谢楼主分享。