得物C++一面

1、要实现一个队列，要求固定长度，push和pop都是O(1)，怎么实现？（说双向链表，结果说不能用链表。我...？后来说用定长数组和指针维护一个循环队列。又追问怎么判断队列满？）

当听见这个题目时，大家肯定第一反应这不是很简单么。。。然而，真的是你想的那样吗？其实这位同学还是有点思路的，但是好像应该是没有答完整。

参考答：

我们可以使用一个静态数组来存储队列的元素，因为数组支持O(1)时间复杂度的随机访问，对于固定长度的队列而言，它是一个更简单的选择。

然后用两个指针维护一个循环队列，一个指向队列的头部，另一个指向队列的尾部。这两个指针在数组中移动，当到达数组的末尾时，就会绕回到数组的开头。在初始化的时候，要指定队列的大小。

这个队列怎么操作呢，将元素添加到队列的尾部。在循环队列中，一定要注意尾指针的处理，确保它绕回数组的开头。如果队列满了，那就无法继续添加元素了。然后从队列的头部移除元素，这个时候同样也需要处理头指针，确保它绕回数组的开头。如果队列为空，就无法继续移除元素了。

这个问题的关键之处在于处理指针的移动和绕回。循环队列中，需要使用取余操作来确保指针在数组范围内移动，这样就能够实现循环。同时，需要维护一个计数器来跟踪队列中的元素数量，以便在判空和判满操作中使用。

以下是一个代码实现，仅供参考哈~

#include <iostream>
#include <vector>

using namespace std;

class FixedSizeQueue {
private:
    vector<int> data;    // 存储队列元素的数组
    int capacity;        // 队列的固定容量
    int front;           // 队列头指针
    int rear;            // 队列尾指针
    int size;            // 队列当前元素数量

public:
    FixedSizeQueue(int cap) : capacity(cap), front(0), rear(0), size(0) {
        data.resize(capacity);
    }

    // 入队操作，时间复杂度O(1)
    void push(int value) {
        if (isFull()) {
            cout << "队列已满，无法入队。" << endl;
            return;
        }

        data[rear] = value;
        rear = (rear + 1) % capacity;
        size++;
    }

    // 出队操作，时间复杂度O(1)
    void pop() {
        if (isEmpty()) {
            cout << "队列为空，无法出队。" << endl;
            return;
        }

        front = (front + 1) % capacity;
        size--;
    }

    // 获取队列头部元素，时间复杂度O(1)
    int frontValue() {
        if (isEmpty()) {
            cout << "队列为空，无法获取头部元素。" << endl;
            return -1; // 返回一个特殊值表示队列为空
        }

        return data[front];
    }

    // 检查队列是否为空，时间复杂度O(1)
    bool isEmpty() {
        return size == 0;
    }

    // 检查队列是否已满，时间复杂度O(1)
    bool isFull() {
        return size == capacity;
    }
};

int main() {
    int capacity = 5;
    FixedSizeQueue queue(capacity);

    cout << "入队操作：" << endl;
    for (int i = 1; i <= capacity + 1; ++i) {
        if (!queue.isFull()) {
            cout << "入队元素: " << i << endl;
            queue.push(i);
        } else {
            cout << "队列已满，无法入队元素 " << i << endl;
        }
    }

    cout << "出队操作：" << endl;
    while (!queue.isEmpty()) {
        cout << "出队元素: " << queue.frontValue() << endl;
        queue.pop();
    }

    return 0;
}

2、C++运行出现Core Dump怎么办？

那先来给大家说说什么是Core Dump吧，可能大多数人都没见过或者说是没留意过这东西。其实问这个问题呢，面试官多数是想考考你gdb这块的内容。

它的话就是程序在运行过程中发生了严重错误，然后导致程序崩溃并生成了一个核心转储文件（通常就命名为 core），这个文件里面包含了程序崩溃时的内存状态信息。它主要就是可以帮助我们开发人员诊断问题并找出导致程序崩溃的原因。

既然是和大家一起看问题，那就多讲点，不光是为了解答这个问题。

产生coredump的原因都有哪些呢？

1. 内存访问越界
   • 由于使用错误的下标，导致数组访问越界；
   • 搜索字符串时，依靠字符串结束符来判断字符串是否结束，但是字符串没有正常的使用结束符；
   • 使用strcpy, strcat, sprintf, strcmp, strcasecmp等字符串操作函数，将目标字符串读/写爆。应该使用strncpy, strlcpy, strncat, strlcat, snprintf, strncmp, strncasecmp等函数防止读写越界。
