深信服---C/C++软开

一面

Linux

1、Linux进程调度的策略，RR具体怎么设置
linux内核的三种调度方法：
SCHED_OTHER 分时调度策略，
SCHED_FIFO实时调度策略，先到先服务
SCHED_RR实时调度策略，时间片轮转

2、Linux网卡收包到应用程序的过程？

当网卡上收到数据以后，首先会以DMA的方式把网卡上收到的帧写到内存里。再向CPU发起一个中断，以通知CPU有数据到达。当CPU收到中断请求后，会去调用网络驱动注册的中断处理函数。 网卡的中断处理函数并不做过多工作，发出软中断请求，然后尽快释放CPU。ksoftirqd检测到有软中断请求到达，调用poll开始轮询收包，收到后交由各级协议栈处理。对于UDP包来说，会被放到用户socket的接收队列中

3、了解SWAP吗
一般所说的swap，指的是一个交换分区或文件。在Linux上可以使用swapon -s命令查看当前系统上正在使用的交换空间有哪些
从功能上讲，交换分区主要是在内存不够用的时候，将部分内存上的数据交换到swap空间上，以便让系统不会因内存不够用而导致oom或者更致命的情况出现。

所以，当内存使用存在压力，开始触发内存回收的行为时，就可能会使用swap空间。

4、Linux内存管理，内存不够用了会怎样
一、物理内存和虚拟内存
我们知道，直接从物理内存读写数据要比从硬盘读写数据要快的多，因此，我们希望所有数据的读取和写入都在内存完成，而内存是有限的，这样就引出了物理内存与虚拟内存的概念。

物理内存就是系统硬件提供的内存大小，是真正的内存，相对于物理内存，在Linux下还有一个虚拟内存的概念，虚拟内存就是为了满足物理内存的不足而提出的策略，它是利用磁盘空间虚拟出的一块逻辑内存，用作虚拟内存的磁盘空间被称为交换空间(Swap Space)。

作为物理内存的扩展，Linux会在物理内存不足时，使用交换分区的虚拟内存，更详细的说，就是内核会将暂时不用的内存块信息写到交换空间，这样以来，物理内存得到了释放，这块内存就可以用于其它目的，当需要用到原始的内容时，这些信息会被重新从交换空间读入物理内存。

Linux的内存管理采取的是分页存取机制，为了保证物理内存能得到充分的利用，内核会在适当的时候将物理内存中不经常使用的数据块自动交换到虚拟内存中，而将经常使用的信息保留到物理内存。

5、Linux页的大小，大页听说过吗

6、awk,sed,free,top,ps

5、用到的数据结构和算法介绍下？（unordered_map）
6、登录页面用模态窗口还是非模态窗口
模态窗口就是在该窗口关闭之前，其父窗口不可能成为活动窗口的那种窗口。
例如：
窗口A弹出窗口B,如果窗口B是模态的，在窗口B关闭前就不可能切换到窗口A;如果B是非模态的，那可以在这两个窗口之间任意切换。

模态对话框 和 非模态对话框区别
模态对话框在显示之后，就不能对同一个程序中的其它窗口进行操作。
非模态对话框在显示之后，还可以对同一个程序的其它窗口进行操作。

7、文件传输丢包如何处理
为了满足TCP协议不丢包。TCP协议有如下规定：
1. 数据分片：发送端对数据进行分片，接受端要对数据进行重组，由TCP确定分片的大小并控制分片和重组
2. 到达确认：接收端接收到分片数据时，根据分片数据序号向发送端发送一个确认
3. 超时重发：发送方在发送分片时设置超时定时器，如果在定时器超时之后没有收到相应的确认，重发分片数据
**4. 滑动窗口：**TCP连接的每一方的接受缓冲空间大小固定，接收端只允许另一端发送接收端缓冲区所能接纳的数据，TCP在滑动窗口的基础上提供流量控制，防止较快主机致使较慢主机的缓冲区溢出
5. 失序处理：作为IP数据报来传输的TCP分片到达时可能会失序，TCP将对收到的数据进行重新排序，将收到的数据以正确的顺序交给应用层;
6. 重复处理：作为IP数据报来传输的TCP分片会发生重复，TCP的接收端必须丢弃重复的数据;
7. 数据校验：TCP将保持它首部和数据的检验和，这是一个端到端的检验和，目的是检测数据在传输过程中的任何变化。如果收到分片的检验或有差错，TCP将丢弃这个分片，并不确认收到此报文段导致对端超时并重发

