百度面试题总结—03(操作系统)

查看原题

1.SSH

问题描述:linux/unix远程登陆都用到了ssh服务,当网络出现错误时服务会中断,linux/unix端的程序会停止。为什么会这样?说下ssh的原理,解释中断的原理。
首先解释一下SSH原理。这里有一篇文章,对SSH讲的很好,点击查看。下面我再对SSH做一个简单的介绍。简单地说,SSH就是一种网络协议,用于计算机之间加密登陆。

  • 最基本的用法:ssh -p 端口号 username@host,其中端口号默认为22;
  • 整个过程:(1)远程主机收到用户的登陆请求,把自己的公钥发给用户,(2)用户使用远程主机的公钥加密密码,将加密后的密码发送过来,(3)远程主机用自己的私钥解密密码,判断能否让远程用户登录。
  • 存在隐患:如果登陆请求被截获,冒充远程主机,将伪造的公钥发给用户,那么用户很难辨别真伪。
    下面解释一下为何网络出现错误时服务会中断,参考原文。网络出错,相当于程序的控制台关闭。
    中断的原理:所谓中断,是指CPU在正常运行程序时,由于程序预先安排或内外部事件,引起CPU中断正在运行的程序,而转到发生中断事件程序中。

2.进程与线程的区别

概念:

  • 进程:一个程序对一个数据集的动态执行的过程,是分配资源的基本单位;
  • 线程:一个进程内的基本调度单位;
  • 线程的划分尺度小于进程,一个进程可以包含一个或更多的线程。

执行过程:

  • 进程:拥有独立的内存单元,而多个线程共享内存,从而提高了应用程序的运行效率;
  • 线程:不能独立运行,必须依赖于线程中的共享资源;

百度面试题总结—02(语言知识)

查看原题

1.解释下面ptr不同含义

1
2
3
4
5
6
7
8
double* ptr = &value;
//ptr是一个指向double类型的指针,ptr的值可以改变,ptr所指向的value的值也可以改变
const double* ptr = &value
//ptr是一个指向const double类型的指针,ptr的值可以改变,ptr所指向的value的值不可以改变
double* const ptr=&value
//ptr是一个指向double类型的指针,ptr的值不可以改变,ptr所指向的value的值可以改变
const double* const ptr=&value
//ptr是一个指向const double类型的指针,ptr的值不可以改变,ptr所指向的value的值也不可以改变

2.去掉const属性

例: const double value = 0.0f; double* ptr = NULL;怎么才能让ptr指向value?
强制类型转换,去掉const属性,如

1
ptr = <const_cast double *>(&value)

3.动态链接库与静态链接库的区别

静态链接库是.lib格式的文件,一般在工程的设置界面加入工程中,程序编译时会把lib文件的代码加入你的程序中因此会增加代码大小,你的程序一运行lib代码强制被装入你程序的运行空间,不能手动移除lib代码。动态链接库是程序运行时动态装入内存的模块,格式*.dll,在程序运行时可以随意加载和移除,节省内存空间。在大型的软件项目中一般要实现很多功能,如果把所有单独的功能写成一个个lib文件的话,程序运行的时候要占用很大的内存空间,导致运行缓慢;但是如果将功能写成dll文件,就可以在用到该功能的时候调用功能对应的dll文件,不用这个功能时将dll文件移除内存,这样可以节省内存空间。

4.指针与引用的区别

相同点:都是地址的概念,指针指向一块内存,它的内容是所指内存的地址,引用是某块内存的别名。
不同点:

  • 指针是一个实体,而引用是一个别名;
  • 指针使用时需要加(*);
  • 引用只能在定义时被初始化一次,之后不可改变,指针可变;
  • 引用没有const,指针有const;
  • 引用不能为空,指针能为空;
  • sizeof引用得到的是所指的变量的大小,sizeof指针得到的是指针本身的大小;
  • 自增含义不同;
  • 内存分配上来看:程序为指针分配内存区域,不为引用分配内存区域。

5.c++对象模型与虚表

  • C++中对象模型:语言中直接支持”面向对象程序设计“的部分,对于各种支持的低层实现机制;
  • 在C++中有两种成员数据:static、nonstatic,三种成员函数:static、nonstatic和virtual;
  • 虚函数:虚函数就是C++语言中,那些被virtual关键字修饰的成员函数。虚函数的作用就是实现多态,多态是将接口与实现进行分离,通俗来讲,就是实现以共同的方法,但因个体差异而采用不同策略。

百度面试题总结—01(算法)

查看原题

