其他
快手秋招C++一二面，超多代码示例!!!
The following article is from 阿Q正砖 Author 阿Q
第一时间收到文章更新
来源 | 阿Q正砖（ID：qq1714320415）
今天继续给大家分享快手C++面经，给了大家非常多的代码示例，在实际应用中可能也会参考到，赶紧收藏起来吧！
其实看面经也是需要有一定基础，在需要的时候作为一个参考罢了，比如说找某公司的C++岗位，但是如果你基础知识一般般，还是建议多看看书，有用的书。
如果你需要面试还在为找面经而烦恼，那你看到我就是找对人了，我给大家分享的不仅是面经题目，还有参考答案和答法。其实大家都知道，计算机本来就是门科学，本就有它精确的答案，我们只是在表述上不一样而已，所以你有了一定的基础知识后，更重要的是回答问题的一些技巧和方法。
一面
C++：
1、派生类继承基类时、虚函数表内的函数是何时替换的？
在C++中，当派生类继承基类时，如果基类中有虚函数，派生类可以选择是否覆盖（override）这些虚函数。如果派生类覆盖了基类的虚函数，那么在派生类对象上调用该虚函数时，将会调用派生类中的实现，而不是基类中的实现。这种动态绑定的机制是通过虚函数表（vtable）来实现的。
虚函数表是用来实现动态多态的一种机制，每个包含虚函数的类都有一个对应的虚函数表。在编译阶段，编译器会为每个包含虚函数的类生成一个虚函数表，表中存储了指向各个虚函数实现的指针。当一个类被实例化时，会在对象的内存布局中分配一个指向其虚函数表的指针（通常被称为虚表指针或vptr），这样就能在运行时实现动态绑定。
当派生类继承基类时，如果派生类覆盖了基类的虚函数，编译器会在派生类的虚函数表中将该虚函数的指针指向派生类中的实现。这样，当通过基类指针或引用调用虚函数时，实际上会根据对象的实际类型在运行时查找对应的虚函数表，并调用正确的虚函数实现。
2、指向派生类的基类指针、强转为 void* 再转为基类指针、此时调用虚函数会发生什么（正常）？
转换为 void*：当将指向派生类的基类指针强制转换为void*类型时，指针的类型信息会丢失，但指针仍然指向原来的对象。再转换回基类指针：当将 void*类型的指针转换回基类指针时，编译器会进行一次静态类型转换。这意味着编译器会假定这个指针是指向基类对象的，而不考虑它原本指向派生类对象。调用虚函数：如果这个基类中的虚函数在派生类中被覆盖（override），那么在运行时，由于编译器在转换回基类指针时假定这个指针指向的是基类对象，因此调用虚函数时会根据基类的虚函数表来确定调用哪个函数。这意味着即使实际上这个指针指向的是派生类对象，也会调用基类中的虚函数实现，而不是派生类中的实现。
算法：
1、反转链表 [l, r] 区间内的所有节点、返回新链表的头节点
思路：
先创建一个哑节点 dummy，并将其指向原链表的头节点，这样可以处理头节点可能被反转的情况。使用 prev指针找到左边界的前一个节点，然后使用cur指针记录当前需要反转的节点。开始从左边界到右边界进行反转，每次将 cur节点的next指针指向下一个节点的next，然后将下一个节点的next指向反转后的链表头部，最后将prev的next指针指向下一个节点，完成一次反转。返回哑节点的 next，即为新链表的头节点。
参考代码：
#include <iostream>
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
ListNode* reverseBetween(ListNode* head, int left, int right) {
if (left == right) return head; // 如果 left 等于 right，无需反转，直接返回头节点
// 创建一个哑节点作为新链表的头节点，并将其指向原链表的头节点
ListNode* dummy = new ListNode(0);
dummy->next = head;
// 使用 prev 指针来记录左边界的前一个节点
ListNode* prev = dummy;
for (int i = 0; i < left - 1; ++i) {
prev = prev->next;
}
// 使用 cur 指针来记录当前需要反转的节点
ListNode* cur = prev->next;
// 从左边界开始反转到右边界
for (int i = 0; i < right - left; ++i) {
ListNode* next = cur->next; // 先记录下一个节点的指针
cur->next = next->next; // 将当前节点的 next 指针指向下一个节点的 next
next->next = prev->next; // 将下一个节点的 next 指针指向反转后的链表头部
prev->next = next; // 将 prev 的 next 指针指向下一个节点，完成一次反转
}
return dummy->next; // 返回新链表的头节点
}
void printList(ListNode* head) {
while (head) {
std::cout << head->val << " ";
head = head->next;
}
std::cout << std::endl;
}
int main() {
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);
std::cout << "Original List: ";
printList(head);
int left = 2, right = 4;
head = reverseBetween(head, left, right);
std::cout << "Reversed List from " << left << " to " << right << ": ";
printList(head);
return 0;
}
二面
C++ & Webserver：
1、线程池实现步骤？
这里就讲讲正常的一个线程池的实现步骤。
定义任务类：首先需要定义一个任务类，用于封装需要在线程池中执行的任务。任务类至少应该包含一个执行任务的方法，可以是一个函数指针或者是一个函数对象。
class Task {
public:
virtual void execute() = 0;
};
定义线程池类：接下来定义线程池类，其中包含了线程池的管理逻辑，如线程的创建、销毁、任务的添加等。线程池类需要包含一个线程池容器，用于存放线程对象。
#include <vector>
#include <thread>
#include <queue>
#include <mutex>
#include <condition_variable>
class ThreadPool {
public:
ThreadPool(size_t numThreads);
~ThreadPool();
void addTask(Task* task);
private:
std::vector<std::thread> workers; // 线程池中的线程
std::queue<Task*> tasks; // 任务队列
std::mutex queueMutex; // 保护任务队列的互斥量
std::condition_variable condition; // 用于线程间通信的条件变量
bool stop; // 标志线程池是否停止的标志位
};
实现线程池类的构造函数和析构函数：在构造函数中创建指定数量的线程，并启动这些线程；在析构函数中停止线程池中的所有线程。
ThreadPool::ThreadPool(size_t numThreads) : stop(false) {
for (size_t i = 0; i < numThreads; ++i) {
workers.emplace_back([this] {
while (true) {
Task* task = nullptr;
{
std::unique_lock<std::mutex> lock(queueMutex);
condition.wait(lock, [this] { return stop || !tasks.empty(); });
if (stop && tasks.empty()) return;
task = tasks.front();
tasks.pop();
}
task->execute();
delete task;
}
});
}
}
ThreadPool::~ThreadPool() {
{
std::unique_lock<std::mutex> lock(queueMutex);
stop = true;
}
condition.notify_all();
for (std::thread& worker : workers) {
worker.join();
}
}
实现添加任务的方法：在线程池类中添加一个方法用于向任务队列中添加任务。
void ThreadPool::addTask(Task* task) {
{
std::unique_lock<std::mutex> lock(queueMutex);
tasks.push(task);
}
condition.notify_one();
}
使用线程池：最后，在主程序中使用定义好的线程池类来执行任务。
int main() {
ThreadPool pool(4); // 创建一个包含4个线程的线程池
// 添加任务到线程池
for (int i = 0; i < 8; ++i) {
pool.addTask(new YourTask()); // YourTask 是需要执行的任务类
}
// ...
return 0;
}
2、存放线程执行任务的结构体或者类型是什么？（std::function）
在一个线程池中，通常需要一个结构体或者类型来表示线程执行的任务。这个结构体或者类型需要包含执行任务的信息，比如任务的具体内容、状态等。在C++中，可以使用函数指针、std::function 或者自定义的函数对象来表示任务。
来个例子：
#include <functional>
// 使用 std::function 来表示任务
struct Task {
std::function<void()> function;
// 构造函数
Task(const std::function<void()>& f) : function(f) {}
// 执行任务的方法
void execute() {
if (function) {
function();
}
}
};
3、线程 A 如何向线程 B 发起异步请求并获取到处理结果、接口是什么？
在 C++ 中，线程 A 可以向线程 B 发起异步请求并获取处理结果的一种常见方式是使用 std::future 和 std::promise。这种方法允许线程 A 发起异步任务，并在需要时等待线程 B 完成任务并获取结果。
使用 std::future 和 std::promise 实现线程 A 向线程 B 发起异步请求并获取处理结果的简单示例：
#include <iostream>
#include <future>
#include <thread>
void asyncTask(std::promise<int>& promiseObj) {
// 模拟一个耗时的异步任务
std::this_thread::sleep_for(std::chrono::seconds(2));
// 设置 promise 的值，表示任务完成
promiseObj.set_value(42);
}
int main() {
// 创建一个 promise 对象和一个 future 对象
std::promise<int> promiseObj;
std::future<int> futureObj = promiseObj.get_future();
// 在另一个线程中执行异步任务
std::thread worker(asyncTask, std::ref(promiseObj));
worker.detach(); // 让 worker 线程在后台运行
// 在主线程中等待异步任务的结果
std::cout << "Waiting for result..." << std::endl;
int result = futureObj.get(); // 阻塞等待任务完成并获取结果
std::cout << "Result: " << result << std::endl;
return 0;
}
示例中，线程 A（主线程）创建了一个 std::promise 对象 promiseObj 和一个与之关联的 std::future 对象 futureObj。然后，线程 A 启动了一个新的线程（线程 B），并将 promiseObj 作为参数传递给异步任务函数 asyncTask。异步任务函数中通过 promiseObj.set_value() 设置了异步任务的结果。
在主线程中，通过 futureObj.get() 方法阻塞等待异步任务的完成，并获取到任务的结果。这样，线程 A 就能够向线程 B 发起异步请求并获取处理结果了。
4、介绍一下智能指针？
std::unique_ptr：
std::unique_ptr用于管理独占所有权的对象，即同一时间只能有一个std::unique_ptr指向一个对象。当 std::unique_ptr被销毁时，它所指向的对象也会被销毁，这样可以确保资源的正确释放。std::unique_ptr不支持拷贝和赋值操作，但可以通过std::move来转移所有权。适合用于管理局部对象或者作为容器元素的指针。
std::shared_ptr：std::shared_ptr用于管理共享所有权的对象，即多个std::shared_ptr可以指向同一个对象。内部通过引用计数来管理资源的生命周期，当最后一个指向对象的 std::shared_ptr被销毁时，对象会被释放。支持拷贝和赋值操作，内部使用引用计数来追踪对象的引用情况。 适合用于多个对象共享同一资源的情况，比如多个对象共享同一个动态分配的对象。
std::weak_ptr：std::weak_ptr是std::shared_ptr的一种辅助工具，用于解决std::shared_ptr的循环引用问题。std::weak_ptr本身不增加引用计数，它只是观察std::shared_ptr的引用计数，并提供了一种机制来检测对象是否已经被释放。可以通过 std::weak_ptr的lock方法获取一个指向对象的std::shared_ptr，如果对象已经被释放，则返回一个空的std::shared_ptr。适合用于解决 std::shared_ptr循环引用导致的内存泄漏问题。
std::auto_ptr（C++11 之前）：std::auto_ptr用于管理动态分配的对象，在 C++11 中已被废弃，不推荐使用。std::auto_ptr具有独占所有权，不支持拷贝构造和拷贝赋值操作，但支持移动语义。在 C++11 中被 std::unique_ptr替代，因为std::unique_ptr具有更好的语义和性能。
5、了解哪些设计模式？（单例、工厂、建造者）（建议收藏）
这里就简单说一下题主给的这几个设计模式吧。
单例模式
主要用于确保一个类只有一个实例，并提供一个全局访问点来访问该实例。
饿汉式单例模式（线程不安全）：
在类的静态成员变量中直接创建实例，并在类的静态方法中返回该实例。 这种方式在程序启动时就会创建单例对象，无论是否需要使用，可能会导致资源浪费。 不适合在多线程环境下使用，因为没有进行线程安全的处理。
class Singleton {
public:
static Singleton& getInstance() {
static Singleton instance;
return instance;
}
// 防止拷贝构造和赋值操作
Singleton(const Singleton&) = delete;
Singleton& operator=(const Singleton&) = delete;
private:
Singleton() {} // 私有化构造函数，禁止外部创建实例
};
懒汉式单例模式（线程不安全）：
在第一次调用时才创建单例对象，避免了在程序启动时就创建对象的资源浪费。 不适合在多线程环境下使用，因为没有进行线程安全的处理。
class Singleton {
public:
static Singleton& getInstance() {
static Singleton instance;
return instance;
}
// 防止拷贝构造和赋值操作
Singleton(const Singleton&) = delete;
Singleton& operator=(const Singleton&) = delete;
private:
Singleton() {} // 私有化构造函数，禁止外部创建实例
};
懒汉式单例模式（线程安全）：
使用加锁的方式保证在多线程环境下也能正常工作，但会影响性能。 在 getInstance方法中加锁，避免了多个线程同时创建实例的问题。
#include <mutex>
class Singleton {
public:
static Singleton& getInstance() {
std::lock_guard<std::mutex> lock(mutex);
static Singleton instance;
return instance;
}
// 防止拷贝构造和赋值操作
Singleton(const Singleton&) = delete;
Singleton& operator=(const Singleton&) = delete;
private:
Singleton() {} // 私有化构造函数，禁止外部创建实例
static std::mutex mutex;
};
std::mutex Singleton::mutex;
Meyers' Singleton（线程安全）：（不常用）
利用 C++11 的特性，在静态变量的初始化阶段进行初始化，保证了线程安全性。 使用静态局部变量的特性，在第一次调用 getInstance方法时才进行实例化。
class Singleton {
public:
static Singleton& getInstance() {
static Singleton instance;
return instance;
}
// 防止拷贝构造和赋值操作
Singleton(const Singleton&) = delete;
Singleton& operator=(const Singleton&) = delete;
private:
Singleton() {} // 私有化构造函数，禁止外部创建实例
~Singleton() {}
};
工厂模式
主要用于封装对象的创建过程。它通过定义一个工厂类来负责创建产品对象，从而将客户端代码与具体产品的实现解耦。
简单工厂模式（Simple Factory Pattern）：
简单工厂模式通过一个工厂类来创建产品对象，客户端只需要与工厂类交互，而不需要直接与具体产品类交互。 客户端通过调用工厂类的静态方法来创建产品对象，工厂类根据参数的不同来创建不同的产品对象。
// 产品基类
class Product {
public:
virtual void operation() = 0;
virtual ~Product() {}
};
// 具体产品类
class ConcreteProduct : public Product {
public:
void operation() override {
// 具体产品的操作
}
};
// 简单工厂类
class SimpleFactory {
public:
static Product* createProduct() {
return new ConcreteProduct();
}
};
工厂方法模式（Factory Method Pattern）：
工厂方法模式通过定义一个创建产品的接口，每个具体产品都有对应的工厂类负责创建。 客户端通过调用具体工厂类的方法来创建产品对象，不同的工厂类创建不同的产品对象。
// 产品基类
class Product {
public:
virtual void operation() = 0;
virtual ~Product() {}
};
// 具体产品类
class ConcreteProduct : public Product {
public:
void operation() override {
// 具体产品的操作
}
};
// 工厂接口
class Factory {
public:
virtual Product* createProduct() = 0;
virtual ~Factory() {}
};
// 具体工厂类
class ConcreteFactory : public Factory {
public:
Product* createProduct() override {
return new ConcreteProduct();
}
};
抽象工厂模式（Abstract Factory Pattern）：
抽象工厂模式通过定义一组工厂接口来创建一组相关或依赖对象的产品族。 客户端通过选择具体的工厂来获取相应的产品族，不同的工厂可以创建不同的产品族。
// 抽象产品A
class AbstractProductA {
public:
virtual void operationA() = 0;
virtual ~AbstractProductA() {}
};
// 具体产品A1
class ConcreteProductA1 : public AbstractProductA {
public:
void operationA() override {
// 具体产品A1的操作
}
};
// 抽象产品B
class AbstractProductB {
public:
virtual void operationB() = 0;
virtual ~AbstractProductB() {}
};
// 具体产品B1
class ConcreteProductB1 : public AbstractProductB {
public:
void operationB() override {
// 具体产品B1的操作
}
};
// 抽象工厂
class AbstractFactory {
public:
virtual AbstractProductA* createProductA() = 0;
virtual AbstractProductB* createProductB() = 0;
virtual ~AbstractFactory() {}
};
// 具体工厂1
class ConcreteFactory1 : public AbstractFactory {
public:
AbstractProductA* createProductA() override {
return new ConcreteProductA1();
}
AbstractProductB* createProductB() override {
return new ConcreteProductB1();
}
};
建造者模式
建造者模式是一种创建型设计模式，它的主要目的是将一个复杂对象的构建与其表示分离，使得同样的构建过程可以创建不同的表示。
建造者模式通常涉及以下几个角色：
Director（指挥者）：负责使用建造者对象构建产品对象的算法。 Builder（建造者）：定义创建产品各个部件的接口，以及构建产品的方法。 ConcreteBuilder（具体建造者）：实现 Builder 接口，负责具体的产品构建工作。 Product（产品）：表示被构建的复杂对象。
给个代码示例来加深理解：
#include <iostream>
#include <string>
// 产品（Pizza）
class Pizza {
public:
void setDough(const std::string& dough) {
dough_ = dough;
}
void setSauce(const std::string& sauce) {
sauce_ = sauce;
}
void setTopping(const std::string& topping) {
topping_ = topping;
}
void showPizza() {
std::cout << "Pizza with " << dough_ << " dough, " << sauce_ << " sauce and " << topping_ << " topping." << std::endl;
}
private:
std::string dough_; // 面团
std::string sauce_; // 酱料
std::string topping_; // 配料
};
// 建造者（Builder）接口
class PizzaBuilder {
public:
virtual void buildDough() = 0; // 建造面团
virtual void buildSauce() = 0; // 建造酱料
virtual void buildTopping() = 0; // 建造配料
virtual Pizza* getPizza() = 0; // 获取Pizza对象
virtual ~PizzaBuilder() {}
};
// 具体建造者（ConcreteBuilder）
class HawaiianPizzaBuilder : public PizzaBuilder {
public:
void buildDough() override {
pizza_->setDough("cross"); // 设置交叉面团
}
void buildSauce() override {
pizza_->setSauce("mild"); // 设置温和酱料
}
void buildTopping() override {
pizza_->setTopping("ham+pineapple"); // 设置火腿+菠萝配料
}
Pizza* getPizza() override {
return pizza_; // 返回构建好的Pizza对象
}
HawaiianPizzaBuilder() {
pizza_ = new Pizza(); // 在构造函数中创建Pizza对象
}
~HawaiianPizzaBuilder() {
delete pizza_; // 析构函数中释放内存
}
private:
Pizza* pizza_; // Pizza对象指针
};
// 指挥者（Director）
class Waiter {
public:
void setPizzaBuilder(PizzaBuilder* builder) {
pizzaBuilder_ = builder; // 设置建造者
}
Pizza* getPizza() {
return pizzaBuilder_->getPizza(); // 获取建造好的Pizza对象
}
void constructPizza() {
pizzaBuilder_->buildDough(); // 建造面团
pizzaBuilder_->buildSauce(); // 建造酱料
pizzaBuilder_->buildTopping(); // 建造配料
}
private:
PizzaBuilder* pizzaBuilder_; // 建造者对象指针
};
int main() {
Waiter waiter; // 创建指挥者对象
HawaiianPizzaBuilder hawaiianPizzaBuilder; // 创建具体建造者对象
waiter.setPizzaBuilder(&hawaiianPizzaBuilder); // 设置具体建造者对象
waiter.constructPizza(); // 指挥者构建Pizza对象
Pizza* pizza = waiter.getPizza(); // 获取建造好的Pizza对象
pizza->showPizza(); // 展示Pizza对象信息
delete pizza; // 释放Pizza对象内存
return 0;
}
观察者模式
观察者模式是一种行为设计模式，用于定义对象间的一种一对多的依赖关系，当一个对象的状态发生改变时，所有依赖它的对象都会得到通知并自动更新。
观察者模式通常包含以下几个角色：
Subject（目标）：目标是被观察的对象，它包含了一组观察者对象，并提供了添加、删除和通知观察者的方法。 Observer（观察者）：观察者是依赖于目标的对象，当目标状态发生改变时，观察者会得到通知并进行相应的更新操作。 ConcreteSubject（具体目标）：具体目标是实现了目标接口的具体对象，它维护了一组观察者对象，并在状态发生改变时通知观察者。 ConcreteObserver（具体观察者）：具体观察者是实现了观察者接口的具体对象，它注册到具体目标中，并在目标状态发生改变时接收到通知并进行更新操作。
再来个例子：
#include <iostream>
#include <vector>
// 观察者接口
class Observer {
public:
virtual void update() = 0;
virtual ~Observer() {}
};
// 目标接口
class Subject {
public:
virtual void attach(Observer* observer) = 0;
virtual void detach(Observer* observer) = 0;
virtual void notify() = 0;
virtual ~Subject() {}
};
// 具体观察者
class ConcreteObserver : public Observer {
public:
void update() override {
std::cout << "ConcreteObserver: Received update from subject." << std::endl;
}
};
// 具体目标
class ConcreteSubject : public Subject {
public:
void attach(Observer* observer) override {
observers_.push_back(observer);
}
void detach(Observer* observer) override {
// 在实际应用中可能需要实现查找并删除的逻辑
observers_.erase(std::remove(observers_.begin(), observers_.end(), observer), observers_.end());
}
void notify() override {
for (auto observer : observers_) {
observer->update();
}
}
void setState(int state) {
state_ = state;
notify();
}
private:
std::vector<Observer*> observers_;
int state_;
};
int main() {
ConcreteSubject subject;
ConcreteObserver observer1, observer2;
// 将观察者注册到目标中
subject.attach(&observer1);
subject.attach(&observer2);
// 改变目标的状态，并通知观察者
subject.setState(1);
// 将观察者从目标中移除
subject.detach(&observer2);
// 再次改变目标的状态，并通知观察者
subject.setState(2);
return 0;
}
6、泛型编程使用经验？
泛型编程是一种编程范式，它以一种抽象的方式描述算法和数据结构，使得它们可以在不同类型上工作，而不是针对特定类型进行硬编码。在 C++ 中，泛型编程主要通过模板实现，它允许编写通用的代码，从而提高了代码的重用性和灵活性。
一些使用经验：
提高代码的重用性：泛型编程允许你编写通用的代码，可以在不同的类型上进行操作，从而减少了重复编写类似代码的工作量。 提高代码的灵活性：泛型编程使得代码更加灵活，可以适应不同的需求和数据类型，而不需要针对每种情况都编写特定的代码。 提高代码的可维护性：通过泛型编程，可以将一些通用的逻辑抽象成模板，这样可以降低代码的复杂度，提高了代码的可维护性。 提高代码的性能：泛型编程可以在编译时进行类型检查和优化，可以生成高效的代码，从而提高了程序的性能。 注意模板代码的可读性：泛型编程中的模板代码可能会比普通的代码更加复杂，因此需要特别注意代码的可读性，以便于他人理解和维护。 谨慎使用模板元编程（TMP）：模板元编程是一种在编译期间执行的元编程技术，它可以实现非常高级的编译时计算，但使用起来相对复杂，容易产生难以理解的代码。 考虑模板实例化的开销：模板代码会在每一次使用时进行实例化，如果模板代码过于复杂或者被频繁使用，可能会导致编译时间增加和代码体积增大的问题，需要注意控制模板实例化的开销。
给个具体的例子加深理解：
#include <iostream>
#include <vector>
#include <stdexcept>
template <typename T>
class Stack {
public:
// 将元素压入栈顶
void push(const T& value) {
data_.push_back(value);
}
// 从栈顶弹出元素
void pop() {
if (empty()) {
throw std::out_of_range("Stack<>::pop(): empty stack");
}
data_.pop_back();
}
// 获取栈顶元素
T& top() {
if (empty()) {
throw std::out_of_range("Stack<>::top(): empty stack");
}
return data_.back();
}
// 判断栈是否为空
bool empty() const {
return data_.empty();
}
private:
std::vector<T> data_; // 用 vector 存储栈中的元素
};
int main() {
// 创建一个存储 int 类型的栈
Stack<int> intStack;
intStack.push(1);
intStack.push(2);
intStack.push(3);
// 依次弹出并输出栈中的元素
while (!intStack.empty()) {
std::cout << intStack.top() << " "; // 输出 3 2 1
intStack.pop();
}
std::cout << std::endl;
// 创建一个存储 string 类型的栈
Stack<std::string> stringStack;
stringStack.push("Hello");
stringStack.push("World");
// 依次弹出并输出栈中的元素
while (!stringStack.empty()) {
std::cout << stringStack.top() << " "; // 输出 "World" "Hello"
stringStack.pop();
}
std::cout << std::endl;
return 0;
}
项目：
1、为什么要使用 cgroup 进行绑核、有没有了解过其他方案？（namespace）
这里根据题主的提示，给一些使用的理由及好处。
在操作系统中，cgroup（Control Groups）是 Linux 内核提供的一种机制，用于限制、控制和监视进程组的资源使用。cgroup 可以用于各种用途，其中包括将进程绑定到特定的 CPU 核心上。绑核可以用于优化多核系统中的任务分配和调度，从而提高系统性能和资源利用率。
为什么要使用 cgroup 进行绑核？
性能优化：在多核系统中，将任务绑定到特定的 CPU 核心上可以减少 CPU 上下文切换的开销，提高程序的运行效率和性能。 资源隔离：通过绑定进程到特定的 CPU 核心，可以避免不同任务之间的资源竞争，提高系统的稳定性和可靠性。 可预测性：绑定进程到特定的 CPU 核心可以使得任务的执行时间更加可预测，有助于实时系统和对延迟要求较高的应用场景。
除了 cgroup 外，Linux 还提供了另一种机制叫做 namespace，用于创建隔离的运行环境。不同的 namespace 可以提供不同类型的隔离，包括进程隔离、网络隔离、文件系统隔离等。与 cgroup 不同的是，namespace 更侧重于提供隔离而不是资源控制。
例如，通过使用 clone 系统调用可以创建新的进程，同时指定使用的 namespace 类型，从而创建隔离的运行环境。常见的 namespace 包括：
CLONE_NEWNS：用于创建新的文件系统隔离CLONE_NEWUTS：用于创建新的主机名和域名隔离CLONE_NEWIPC：用于创建新的进程间通信隔离CLONE_NEWNET：用于创建新的网络隔离CLONE_NEWPID：用于创建新的进程隔离CLONE_NEWUSER：用于创建新的用户隔离
2、C++ 中 CPU 绑核的 API 是什么？（sched_setaffinity）
在 C++ 中，CPU 绑核的 API 主要是通过操作系统提供的调度机制来实现的，因为 CPU 的绑定通常需要特权操作，而这些操作通常由操作系统提供的系统调用或库函数来完成。在 Linux 系统中，可以使用 sched_setaffinity 和 sched_getaffinity 等系统调用来实现 CPU 的绑定。
sched_setaffinity：设置进程或线程的 CPU 亲和性（affinity），即将进程或线程绑定到特定的 CPU 核心上。
#include <sched.h>
int sched_setaffinity(pid_t pid, size_t cpusetsize, const cpu_set_t *mask);
pid：进程或线程的 PID，如果为 0，则表示设置当前进程的 CPU 亲和性。cpusetsize：CPU 集合的大小，通常使用CPU_SETSIZE宏来表示系统支持的最大 CPU 数量。mask：CPU 掩码，用于指定绑定的 CPU 核心。
sched_getaffinity：获取进程或线程的 CPU 亲和性。
#include <sched.h>
int sched_getaffinity(pid_t pid, size_t cpusetsize, cpu_set_t *mask);
pid：进程或线程的 PID，如果为 0，则表示获取当前进程的 CPU 亲和性。cpusetsize：CPU 集合的大小，通常使用CPU_SETSIZE宏来表示系统支持的最大 CPU 数量。mask：用于存储获取到的 CPU 掩码。
3、如果车端 CPU 开销超过原有的 11 个核怎么办？
场景题：
1、按行和按列遍历二维数组在性能上的差异？（建议收藏）
按行遍历：
内存访问连续性：按行遍历可以利用内存的连续性，因为二维数组在内存中是按行存储的，这样可以提高内存访问的效率，减少缓存未命中的情况。 缓存友好性：按行遍历可以更好地利用 CPU 缓存，因为它可以利用局部性原理，使得相邻的数据会被加载到缓存中，减少了缓存的不命中率。 缺点：在某些情况下，按行遍历可能会导致跨 cache line 的访问，影响了 cache line 的利用效率。
内存访问不连续：按列遍历会导致内存访问的不连续性，因为在二维数组中，每一列的数据并不是连续存储的，这可能会导致缓存未命中和内存访问效率低下。 缓存不友好：按列遍历可能会导致较多的缓存未命中，因为它破坏了局部性原理，使得相邻的数据不会被预先加载到缓存中。 优点：在某些特定情况下，按列遍历可能更符合特定的数据布局和访问模式，从而提高数据访问的效率。
2、死循环中执行 i++ 自增操作后睡眠 1ms、CPU 占用是怎么样的？
在一个死循环中执行 i++ 自增操作后再睡眠 1ms，会导致 CPU 的占用情况取决于具体的实现方式和系统调度器的行为。
CPU 占用情况：
如果循环是一个忙等待的死循环，即没有合适的条件来退出循环，那么在执行 i++自增操作后立即睡眠 1ms，CPU 会在这 1ms 内继续被占用，因为线程没有被阻塞或者让出 CPU 的执行权，它会继续占用 CPU 执行循环。如果循环内有条件判断，并且在某些条件下可以退出循环，那么在条件不满足时，线程可能会被阻塞，此时 CPU 的占用情况取决于系统调度器的行为。在某些系统中，如果线程被阻塞，它会让出 CPU 的执行权，这样 CPU 的占用率会降低。
如果系统调度器是抢占式的，它会周期性地切换线程，即使一个线程不主动让出 CPU 的执行权，系统调度器也会在一定时间片后切换到其他线程执行，这样可以保证系统的响应性和公平性，但会增加 CPU 的上下文切换开销。 如果系统调度器是非抢占式的，那么只有在线程主动让出 CPU 的执行权或者发生阻塞等情况时才会进行线程切换，这样可能会导致某些线程长时间占用 CPU，影响系统的响应性。
算法：
1、手撕 shared_ptr？（建议收藏）
std::shared_ptr 是 C++ 标准库提供的智能指针，用于管理动态分配的内存资源，它可以自动进行内存的释放，避免了手动管理内存的麻烦和内存泄漏的风险。
给个例子供大家学习：
template <typename T>
class SharedPtr {
public:
// 构造函数
explicit SharedPtr(T* ptr = nullptr) : ptr_(ptr), count_(new size_t(ptr ? 1 : 0)) {}
// 拷贝构造函数
SharedPtr(const SharedPtr& other) : ptr_(other.ptr_), count_(other.count_) {
if (ptr_) {
++(*count_);
}
}
// 移动构造函数
SharedPtr(SharedPtr&& other) noexcept : ptr_(other.ptr_), count_(other.count_) {
other.ptr_ = nullptr;
other.count_ = nullptr;
}
// 析构函数
~SharedPtr() {
if (ptr_ && --(*count_) == 0) {
delete ptr_;
delete count_;
}
}
// 拷贝赋值运算符
SharedPtr& operator=(const SharedPtr& other) {
if (this != &other) {
if (ptr_ && --(*count_) == 0) {
delete ptr_;
delete count_;
}
ptr_ = other.ptr_;
count_ = other.count_;
if (ptr_) {
++(*count_);
}
}
return *this;
}
// 移动赋值运算符
SharedPtr& operator=(SharedPtr&& other) noexcept {
if (this != &other) {
if (ptr_ && --(*count_) == 0) {
delete ptr_;
delete count_;
}
ptr_ = other.ptr_;
count_ = other.count_;
other.ptr_ = nullptr;
other.count_ = nullptr;
}
return *this;
}
// 获取原始指针
T* get() const {
return ptr_;
}
// 解引用操作符
T& operator*() const {
return *ptr_;
}
// 成员访问操作符
T* operator->() const {
return ptr_;
}
// 获取引用计数
size_t use_count() const {
return *count_;
}
// 检查是否为空
bool empty() const {
return ptr_ == nullptr;
}
// 重置智能指针
void reset(T* ptr = nullptr) {
if (ptr_ && --(*count_) == 0) {
delete ptr_;
delete count_;
}
ptr_ = ptr;
count_ = new size_t(ptr ? 1 : 0);
}
private:
T* ptr_; // 原始指针
size_t* count_; // 引用计数
};
2、平衡二叉树（No. 110）
思路：
定义一个递归函数 height，用来计算二叉树的高度。在递归函数中，首先判断当前节点是否为空，如果为空则返回高度 0。 分别递归计算左右子树的高度，并判断左右子树的高度差是否超过 1。 如果左右子树的高度差不超过 1，则返回当前节点的高度，否则返回 -1 表示不是高度平衡的。 在 isBalanced函数中，调用递归函数判断整棵树是否是高度平衡的。
参考代码：
#include <iostream>
#include <algorithm>
// 二叉树节点的定义
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
public:
// 计算二叉树的高度
int height(TreeNode* root) {
if (root == nullptr) {
return 0; // 如果节点为空，返回高度 0
}
// 递归计算左右子树的高度
int leftHeight = height(root->left);
int rightHeight = height(root->right);
// 如果左右子树的高度差超过 1，或者左右子树有一个不平衡，则返回 -1
if (leftHeight == -1 || rightHeight == -1 || std::abs(leftHeight - rightHeight) > 1) {
return -1;
}
// 返回当前节点的高度
return std::max(leftHeight, rightHeight) + 1;
}
// 判断二叉树是否是高度平衡的
bool isBalanced(TreeNode* root) {
// 调用 height 函数，如果返回值不为 -1，则表示是高度平衡的
return height(root) != -1;
}
};
// 测试
int main() {
// 创建一个高度平衡的二叉树
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(2);
root->left->left = new TreeNode(3);
root->left->right = new TreeNode(3);
root->right->left = new TreeNode(3);
root->right->right = new TreeNode(3);
Solution solution;
std::cout << solution.isBalanced(root) << std::endl; // 输出 1，表示是高度平衡的
// 释放内存
delete root->left->left;
delete root->left->right;
delete root->right->left;
delete root->right->right;
delete root->left;
delete root->right;
delete root;
return 0;
}
我还是希望大家能在看完我面经之后有所收获，不仅仅是问题本身，一个好的习惯，一个好的方法论都值得我们一起实践与学习。
如果可以，也可以分享给有需要的同学和朋友，让我们一起进步、一起成长。
不愧是字节，面个实习也满头大汗！ 字节面试原题，两人都没做出来，都凉了 拼多多二面笔试原题，15分钟没做出来，直接挂了。。。 《面试经典算法题》之 合并两个有序数组 拼多多一面笔试原题，15分钟没做出来，直接挂了。。。