C++闯关手册 - 面试实例：第一轮面试

C++ 闯关手册 - 面试实例

第一面：基础面试

1）自我介绍

每一个面试都会有个自我介绍，这里省略，基本面试几次自己都会说的比较溜了。面试官是有可能根据你的介绍内容进行提问的，这里介绍的时候可以根据情况引导面试官。

2）C++11的新特性有哪些？

简单回答：智能指针、auto、for range、lamada、初始化列表等；
详细回答如下：

C++11是C++语言的一个重要版本，它引入了许多新特性以增强语言的功能性和易用性。以下是一些主要的C++11特性：

1. 自动类型推断（auto）：auto关键字可以让编译器自动推断变量的类型。

   auto a = 1; // a is an integer
   

2. 范围for循环（Range-based for loops）：这种新的for循环语法可以更简洁地遍历容器。

   std::vector<int> v = {1, 2, 3, 4, 5};
   for(auto i : v)
       std::cout << i << ' ';
   

3. nullptr：nullptr是一个新的关键字，用于表示空指针，以替代C++03中的NULL。

   int* p = nullptr;
   

4. 初始化列表（Initializer lists）：初始化列表提供了一种统一的初始化语法。

   std::vector<int> v = {1, 2, 3, 4, 5};
   

5. Lambda表达式（Lambda expressions）：Lambda表达式是一种创建匿名函数对象的方式。

   auto f = [](int a, int b) -> int { return a + b; };
   

6. 智能指针（Smart pointers）：C++11引入了unique_ptr、shared_ptr和weak_ptr等智能指针，以便更好地管理内存。

   std::unique_ptr<int> p(new int(5));
   

7. 多线程支持（Multithreading support）：C++11在标准库中增加了对多线程编程的支持。

8. 移动语义和右值引用（Move semantics and Rvalue references）：这两个特性可以提高程序的性能，减少不必要的拷贝。

9. 静态断言（Static assertions）：static_assert可以在编译时进行断言。

10. 类型推导（Type inference）：decltype关键字可以推导出表达式的类型。

3）C++智能指针有哪些？原理是什么？

C++11中主要有三种智能指针：std::unique_ptr，std::shared_ptr和std::weak_ptr。

1. std::unique_ptr：std::unique_ptr是一种独占所有权的智能指针，即在任何时刻，只能有一个std::unique_ptr指向给定的对象。std::unique_ptr通过禁止复制构造和复制赋值来实现独占所有权的语义。但你可以使用std::move来转移所有权。std::unique_ptr在其析构函数中删除其所指向的对象，这样可以避免内存泄漏和其他资源管理问题。std::unique_ptr还支持自定义删除器，这可以让你自定义资源的清理方式。
2. std::shared_ptr：std::shared_ptr是一种共享所有权的智能指针，即多个std::shared_ptr可以指向同一个对象。std::shared_ptr通过引用计数来实现共享所有权的语义。每当一个std::shared_ptr被复制时，引用计数就会增加。当std::shared_ptr被删除或者离开其作用域时，引用计数就会减少。只有当引用计数降为0时，其所指向的对象才会被删除。std::shared_ptr也支持自定义删除器。
3. std::weak_ptr：std::weak_ptr是一种不控制所有权的智能指针，它可以观察std::shared_ptr，但不会增加其引用计数。std::weak_ptr主要用来解决std::shared_ptr的循环引用问题。你不能直接使用std::weak_ptr来访问其所观察的对象，但你可以使用std::weak_ptr::lock或std::weak_ptr::expired来获取一个std::shared_ptr。

这些智能指针的设计目标是为了提供一种自动管理资源的方式，避免内存泄漏和其他资源管理问题。同时，它们也提供了灵活的所有权语义，可以满足不同的使用场景。

template<typename T>
class SharedPtr;

template<typename T>
class WeakPtr {
public:
    WeakPtr() : ptr_(nullptr), control_block_(nullptr) {}

