最近几个公司的笔试题

(1)RGB排序，一个字符串，里面只有三种字符R G B，所有的R都在G的前面，所有的G都在B的前面。将给定字符串按照此规律排序。要求不允许用辅助空间，复杂度控制在O(N)。遍历一遍就排好序。

#include "stdio.h"
#include "string.h"
#include 
#include 
using namespace std;
#define MAX 1024
int cmp(char c,char d)
{
int ret=0;

if(c=='B')
{
(d=='B')?ret=0:ret=1;
}
else if(c=='G')
{
d=='R'?ret=1:(d=='G')?ret=0:ret=-1 ;
}
else if(c=='R')
{
d=='R'?ret=0:ret=-1;
}
return ret;
}
int Partion(char *str,int s,int e)
{
int i=s-1;
int j;
for(j=s;j{
if(cmp(str[j],str[e])<0)
{
swap(str[i+1],str[j]);
i+=1;
}
}
swap(str[i+1],str[e]);
return i+1;
}
int quickSort(char *str,int s,int e)
{
int p=0;
if(s{
p = Partion(str,s,e);

}
return p;
}


int main()
{
char str[MAX];
int i=0;
int len =0;
int p;
scanf("%s",str);
len = strlen(str);
for(i=0;i{
if(str[i]=='G')
break;
}
swap(str[i],str[len-1]);
/*至于判断是否有G或者B这里省去了，直接考虑包含RGB的情况*/
p = quickSort(str,0,len-1);
for(i=p+1;i{
if(str[i]=='B')
break;
}
swap(str[i],str[len-1]);
p = quickSort(str,p+1,len-1);
cout<return 0;
}

(2)句子翻转

i am superman ---> superman am i

答案：这个简单 做了很多遍了，amazon笔试题里面写过，先每个单词转，后整个转

(1)判断两个Query是否相同“北京欢迎你”和“你欢迎北京”

答案：搜索引擎会对其进行分词，一般为 北京/欢迎/你  你/欢迎/北京

           只有判断句子是否相同，这个不太清楚

(2)最长前缀子串问题

a="abdcdef"   b="dex"   则最长子串是de

 答案：这种情况下对a建立后缀数组，然后查找b的最长前缀匹配

(3)某数据库应用，大量的插入和查询，查询速度只有10次/秒，请问：问题可能在哪里？

答案：应该是索引没有，或是索引建的不好

(4)中国到香港搭了一个10G的私有光线，单进程传输速度只有1,2M，请问：问题可能出在哪里？

答案：（待研究）应该是服务器 到客户端 这里的流量不够吧。

(5)有个Sequence，形如：S[]={a,b,...z,aa,ab,...az,ba,bb,...bz,...aaa,aab,...aaz,...}

给定一个字符串，查找在不在Sequence里，位置是多少？

答案：也就是一个26进制的处理吧，二分查找吧