今天早上的面试题9道，比较难，向牛人请教，国内的一牛公司，坐落在北京北四环某大厦：
今天早上的面试题9道，比较难，向牛人请教，国内的一牛公司，坐落在北京北四环某大厦：
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语言），空间和时间复杂度，
问题点数：100、回复次数：18Top
1 楼yuyes（无业游民）回复于 2006-03-02 23:50:05 得分 0
第一题见过，呵呵
markTop
2 楼jefson（jefson）回复于 2006-03-02 23:53:08 得分 0
还请牛人给出答案，多谢Top
3 楼ox_thedarkness（）回复于 2006-03-03 00:19:27 得分 0
强... 不过楼主咋发了两贴？Top
4 楼llf_hust（）回复于 2006-03-03 00:20:29 得分 0
3、用递归算法判断数组a[N]是否为一个递增数组。
#include "stdio.h"
#include "iostream.h"
int Fun(int a[],int n)
{
if( n == 1 )
return 1;
else if( a[n-1] > a[n-2] )
{
Fun(a,--n);
}
else
return 0;
}
int main()
{
int a[3];
int i;
for( i = 0; i < 3; i ++)
scanf("%d", &a[i]);
int bRetval;
bRetval = Fun(a,3);
cout<<bRetval<<endl;
}Top
5 楼cunsh（村少）回复于 2006-03-03 00:23:49 得分 0
markTop
6 楼ox_thedarkness（）回复于 2006-03-03 01:21:27 得分 0
建议楼主趁没人回帖删掉另一个重复楼返分，一旦有人回帖就不能删了。Top
7 楼iceprince83（iceprince83）回复于 2006-03-03 02:10:44 得分 0
1。 见归并排序的算法
2。使用回溯法
NextColor(j) //进入此过程潜，X[1]....X[j-1]已经确定并且满足约束条件，本函数给X[j]赋值，如果赋值成功则返回所赋的值，如果不成功，返回0
global integer m,n,X[1,n],W[1:n,1:n];
integer j,k;
loop
X[j]=(x[j]+1)mod(m+1);
ifX[j]=0 then return endif;
for i from 1 to j-1 do
ifW[i,j]=1&&X[i]=X[j] then exit endif
endfor
if i=j then return endif
endloop
end NextColor
GraphColor(k)
global integer m,n,X[1:n],W[1:n,1:n];
loop
NextColor(k);
if X[k]=0 then exit endif
if k=n then print(x);
else GraphColor(k+1);//递归
endif
endloop
end GraphColor
Top
8 楼NC（比尔.盖饭）回复于 2006-03-03 02:30:43 得分 0
我只会第五个
#include <signal.h>
void main()
{
pid_t pid;
signal ( SIGCHILD , SIG_IGN ) ; //加这一句就不会用僵尸进程了
while ( 1 )
{
pid = fork ();
if ( pid == 0) //子进程
{
//这里爱干嘛就干嘛
}
else if ( pid > 0 )
continue;
else printf ( "fork error\n");
}Top
9 楼noOnlyCode（不错，偶就是传说中高数上下册都考80多分的牛逼人物！）回复于 2006-03-03 04:13:49 得分 0
1、线形表a、b为两个有序升序的线形表，编写一程序，使两个有序线形表合并成一个有序升序线形表
#include<iostream>
using namespace std;
void main()
{
const int m=10;
const int n=20;
int a[m],b[m],c[n];
int i,j,k;
for(i=0;i<m;i++)
{
a[i]=2*i+1;
b[i]=4*i;
//a、b为两个有序升序的线形表
}
i=j=k=0;
while(k<n)
{
if(a[i]<b[j])
c[k++]=a[i++];
else
c[k++]=b[j++];
//合并成一个有序升序线形表
}
}Top
10 楼PPower（月亮光光，照地堂）回复于 2006-03-03 10:32:04 得分 0
4、编写算法，从10亿个浮点数当中，选出其中最大的10000个。
用分組計算合並的方法。下面是C++模板代碼
template <typename T >
class Mycount
{
//取得可分配內存.
size_t GetRam() ;
public :
int MaxCount ; //結果數 = 10000
int_64 SizeOfCount ; //計算規模 = 1000000000 (10亿)
int GroupCount ; //分組數
int GroupResultCount ; //每一組要計算的結果數。
typedef int(*TGetDataToVector)(std::vector<T>&Data,int GroupNo,int Count);
private :
std::vector<T> ResultData; //最後計算結果
//計算分組數,確定每組計算的量。讓分組計算的結果不會超出內存及保障數據不溢出,
int GetDArrayCount(int &GroupResultCount ) ;
//取來源數據, n為第幾組數據
void GetSourceData(std::vector<T> &Source,size_t n, TGetDataToVector );
//分組計算結果，ResultCount為該組要得到多少個符合要求的數
void CountGroup(std::vector<T> &Data , std::vector<T> &Result ,int ResultCount);
//計算最終結果。
void CountResult(std::vector< std::vector<T> > &GroupData,
std::vector<T> &Result ,
int ResultCount );
public :
//整個計算過程,
std::vector<T> &Count(int resultCount ,int_64 SizeOfCount,TGetDataToVector GetData)
{
MaxCount = resultCount ;
SizeOfCount =SizeCount ;
std::vector<T> SourceData; //每一組的計算來源
std::vector< std::vector<T> > GroupData; //每一組的臨時計算結果。
DArrayCount = GetDArrayCount(GroupResultCount);
//分配內存
GroupData.resize(DArrayCount );
for(int i = 0 ; i < DArrayCount ; ++i )
{
GetSourceData(SourceData, i, GetData );
CountGroup(SourceData,GroupData[i],GroupResultCount );
}
CountResult(GroupData,ResultData,MaxCount );
return ResultData ;
}
};
上面是分組計算的過程分解，具體算法沒寫出。
Top
11 楼insanehh（有一个美麗的小豆豆）回复于 2006-03-03 10:39:49 得分 0
強Top
12 楼waxic（waxic）回复于 2006-03-03 10:58:31 得分 0
厉害啊Top
13 楼PPower（月亮光光，照地堂）回复于 2006-03-03 11:04:57 得分 0
4.国内的一些帖吧，如baidu,有几十万个主题，假设每一个主题都有上亿的跟帖子，怎么样设计这个系统速度最好，请描述思想，写出算发（c语言），空间和时间复杂度，
對韙目的理解：對數據放在內存中的緩存做優化，如果數據要固化，那要選擇一個數據庫系統。把題目理解為，只做內存模型如何做才最優化,即如何在給定的空間內做好數據緩存。
一個貼子的組成：ID，主題，多個關鍵字，內容,父貼子。題目只要求處理 主題，與跟帖的快速查找。也就是一個父子系統，對於這裡，可理解為多層的系統也可以理解為只有兩層的系統，因為這兩種論壇在國內大量並存著。要想速度最好，當然是兩層的比多層的速度快了。題目也就演變成了：對於超大數據量的兩層的父子關系如何在內存中表示，查找才最快？這樣的設計其空间和时间复杂度是多少？
所有的超大數據量計算都避免不了分組合併的計算方法。目前並行與分布式計算是最快的。基於這是一個考試題，再把題目理解為在單CPU的PC系統上如何做？但對於不同的數據量很明顯應該采用不同的算法從而有不同的複雜度。几十万个主题，每一主题有上亿的跟帖這樣的規模明顯超出了PC的64G內存的容量。這時其時查找效率就關鍵就是：對於這樣的數據量應該如何分桶(分組)計算才最優 ？
這是我對這一題目的理解。這樣的題目真是不清不楚。
Top
14 楼ycy589（ycy589）回复于 2006-03-03 11:41:49 得分 0
学习Top
15 楼noOnlyCode（不错，偶就是传说中高数上下册都考80多分的牛逼人物！）回复于 2006-03-03 19:03:56 得分 0
1、线形表a、b为两个有序升序的线形表，编写一程序，使两个有序线形表合并成一个有序升序线形表
#include<iostream>
using namespace std;
void main()
{
const int m=10;
const int n=20;
int a[m],b[m],c[n];
int i,j,k;
for(i=0;i<m;i++)
{
a[i]=2*i+1;
b[i]=4*i;
//a、b为两个有序升序的线形表
}
i=j=k=0;
while(k<n)
{
if(a[i]<b[j])
c[k++]=a[i++];
else
c[k++]=b[j++];
//合并成一个有序升序线形表
}
}
----------------------------
修改一下
1、线形表a、b为两个有序升序的线形表，编写一程序，使两个有序线形表合并成一个有序升序线形表
#include<iostream>
using namespace std;
void main()
{
const int m=10;
const int n=20;
int a[m],b[m],c[n];
int i,j,k;
for(i=0;i<m;i++)
{
a[i]=2*i+1;
b[i]=4*i;
//a、b为两个有序升序的线形表
}
i=j=k=0;
while(i<m && j<m)//判别条件错误
{
if(a[i]<b[j])
c[k++]=a[i++];
else
c[k++]=b[j++];
//合并成一个有序升序线形表
}
//应该添加以下两行
while(i<m) c[k++]=a[i++];
while(j<m) c[k++]=b[j++];
}
Top
16 楼manplus（魅力加加）回复于 2006-03-14 15:10:27 得分 0
mark个Top
17 楼ra_zy（）回复于 2006-03-14 15:49:30 得分 0
markTop
18 楼skywoody（）回复于 2006-03-14 16:01:57 得分 0
第三题
先hash之
然后排出一个有10个元素的heap
（每次和heap中最小的那个比较，如果比它大，则放入并整理heap，扔掉heap中最小的）
复杂度：O（N）Top