2. 多线程程序使用了线程不安全的函数。
3. 多线程读写的数据未加锁保护。对于会被多个线程同时访问的全局数据，应该注意加锁保护，否则很容易造成core dump。
4. 非法指针，比如说空指针。。。
5. 堆栈溢出。不要使用大的局部变量（因为局部变量都分配在栈上），这样容易造成堆栈溢出，破坏系统的栈和堆结构，导致出现莫名其妙的错误。

接下来说说遇到它怎么办吧？

1. 检查指针是否被正确初始化和使用，并确保不越界。
2. 检查代码中是否存在内存泄漏，并在分配内存后及时释放内存。
3. 检查函数调用嵌套层数和在栈上分配的内存大小，避免栈溢出。
4. 使用调试工具，如gdb，在程序崩溃时捕获core dump文件，并分析该文件以确定错误原因。
5. 在程序开发和测试过程中，尽可能使用静态代码分析工具和动态内存分析工具，检查和预防程序错误。

以上就是一些常见的解决coredump错误的方法。当然，具体的还需根据具体问题进行分析，如果开发过程中遇到了这种问题，不要慌，自己不会的话就找找网上的经验。。。

3、GDB调试输出栈的信息用什么命令？

在GDB调试过程中，要输出栈的信息，可以使用 backtrace 或其简写形式 bt 命令。这些命令用于查看当前的函数调用堆栈。

backtrace
或者
bt

GDB将会显示当前函数调用的堆栈跟踪信息，包括每个函数的名称、源文件和行号（如果有调试信息可用的话），以及每个函数的调用参数和局部变量。

4、GDB调试切换线程用什么命令？（？忘了）

在gdb调试过程中，我们可以用info threads来查看当前线程的信息，包括线程号、状态、堆栈等。

然后用thread <num> 来切换到想要的线程。num是上面查询到的线程号。

需要注意的是GDB中线程调试需要支持多线程调试的二进制可执行文件，并且你的程序必须正在多线程模式下运行，才能够进行线程切换和调试。如果你的程序没有启用多线程支持，或者线程没有正确配置，那么线程调试功能可能会受到限制。

5、C++程序运行起来如果发现内存使用不断在长，怎么确定问题位置？（说可能发生了内存泄漏，在申请内存的相关位置写日志然后分析？）

可以考虑内存泄漏：

• 我们平时在使用new malloc等函数，却忘记释放，如果不知道出问题的具体代码段，搜索关键字依次查看即可。 某些接口在内部进行了内存申请，并不是直观的有内存分配函数，未删除导致内存泄漏。

也考虑有没有日志类，如果程序在运行时不断向控件中写日志，而又没有采用控制日志条目，则内存会一直增大。

6、C++多线程相关的应该注意些什么？（互斥问题、同步问题；通过信号量、锁机制、条件变量等方法）

此处就不多赘述了，详细的点击另外一篇有详细解答。所以说多线程是C++面试过程中必会问到的一个东西。

1. 信号量和互斥锁有什么区别？
   • 信号量用于线程的同步，互斥锁用于线程的互斥。
   • 信号量值可以为非负整数，互斥锁值只能为0/1。
   • 信号量可以由一个线程释放，另一个线程得到，互斥锁的加锁和解锁必须由同一线程分别对应使用。
   • 信号量用在多线程多任务同步的，一个线程完成了某一个动作就通过信号量告诉别的线程，别的线程再进行某些动作。互斥锁是用在多线程多任务互斥的，一个线程占用了某一个资源，那么别的线程就无法访问，直到这个线程unlock，其他的线程才开始可以利用这个资源。
2. 死锁是什么引起的？给一个死锁场景？怎么避免？（死锁八股）

在多进程或多线程环境中的一种特殊情况，其中两个或多个进程（线程）无法继续执行，因为它们彼此等待对方释放资源。

四个必要条件：

• 互斥条件：至少有一个资源是排他性的，即一次只能由一个进程（线程）占用。这意味着其他进程无法同时访问该资源。
• 持有与等待条件：一个进程（线程）可以持有一些资源并等待获取其他资源，同时不释放已经持有的资源。
• 不可剥夺条件：资源不能被强制性地从一个进程（线程）中抢占，只能由占用资源的进程主动释放。
• 循环等待条件：一组进程之间存在循环等待资源的关系，每个进程都等待另一个进程所持有的资源。