    WeakPtr(const SharedPtr<T>& sp) : ptr_(sp.ptr_), control_block_(sp.control_block_) {
        if (control_block_) {
            control_block_->weak_count_++;
        }
    }

    ~WeakPtr() {
        if (control_block_ && --control_block_->weak_count_ == 0 && control_block_->shared_count_ == 0) {
            delete control_block_;
        }
    }

    bool expired() const {
        return control_block_ == nullptr || control_block_->shared_count_ == 0;
    }

    SharedPtr<T> lock() const {
        if (expired()) {
            return SharedPtr<T>();
        } else {
            return SharedPtr<T>(*this);
        }
    }

private:
    T* ptr_;
    ControlBlock* control_block_;

    friend class SharedPtr<T>;
};

template<typename T>
class SharedPtr {
public:
    SharedPtr(T* ptr) : ptr_(ptr), control_block_(new ControlBlock) {
        control_block_->shared_count_ = 1;
    }

    SharedPtr(const WeakPtr<T>& wp) : ptr_(wp.ptr_), control_block_(wp.control_block_) {
        if (control_block_) {
            control_block_->shared_count_++;
        }
    }

    ~SharedPtr() {
        if (--control_block_->shared_count_ == 0) {
            delete ptr_;
            if (control_block_->weak_count_ == 0) {
                delete control_block_;
            }
        }
    }

private:
    T* ptr_;
    ControlBlock* control_block_;

    struct ControlBlock {
        int shared_count_;
        int weak_count_ = 0;
    };

    friend class WeakPtr<T>;
};

这个例子中的`weak_ptr`和`shared_ptr`都是模板类，可以用于任何类型的对象。`weak_ptr`和`shared_ptr`共享一个控制块，其中包含了共享的引用计数和弱引用计数。当`shared_ptr`的引用计数降为0时，它会删除其所指向的对象。当`weak_ptr`的引用计数也降为0时，它会删除控制块。

4）介绍下C++的多态

在C++中，多态是面向对象编程的一个重要特性，它允许我们通过基类指针来操作派生类对象。多态分为两种：编译时多态（静态多态）和运行时多态（动态多态）。

1. 编译时多态：通过函数重载和运算符重载实现。在编译时，编译器会根据参数类型和数量决定调用哪个函数。
2. 运行时多态：通过虚函数和纯虚函数实现。在运行时，根据对象的实际类型来决定调用哪个函数。这是通过虚表（vtable）和虚表指针（vptr）来实现的。

虚表是一个存储类中虚函数地址的表，每个包含虚函数的类都有一个虚表。虚表指针是一个指向虚表的指针，每个对象都有一个虚表指针。

当我们通过基类指针调用虚函数时，编译器会先通过虚表指针找到虚表，然后在虚表中查找虚函数的地址，最后调用该函数。这个过程是在运行时完成的，因此称为运行时多态。

以下是一个简单的示例：

class Base {
public:
    virtual void print() {
        cout << "Base" << endl;
    }
};

class Derived : public Base {
public:
    void print() override {
        cout << "Derived" << endl;
    }
};

int main() {
    Base* ptr = new Derived();
    ptr->print();  // 输出 "Derived"
    delete ptr;
    return 0;
}

在这个示例中，print函数是虚函数，当我们通过基类指针ptr调用print函数时，实际上调用的是派生类Derived的print函数。这就是运行时多态的一个例子。

5）构造函数能被声明为虚函数吗，为什么？

在C++中，构造函数不能被声明为虚函数。

这是因为虚函数依赖于对象的虚表指针（vptr）来进行动态绑定，而这个虚表指针是在构造函数中初始化的。当我们创建一个对象时，首先会调用构造函数，这时对象的虚表指针还没有被初始化，所以我们不能在构造函数中使用虚函数机制。

