[转]搜索工程师的面试题（整理）

面试题(整理了一下)

题目：

算法题：
1、线形表a、b为两个有序升序的线形表，编写一程序，使两个有序线形表合并成一个有序升序线形表h；
2、运用四色定理，为N个局域举行配色，颜色为1、2、3、4四种，另有数组adj[][N]，如adj[i][j]=1则表示i区域与j区域相邻，数组color[N]，如color[i]=1,表示i区域的颜色为1号颜色。
3、用递归算法判断数组a[N]是否为一个递增数组。
4、编写算法，从10亿个浮点数当中，选出其中最大的10000个。
5、编写一unix程序，防止僵尸进程的出现.

搜索题：
同学的4道面试题，应聘的职位是搜索引擎工程师，后两道超级难，（希望大家多给一些算发）

1.给两个数组和他们的大小，还有一动态开辟的内存，求交集，把交集放到动态内存dongtai，并且返回交集个数
long jiaoji(long* a[],long b[],long* alength,long blength,long* dongtai[])

2.单连表的建立，把'a'--'z'26个字母插入到连表中，并且倒叙，还要打印！

3.可怕的题目终于来了：
象搜索的输入信息是一个字符串，统计300万输入信息中的最热门的前十条，我们每次输入的一个字符串为不超过255byte,内存使用只有1G,
请描述思想，写出算发（c语言），空间和时间复杂度

4.国内的一些帖吧，如baidu,有几十万个主题，假设每一个主题都有上亿的跟帖子，怎么样设计这个系统速度最好，请描述思想，写出算发（c语言），空间和时间复杂度，

回答：

========================================================

时间问题，我不发代码了，但这些问题书上都有，我给你说一下书名

1、线形表a、b为两个有序升序的线形表，编写一程序，使两个有序线形表合并成一个有序升序线形表h；
答案在请化大学严锐敏《数据结构第二版》第二章例题（有错字不好意思下同）

2、运用四色定理，为N个局域举行配色，颜色为1、2、3、4四种，另有数组adj[][N]，如adj[i][j]=1则表示i区域与j区域相邻，数组color[N]，如color[i]=1,表示i区域的颜色为1号颜色。
答案在中国水利出版社引进的一套国外《数据结构》教材上，单兰色的封皮（这套书包括操作系统（利用的minux），多媒体都有，估计有年岁了）

3、用递归算法判断数组a[N]是否为一个递增数组。
这个我没在教才上看到过但不难！！
一会贴代码

4、编写算法，从10亿个浮点数当中，选出其中最大的10000个。
用外部排序，在《数据结构》书上有！！！

5、编写一unix程序，防止僵尸进程的出现.
你说的僵尸进程是死锁吗？unix程序我不会

1.给两个数组和他们的大小，还有一动态开辟的内存，求交集，把交集放到动态内存dongtai，并且返回交集个数
long jiaoji(long* a[],long b[],long* alength,long blength,long* dongtai[])

这个我没在教才上看到过但不难！！
一会贴代码

2.单连表的建立，把'a'--'z'26个字母插入到连表中，并且倒叙，还要打印！
这个有点读不懂

3.可怕的题目终于来了
象搜索的输入信息是一个字符串，统计300万输入信息中的最热门的前十条，我们每次输入的一个字符串为不超过255byte,内存使用只有1G,
请描述思想，写出算发（c语言），空间和时间复杂度，
的确可怕，

4.国内的一些帖吧，如baidu,有几十万个主题，假设每一个主题都有上亿的跟帖子，怎么样设计这个系统速度最好，请描述思想，写出算发（c语言），空间和时间复杂度.
的确可怕，

========================================================

1、线形表a、b为两个有序升序的线形表，编写一程序，使两个有序线形表合并成一个有序升序

