面试经典题

找出字符串中第一个匹配项的下标

class Solution {
public:vector<int> getNextArray(string needle){int n = needle.size();if(n == 1){return {-1};}else if(n == 2){return {-1, 0};}vector<int> res(n);res[0] = -1;res[1] = 0;int cnt = 0;int i = 2;while(i < n){if(needle[i-1] == needle[cnt]){res[i++] = ++cnt;}else if(cnt > 0){cnt = res[cnt];}else{res[i++] = 0;}}return res;}int strStr(string haystack, string needle) {int n = haystack.size(), m = needle.size();if(m == 0){return 0;}if(n == 0 || n < m){return -1;}vector<int> nextArray = getNextArray(needle);int i1 = 0, i2 = 0;while(i1 < n && i2 < m){if(haystack[i1] == needle[i2]){i1++;i2++;}else if(i2 > 0){i2 = nextArray[i2];}else if(i2 == 0){i1++;}}return i2 == m ? i1 - i2 : -1;}
};

最长公共前缀

编写一个函数查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串“”。

class Solution {
public:string longestCommonPrefix(vector<string>& strs) {string tempStr = strs[0];for(int i=1; i<strs.size(); i++){if(strs[i].size() < tempStr.size()){tempStr = strs[i];}}string str;for(int i=0; i<tempStr.size(); i++){for(int j=0; j<strs.size(); j++){if(tempStr[i] != strs[j][i]){return str;}}str += tempStr[i];}return str;}
};

最后一个单词的长度

class Solution {
public:int lengthOfLastWord(string s) {int res = 0;int i = s.size()-1;while( i >= 0 && s[i] == ' '){i--;}while( i >= 0 && s[i] != ' '){res++;i--;}return res;}
};

使用分段存储管理方式，当进程在主存中没有找到需要访问的页面并且内存中没有空闲物理块，需要进行页面置换。

产生缺页中断后，首先去内存寻找空闲物理块，若内存没有空闲物理块，使用相应的页面置换算法决定淘汰页面，然后调出淘汰页面，最后调入该进程需要访问的页面。

volatile关键字并不能保证线程安全。

HTTP协议的响应码由三个十进制数字组成，第一个数字为1~5表示5种状态。

TCP三次握手建立连接过程中，所有的标志位至少会有多少次被置为1？（4个）

A发送一个请求连接报文（SYN置为1）
B发回确认（SYN=1,ACK=1）
A再次确认（ACK=1）

C++String类中没有自带的排序方法，但可以使用算法库中的sort()方法来进行排序。默认按照字典序进行排序。

string类相比于传统的字符数组可以更加简单和安全地进行字符串操作。

string类定义在头文件中，可以使用标准命名空间std来访问它。

string类提供了一组重载的运算符来方便执行字符串的拼接、比较操作。

dirname命令用于获取指定路径中的目录部分。

Linux中，inode记录了最后一次读取时间、最近修改的事件，该文件的容量。

小欧喝水

小欧拿n个杯子排成一排，其中有k个杯子装满了水，剩余的n-k个杯子为空。

随机选择一个杯子
杯子是空的，回合直接结束
杯子是满的，如果小欧上一回合喝过水，回合结束，否则将喝完这杯水，回合结束。

HTTP协议

HTTP协议是一种无状态的协议，因为每个请求都是独立的，服务器不会保存客户端的状态信息。

HTTP使用TCP作为传输协议，HTTP协议的默认端口号是80，HTTP协议本身不提供数据加密功能，为了提高传输数据的安全性，可以使用HTTPS，它是HTTP协议的安全版本，使用SSL/TLS协议加密传输数据。

分页式、分段式以及段页式存储管理方式中，一个进程可以划分为许多块，页或者段，这些块在内存中不需要连续存储，动态运行时，通过页表或者快表实现地址转换。但是这些存储管理方式要求为进程分配足够的存储空间，以装入进程有关的全部指令和数据，当进程大小超出内存可用空间的长度时，这个进程就无法运行。

