linux c/c++ 面试题目整理(五)

1、怎么避免死锁？

1) 有序资源分配法，就是大家申请资源时都按照相同的顺序来；

2) 使用银行家算法，进程首次申请资源时测试该进程对资源的最大需求量，若系统现有资源可以满足，则按照当前申请量分配，否则推迟分配。当进程在执行中继续申请资源时，先测试该进程，本次申请的资源数是否超过该资源所剩总量，满足则分配，否则推迟分配。

2、实现斐波列算法

斐波列函数：

1. int fibo(int n)
2. {
3. if (n <= 2)
4. return 1;
5. else
6. return fibo(n-1)+fibo(n-2);
7. }

数组法：

根据n来new一个n大小的数组，知道数组第一个数为1，第二个数也为1，再根据循环求后面的数。

3、写程序将I love English转换为English love I

算法：先将整个句子反转，再对每个单词反转

异或：^ 值相同为0，不同为1.

1. #include <iostreaaam>
2. #include <string>
3. using namespace std;
4. void inverseString(char* p, char* q)
5. {
6. while(q-p >=1)
7. {
8. *p = *p ^ *q;
9. *q = *p ^ *q;
10. *p = *p ^ *q;
11. p++;
12. q--;
13. }
14. }
15. int main()
16. {
17. char str[] = “I come from tianjian”;
18. int iStrlen = strlen(str);
19. inverseString(str, str+iStrlen-1);
20. char* p = str;
21. char* q = str;
22. while(*p != ‘\0’)
23. {
24. if (*p == ‘ ‘)
25. {
26. inverseString(q, p-1);
27. q = p+1;
28. }
29. p++;
30. }
31. printf(“%s\n”, str);
32. return 0;
33. }

4、c++中如何捕捉异常，是引用还是值？哪个成员函数用于从异常中获取错误信息？

直接捕捉的值，捕捉用的成员函数是catch。

5、std::string::find()的返回类型是什么？如果没有找到该函数返回值是什么？

返回类型是size_type，没找到返回值是string::npos。

6、std::vector的运算符[]和at()有什么区别？

at()返回元素数据，如果越界，跑出outofrange，[]返回容器中指定位置的一个引用。

7、什么是const成员函数？

const成员函数不允许修改类的数据成员，只有被声明为const的成员函数才能被一个const类对象调用。

8、请使用fabs和DBL_EPSILON写一个简单函数比较double dVal和0.45是否相等，相等返回true，不等返回false；

1. bool CheckDblEq(double dVal)
2. {
3. if (fabs(dVal-0,45) < DBL_EPSILON)
4. return true;
5. else
6. return false;
7. }

9、多个集合合并成没有交集的集合

给定一个字符串的集合，格式如：{aaabbbccc}，{bbbddd}，{eeefff}，{ggg}，{dddhhh}要求将其中交集不为空的集合合并，要求合并完成后的集合之间无交集，例如上例应输出{aaabbbcccdddhhh}，{eeefff}，{ggg}。

　　（1）请描述你解决这个问题的思路；

　　（2）请给出主要的处理流程，算法，以及算法的复杂度

　　（3）请描述可能的改进。

回答：

　　集合使用hash_set来表示，这样合并时间复杂度比较低。

　　1)给每个集合编号为0，1，2，3...

　　2)创建一个hashmap，key为字符串，value为一个链表，链表节点为字符串所在集合的编号。遍历所有的集合，将字符串和对应的集合编号插入到hashmap中去。

　　3)创建一个长度等于集合个数的int数组，表示集合间的合并关系。例如，下标为5的元素值为3，表示将下标为5的集合合并到下标为3的集合中去。开始时将所有值都初始化为-1，表示集合间没有互相合并。在集合合并的过程中，我们将所有的字符串都合并到编号较小的集合中去。

　 遍历第二步中生成的hash_map，对于每个value中的链表，首先找到最小的集合编号（有些集合已经被合并过，需要顺着合并关系数组找到合并后的集合编号），然后将链表中所有编号的集合都合并到编号最小的集合中（通过更改合并关系数组）。

　　4)现在合并关系数组中值为-1的集合即为最终的集合，它的元素来源于所有直接或间接指向它的集合。

　　算法的复杂度为O(n)，其中n为所有集合中的元素个数。

　　题目中的例子：

• 0:{aaabbbccc}
• 1:{bbbddd}
• 2:{eeefff}
• 3:{ggg}
• 4:{dddhhh} 　　生成的hash_map，和处理完每个值后的合并关系数组分别为 　　aaa:0。[-1,-1,-1,-1,-1] 　　bbb:0,1。[-1,0,-1,-1,-1] 　　ccc:0。[-1,0,-1,-1,-1] 　　ddd:1,4。[-1,0,-1,-1,0] 　　eee:2。[-1,0,-1,-1,0] 　　fff:2。[-1,0,-1,-1,0] 　　ggg:3。[-1,0,-1,-1,0] 　　hhh:4。[-1,0,-1,-1,0] 　　所以合并完后有三个集合，第0，1，4个集合合并到了一起。

10、求某数是否在40亿个整数中

给40亿个不重复的unsigned int的整数，没排过序的，然后再给几个数，如何快速判断这几个数是否在那40亿个数当中?

解法一：

unsigned int的取值范围是0到2^32-1。我们可以申请连续的2^32/8=512M的内存，用每一个bit对应一个unsigned int数字。首先将512M内存都初始化为0，然后每处理一个数字就将其对应的bit设置为1。当需要查询时，直接找到对应bit，看其值是0还是1即可。

怎么将对应的bit设为1？

也许通过结构体里面设置占用bit位为1，然后以该结构体去申请512M的空间，这样就相当于对数组操作了。

解法二：

将要判断的几个数放到一个hash中，然后遍历40亿个数，看是否有数包含在数组里面，若有则将该数删掉并记录下来。

这样占用内存就很小，但是如果要判断的数有变化，那么就要重新做hash，重新遍历40亿个数了。

思路：通过bit位来解决问题。