8、文件在接收端如何拼接

9、文件接送拼接如何保证数据的完整性
10、点对点通信怎么做，数据结构还使用链表吗，如何实现O(1)查找套接字

11、客户端单方面断线如何处理
报冲突，只会在你客户端仍然用同一个端口当作本地端口去连接服务器，否则是不会报冲突的。所以依着上面的原因，你只需要在下一次连接的时候，把本地端口换掉就好了。不知道你们这个服务器侧是否有这样的设置，tcp重传累积到一定时间或者次数，就reset，释放资源，如果有，等过了这段时间，再连也行

上一种情况的触发条件是客户端手机本身断网或网络发生异常的情况的触发，但实际情况中，还有可能发生客户端网络并未断开，也并没有异常抛出，但是却出现客户端和服务器无法正常进行收发消息的情况。
　　这种情况一方面原因是中间链路的连接异常，另一方面也会由于延迟过高或丢包导致的TCP重发造成的延迟过大，影响到服务器和客户端之间正常的收发消息。

12、聊天记录查询可以做到按照相似字查找吗

13、网络字节序和主机字节序的区别。
大端字节序是指一个整数的高位字节（32-31bit）存储在内存的低地址处，低位字节（0-7bit）存储在内存的高地址处。

小端字节序是指一个整数的高位字节（32-31bit）存储在内存的高地址处，低位字节（0-7bit）存储在内存的低地址处。
小端字节序又被称为主机字节序。
大端字节序也称为网络字节序
同理，0x1234567的大端字节序和小端字节序的写法如下图。

14、组播能跨网络域通讯吗？
组播协议允许将一台主机发送的数据通过网络路由器和交换机复制到多个加入此组播的主机，是一种一对多的通讯方式。
组播是可以跨网段的,只要路由器支持

15、场景题：有人收集了一堆域名黑名单，用什么数据结构存储能让查询速度快呢？

16、 场景题：有人收集了一堆ip网段黑名单，用什么数据结构存储能让查询速度快呢？
是一个索引查找的原理。
223.255.255.1 转换成数字就是223255+255255+255255+1255
作成树状，很明显可以通过算法跳过好多多余数据。
如果算法基础不强，直接用数据库。数据库的索引查找速度巨快。纯真ip库目的是脱离数据库运行环境，加上自己算法很强就自己实现了。

代码

1、手撕代码——实现memcpy

void *memcpy(void *dest, const void *src, size_t n);
//dest 是要拷贝到的目标内存区域，src是被拷贝的内存区域，n是拷贝的字节长度。
void *memcpy(void *dest, const void *src,size_t n)
{
if(dest==nullptr||src==nullptr)
    return nullptr;
void *res = dest;
if(dest<=src||(char*)dest>=(char*)src+n){
        while(len--){
//从低地址开始复制
        *(char*)dest =*(char*)src;
        dest=(char*)dest+1;
        src=(char*)src+1;
        }
}
else{
//从高地址开始复制
      src = (char*)src + len -1;
      dst = (char*)dst + len -1;
      while(len--){
            *(char*)dst = *(char*)src;
            dst = (char*)dst -1;
            src = (char*)src -1;
          }
    }
return res;
}

2、（Leetcode 445）两个链表相加

