快手C++ 二面凉经

都什么奇奇怪怪的问题

关于10，每次递归处理小的部分，然后大的部分用类似消除尾递归的方式做是否可行

因为是尾递归，用栈？😂哈人

快拍的时间复杂度取决于数据的有序程度，比如987654321，这种如果将第一个作为分割线，则需要每次都将前i-1个元素移到前面，时间复杂度就会来到n^2，所以我们可以随机取一个分界点，或者说取中间元素作为分界，很大程度避免这种问题。（不过看面试官好像不是这个意思。。）

所以虚函数查表的时间复杂度是多少

gpt生成的，看看如何 快速排序的递归实现可能会导致在最坏情况下达到 \(O(n)\) 的空间复杂度。为了确保空间复杂度在最坏情况下为 \(O(\log n)\)，我们可以使用迭代（而不是递归）以及一种称为尾递归消除（Tail Recursion Elimination）的技巧。 快速排序的基本思想是每次选择一个基准值并将数组划分为两部分：小于基准值的元素和大于基准值的元素。通常，我们会递归地对这两部分进行排序。 但要保证空间复杂度为 \(O(\log n)\)，我们可以采取以下策略： 1. **迭代排序小的部分，手动排序大的部分**: 每次分区后，使用递归或迭代对较小的部分进行排序，并手动处理（例如使用循环）较大的部分。 2. **使用栈代替递归**: 使用一个栈来存储待排序的数组部分的索引。首先，将整个数组的开始和结束索引入栈。然后，在每次迭代中，从栈中弹出一个范围，对它进行分区，然后将较小的部分和较大的部分的索引入栈。 具体算法如下： 1. 初始化一个栈，将数组的开始和结束索引入栈。 2. 只要栈不为空，执行以下步骤： a. 弹出一个范围（即开始和结束索引）。 b. 对该范围进行分区，并获取基准值的位置。 c. 先将较小的部分的开始和结束索引入栈，再将较大的部分的开始和结束索引入栈。 此方法确保了我们始终先处理较小的部分，从而确保栈的深度最多为 \(O(\log n)\)。 这种方法结合了快速排序的原理和迭代的思想，使得空间复杂度在最坏情况下为 \(O(\log n)\)。

你这是音视频部门吗，这面试风格，好像我二面面试官

6. 如何实现动态多态：在C++中，通过在基类中将函数声明为虚函数，然后在派生类中重写该函数，就可以实现动态多态。当使用基类指针或引用来调用虚函数时，会根据所指向的实际对象的类型来决定调用的函数版本。 7. 虚函数表查表的时间复杂度：虚函数表是一个存储虚函数地址的数据结构，它由编译器在类的布局中创建。虚函数表的查表操作是通过在对象中的虚函数表中查找函数地址然后进行调用的。因为虚函数表是一个固定大小的数组，所以查表的时间复杂度为O(1)。 9. 快排的时间复杂度和空间复杂度：快速排序的时间复杂度取决于划分的平衡性，最坏情况下是O(n^2)，平均情况下是O(nlogn)。空间复杂度是O(logn)用于存储递归调用时的栈空间。 10. 如何降低快排的空间复杂度：要降低快速排序的空间复杂度，可以使用迭代代替递归，将递归调用转换为循环。通过维护一个栈或队列模拟递归调用时的栈帧，可以以迭代的方式完成快速排序，并降低空间复杂度为O(logn)。

8. 快排示例代码： ```cpp #include <iostream> (30316)#include <vector> int partition(std::vector<int>&amp; arr, int low, int high) { int pivot = arr[high]; int i = low - 1; for (int j = low; j < high; j++) { if (arr[j] < pivot) { i++; std::swap(arr[i], arr[j]); } } std::swap(arr[i + 1], arr[high]); return i + 1; } void quickSort(std::vector<int>&amp; arr, int low, int high) { if (low < high) { int pi = partition(arr, low, high); quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high); } } int main() { std::vector<int> arr = {8, 4, 2, 7, 1, 5, 9}; int n = arr.size(); quickSort(arr, 0, n - 1); std::cout << "Sorted array:"; for (auto num : arr) { std::cout << " " << num; } std::cout << std::endl; return 0; } ```

来我厂一试

怎么感觉一个面试官。。。我也是让降复杂度到logn

问的问题都比较活呀，不太八股，哈哈。 这不卡学历-->https://www.nowcoder.com/share/jump/33433063816925

佬，有后续嘛，过了吗

可以试试我司，多个offer多个argue，c++ 嵌入式 硬件 前后端 hc都挺充裕的～

第十题很简单，只要保证在大于等于的时候都会发生交换就行

7. 虚函数查表的复杂度：这肯定不是cpp标准要求的东西了，个人主观上来说，复杂度应该是O(1)级别，直接根据索引查找函数地址； 10. 快排：面试官不太会举例子，寻常二分（比如快速幂）和快排那能一样么？快排这种机制就是要自顶向下的；如果说降低递归深度的话，可以参考标准库的实现，即如果递归深度太多或者序列较短的时候，采用插入排序

兄弟，试试光伏电池行业～