由于线程拥有的资源少，但同时又具有传统进程的许多特性，因此又把线程叫做轻量级进程，不属于线程的实现类型。

线程的实现主要分为三类：用户级线程、内核级线程以及前两类的组合-混合线程。

TCP首部的固定长度为20Byte。

ORDER BY排序，默认是正序，可以对多列或者单列进行排序，多列排序是前一列存在相同值才会根据后一列进行排序。

临界资源是互斥共享资源。

HTTP首部字段

HOST字段：客户端发送请求时，用来指定服务器的域名。
Content-Length：服务器在返回数据时，表明本次回应的数据长度
Connection：客户端要求服务器使用持久连接，以便其它请求复用
Content-Type 字段用于服务器回应时，告诉客户端，本次数据是什么格式
Content-Encoding 字段说明数据的压缩方法。表示服务器返回的数据使用了什么压缩格式
Referer 告知服务器请求的原始资源的URI

创建软链接的命令：ln -s file1 link1

硬链接和软链接的区别

硬链接：硬链接是指多个文件或目录指向同一个inode节点。inode节点是文件在文件系统中的唯一标识，它包含了文件的元数据信息，例如文件大小、权限。所有者等。多个文件或目录共享同一个inode节点，就意味着它们是同一文件的不同引用。

软链接：软链接是指一个文件或目录指向另一个文件或目录的路径。软链接本身是一个独立的文件，它包含了目标文件或目录的绝对路径。
当访问一个软链接时，系统会根据软链接中保存的路径找到目标文件或目录，然后进行相应的操作。

硬链接：

具有相同的inode节点，因此实际上是同一文件的不同入口。
删除其中一个链接不会影响其他链接，只有所有链接都被删除时，文件才会真正删除。
不能跨文件系统创建。
不能指向目录。

软链接：

具有不同的inode节点号，因此是两个不同的文件
删除源文件或目标文件都会导致软链接失效。
可以跨文件系统创建。
可以指向目录。

应用场景
硬链接：

用于创建文件备份，因为删除其中一个备份不会影响其他备份。
提高文件访问性能，可以直接访问inode节点中的数据，无需重新读取文件内容。
用于实现文件共享，因为多个用户可以同时使用同一个文件。

软链接：

用于节省磁盘空间，因为多个软链接指向同一个文件，无需重复存储文件内容。
用于管理文件或目录的区别，方便不同位置引用同一个文件或目录。
用于在不同文件系统之间共享文件或目录。

查看当前的防火墙状态：iptables -L

经常要操作的内存分为哪几个类别？

栈区：由编译器自动分配和释放，存放函数的参数值，局部变量的值等。
堆：一般由程序员分配和释放，存放动态分配的变量。
全局区（静态区）：全局变量和静态变量存放在一块，初始化和未初始化的分开放。
文字常量区：常量字符串就放在这里，重新自动释放。
程序代码区：参访函数体的二进制代码。

线性结构包括链表、数组、栈。

文件读写权限

w：表示写入模式。当使用此模式打开文件时，如果文件已经存在，则会被截断为零长度，即原有内容会被删除；如果文件不存在，则会创建一个新文件。
b：表示二进制模式。表示二进制模式。在某些系统中，文本文件和二进制文件的行结束符处理方式不同。b直接以字节流的形式进行读写，适用于所有类型的文件，特别是包含图片、音频等文件。
+：表示同时开启读取和写入权限。

线程和进程

进程间相互独立，同一进程的各线程间共享。某进程内的线程在其它进程不可见。

线程间可以直接读写数据段（如全局变量）来通信。

线程上下文切换要比进程快得多。

有m个进程共享同一临界资源，则信号量1~1-m

堆的形状是一颗完全二叉树。

map数据结构是用红黑树实现的。

继承是C++中的多态实现方式之一。

什么是野指针

野指针是指向位置是随机的、不可知的、不正确的。

野指针产生的原因：