将两个链表的节点分别放入两个栈中，若两个栈都非空，拿两个栈顶元素和进位，求出和以及新的进位；若其中一个栈为空，则拿一个栈顶元素和进位，求出和以及新的进位。然后新建节点，在链表头部进行插入，最后只用处理一下最高位的进位即可。
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        
        stack<ListNode *> stack1;
        stack<ListNode *> stack2;
        
        while (l1)
        {
            stack1.push(l1);
            l1 = l1->next;
        }
        
        while (l2)
        {
            stack2.push(l2);
            l2 = l2->next;
        }
        
        int sum = 0;
        int carry = 0;
        
        ListNode *new_head = new ListNode(0);
        ListNode *temp = NULL;
        
        while (!stack1.empty() && !stack2.empty())
        {
            sum = stack1.top()->val + stack2.top()->val + carry;
            
            if (sum >= 10)
            {
                sum = sum % 10;
                carry = 1;
            }
            else
                carry = 0;
            
            temp = new ListNode(sum);
            temp->next = new_head->next;
            new_head->next = temp; 
            
            stack1.pop();
            stack2.pop();
        }
                

         while (!stack1.empty())
         {
            sum = stack1.top()->val + carry;

            if (sum >= 10)
            {
                sum = sum % 10;
                carry = 1;
            }
            else
                carry = 0;

            temp = new ListNode(sum);
            temp->next = new_head->next;
            new_head->next = temp; 

            stack1.pop();
         }
        

         while (!stack2.empty())
         {
            sum = stack2.top()->val + carry;

            if (sum >= 10)
            {
                sum = sum % 10;
                carry = 1;
            }
            else
                carry = 0;

            temp = new ListNode(sum);
            temp->next = new_head->next;
            new_head->next = temp; 

            stack2.pop();
         }
        
        if (carry)
        {
            temp = new ListNode(carry);
            temp->next = new_head->next;
            new_head->next = temp; 
        }
        
        return new_head->next;
    }   
};

3、手撕：合并两个有序链表

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode *dummy = new ListNode(-1), *cur = dummy;
        if(l1 == NULL) return l2;
        if(l2 == NULL) return l1;
        while(l1 && l2){
            if(l1->val < l2->val){
                cur->next = l1;
                l1 = l1->next;
            }
            else{
                cur->next = l2;
                l2 = l2->next;
            }
            cur = cur->next;
        }
        if(l1) cur->next = l1;
        if(l2) cur->next = l2;
        return dummy->next;
    }
};

1）内存不足怎么办
2）如何不创建头结点实现
4、查找一个字符串是否包含另一个字符串

#include "string"

#include "boost/algorithm/string.hpp"

using namespace std;
using namespace boost;
int main(){
    string s("Hello Word!");
    string t("ello");
    bool b = contains(s, t);
    cout << b << endl;
    return 0;
}


#include <iostream>
#include <string>

bool CheckSubstring(std::string firstString, std::string secondString)
{
    if (secondString.size() > firstString.size())
        return false;

    for (int i = 0; i < firstString.size(); i++)
    {
        int j = 0;
        // If the first characters match
        if (firstString[i] == secondString[j])
        {
            int k = i;
            while (firstString[i] == secondString[j] && j < secondString.size())
            {
                j++;
                i++;
            }
            if (j == secondString.size())
                return true;
            else // Re-initialize i to its original value
                i = k;
        }
    }
    return false;
}

int main()
{
    std::string firstString, secondString;

    std::cout << "Enter first string:";
    std::getline(std::cin, firstString);

    std::cout << "Enter second string:";
    std::getline(std::cin, secondString);

    if (CheckSubstring(firstString, secondString))
        std::cout << "Second string is a substring of the frist string.\n";
    else
        std::cout << "Second string is not a substring of the first string.\n";

    return 0;
}