另外，虚函数主要用于实现多态，允许我们通过基类指针来调用派生类的函数。但是，构造函数和析构函数是特殊的函数，它们不是为了被派生类重写的，而是为了初始化和清理对象的。构造函数是用来创建对象的，它决定了对象的初始状态，而析构函数是用来销毁对象的，它负责清理对象占用的资源。

因此，构造函数不能被声明为虚函数。

6）析构函数需要被声明为虚函数吗，为什么？

在C++中，析构函数可以并且在某些情况下应该被声明为虚函数。

当我们通过基类指针删除派生类对象时，如果基类的析构函数不是虚函数，那么只有基类的析构函数会被调用，派生类的析构函数不会被调用，这可能会导致资源泄漏。

如果基类的析构函数是虚函数，那么在删除派生类对象时，首先会调用派生类的析构函数，然后再调用基类的析构函数。这样就可以确保对象的资源被正确地清理。

以下是一个简单的示例：

class Base {
public:
    virtual ~Base() {
        cout << "Base Destructor" << endl;
    }
};

class Derived : public Base {
public:
    ~Derived() {
        cout << "Derived Destructor" << endl;
    }
};

int main() {
    Base* ptr = new Derived();
    delete ptr;  // 输出 "Derived Destructor" 和 "Base Destructor"
    return 0;
}

在这个示例中，Base类的析构函数是虚函数，所以在删除Derived对象时，首先调用Derived的析构函数，然后再调用Base的析构函数。这就是虚析构函数的作用。

7）new和malloc的区别

new和malloc都是用于在堆上分配内存的，但它们之间有几个主要的区别：

1. 调用构造函数和析构函数：new不仅会分配内存，还会调用对象的构造函数。同样，delete不仅会释放内存，还会调用对象的析构函数。而malloc和free只负责分配和释放内存，不会调用构造函数和析构函数。
2. 返回类型：new返回的是指定类型的指针，不需要类型转换。而malloc返回的是void*，通常需要进行类型转换。
3. 错误处理：如果内存分配失败，new会抛出std::bad_alloc异常，而malloc则返回NULL。
4. 分配数组：new[]和delete[]可以用于分配和删除数组，它们会自动调用构造函数和析构函数。而malloc和free则需要手动计算数组的大小。

以下是一个简单的示例：

// 使用 new 和 delete
int* p1 = new int(10);  // 分配内存并初始化为10
delete p1;  // 释放内存

// 使用 malloc 和 free
int* p2 = (int*)malloc(sizeof(int));  // 分配内存
*p2 = 10;  // 初始化为10
free(p2);  // 释放内存

在这个示例中，new和delete不仅分配和释放了内存，还自动调用了构造函数和析构函数。而malloc和free则只负责分配和释放内存。

8）new底层是用什么实现的？

在C++中，new操作符的底层实现通常依赖于一种名为operator new的函数。这是一个可以被重载的全局函数，其默认实现通常使用C语言的malloc函数来分配内存。

当你使用new操作符创建一个对象时，实际上发生了两步操作：

1. 首先，new操作符调用operator new函数来分配足够的内存。这个函数的默认实现通常使用malloc函数。
2. 然后，new操作符在分配的内存上调用对象的构造函数来初始化对象。

在C++中，你可以重载operator new和operator delete来自定义对象的内存分配和释放行为。以下是一个简单的示例：

class MyClass {
public:
    MyClass() {
        cout << "Constructor is called" << endl;
    }

    ~MyClass() {
        cout << "Destructor is called" << endl;
    }

    // 重载 operator new
    static void* operator new(size_t size) {
        cout << "operator new is called" << endl;
        void* p = malloc(size);  // 使用 malloc 分配内存
        return p;
    }

    // 重载 operator delete
    static void operator delete(void* p) {
        cout << "operator delete is called" << endl;
        free(p);  // 使用 free 释放内存
    }
};

int main() {
    MyClass* p = new MyClass();  // 输出 "operator new is called" 和 "Constructor is called"
    delete p;  // 输出 "Destructor is called" 和 "operator delete is called"
    return 0;
}