二路归并,不难
2、运用四色定理，为N个局域举行配色，颜色为1、2、3、4四种，另有数组adj[][N]，如adj[i][j]=1则表示i区域与j区域相邻，数组color[N]，如color[i]=1,表示i区域的颜色为1号颜色。
可转化位图论问题,将各个区域视为图上的点,相邻的点之间连上一条线,构成一个无向图,可得其邻接矩阵,根据邻接矩阵得色数.
3、用递归算法判断数组a[N]是否为一个递增数组。
楼上有正解

4、编写算法，从10亿个浮点数当中，选出其中最大的10000个。
用快排.可先从10亿个浮点数当中选出第10000大的数,设位M,在选M位基值,利用一趟快速排序,M
之后的数即为所求.

========================================================

1.给两个数组和他们的大小，还有一动态开辟的内存，求交集，把交集放到动态内存dongtai，并且返回交集个数
long jiaoji(long* a[],long b[],long* alength,long blength,long* dongtai[])
我想到的是蛮力法,时间复杂度位O(alength*blength);想必大家都知道了!

2.单连表的建立，把'a'--'z'26个字母插入到连表中，并且倒叙，还要打印！
在创建单链表的时候使之逆序,不难.

3.可怕的题目终于来了
象搜索的输入信息是一个字符串，统计300万输入信息中的最热门的前十条，我们每次输入的一个字符串为不超过255byte,内存使用只有1G,
请描述思想，写出算发（c语言），空间和时间复杂度，
255byte*300万<1G;也就是说可全部调进输入信息,利用PAGERANK算法实行频率统计,排序即可.
注:PAGERANK算法受google专利保护,看不到源代码.

1、线形表a、b为两个有序升序的线形表，编写一程序，使两个有序线形表合并成一个有序升序线形表h；
　　　已知：a[0]             b[0]
    一、a[n]
    二、b[n]
    三、插入排序&&二分排序
　　　#include "stdio.h"
#include "conio.h"

main()
{
    int i,j,k;
    int h[20];
    int a[10]={2,5,6,9,11,24,56,78,80,81};
    int b[10]={1,3,8,7,10,21,32,45,65,79};
    i=0;
    j=0;
    for(k=0;k<20;k++)
       if(a[i]>b[j])
             { h[k]=b[j];j++;}
          else
             { h[k]=a[i];i++;}

    for(i=0;i<20;i++)
        printf("%d ",h[i]);

    getch();

}

//单连表的建立，把'a'--'z'26个字母插入到连表中，并且倒叙，还要打印！

node *p = NULL;
node *q = NULL;

node *head = (node*)malloc(sizeof(node));
head->data = ' ';head->next=NULL;

node *first = (node*)malloc(sizeof(node));
first->data = 'a';first->next=NULL;head->next = first;
p = first;

int longth = 'z' - 'b';
int i=0;
while ( i<=longth )
{
node *temp = (node*)malloc(sizeof(node));
temp->data = 'b'+i;temp->next=NULL;q=temp;

head->next = temp; temp->next=p;p=q;
i++;
}

print(head);

========================================================

其实第四题这样的题目楼上没有人说对。
说是从10亿个数中选，实际上是说数很多。当然用外部排序是一个方法。
估计想考的是看你会不会二叉排序树。
10000个最大的数，就是10000个结点，这个内存是可以装下的。
但10亿个数就要从外部文件读出来了。每读入一个/组，就试图将之放入排序树中。等10亿个数全读完了，10000个结点按中序输出就行了。
我还在CSDN中见过类似的题目，答案也是二叉排序树，好像没人回答出来。

========================================================

象搜索的输入信息是一个字符串，统计300万输入信息中的最热门的前十条，我们每次输入的一个字符串为不超过255byte,内存使用只有1G,
请描述思想，写出算发（c语言），空间和时间复杂度，
这道题不是很难吧，用哈希的方法，将这些字符串哈希到不同的桶中，然后判断那个最多就行了

========================================================

关于第4题的我写的程序