5、算法：二分查找
6、手撕代码：给一段字符串"I am student."，将其反转为"student. am I"。
7、如何用一个5L的杯子和一个6L的杯子得到3L的水。
8、23枚硬币，其中10枚正面朝上，假设你的眼睛被蒙住，而且摸不出正反面，如何将硬币分为两堆，并且每一堆正面朝上的个数相同。
9、手撕单链表节点插入和删除
10、用栈实现队列，具体怎么做，怎么写入队列，怎么取出
11、1亿个数找最小的1000个，这个没答出来，分组排序，冒泡1000，然后面试官问了解堆吗？问了一些堆的实现细节，让我反过来看这道题，我才想起用大顶堆。
12、两个数组的交集
13、64位计算机如何实现128位数据的加减运算，伪代码
14、力扣原题，100*100的网格，从左上角到右下角的方案数量，提升:如果路径中带有障碍物，

C++：

1、inline关键字的作用

在函数声明或定义中函数返回类型前加上关键字inline即把min（）指定为内联。
inline的函数是复制到调用位置，而不是跳转调用，这样的好处是避免函数调用本身出栈入栈消耗额外的时间，而且高速缓存会更容易命中（一项CPU的技术，命中时会提高运行速度，数据不走内存避免了额外时间消耗）。。。 inline只用于内容重复，但代码很短的函数，避免出栈入栈消耗额外的时间，其实内联函数并不是真正意义的函数。。。而是对重复代码的简化。。。

(1)关键字inline 必须与函数定义体放在一起才能使函数成为内联，仅将inline 放在函数声明前面不起任何作用。
(2)定义在类声明之中的成员函数将自动地成为内联函数

2、内存泄漏如何定位
Windows下：Visual Leak Detector
接下来需要将VLD加入到自己的代码中。方法很简单，只要在包含入口函数的.cpp文件中包含vld.h就可以。如果这个cpp文件中包含了stdafx.h，则将包含vld.h的语句放在stdafx.h的包含语句之后，否则放在最前面。

3、C++static关键字
首先static的最主要功能是隐藏，其次因为static变量存放在静态存储区，所以它具备持久性和默认值0.
(1)隐藏
所有未加static前缀的全局变量和函数都具有全局可见性，其它的源文件也能访问。如果加了static，就会对其它源文件隐藏。static可以用作函数和变量的前缀，对于函数来讲，static的作用仅限于隐藏.
（2）保持变量内容的持久。（static变量中的记忆功能和全局生存期）

4、c++内存有哪些种类？
(1).栈区(stack)：由编译器自动分配和释放，存放函数的参数值，局部变量的值等。
(2).堆区(heap)：一般是由程序员分配释放(动态内存申请与释放)，若程序员不释放，程序结束时可能由操作系统回收
(3).全局区(静态区，常量区)：全局变量和静态变量的存储是放在一起的，初始化的全局变量和静态变量在一块区域，未初始化的全局变量和未初始化的静态变量在相邻的另一块区域，该区域在程序结束后由操作系统释放。常量区是字符串常量和其他常量的存储位置，程序结束后由系统自动释放。
(4).程序代码区：存放函数体的二进制代码。

5、堆是干什么的？
6、new出来的对象，使用delete时它怎么知道这个内存的大小?
需要在 new [] 一个对象数组时，需要保存数组的维度，C++ 的做法是在分配数组空间时多分配了 4 个字节的大小，专门保存数组的大小，在 delete [] 时就可以取出这个保存的数，就知道了需要调用析构函数多少次了
new/delete、new[]/delete[] 要配套使用总是没错的！

9、哪些函数不能设定为虚函数
(1)普通的函数
因为普通函数只能被overload，不能被override，也不能被继承，所以在编译的时候就绑定函数，所以不能申明为virtual，没有意义！

(3)构造函数
这个也很简单。主要因为构造函数是用来确定初始化对象的，而virtual主要是为了在不了解具体的情况下实现动态绑定，调用不同类型中合适的成员函数而存在的，现在对象都没产生，怎么能实现多态呢。一个是为了具体化，一个是为了在不同对象类型中确定合适的函数，这是不可能的！
此外，构造函数不能被继承，所以不能virtual；构造函数是系统默认提供或者自己写的，并且和类名相同，就算继承了也不是自己的了，所以不能被继承；
构造函数是在为了创建初始化对象存在的，对象不存在实现多态是不可能的；