在这个示例中，我们重载了MyClass的operator new和operator delete。当我们使用new MyClass()创建一个MyClass对象时，首先调用重载的operator new来分配内存，然后在分配的内存上调用MyClass的构造函数。当我们使用delete删除对象时，首先调用MyClass的析构函数，然后调用重载的operator delete来释放内存。

需要注意的是，operator new和operator delete必须是静态的，因为它们在对象创建和删除时被调用，这时对象可能还不存在或已经不存在了。

9）new实现需要类型转换吗？

在C++中，new操作符的实现不需要类型转换。当你使用new操作符创建一个对象时，new操作符会自动返回正确类型的指针。

例如，如果你使用new int创建一个整数，new操作符会返回一个int*指针。如果你使用new MyClass创建一个MyClass对象，new操作符会返回一个MyClass*指针。你不需要进行任何类型转换。

以下是一个简单的示例：

int* p1 = new int;  // 创建一个整数，返回 int* 指针

class MyClass {};
MyClass* p2 = new MyClass;  // 创建一个 MyClass 对象，返回 MyClass* 指针

在这个示例中，new操作符自动返回了正确类型的指针，我们不需要进行任何类型转换。

然而，如果你在重载operator new时使用了malloc函数，你需要进行类型转换，因为malloc返回的是void*指针。例如：

class MyClass {
public:
    static void* operator new(size_t size) {
        void* p = malloc(size);  // malloc 返回 void* 指针
        return p;  // 我们需要返回 void* 指针，new 操作符会自动进行类型转换
    }
};

在这个示例中，我们在operator new中使用了malloc函数，所以我们需要返回void*指针。但是，当我们使用new MyClass创建一个MyClass对象时，new操作符会自动将void*指针转换为MyClass*指针，我们不需要进行任何类型转换。

10）调用析构函数的时候类型是void类型，指向的是类对象，会正确调用析构函数吗？ 怎么调用？使用地址吗？

如果你有一个 void* 指针，指向一个对象，然后尝试通过这个指针调用该对象的析构函数，这是不安全的，也是不正确的。void* 指针是一个通用指针类型，它不知道它所指向的对象的实际类型，因此也就无法知道应该调用哪个析构函数。

在C++中，如果你需要删除一个通过 new 创建的对象，你应该使用正确的类型的指针来调用 delete，这样就会自动调用正确的析构函数。例如：

class MyClass {
public:
    ~MyClass() {
        // 析构函数的实现
    }
};

MyClass* obj = new MyClass();
delete obj;  // 这将调用 MyClass 的析构函数

如果你只有一个 void* 指针，你需要先将它转换回正确的类型，然后再调用 delete：

void* ptr = new MyClass();
delete static_cast<MyClass*>(ptr);  // 这将调用 MyClass 的析构函数

class MyClass {
public:
    ~MyClass() {
        // 析构函数的实现
    }
};

MyClass* obj = new MyClass();
obj->~MyClass();  // 显式调用析构函数

operator delete(obj);  // 释放内存

delete obj;  // 调用析构函数并释放内存

11）vector/list/map的底层实现，增删改查复杂度

C++ STL中的vector、list和map的底层实现和操作复杂度如下：

1. vector：vector是一个动态数组，其底层实现是一个连续的内存块。因此，它支持随机访问，访问元素的时间复杂度是O(1)。添加元素到末尾的时间复杂度也是O(1)，但如果内存不足，需要重新分配内存，那么时间复杂度就变成了O(n)。删除末尾元素的时间复杂度是O(1)，但删除中间元素的时间复杂度是O(n)，因为需要移动元素。
2. list：list是一个双向链表，其底层实现是一系列的节点，每个节点包含一个元素和两个指向前后节点的指针。因此，它不支持随机访问，访问元素的时间复杂度是O(n)。但添加和删除元素的时间复杂度都是O(1)，因为只需要改变指针。
3. map：map是一个平衡二叉搜索树（通常是红黑树），其底层实现是一系列的节点，每个节点包含一个键值对和两个指向左右子节点的指针。因此，它支持按键排序和快速查找，查找、添加和删除元素的时间复杂度都是O(log n)。