#include
#include
#define MAX 1000000 //设置总数，我这里设置了一百万，也可以到一千万，一亿的话内存受不了，但是我的程序是串行读出数据的，所以也是可以处理更大的数据的，这里全部放在数据里是为了方便
#define TOP 1000

void quicksort(int array[ ],int left,int right)
{
if(left < right)
{
        int div = array[right];
int i = left;
int j = right-1;
int temp;
if(i==j){//只有两个数据，直接处理完了事
if(array[i] < div)
{
                array[i+1] = array[i] ;
                array[i] = div;
return;
}
}
else
{
while(i< j)
{
for( ; array[i] > div ; i++);
for( ; array[j] <= div ; j--);
if(i>=j)break;

temp = array[i];
array[i] = array[j];
array[j] = temp;

}

if(i!=right)
{
array[right] = array[i];
array[i] = div;
}
            quicksort(array,left,i-1);
quicksort(array,i+1,right);

}
}
}

int main()
{

int *Big = new int[MAX];
int * pSort = new int[TOP*4];//最好pSort[0]-pSort[Top-1]为结果
int i=0, j=TOP, k=0;
int h=0;
int all = 0;//Big数据计数器
srand(time(NULL));
for( i =0; i< MAX; i++)
{
//int jj= rand( )%77 + 1;
//int nn = rand( )%jj;
        Big[i] = rand( );
//cout< <<" ";
}

//可加入一些测试数据，看看大的能否排到前面
Big[0] = 100000;
Big[10] =300002;
Big[11] =200002;
Big[MAX-2] =200007;

int temp = Big[0];

for( all = 0; all < TOP; all++)
{
pSort[all] = Big[all];

}
quicksort(pSort,0,TOP-1);

//for( k =0;k //cout<
temp = pSort[TOP-1];
i = TOP-1;
j = TOP*2;

int sum = 0;

for( all= TOP; all {
    sum++;
if( Big[all]>temp )
{

sum++;

pSort[i++] = Big[all];

if(i==TOP*2) // i满TOP*2了
{
sum += 3;
i = 0;
j = TOP*2;
int temp2 = pSort[TOP*2-1];

for(int n=0; n< TOP*2-1; n++)
{
sum += 2;

if(pSort[n]> temp2)
{
if(i!=n)pSort[i] = pSort[n]; //大的放到pSort前部分
i++;
}
else
{
pSort[j++] = pSort[n]; //小的放到pSort后部分
}

}

if(i {
while(i
{
sum += 5;

pSort[i++] = temp2;
j--;
temp2 = pSort[j];
k = TOP*2;
h = TOP*2;
for( ;k
{
sum += 2;

if(pSort[k]>temp2)
{
pSort[i++] = pSort[k];
}
else
{
if(h!=k) pSort[h] = pSort[k];
h++;
}
}
j = h;
} //i>100了，选择排在100名后的分割数的操作完毕
}
sum++;
temp = temp2;
}
}
}

cout< < <<""< <<" "< <

///这里是全排序输出前TOP个，看看后面的结果是否和这个相同，但必须在MAX值比较小才可以执行，否则堆栈溢出/
/*
quicksort(Big,0,MAX-1);

for(k=0; k cout<
cout<
*/
//

//输出前TOP个
quicksort(pSort,0,i-1);
for( k =0;k
getchar( );
delete[ ] Big;
delete[ ] pSort;
return 0;
}

========================================================

算法的题不难啊。
我说个思路吧：
1、线形表a、b为两个有序升序的线形表，编写一程序，使两个有序线形表合并成一个有序升序线形表h；
    这个问题和下面那个第一题本质是一样的，我==一起说。

3、用递归算法判断数组a[N]是否为一个递增数组。
    这个就是每次拿最后一个和边界上的比下缩小规模，没难度。

4、编写算法，从10亿个浮点数当中，选出其中最大的10000个。
    外部排序

5、编写一unix程序，防止僵尸进程的出现.
    和算法没关系。我不会。

1.给两个数组和他们的大小，还有一动态开辟的内存，求交集，把交集放到动态内存dongtai，并且返回交集个数
    先排序O（N*LOG（N）），然后进行的步骤和第一题一样就对了。对这题是：取小头，比较，一样进内存，不一样小的扔O（N）内完成。加上排序O（N*LOG（N））搞定。
对上面那题不用讲应该都知道了，就是比完合并就行了。

2.单连表的建立，把'a'--'z'26个字母插入到连表中，并且倒叙，还要打印！
    链表是基本功，没什么好说的。

象搜索的输入信息是一个字符串，统计300万输入信息中的最热门的前十条，我们每次输入的一个字符串为不超过255byte,内存使用只有1G,
请描述思想，写出算发（c语言），空间和时间复杂度，
    我不知道。不过你算下就知道空间肯定是够的：全部装入都够（当然我们不会这么做）
4.国内的一些帖吧，如baidu,有几十万个主题，假设每一个主题都有上亿的跟帖子，怎么样设计这个系统速度最好，请描述思想，写出算发（c语言），空间和时间复杂度，
    我不知道。没学过着方面知识

========================================================

楼上几个朋友回排序的，我们一起来讨论一个问题。
结果要求的是10000个排好顺序的数而已，并没有要求你把10亿个数都拿出来排序。
所以更有效率的思路应当是
1、读入的头10000个数，直接创建二叉排序树。O(1)
2、对以后每个读入的数，比较是否比前10000个数中最小的大。(N次比较)如果小的话接着读下面的数。O(N)
3、如果大，查找二叉排序树，找到应当插入的位置。
4、删除当前最小的结点。
5、重复步骤2，直到10亿个数全都读完。
6、按照中序遍历输出当前二叉排序树中的所有10000个数字。
基本上算法的时间复杂度是O(N)次比较
算法的空间复杂度是10000(常数)

========================================================

我来回答后面两道“难题”吧：
1. 最近时有公司出这种从几百万词条中找出频率最大的前几条或者重复的条目的问题。
对于这种问题实际上并不需要太多所谓的搜索专业知识，想想数据库是怎么实现或者数据结构中关于词典索引的章节就不难知道，这些题目的解决办法不外乎，采用二种数据结构：
树（二叉树，Trie树和B树）和哈希表。对于300万词条来说，构建一个开地址哈希肯定用不了1G内存，如果还不放心，就构建一棵Trie树，如果还怕内存不够就构建B+树进行多级索引。至于复杂度分析，稍微回忆一下你的数据结构书吧。
2.类似贴吧的设计无非是个多级索引，查询与更新问题。
一级是个主题，10多万主题为了效率直接哈希就成，查询时候这些主题肯定是要全部载入内存的；
二级索引是上亿数据，查询或者更新时内存肯定不能放呀，自然就要用B＋树。稍微补充一下，为啥要用B+树就是为了解决内存中不能载入全部数据的时候用来分级载入数据，这样可以充分利用内存的换入换出来解决海量数据操作的问题。这和操作系统的文件系统设计以及数据库实现原理是相似的。

========================================================

4、编写算法，从10亿个浮点数当中，选出其中最大的10000个。

记得，排序算法的时间复杂度是O(N*log N), 这个是最快了
但是这个地方时间复杂度是 O(N*log n),
其中N 是 1G， n 是 10K 大概是: 30/13
除此之外，这个地方还不需要使用耗时巨大的外排序
像对于磁盘访问远远慢于内存访问的常规系统来说，效率不在一个数量级。

class CSearch
{
public:
    void Input(float f)
    {
        if ( m_vBuf.size() < 10000 || f > *m_vBuf.begin() )
        {
            m_vBuf.insert(f);       // log(2, n) 时间复杂度
            if ( m_vBuf.size() > 10000 )
                m_vBuf.erase(m_vBuf.begin());
        }
     }

    std::set m_vBuf;
};

剩下的，就是把所有数据过一遍这边就OK了。