场景？

假设有两个线程A和B，以及两个资源X和Y。这两个线程试图获取这两个资源，但它们的顺序不同，可能导致死锁。

• 线程A获取资源X，然后进入临界区，执行一些操作，但在操作完成前不会释放资源X。
• 同时，线程B获取资源Y，然后进入临界区，执行一些操作，但在操作完成前不会释放资源Y。
• 线程A现在尝试获取资源Y，但由于线程B已经持有资源Y，所以线程A被阻塞，无法继续执行。
• 同样，线程B也尝试获取资源X，但由于线程A已经持有资源X，所以线程B也被阻塞，无法继续执行。

在这种情况下，线程A和线程B都被阻塞，无法释放它们已经持有的资源，导致彼此相互等待，从而发生死锁。

怎么避免？

怎么避免死锁经常是要根据它的具体实例来进行解决，也就是围绕它产生的几个条件来讲。

• 资源分配顺序： 一种常见的方法是规定所有线程必须按照相同的顺序请求资源。比方说，如果一个线程需要首先锁定资源A，然后才能请求资源B，那么所有线程都必须按照相同的顺序来请求这两个资源。这种方法可以破坏循环等待条件。
• 超时和重试： 允许线程在一段时间内等待资源，但如果等待超过了某个时间限制，线程将放弃等待，并可以选择重试或回退操作。这可以防止线程永久阻塞，尽管它可能会导致一些操作的失败和重试。
• 资源分级： 将资源划分为多个级别，每个级别有一个获取的顺序。线程只能请求比它当前拥有的级别更高的资源。这种方法可以减少死锁的可能性。
• 死锁检测和恢复： 周期性地检测系统中是否存在死锁。如果检测到死锁，可以采取措施来中断其中一个或多个线程，以解除死锁。这种方法可能会引入一些性能开销，但可以保证系统的可用性。
• 避免共享资源： 通过设计避免共享资源，或者尽量减少资源共享，可以降低死锁的可能性。这可以通过使用副本而不是共享数据，或者通过使用消息传递来实现。
• 使用同步工具： 使用更高级的同步工具，如信号量、互斥锁、条件变量等，可以更容易地避免死锁。这些工具通常提供了更复杂的同步操作，允许更精细的控制资源的分配和释放。

7、C++中关键字volatile修饰一个int，在多线程场景下会有安全问题吗？（这个说错了，查了查是有问题的。）

请先记住这句话：永远不要用volatile保证线程安全！

在C++中，volatile 关键字是用来告诉编译器，某个变量可能会在程序中的不同地方被修改，因此编译器不应该进行某些优化，以确保每次访问该变量都会从内存中读取而不是使用寄存器中的缓存值。

volatile 并不提供多线程安全性。它只是告诉编译器不要进行某种特定的优化，以确保变量的可见性，但它并不能保证线程安全。在多线程环境下，多个线程可以同时访问同一个被 volatile 修饰的变量，而不受编译器的影响。

如果多个线程并发地访问并修改一个 volatile 变量，仍然可能发生竞态条件和数据竞争。为了确保在多线程环境中的安全访问，通常需要使用互斥锁、信号量或其他同步机制来保护共享变量的访问。

8、MySQL事务，四大特性？隔离级别？

事务是由一系列对系统中数据进行访问与更新的操作所组成的一个程序执行逻辑单元，事务不可分割。

四大特性？

• 原子性：指的是事务包含的所有操作要么全部成功，要么全部失败回滚，因此事务的操作如果成功就必须要完全应用到数据库，如果操作失败则不能对数据库有任何影响。
• 一致性：指的是事务必须使数据库从一个一致性状态变换到另一个一致性状态，也就是说一个事务执行之前和执行之后都必须处于一致性状态。
• 隔离性：同一时间，只允许一个事务请求同一数据，不同的事务之间彼此没有任何干扰。
• 持久性：事务完成后，事务对数据库的所有更新将被保存到数据库，不能回滚。

隔离级别？

• 读未提交（Read Uncommitted）：
  • 最低的隔离级别，事务中的修改操作对其他事务是可见的，即未提交的修改可以被其他事务读取。
  • 存在脏读（Dirty Read）问题，即一个事务读取到了另一个未提交事务的修改结果。