以上是这三种数据结构的基本操作的时间复杂度，但实际的性能可能会受到许多因素的影响，比如内存分配和缓存效果等。

12）const关键字，const怎么修改？

在C++中，const关键字的主要作用是声明一个常量，也就是说，一旦被初始化，就不能再改变其值。例如：

const int a = 10;

在这个例子中，a是一个常量，你不能再改变它的值。

此外，const关键字还有以下几个作用：

1. 修饰函数参数：当函数参数被声明为const时，意味着这个参数在函数内部不能被修改。这可以防止函数意外地修改参数的值。

void foo(const int a) {
    // a = 10;  // 这是错误的，因为a是const的
}

2. 修饰函数：当成员函数被声明为const时，意味着这个函数不能修改类的任何成员变量（除非这个成员变量是mutable的）。这可以保证这个函数不会改变对象的状态。

class MyClass {
public:
    int a;
    mutable int b;
    void foo() const {
        // a = 10;  // 这是错误的，因为foo是const的
        b = 20; //这是合法的
    }
};

3. 修饰指针：当指针被声明为const时，可以防止通过这个指针来修改指向的值。例如：

int a = 10;
const int* p = &a;
// *p = 20;  // 这是错误的，因为p是一个指向const的指针

在这个例子中，p是一个指向const int的指针，你不能通过p来修改a的值。然而，有时候我们可能需要修改一个const变量的值。这时，我们可以使用const_cast来移除变量的const属性。例如：

const int a = 10;
int* p = const_cast<int*>(&a);
*p = 20;

在这个例子中，我们首先使用const_cast将a的地址转换为一个非const的指针，然后通过这个指针来修改a的值。

注意
这种做法是非常危险的，因为它破坏了const的语义，可能会导致未定义的行为。在实际编程中，我们应该尽量避免修改const变量的值。如果你需要修改一个变量的值，那么你应该在声明这个变量时不要使用const关键字

13）进程和线程的同步方法和效率，哪种效率最高，为什么?

进程间同步

进程间同步用于协调多个进程之间的操作，确保它们共享资源或数据的一致性。常用的进程间同步方法包括：

1. 管道（Pipe）：管道是一种单向数据传输方式，数据从一个进程流向另一个进程。它类似于水管，数据只能从一个方向流动。管道通常用于父子进程之间或具有亲缘关系的进程之间通信。效率一般，因为数据只能单向流动，并且管道的大小有限。
2. 消息队列（Message Queue）：消息队列是一种存储消息的容器，进程可以向队列中发送消息，其他进程可以从队列中读取消息。消息队列允许非父子进程之间通信，但通信模式是异步的，即发送消息的进程不会立即收到接收进程的响应。效率较高，因为消息队列可以存储大量数据，并且允许多个进程同时读写消息队列。
3. 共享内存（Shared Memory）：共享内存是一块物理内存区域，多个进程可以同时访问。共享内存提供最快的数据传输速度，但需注意同步和数据一致性问题，因为多个进程可以同时修改共享内存中的数据。效率最高，但需谨慎使用，否则可能导致数据损坏或死锁。
4. 信号量（Semaphore）：信号量是一种用于控制资源访问的计数器。信号量可以防止多个进程同时访问同一资源，并允许进程间通信。效率中等，因为信号量需要原子操作来保证线程安全。
5. 套接字（Socket）：套接字用于不同机器上的进程通信。套接字是一种网络通信协议，可以可靠地传输数据。效率取决于网络状况，如果网络延迟高或带宽不足，则套接字的效率会降低。
6. 信号（Signal）：信号是一种轻量级的通信方式，用于通知进程事件。信号可以用于进程间通信，但语义简单，只传递有限的信息。效率较高，但需注意信号的处理机制。

