本文主要是介绍【100题】第八十一 ~ 第九十题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
81）第1组百度面试题
1）题目：一个int数组，里面数据无任何限制，要求求出所有这样的数a[i]，其左边的数都小于等于它，右边的数都大于等于它。能否只用一个额外数组和少量其它空间实现。
分析： 题意说明如果对数组排序的话，a[i] 就应该排在 i 的位置 只有这样才能保证左边的数都小于等于它，右边的数都大于等于它
解答：新建另一数组b[ ]，将原数组拷贝到新数组，然后对新数组排序。所有a[i] = b[i] 的数为所求
2）题目：一个文件，内含一千万行字符串，每个字符串在1K以内，要求找出所有相反的串对，如abc 和cba。
2^20 =1048576 ~一百万
一千万 ~ 2^23
所以总共 约10G 左右数据 ，完全装入内存处理，不太可能。
方法一：暴力查找 时间复杂度 O(n^2)
方法二：Hash法
第一趟，依次读入文件中字符串（分批读入内存），然后Hash处理
第二趟，依次读入文件中字符串，先做逆序处理，再Hash处理，然后去Hash表中查找有无对应字串的Hash。
3）STL的set 用什么实现的？为什么不用hash？
红黑树（RB-Tree）平衡二叉搜索树，自动排序的效果不错
Hash浪费空间，随着元素的增长，Hash表可能要变化，或者搜索性能下降。
82）第2组百度面试题--》参考
1）给出两个集合A和B，其中集合A={name}，集合B={age、sex、scholarship、address、...}，
要求：
问题1、根据集合A 中的name 查询出集合B 中对应的属性信息；
问题2、根据集合B 中的属性信息（单个属性，如age<20 等），查询出集合A 中对应的name。
解答：
问题1、
方法一：数据库方法
问题1， select * from A,B where A.name = B.name;
问题2 ，select name from A,B where A.name =(select name from B where age<20 group by name);
点评：百度面试题，写两个SQL语句??这样可以？
方法二：直接采用STL 中的Map<key，value> 其中 key 记录A中的name，而value 记录集合B的属性向量信息。通过key直接查询B中对应属性的信息。
MultiMap<key,value> 允许key可以重复，感觉这里name应该不重复
方法三：(Java而不是C++ STL) 为了提高查询效率，就是给出name可以迅速查找出对应B中向量的信息，采用hashtable<key，value>
HashMap是在hashtable的基础上演变而来的，Hashtable是线程安全;HashMap是线程不安全的;HashMap允许多线程操作所以HashMap更快！
查询数据采用 get（key）
方法四：自定义映射关系，struct {set,vector} 这样做能提高查询效率么？
问题2、
方法一：暴力法，遍历B 判断age< 20 则去A中查寻对应 name （效率低）
方法二：遍历一遍A中name 存放Hash表中，然后 遍历B age <20 则取name 的Hash值 去Hash表中查找，有则输出。
2）给出一个文件，里面包含两个字段{url、size}，即url 为网址，size 为对应网址访问的次数
要求：
问题1、利用Linux Shell 命令或自己设计算法，查询出url 字符串中包含“baidu”子字符串对应的size字段值；
问题2、根据问题1 的查询结果，对其按照size 由大到小的排列。（说明：url数据量很大，100 亿级以上）
解答：
用不熟悉的awk 命令
1. shell: awk ‘/baidu/ { print $2 }’ FILE
2. shell: awk ‘/baidu/ {print $2}’ FILE | sort -nr >> Result_FILE //-r 颠倒指定顺序 -n 按算术值对数字字段排序
用熟悉的grep命令
1. grep "baidu" baidu.txt
2. grep "baidu" baidu.txt > baidu2.txt 然后 sort -rn baidu2.txt >>baidu3.txt
ls -l | sort -rn baidu2.txt //查看排序后的结果
用算法解决
1，KMP算法解决字符串匹配问题（next数组） 先查找所有匹配"baidu"的url
2，对1中结果 中的size 转化为 整形 然后排序 （希尔、快排、堆）
3）测试题：如何测试一部手机或者如何测试一台露天售货机（需要测试硬件部分和软件部分）
其实测试，只要把握三条最基本的原则：1、等价划分；2、边界值测试；3、经验评估查错（当然啦，经理还需要考虑效益、进度等经济因素）
然后遵照这些原则进行分析、思考测试用例、总结。
解答：
例如本次测试一部手机，先划分为硬件与软件测试两部分。
1）硬件测试如温度、按键、开机、抗摔、抗震、抗摸等等物理特性；
2）软件部分需要细划分为系统软件与应用软件两部分，因为系统软件和应用软件的功能和使用频度不一样，
因此需要考虑测试的轻重缓急，由重点软件（如电话薄）到次重点软件（如电子书）再到非重点软件（如游戏），由使用频繁到较频繁再到较少使用等频度划分，
如此依次划分进行计划、安排、进行测试。列举硬件、软件；系统软件、应用软件；百度软件和其它应用软件；以及在Android手机上详细测试百度手机输入法等测试过程。
核心思路：等价划分——》边界值测试——》凭经验重点测试经常或较易出bug的地方（如果大家想深入学习软件测试的核心思想和方法，推荐一本经典——大师级的Myers编写的《The Art of Software Testing》（软件测试的艺术）
83）第3组百度面试题
1）今年百度的一道题目
百度笔试：给定一个存放整数的数组，重新排列数组使得数组左边为奇数，右边为偶数。要求：空间复杂度O(1)，时间复杂度为O（n）。
思路：借鉴快速排序一次换分思想，从左边找偶数，右边找奇数，然后交换，直到遍历所有元素。
2）百度笔试题
用C语言实现函数void * memmove(void *dest, const void *src, size_t n)。memmove 函数的功能是拷贝src所指的内存内容前n 个字节到dest 所指的地址上。
分析：
由于可以把任何类型的指针赋给void类型的指针, 这个函数主要是实现各种数据类型的拷贝。
这里区别于strncpy(void *dest, const void *src, size_t n) ; 这个复制字符串的函数是遇到 ‘\0’则停止或者复制长度达到 n 。
区别于 memcpy（void *dest , const void *src, size_t n）; 对于src 和 dest 重叠情况 返回NULL
而memmove 实现的功能：是由src所指内存区域复制count个字节到dest所指内存区域。
说明：而src和dest所指内存区域可以重叠，但复制后dest内容会被更改。函数返回指向dest的指针。
使用：
char *str1="12345";
char *str2=(char *)malloc(sizeof(char)*strlen(str1));
memmove(str2,str1,strlen(str1));
memmove的处理措施：
（1）当源内存的首地址等于目标内存的首地址时，不进行任何拷贝
（2）当源内存的首地址大于目标内存的首地址时，实行正向拷贝
（3）当源内存的首地址小于目标内存的首地址时，实行反向拷贝
memcpy的实现
void* memcpy(void* dest, const void* src, size_t n)
{
char* d = (char*) dest;
const char* s = (const char*) src;
while(n-–)
*d++ = *s++;
return dest;
}
memcpy的实现
void* memmove(void* dest, const void* src, size_t n)
{
char* d = (char*) dest;
const char* s = (const char*) src;
if (s>d)
{
// start at beginning of s
while (n--)
*d++ = *s++;
}
else if (s<d)
{
// start at end of s
d = d+n-1;
s = s+n-1;
while (n--)
*d-- = *s--;
}
return dest;
示意图：
（1）内存低端 <-----s-----> <-----d-----> 内存高端 start at end of s
（2）内存低端 <-----s--<==>--d-----> 内存高端 start at end of s
（3）内存低端 <-----sd-----> 内存高端 do nothing
（4）内存低端 <-----d--<==>--s-----> 内存高端 start at beginning of s
（5）内存低端 <-----d-----> <-----s-----> 内存高端 start at beginning of s
84）第4组百度面试题
2010 年3 道百度面试题[相信，你懂其中的含金量]
1）a~z 包括大小写与0~9 组成的N 个数, 用最快的方式把其中重复的元素挑出来。
这里题意应该是N个字符，则采用Hash[256] 则可以。
一旦提到“最快的方式” 首先想到的是 Hash的方法 O(n) 的复杂度处理一趟就可以找出重复元素
void thesame(char *str) {
char dsc[256] = {0};
char *tmp;
for (tmp = str; *tmp; tmp++) {
if (dsc[*tmp] == 1) {
printf("%c is the same\n");
} else {
dsc[*tmp] = 1;
}
}
}
2）已知一随机发生器，产生0的概率是p，产生1 的概率是1-p，现在要你构造一个发生器，使得它构造0 和1的概率均为1/2；构造一个发生器，使得它构造1、2、3 的概率均为1/3；...，构造一个发生器，使得它构造1、2、3、...n 的概率均为1/n，要求复杂度最低。
分析：这道题的核心思想是，通过产生0和1的概率来组合成不同的数，代表1,2,3……n 每个数，其中产生代表每个数的概率相等。
解答：
方法一：最直观的方法，产生N位的二进制数，仅有一位为1 ，而其余位为0则符合构造数要求，否则丢弃重新选择（例如，0001 代表1， 0010 代表2，0100代表3）
这种方法显然十分低效，存在长时间选不出数的可能。
方法二：在方法一的基础上改进，既然找到了产生0 和 产生1 等概率的方法，则利用二进制表示法，可以表示出1-n中任意数
整数N 需要的位数M = log2^n+1 。 则每次产生M 位二进制数，其所代表的数即为所求。
3）有10个文件，每个文件1G，每个文件的每一行都存放的是用户的query，每个文件的query 都可能重复。要求按照query 的频度排序.
分析：首先应该求每个query 的频度，然后排序。最后把各部分排序好的文件合并到一起。
解答：典型的TOP K算法
方案1： 顺序读取10个文件，按照hash(query)%10的结果将query写入到另外10个文件（记为）中。这样新生成的文件每个的大小大约也1G（假设hash函数是随机的）。 找一台内存在2G左右的机器，依次对用hash_map(query, query_count)来统计每个query出现的次数。利用快速/堆/归并排序按照出现次数进行排序。将排序好的query和对应的query_cout输出到文件中。这样得到了10个排好序的文件（记为）。
对这10个文件进行归并排序（内排序与外排序相结合）。
方案2： 一般query的总量是有限的，只是重复的次数比较多而已，可能对于所有的query，一次性就可以加入到内存了。这样，我们就可以采用trie树/hash_map等直接来统计每个query出现的次数，然后按出现次数做快速/堆/归并排序就可以了。
方案3： 与方案1类似，但在做完hash，分成多个文件后，可以交给多个机器来处理，采用分布式的架构来处理（比如MapReduce），最后再进行合并。
hashmap<query,query_count> 允许query为null ，先处理一趟，记下query,query_count=0; 然后再处理一趟，记录query_count++
85）又见字符串的问题
1）给出一个函数来复制两个字符串A和B。字符串A 的后几个字节和字符串B 的前几个字节重叠。
分析：
记住，这种题目往往就是考你对边界的考虑情况。
上一次解答是按照：给定 str1="abcd"; str2="cdcsd";则 res="abcdcsd";
这次解答是：写一个void * memmove(void *des, void *src ,size_t n);
如果ｓｒｃｐｙ（Ｂ，Ａ）这里源字符串Ａ 的后几个字节与 目标字符串Ｂ的前几个字节重复，则从源字符串Ａ的最后一个字节开始复制
2）已知一个字符串，比如asderwsde,寻找其中的一个子字符串比如sde 的个数，如果没有返回0，有的话返回子字符串的个数。
#include <cstring>
#include <iostream>
using namespace std;
int count_of_substr(const char* str, const char * sub)
{
int count = 0;
const char * p = str;
int n = strlen(sub);
while ( *p !='\0')
{
if (strncmp(p, sub, n) == 0)
count ++;
p++;
}
return count;
}
int main()
{
char *str1="asderwsde";
char *str2="sde";
cout<< count_of_substr(str1,str2)<<endl;
}
86）怎样编写一个程序，把一个有序整数数组放到二叉树中？
题意：建立一个中序遍历是有序的二叉树
解答：采用递归，每次创建的节点都是 数组中间的元素 mid =length>>1 而当数组长度==0 时候，则返回NULL叶子
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
struct student {
int value;
struct student *lchild;
struct student *rchild;
};
void arraytotree(int *a, int len, struct student **p) {
if(len) {
*p = (struct student*)malloc(sizeof(struct student));
(*p)->value = a[len/2];
arraytotree(a, len/2, &((*p)->lchild));
arraytotree(a+len/2+1, len-len/2-1, &((*p)->rchild));
} else {
*p = NULL;
}
}
void display_tree(struct student *head) {
if(head->lchild)display_tree(head->lchild);
printf("%d\t", head->value);
if(head->rchild)display_tree(head->rchild);
}
int main() {
int a[] = {1,2,3,4,9,10,33,56,78,90};
struct student *tree;
arraytotree(a, sizeof(a)/sizeof(a[0]), &tree);
printf("After convert:\n");
display_tree(tree);
printf("\n");
return 0;
}
87）三道算法题
1）大整数数相乘的问题
这里就是用数组模拟两个大整数相乘。
#include <iostream>
using namespace std;
void multiply(int a[],int a_length,int b[],int b_length)
{
int length= a_length+b_length;
int *result=(int *)malloc(length*sizeof(int));
memset(result,0,length*sizeof(int));
int temp;//暂存两个数
int HF=0;//进位
int LF;//低位
int shift=0;
for(int i=b_length-1;i>=0;i--)//b[ ] 下面
{
HF=0; //一趟的 进位不能进入下一趟
for(int j=a_length-1;j>=0;j--)//a[ ] 上面
{
temp=b[i]*a[j]+HF;
LF=temp%10;//取低 位
result[length-shift-(a_length-j)]+=LF;//低位的数加上
HF=temp/10;//取高位
HF+=result[length-shift-(a_length-j)]/10; //相加产生的进位
result[length-shift-(a_length-j)]%=10; //最终值
}
shift++;
result[length-shift-a_length]=HF; //最后的进位
}
for(int i=0;i<length;i++)
{
if(result[0] == 0)
continue;
cout<<result[i];
}
cout<<endl;
}
int main()
{
int a[]={1,2,3,4};
int b[]={9,0,9};
int length= sizeof(a)+sizeof(b);
int *result=(int *)malloc( sizeof(int) * length );
multiply(a,sizeof(a)/sizeof(int),b,sizeof(b)/sizeof(int));
}
2）求最大连续递增数字串（如“ads3sl456789DF3456ld345AA”中的“456789”）
#include <iostream>
using namespace std;
int continumax(char *outputstr, char *intputstr)
{
int i, maxlen = 0;
char * maxstr = 0;
bool a=true;
while (a)
{
while (intputstr &&(*intputstr<'0' || *intputstr>'9')) //skip all non-digitcharacters
{
intputstr++;
if(*intputstr =='\0')
{
a=false;
break;
}
}
int count = 0;
char * tempstr = intputstr;
while (intputstr &&(*intputstr>='0' && *intputstr<='9')) //OK, these characters are digits
{
count++;
intputstr++;
if(*intputstr =='\0')
{
a=false;
break;
}
}
if (count > maxlen)
{
maxlen =count;
maxstr =tempstr;
}
}
for (i=0; i<maxlen;i++)
{
outputstr[i] = maxstr[i];
}
outputstr[i] = '\0';
cout<<"outputstr: "<<outputstr<<endl;
return maxlen;
}
int main()
{
char *intputstr="abcd12345ed125ss123456789";
char *outputstr=new char[100]; ;
cout<<"cout:"<<continumax(outputstr, intputstr)<<endl;
return 0;
}
3）实现strstr功能，即在父串中寻找子串首次出现的位置
const char * _strstr(const char *src, const char *needle)
{
const char *p1, *p2;
int length_src=strlen(src);
int length_needle=strlen(needle);
if(length_needle > length_src)
return NULL;
p1=src;
p2=needle;
while(*p1!='\0')
{
while(*p1==*p2)
{
p1++;
p2++;
if(*p2=='\0')//这里防止 到头时比较
return src;
}
if(*p2=='\0')
return src;
else
{
p1=src+1;
p2=needle;
}
src+=1;
}
return NULL;
}
改进后的
char *str_str(char *haystack, char *needle)
{
char *res=NULL;
int len1=strlen(haystack);
int len2=strlen(needle);
int i,j,n;
if(len2> len1)
return res;
n=len1-len2;
for(i=0;i <=n;i++)
{
for(j=0;j <len2;j++)
{
if(haystack[i+j] != needle[j])
break;
}
if(j==len2)
{
res=haystack+i;
break;
}
}
return res;
}
88）2005 年11 月金山笔试题。编码完成下面的处理函数。
函数将字符串中的字符'*'移到串的前部分，前面的非'*'字符后移，但不能改变非'*'字符的先后顺序，函数返回串中字符'*'的数量。
例如：原始串为：ab**cd**e*12，处理后为*****abcde12，函数并返回值为5。（要求使用尽量少的时间和辅助空间）
思路：char *p1 始终指向最后一个 ' * '，char *p2 查找p1 之前的第一个 非' * ' 然后交换，直到 p1之前没有 非' * '字符为止。由p1的位置 很容易求 字符' * '数量
解答：
int partitionStar(char a[],int length)
{
int i = length-1, j=length-1; // i for the cursor, j for the first non-* char
while (i >= 0)
{
if (a[i] !='*')
swap(a, i--, j--);
else
i--;
}
return j+1;
}
89）神州数码、华为、东软笔试题
1）2005 年11 月15 日华为软件研发笔试题。实现一单链表的逆转。
2）编码实现字符串转整型的函数（实现函数atoi的功能），据说是神州数码笔试题。
如将字符串”+123”123,”-0123”-123,“123CS45”123,“123.45CS”123,“CS123.45”0
int atoi(const char * a)
{
if (*a=='+')
return atoi(a+1);
else if (*a=='-')
return atoi(a+1) * (-1);
char *p = a;
int c = 0;
while (*p >='0'&& *p <='9')
{
c = c*10 + (*p -'0');
p++;
}
return c;
}
3）快速排序（东软喜欢考类似的算法填空题，又如堆排序的算法等）
4）删除字符串中的数字并压缩字符串。如字符串”abc123de4fg56”处理后变为”abcdefg”。注意空间和效率。
（下面的算法只需要一次遍历，不需要开辟新空间，时间复杂度为O(N)）
#include <iostream>
using namespace std;
char * partition(char *str)
{
int i = 0; //指向数字
int j = 0; //指向非数字
while (str[j]!='\0')
{
while(str[i] > '9'|| str[i] <'0')//非数字
i++;
j=i;
while(str[j] >'0'&& str[j] <'9')
j++;
for(int k=0;k<j-i;k++)
{
swap(str[i],str[j]);
i++;
j++;
}
}
str[i] = '\0';
return str;
}
int main()
{
char str[]="abc12454652sdjkhknnkn"; //注意这里是数组，而不能是字符串常量
cout<<partition(str);
}
5）求两个串中的第一个最长子串（神州数码以前试题）。如"abractyeyt","dgdsaeactyey"的最大子串为"actyey"。
方法一：最基本的方法：O(n^2)
#include <iostream>
using namespace std;
const int N = 1000;
char* FirstMaxSubString(const char *str1,char *str2)
{
int pos; //存放第一个最长子串的起始位置
int max = 0; //第一个最长子串的长度
int i,j;
for(i=0;str1[i];i++)
{
for(j=0;str2[j];j++)
{
for(int k=0;str1[i+k]==str2[j+k] && (str1[i+k] || str2[i+k]);k++)
if(k>max)
{
pos = j;
max = k+1;
}
}
}
char *result = new char[max+1];
for(i=0;i<max;i++)
result[i] = str2[pos++];
result[i] = '\0';
return result;
//或者直接用下面的语句返回，好处是不用申请空间
/*str2[pos+max] = '/0';
return (char *)(str2+pos);*/
}
int main()
{
char *str1 = "abractyeyt";
char *str2 = "dgdsaeactyey";
//固定测试例
/*
char *str1 = "abractyeyt";
char *str2 = "dgdsaeactyey";
*/
cout<<"FirstMaxSubString:"<<FirstMaxSubString(str1,str2)<<endl;
return 0;
} 方法二：动态规划 http://blog.csdn.net/tianshuai11/article/details/7897592
90）简单三道题
1）不开辟用于交换数据的临时空间，如何完成字符串的逆序(在技术一轮面试中，有些面试官会这样问)。
2）删除串中指定的字符（做此题时，千万不要开辟新空间，否则面试官可能认为你不适合做嵌入式开发）
3）判断单链表中是否存在环。
这篇关于【100题】第八十一 ~ 第九十题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