• 读提交（Read Committed）：
  • 事务中的修改操作在提交之前对其他事务是不可见的，只有已提交的修改才能被其他事务读取。
  • 解决了脏读问题，但可能存在不可重复读（Non-repeatable Read）问题，即在同一事务内多次读取同一数据可能会得到不同的结果。
• 可重复读（Repeatable Read）：
  • 保证在同一事务内多次读取同一数据时，得到的结果始终一致。
  • 解决了不可重复读问题，但可能存在幻读（Phantom Read）问题，即在同一事务内多次执行查询，得到的结果集不一致。
• 串行化（Serializable）：
  • 最高的隔离级别，完全隔离事务，确保事务串行执行，避免并发问题。
  • 解决了幻读问题，但在高并发情况下会导致性能下降，因为事务需要串行执行。

9、聚簇索引和非聚簇索引有什么区别，回表是什么意思？

区别？

• 聚簇索引叶子节点存储的是行数据；而非聚簇索引叶子节点存储的是聚簇索引（通常是主键 ID）。
• 聚簇索引查询效率更高，而非聚簇索引需要进行回表查询，因此性能不如聚簇索引。
• 聚簇索引一般为主键索引，而主键一个表中只能有一个，因此聚簇索引一个表中也只能有一个，而非聚簇索引则没有数量上的限制。

回表？

回表，顾名思义就是回到表中，也就是先通过普通索引扫描出数据所在的行，再通过行主键ID 取出索引中未包含的数据。所以回表的产生也是需要一定条件的，如果一次索引查询就能获得所有的select 记录就不需要回表，如果select 所需获得列中有其他的非索引列，就会发生回表动作。即基于非主键索引的查询需要多扫描一棵索引树。

10、口述SQL：有一张表有学生、班级、性别等字段，如何通过一条SQL语句查出各班级分别有多少男生和女生？（紧张没说出来，麻了）

SELECT 班级, 
   SUM(CASE WHEN 性别 = '男' THEN 1 ELSE 0 END) AS 男生人数,
   SUM(CASE WHEN 性别 = '女' THEN 1 ELSE 0 END) AS 女生人数
FROM 学生表
GROUP BY 班级;

首先将学生表按照班级分组（使用 GROUP BY 班级），然后使用条件聚合函数 SUM 结合 CASE 表达式来计算每个班级内男生和女生的人数。

11、手写一下快排

先说说它的思想：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

这里给出参考代码

递归法

#include <iostream>
#include <vector>

using namespace std;

void quickSort(vector<int>& nums, int left, int right) {
    if (left >= right) return;

    int pivot = nums[left]; // 选取基准数
    int i = left, j = right;

    while (i < j) {
        // 从右往左找到第一个小于基准数的元素
        while (i < j && nums[j] >= pivot) j--;
        if (i < j) nums[i++] = nums[j]; // 将该元素移到基准数左侧

        // 从左往右找到第一个大于基准数的元素
        while (i < j && nums[i] < pivot) i++;
        if (i < j) nums[j--] = nums[i]; // 将该元素移到基准数右侧
    }

    nums[i] = pivot; // 将基准数放回中间位置

    // 对基准数左侧和右侧的子数组分别递归调用快排
    quickSort(nums, left, i - 1);
    quickSort(nums, i + 1, right);
}

int main() {
    vector<int> nums = { 3, 7, 2, 9, 1, 5, 8, 4, 6 };
    quickSort(nums, 0, nums.size() - 1);

    for (int i = 0; i < nums.size(); i++) {
        cout << nums[i] << " ";
    }
    cout << endl;

    return 0;
}

非递归：

void quickSort(vector<int>& nums) {
    if (nums.empty()) {
        return;
    }
    stack<int> s;
    int left = 0, right = nums.size() - 1;
    s.push(left);
    s.push(right);
    while (!s.empty()) {
        right = s.top();
        s.pop();
        left = s.top();
        s.pop();
        int pivot = nums[left];
        int i = left, j = right;
        while (i < j) {
            while (i < j && nums[j] >= pivot) {
                j--;
            }
            if (i < j) {
                nums[i++] = nums[j];
            }
            while (i < j && nums[i] < pivot) {
                i++;
            }
            if (i < j) {
                nums[j--] = nums[i];
            }
        }
        nums[i] = pivot;
        if (i - 1 > left) {
            s.push(left);
            s.push(i - 1);
        }
        if (i + 1 < right) {
            s.push(i + 1);
            s.push(right);
        }
    }
}

好了，今天就分享这么多了。。。