选择进程间同步方法取决于以下因素：

• 数据复杂度：如果需要传输复杂数据，可能需要更复杂的同步机制，如共享内存或消息队列。
• 进程关系：亲缘进程可以使用简单机制，如管道，非亲缘进程需要更通用机制，如消息队列或套接字。
• 同步需求：如果需要严格的同步控制，可能需要更强的机制，如信号量或互斥锁。如果不需要严格的同步控制，可以使用简单机制，如信号。
• 性能需求：如果对性能有高要求，可能需要更快的机制，如共享内存。如果对性能要求不高，可以使用简单机制，如管道或信号。
• 跨机器通信：如果进程需要在不同的机器上进行通信，则需要支持网络通信的机制，如套接字。

线程间同步

线程间同步用于协调同一进程内多个线程之间的操作，确保它们共享资源或数据的一致性。常用的线程间同步方法包括：

1. 互斥锁（Mutex）：互斥锁用于保护共享资源，一次只能有一个线程访问。互斥锁是线程同步中最常用的方法，但容易造成锁竞争，即多个线程同时尝试获取同一个锁。效率中等，但易造成锁竞争。
2. 读写锁（Read-Write Lock）：读写锁允许多个线程同时读，但写时只能有一个线程操作。读写锁适用于读多写少的场景，可以提高读操作的并发性。效率较高，但需注意读写锁的升级和降级。
3. 条件变量（Condition Variable）：条件变量用于线程等待特定条件满足。条件变量通常与互斥锁一起使用，用于线程等待锁的释放或特定事件的发生。效率中等，但需注意条件变量的唤醒机制。
4. 信号量（Semaphore）：信号量在多线程环境下与进程间信号量类似，用于控制资源访问。信号量可以防止多个线程同时访问同一资源，并允许线程间通信。效率中等，但需注意信号量的初始化和操作。
5. 屏障（Barrier）：屏障使一组线程在特定点同步。屏障通常用于需要所有线程都完成特定任务后再继续的场景。效率较低，但可实现很好的同步效果。
6. 原子操作（Atomic Operation）：原子操作是不可中断的操作，用于保护单个变量的访问。原子操作是效率最高的。

选择线程间同步方法取决于以下因素：

• 锁竞争程度：高竞争需要更有效的机制，如自旋锁或无锁机制。
• 锁保护范围：尽量减小锁的保护范围，提高效率。
• 锁类型：根据竞争情况选择合适的锁类型，如自旋锁、互斥锁等。
• 等待策略：忙等待消耗CPU，睡眠等待延迟较高，需权衡选择。

总体而言，原子操作是效率最高的同步方法，因为它避免了锁竞争和上下文切换的开销。但是，原子操作仅适用于保护单个变量，对于更复杂的数据结构或同步需求，其他方法可能更合适。

以下是一些提高同步效率的建议：

• 尽量减少锁的使用范围和时间：只在必要时加锁，并尽快解锁。
• 使用无锁机制：当锁竞争激烈时，可以考虑使用无锁机制，如CAS（Compare And Swap）操作。
• 选择合适的锁类型：根据竞争情况选择合适的锁类型，如自旋锁、互斥锁等。
• 合理设计同步算法：避免不必要的等待和唤醒。

14）算法题：求链表的第K个节点，写测试用例测试

要获取链表的第K个节点，我们可以使用一个简单的迭代方法。首先，我们创建一个指针，让它指向链表的头部。然后，我们将这个指针向前移动K-1次。如果我们能够这样做，那么这个指针现在就指向第K个节点。如果链表的长度小于K，那么在尝试移动指针时，我们将达到链表的尾部，此时我们应该返回一个错误或者null。

以下是这个思路的C++实现：

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

ListNode* findKthNode(ListNode* head, int k) {
    ListNode* node = head;
    for (int i = 0; i < k - 1; ++i) {
        if (node == NULL) {
            return NULL;  // 链表长度小于k
        }
        node = node->next;
    }
    return node;
}