(3)内联函数
inline函数在编译时被展开，在调用处将整个函数替换为代码块，省去了函数跳转的时间，提高了SD，减少函数调用的开销，虚函数是为了继承后对象能够准确的调用自己的函数，执行相应的动作。
主要的原因是：inline函数在编译时被展开，用函数体去替换函数，而virtual是在运行期间才能动态绑定的，这也决定了inline函数不可能为虚函数。（inline函数体现的是一种编译机制，而virtual体现的是一种动态运行机制）
(4)静态成员函数
静态成员函数是类的组成部分，但是不是任何对象的组成部分，所有对象共享一份，没有必要动态绑定，也不能被继承【效果能，但机理不能。静态成员函数就一份实体，在父类里；子类继承父类时也无需拷贝父类的静态函数，但子类可以使用父类的静态成员函数】，并且静态成员函数只能访问静态变量。所以不能为virtual。
(5)友员函数
友员函数不是类的成员函数，C++不支持友员被继承，所以不能为virtual。

10、UDP怎么保证可靠？
UDP它不属于连接型协议，因而具有资源消耗小，处理速度快的优点，所以通常音频、视频和普通数据在传送时使用UDP较多，因为它们即使偶尔丢失一两个数据包，也不会对接收结果产生太大影响。
传输层无法保证数据的可靠传输，只能通过应用层来实现了。实现的方式可以参照tcp可靠性传输的方式，只是实现不在传输层，实现转移到了应用层。
实现确认机制、重传机制、窗口确认机制。
如果你不利用Linux协议栈以及上层socket机制，自己通过抓包和发包的方式去实现可靠性传输，那么必须实现如下功能：

发送：包的分片、包确认、包的重发
接收：包的调序、包的序号确认
目前有如下开源程序利用udp实现了可靠的数据传输。分别为RUDP、RTP、UDT。

11、野指针的理解。怎么防止野指针？
野指针不是NULL指针，是指向“垃圾”内存的指针。
即它是随机指向的，系统自动对其初始化。

1.首先我们要养成良好的编码习惯。
2.当我们定义一个指针的时候，直接让它指向NULL。
因为NULL在宏定义是#define NULL (void *) 0 它代表的是零地址，而零地址是不能进行读写操作的。
3.要想给指针指向的空间赋初值的时候，必须给指针分配空间。
可是使用malloc()进行分配空间，它返回的是空间的首地址。

4.在分配空间后，我们首要做的是检查是否分配成功。
简单的检测方法：

 if (p == NULL) //p为指针变量
 {
 printf(“malloc分配失败!”);
 exit(1); //结束整个程序,return 是结束一个函数
 }

5.在使用malloc分配后的空间之前一定要对其清零。
因为我们分配的空间里面可能残留一些垃圾数据，这样会导致程序出错。
6.使用完空间后，记得释放空间，可以用free§;//p为指针变量
7.释放完后可以让指针指向NULL，如：p = NULL

12、数组与链表的区别
数组静态分配内存，链表动态分配内存；
数组在内存中连续，链表不连续；
数组元素在栈区，链表元素在堆区；
数组利用下标定位，时间复杂度为O(1)，链表定位元素时间复杂度O(n)；
数组插入或删除元素的时间复杂度O(n)，链表的时间复杂度O(1)。
13、对虚函数的理解
14、实现单链表尾插，翻转链表
15、宏实现max(a,b)

#define swap(a, b) { \
a ^= b;                         \
b ^= a;                          \
a ^= b;                          \
}

16、介绍下vector内部原理，vector内存回收，clear会回收vector内存吗？
18、还了解过什么数据结构？完全二叉树说下。