1.用C语言实现一个revert函数,它的功能是将输入的字符串在原串上倒序后返回。

思路:重新定义一个字符串,反向取出原字符串的值

1
2
3
4
5
6
7
8
9
10
11
12
char *revert(char *str)
{

int lenght = strlen(str);
char *ret = new char(lenght);
int left = 0, right = lenght - 1;
for (int i = lenght - 1; i >= 0; i--)
{
ret[lenght - i - 1] = str[i];
}
ret[lenght] = '\0';
return ret;
}

2.用C语言实现函数void memmove(void dest, const void *src, size_t n),memmove函数的功能是拷贝src所指的内存内容前n个字节到dest所指的地址上。

思路:主要解决内存重叠的问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
void *memmove(void *dest, const void *src, size_t n)
{

if (NULL == dest || NULL == src)
{
cerr << "NULL pointers";
return NULL;
}
int step;
char *p, *q;
if ((char *)src == (char *)dest)
return dest;
else if ((char *)src > (char *)dest)
{
step = 1;
p = (char *)src;
q = (char *)dest;
}
else
{
step = -1;
p = (char *)src + n - 1;
q = (char *)dest + n - 1;
}
for (int i = 0; i != n; i++)
{
*q = *p;
p += step;
q += step;
}
return dest;
}

3.蚂蚁与木杆

描述:有一根27厘米的细木杆,在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置上各有一只蚂蚁。木杆很细,不能同时通过一只蚂蚁。开始时,蚂蚁的头朝左还是朝右是任意的,它们只会朝前走或调头,但不会后退。当任意两只蚂蚁碰头时,两只蚂蚁会同时调头朝反方向走。假设蚂蚁们每秒钟可以走一厘米的距离。编写程序,求所有蚂蚁都离开木杆的最小时间和最大时间。
思路:蚂蚁相遇掉头,可以看作蚂蚁还在继续往各自的前方走。

4.给定一个存放整数的数组,重新排列数组使得数组左边为奇数,右边为偶数。

思路:取左右两个指针,分别从头部和尾部遍历,交换不和谐元素。

5.在一维坐标轴上有n个区间段,求重合区间最长的两个区间段。

思路:根据每个区段左坐标排序,每次记录最大重合距离和最远有坐标。
备注:贪心问题,类似不同时间段任务安排。

6.现在有1千万个随机数,随机数的范围在1到1亿之间。现在要求写出一种算法,将1到1亿之间没有在随机数中的数求出来。

思路:利用位图,即开一个1亿位的bitset,内存为100m/8== 12.5m, 然后如果一个数有出现,对应的bitset上标记为1,最后统计bitset上为0的即可。

7.循环有序数组的二分查找。

对已排好序的数组A,一般来说可用二分查找可以很快找到。现有一特殊数组A[],它是循环递增的,如A[]={ 17 19 20 25 1 4 7 9},试在这样的数组中找一元素x,看看是否存在。
LeetCode原题,查看请点击LeetCode-num033

8.如何解决Hash冲突等问题

(1)哈希函数的构造方法:数字分析方法,平方取中法,分段叠加法,除留取余法,伪随机数法
(2)处理冲突的方法:开放定址法,再哈希法,链地址法,建立公共溢出区。

9.判断一个数的所有因数的个数是偶数还是奇数

开始每太理解,仔细看一下答案,才理解题意。答案是这样的,如果这个数是平方数,那么结果为奇数,否则为偶数。
那么顺着这个思路可以继续思考,如果这个数所有质因数都是偶数个,那么这个数就是平方数,结果为奇;否则只要有质因数个数是一个,结果就是偶。

10.

问题描述:写一个C的函数,输入整数N,输出整数M,M满足:M是2的n次方,且是不大于N中最大的2的n次方。例如,输入4,5,6,7,都是输出4。
思路:平均时间复杂度可以达到O(logN),遍历从一到给定数之间所有的2的倍数。找到最大不大于给定数的值。
但是这是最好的答案了吗?我觉得不是,可以寻找更好的办法。
优化:我们都知道位运算,2的次方数的二进制有个特点,就是首位为1,而其他所有的位都是0。那么从这个角度出发。那么我们只要得到最二进制中最高位的值就可以了。那么我们可以直接通过位运算求得输入数字的二进制最高位就可以了。
那么问题又来了,怎么获得最高位的值呢,可以不断移位,计数数位数,但这样做的其实和最开始的方法效率是一样的。
优化:其实再想一下的话,我们可以先获得除了二进制首位剩余位的值,然后与原数异或运算,就可以直接得到结果。时间复杂度降到O(1)。