然后，我们可以编写一些测试用例来测试这个函数：

int main() {
    // 创建一个链表：1 -> 2 -> 3 -> 4 -> 5
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = new ListNode(5);

    // 测试用例1：获取第3个节点
    ListNode* node = findKthNode(head, 3);
    if (node != NULL) {
        cout << "The 3rd node is: " << node->val << endl;  // 应该输出：3
    } else {
        cout << "The 3rd node does not exist." << endl;
    }

    // 测试用例2：获取第6个节点
    node = findKthNode(head, 6);
    if (node != NULL) {
        cout << "The 6th node is: " << node->val << endl;
    } else {
        cout << "The 6th node does not exist." << endl;  // 应该输出：不存在
    }

    return 0;
}

ListNode* findKthNode(ListNode* head, int k) {
    if(k<=0)  return NULL;
    ListNode* fast = head;
    ListNode* slow = head;

    for (int i = 0; i < k; ++i) {
        if (fast == NULL) {
            return NULL;  // 链表长度小于k
        }
        fast = fast->next;
    }

    while (fast != NULL) {
        fast = fast->next;
        slow = slow->next;
    }

    return slow;
}

15）算法题：数组的TOPK，给一个数组，求数组的前K个小的数字并返回

这是一个经典的问题，可以使用优先队列（堆）来解决。我们可以创建一个大顶堆，然后遍历数组，将每个元素加入堆中。如果堆的大小超过了K，我们就从堆中删除最大的元素。这样，当我们遍历完数组后，堆中就包含了前K个最小的元素。

以下是解决这个问题的C++代码：

#include <vector>
#include <queue>

std::vector<int> topK(std::vector<int>& nums, int k) {
    std::priority_queue<int> pq;
    for (int num : nums) {
        pq.push(num);
        if (pq.size() > k) {
            pq.pop();
        }
    }

    std::vector<int> res;
    while (!pq.empty()) {
        res.push_back(pq.top());
        pq.pop();
    }
    std::reverse(res.begin(), res.end());
    return res;
}

这个函数接受一个整数数组和一个整数K作为输入，返回一个包含数组中前K个最小元素的向量。注意，返回的结果可能不是按照原始数组中的顺序。

#include <vector>
#include <algorithm>

int findKthSmallest(std::vector<int>& nums, int k) {
    int left = 0, right = nums.size() - 1;
    while (true) {
        int pos = partition(nums, left, right);
        if (pos == k - 1) {
            return nums[pos];
        }
        if (pos > k - 1) {
            right = pos - 1;
        } else {
            left = pos + 1;
        }
    }
}

int partition(std::vector<int>& nums, int left, int right) {
    int pivot = nums[left], l = left + 1, r = right;
    while (l <= r) {
        if (nums[l] > pivot && nums[r] < pivot) {
            std::swap(nums[l], nums[r]);
        }
        if (nums[l] <= pivot) {
            l++;
        }
        if (nums[r] >= pivot) {
            r--;
        }
    }
    std::swap(nums[left], nums[r]);
    return r;
}

#include <vector>
#include <algorithm>

void quickSort(std::vector<int>& nums, int left, int right) {
    if (left < right) {
        int pivot = partition(nums, left, right);
        quickSort(nums, left, pivot - 1);
        quickSort(nums, pivot + 1, right);
    }
}

int partition(std::vector<int>& nums, int left, int right) {
    int pivot = nums[right];
    int i = left;
    for (int j = left; j < right; j++) {
        if (nums[j] < pivot) {
            std::swap(nums[i], nums[j]);
            i++;
        }
    }
    std::swap(nums[i], nums[right]);
    return i;
}

16）反问环节

一般可以问些岗位、团队相关的，如：面试的岗位会大概负责什么方向？团队在公司的定位及未来的方向？这也是要求职者本质需要关注的问题，团队的问负责人会更好。

忌讳问面试感受类的，这个是后面HR通知你的；