【面经合集】当 deepseek 遇上文远知行的面试｜CPP｜01

🌟【友情提示】本篇面经来自粉丝投稿+智能润色，点击进入 -> 🔗互联网面经大全 围观25届校招修罗场！！每个技术细节都经过脱敏处理，请勿对号入座~

🌈 面试官：

“小基，咱们先聊聊快排。你能简单说说快排在平均情况下和最坏情况下的时间复杂度吗？以及什么情况下会出现最坏情况，怎么避免这种塌缩？”

💬 小基：

“快排在平均情况下的时间复杂度是 ，但当数组基本有序或者所有元素几乎相同时，就会出现分割极不平衡的情况，时间复杂度退化到 。为了规避这种情况，我们平时往往采用随机化策略选取pivot或者用三数取中法来确保分割尽量均匀。”

🌈 面试官：

“那你有没有看过 STL 中 sort 的实现？它是怎么避免退化到最坏情况的呢？”

💬 小基：

“我有关注过。STL 的 sort 并不单纯依赖快速排序，而是采用了一种混合排序策略，在大多数情况下使用快速排序，但在遇到递归深度过深或者数据分布不均的情况时，会转而使用堆排序或插入排序，从而规避最坏情况的发生。”

🌈 面试官：

“很好。再谈谈数据结构方面，AVL 树你了解吗？它是如何保持平衡的？”

💬 小基：

“AVL 树是一种自平衡的二叉搜索树。在每次插入或删除节点后，它会检查节点的平衡因子——即左右子树高度的差。如果发现不平衡，就会通过左旋、右旋或者先左后右、先右后左的旋转操作来调整树结构，确保整个树的高度保持在 的范围内，这样可以保证查找、插入和删除操作的效率。”

🌈 面试官：

“关于数据库存储，你知道为什么数据库更倾向于使用 B+ 树而不是 AVL 树吗？”

💬 小基：

“主要是因为 B+ 树的叶子节点采用连续存储，这对磁盘 I/O 非常友好。数据库查询时，磁盘I/O的性能往往远比算法本身的计算时间重要。AVL树虽然也能保持平衡，但其节点分布在内存中通常不连续，不利于范围查询，而B+树在这方面优势明显。”

🌈 面试官：

“接下来考一道手撕题：求数组中第 K 小的数，你会使用 partition 算法。请你说明下 partition 的平均和最坏时间复杂度，并简单介绍你的思路。”

💬 小基：

“这道题目通常使用快速选择算法。利用 partition 可以把数组划分为两部分，根据 pivot 的位置判断第K小的数在哪一侧，然后递归寻找。平均时间复杂度是 ，但如果每次分割都非常不平衡，最坏情况下可能退化到 ，比如数组几乎已经有序时。”

🌈 面试官：

“非常好。那你口算下 (9^999999)%5 的值是多少？”

💬 小基：

“口算时，首先9对5取模得到4，等价于 。通过观察周期性规律，我们可以迅速判断结果为4。”

🌈 面试官：

“现在请你写出快速幂算法的递归版本，计算 (a^b)%n。注意，a、b、n 的数值可能非常大，要使用 long 类型避免溢出。”

💬 小基：

“好的，这是我写的 C++ 版本的递归快速幂代码，附有详细注释：”

#include <iostream>
using namespace std;

// 递归实现快速幂，计算 (a^b) % n
long long fastPower(long long a, long long b, long long n) {
    // 如果指数为 0，则结果为 1
    if(b == 0) return 1;
    // 递归计算 a^(b/2) % n
    long long half = fastPower(a, b / 2, n);
    // 将中间结果平方后取模
    long long result = (half * half) % n;
    // 如果指数 b 为奇数，再乘以 a 后取模
    if(b % 2 == 1)
        result = (result * a) % n;
    return result;
}

int main(){
    long long a = 123456789, b = 987654321, n = 1000000007;
    cout << fastPower(a, b, n) << endl;  // 输出结果
    return 0;
}

🌈 面试官：

“好，接下来聊聊数据库部分。假设让你设计一张表，你会怎么做？为什么需要建立索引？有哪些情况下你觉得不必建立索引？顺便说说数据库三大范式。”

💬 小基：

“设计表时，我会先明确表的业务需求，并确定需要存储的字段。确保每个字段都符合第一范式，即不可再分的原子值，接着根据业务逻辑满足第二范式和第三范式，从而避免数据冗余，确保数据一致性。建立索引主要是为了提高查询速度，因为索引能大大减少扫描的数据量；不过在数据量很小或更新频繁的场景下，过多的索引反而会拖慢写操作和修改速度。”

🌈 面试官：

“关于锁，你能简单描述一下常见的锁有哪些，它们的应用场景又有何不同吗？”

💬 小基：

“常见的锁主要有互斥锁、读写锁、自旋锁和信号量。互斥锁用于保护临界区，只允许一个线程访问；读写锁允许多个线程同时读，但写操作时必须独占；自旋锁适用于锁持有时间极短的情况下，避免线程切换开销；信号量则可以控制对多个资源的访问权限，常用于实现资源池等场景。”

🌈 面试官：

“最后还有两道手撕题。第一道题是：给定一个包含n个数的数组，请求出两个不相交区间，使得这两个区间内的数之和最大，并输出这个最大值。第二道题是：根据实际场景构造一个有向图，然后求出图中的最长路径。你会如何思考和实现这两道题？”

💬 小基：

“关于第一个手撕题，我会考虑先用一次遍历或者预处理，计算出各个可能区间的最大子数组和，再利用分治的思路或动态规划来确定最佳的两个不相交区间，使得整体和最大。这个问题核心在于如何快速地更新和查询区间最优解。至于第二个题目，我会先将实际情况抽象为一个有向图，确认没有环后利用拓扑排序的方法，再结合动态规划求得每个节点的最长路径，从而最终求出全局最长路径。如果遇到环存在，则需要先做环检测，然后使用改进后的算法解决。”