指针变量未初始化或随便赋值：指针变量没有初始化，其值是随机的，也就是指针变量指向的是不确定的内存，如果对它解引用，结果是不可知的。
指针释放后未置空：有时候指针在释放后没有复制为nullptr，虽然指针变量指向的内存被释放掉了，但是指针变量中的值还在，这时指针变量就是指向一个未知的内存，如果对它解引用，结果是不可知的。
指针操作超出了变量的作用域：函数中返回了局部变量的地址或引用，因为局部变量出了作用域就释放了，这时候返回的地址指向的内存也是未知的。

如何避免野指针

指针变量一定要初始化，可以初始化为nullptr，因为nullptr明确表示空指针。
释放后置为nullptr。
不要用指针接收局部变量的地址。

C语言和C++的区别

C语言是面向过程的语言，而C++支持面向对象，所以C语言自然没有面向对象的封装、继承、多态等特性，也不支持面向对象的一些语法。
C++支持函数重载，C语言不支持。
C程序中如果函数没有任何参数要将参数定义为void以此限定函数不可传递任何参数，如果不进行限定让参数表默认为空，其意义是可以传递任何参数，在C++中，不带参数的函数表示函数不能传递任何参数。
C语言struct中不能有函数，C++中可以有。
C语言函数不支持默认值，C++支持参数默认值。
C++语言支持内联函数，C语言不支持。
C++语言支持引用，C语言不支持
C语言采用malloc和free函数动态申请和释放内存，而C++使用new和delete运算符
C语言中只有局部和全局两个作用域，而C++中有局部、全局、类、名称空间作用域。

const和define的区别

const在C语言中表示只读，编译器禁止对它修饰的变量进行修改，在C++中增加了常量的语义。

const生效于编译阶段，而define生效于预处理阶段。
define只是简单的字符串替换，没有类型检查。而const有对应的数据类型，编译器需要进行判断，可以避免一些低级错误。
define定义的常量不可以用指针变量去指向，const定义的常量可以用指针去指向该常量的地址。
define不分配内存，给出的是立即数，有多少次使用就进行多少次替换，内存中会有多个拷贝，消耗内存大，const在静态存储区中分配空间，程序运行过程中内存中只有一个拷贝
可以对const常量进行调试，但不能对宏常量进行调试。

extern

extern可以置于变量声明或者函数声明前，表示变量或函数的定义在别的文件中，提示编译器遇到此变量和函数时在其它文件中寻找定义。

extern变量表示声明一个变量，表示该变量是一个外部变量，也就是全局变量，所以extern修饰的变量保存在静态存储区（全局区），全局变量如果没有显示初始化，它会默认初始化为0，或者显示初始化为0，则保存在程序的BSS段，如果初始化不为0就保存在程序的DATA段。

extern "C"的作用是为了能够正确地实现C++代码调用C语言代码，加上extern "C"后，会指示编译器这部分按照C语言（而不是C++）的方式进行编译。
由于C++支持函数重载，因此编译器编译函数的过程中会将函数的参数类型也加到编译后的代码，而不仅仅是函数名。而C语言不支持函数重载，因此编译C语言代码的函数时不会带上函数的参数类型，一般只包括函数名。

const的用法

用在变量身上，表示该变量只读，不能对它的值进行修改。

const int a = 10;
a = 20;

编译会报错，因为a只读，不能对它进行修改。

结合指针一起使用

const int *p;常量指针
int * const p：指针常量

常量指针：指针变量p指向的内容不能修改，但指针变量p可以修改。
指针常量：指针变量不可以修改，但指向的内容可以更改。

const int * const p

都不可以修改

const用于函数参数

void foo(const int* p);
void foo(const int& p);

const用于行参时说明行参在函数内部不能被改变，这时非常有用的，有时候函数参数传递指针或引用，在函数内部不希望对指针和引用指向的数据修改，可以加const。

class A{int a;void fun() const{a = 20;}
}

const修饰的成员方法中不能修改非静态成员变量。

const修饰类的成员变量

class A{const int a;static const int b;
}

类的成员变量分为静态和非静态。
如果const修饰的是静态成员变量，可以在构造函数中对该变量进行初始化；如果const修饰的是静态的成员变量，需要在类外对该变量进行初始化。