华为od-C++面经

大家好，我是阿Q。

最近一段时间面经的分享，我相信对大家的帮助还是很大的。

这么多粉丝的关注，也是我最大的动力。你们既然相信我，那我就会输出高质量的总结供大家学习参考。

大家可能对华为od可能多少有点那啥...（懂的都懂哈哈），但是没关系，我们可以也可以尝试，最多的是学习和成长，选择还是要自己做的。

今天这位同学的面经还是挺有质量的，有基础也有难点。

主页还有更多的面经，您来都来了，不妨进去多看看，总没有坏处吧哈哈。在此也祝贺这位同学顺利拿到offer。

来源：https://www.nowcoder.com/discuss/521983121017823232

一面（60min）

1. 首先，处理右移距离 m
   大于数组长度 n
   的情况，这是通过将 m
   取模 n
   来实现的，以确保右移的距离在合理范围内。
2. 接下来，创建一个新的整数数组 result
   ，它的大小与输入数组 a
   相同，用于存放操作后的结果。
3. 接下来，使用两个循环来将输入数组 a
   中的元素按照右移的规则复制到 result
   数组中：
1. 第一个循环负责将数组 a
   的后面 m
   个元素复制到 result
   数组的末尾。这是通过将 a
   数组的后面 m
   个元素复制到 result
   数组的前面来实现的。
2. 第二个循环负责将数组 a
   的前面 (n-m)
   个元素复制到 result
   数组的前面。
4. 最后，函数返回 result
   数组作为结果。

#include <iostream>
#include <vector>


class Solution {
public:
    std::vector<int> solve(int n, int m, std::vector<int>& a) {
        // 首先，处理 m 大于数组长度的情况
        m = m % n;


        // 创建一个新数组用于存放结果
        std::vector<int> result(n);


        // 将前 M 个元素复制到结果数组的末尾
        for (int i = 0; i < m; i++) {
            result[i] = a[n - m + i];
        }


        // 将后面的 (N-M) 个元素复制到结果数组的前面
        for (int i = 0; i < n - m; i++) {
            result[m + i] = a[i];
        }


        return result;
    }
};


int main() {
    int n, m;
    std::cin >> n >> m; // 输入数组长度和右移距离


    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i]; // 输入数组元素
    }


    Solution solution;
    std::vector<int> result = solution.solve(n, m, a);


    // 输出结果数组
    for (int i = 0; i < n; i++) {
        std::cout << result[i];
        if (i < n - 1) {
            std::cout << " ";
        }
    }
    std::cout << std::endl;


    return 0;
}

6 2   // 数组长度为5，右移距离为2
1 2 3 4 5 6  // 数组元素

1. 封装：封装是面向对象编程的核心概念之一。它允许将数据和方法组合成一个单一的单元，即类。通过类，数据（成员变量）可以被隐藏在类的内部，只有类的方法（成员函数）可以访问和操作这些数据。这提供了数据的安全性和保护，防止了未经授权的直接访问。
2. 继承：继承允许创建一个新的类，可以继承现有类的属性和方法。子类（派生类）可以继承父类（基类）的特性，然后根据需要添加新的属性和方法，或者覆盖父类的方法。继承促进了代码的重用和层次化设计。
3. 多态：多态性允许不同类型的对象对同一方法做出不同的响应。这可以通过函数重载和虚函数来实现。多态性使得代码更加灵活，能够以一种通用的方式处理不同类型的对象。
4. 类和对象：C++ 中，面向对象编程的基本单元是类（Class）和对象（Object）。类是一个抽象的模板，描述了数据和方法的结构，而对象是类的实例，代表了具体的数据和方法的调用。
5. 构造函数和析构函数：C++ 中的构造函数和析构函数用于对象的初始化和清理工作。构造函数在对象创建时自动调用，而析构函数在对象销毁时自动调用。这使得资源管理更加方便，例如内存分配和释放。
6. 访问控制：C++ 中，类可以定义不同的访问控制级别，包括公共（public）、私有（private）、受保护（protected）。这些级别决定了哪些部分的类可以被外部访问，哪些部分是私有的，只能在类内部访问。
7. 运算符重载：C++ 允许用户重载运算符，使得用户自定义的类可以像内置类型一样使用运算符。这增强了自定义类的可用性和可读性。
8. 模板（Templates）：C++ 支持泛型编程，通过模板可以创建通用的数据结构和算法，而不必为每种类型都编写特定的代码。这提高了代码的复用性和灵活性。

1. 多态是指同一个方法名或操作符可以有多个不同的实现方式，具体取决于对象的类型或类的结构。这意味着相同的函数名可以在不同的类中具有不同的实现，或者相同的运算符可以根据操作数的类型执行不同的操作。
2. 在面向对象编程中，多态性通常通过继承和虚函数（或抽象类）来实现。子类可以继承父类的虚函数，并根据需要提供自己的实现。当通过基类指针或引用调用虚函数时，实际执行的是对象的子类版本，而不是基类版本。
3. 多态的体现：
1. 函数重载：在同一个类中，可以定义多个同名但参数列表不同的函数。编译器根据函数参数的类型和数量来选择调用哪个函数。这被称为编译时多态（静态多态）。
2. 虚函数：通过在基类中声明虚函数，并在派生类中覆盖（重写）虚函数，可以实现运行时多态。当通过基类指针或引用调用虚函数时，将根据实际对象的类型来决定调用哪个子类的实现，这被称为运行时多态。
3. 抽象类和接口：抽象类可以包含纯虚函数，子类必须提供这些函数的具体实现。接口是一种特殊的抽象类，只包含纯虚函数，用于定义类之间的契约。这使得不同类可以实现相同的接口，从而实现多态性。
4. 多态的优点：
1. 代码复用性：多态允许不同类共享相同的接口和行为，从而提高了代码的复用性。
2. 可扩展性：通过添加新的子类或实现新的接口，可以轻松扩展程序的功能，而无需修改现有代码。
3. 可维护性：多态使代码更容易理解和维护，因为它隐藏了对象的具体类型，减少了条件分支语句。

1. 析构函数：析构函数在对象的生命周期结束时被调用，用于清理对象占用的资源（如释放内存、关闭文件等）。当对象超出作用域、被 delete
   运算符销毁或程序结束时，析构函数会被调用。

class MyClass {
public:
    ~MyClass() {
        // 析构函数被调用
    }
};


int main() {
    {
        MyClass obj; // 对象超出作用域，析构函数被调用
    }
    MyClass* ptr = new MyClass();
    delete ptr; // delete 运算符销毁对象，析构函数被调用
    return 0; // 程序结束，析构函数被调用
}

2. 构造函数：
1. 构造函数在创建对象时被调用，用于初始化对象的成员变量。当通过 new
   运算符创建对象或在栈上声明对象时，构造函数都会被调用。
2. 如果有继承关系，派生类的构造函数会首先调用基类的构造函数，然后再执行自己的构造逻辑。

class MyClass {
public:
    MyClass() {
        // 构造函数被调用
    }
};


int main() {
    MyClass obj; // 构造函数被调用
    MyClass* ptr = new MyClass(); // 构造函数被调用
    return 0;
}

3. 复制构造函数：
1. 复制构造函数在创建一个对象并将其初始化为另一个对象的副本时被调用。这包括对象的传递、返回和初始化。
2. 当需要将一个对象从一种类型转换为另一种类型时，复制构造函数可能会被调用。

class MyClass {
public:
    MyClass(const MyClass& other) {
        // 复制构造函数被调用
    }
};


int main() {
    MyClass obj1;
    MyClass obj2 = obj1; // 复制构造函数被调用
    return 0;
}

• 指针：指针是一个变量，存储的是另一个变量的内存地址。它必须经过定义和初始化才能使用，可以指向不同的变量。
• 引用：引用是一个别名，它没有自己的内存地址。引用必须在定义时初始化，并且一旦初始化，不能再引用其他变量。

• 指针：通过使用*
  运算符来声明指针和访问指针指向的值，同时使用&
  运算符来获取变量的地址。
• 引用：引用的声明和使用与普通变量类似，不需要*
  运算符来访问值，因为引用本身就是变量的别名。

• 指针：指针可以具有空值（nullptr），表示它不指向任何有效的内存地址。
• 引用：引用在定义时必须初始化，并且一旦初始化后，不能改变其引用的对象，因此不具备可空性。

• 指针：通常用于需要动态分配内存、数组操作、迭代等情况，或者当需要多态性（通过基类指针访问派生类对象）时。
• 引用：用于函数参数传递、函数返回值、避免对象拷贝的情况，以及需要直观的别名来简化代码。

• 指针：指针的操作可能需要更多的代码，因为需要解引用操作（*ptr
  ）来访问值。
• 引用：引用在访问值时更加直接，因此通常更高效。

1. 静态成员vs普通成员：

• 静态成员属于类而不是类的实例，它在类的所有实例之间共享相同的值。
• 可以通过类名来访问静态成员，不需要创建类的实例。
• 通常用于存储类的共享数据，例如计数器、配置信息等。
• 静态成员的内存分配在编译时进行，不需要实例化类。

• 普通成员属于类的实例，每个实例都有自己的副本。
• 必须创建类的实例才能访问和使用普通成员。
• 用于存储特定于实例的数据，通常是对象的属性。

1. 静态函数vs普通函数：

• 静态函数属于类而不是类的实例，它不能访问非静态成员（包括普通成员和非静态函数）。
• 可以通过类名来调用静态函数，不需要创建类的实例。
• 通常用于执行与类相关的操作，而不需要实例的状态。

• 普通函数不属于类，它可以访问类的实例成员和状态。
• 必须通过类的实例来调用普通函数。
• 用于执行与对象状态相关的操作。

1. 如果使用 new
   或 malloc
   分配了内存，但没有使用 delete
   或 free
   进行释放，就会导致内存泄漏。
2. 当一个指向动态分配内存的指针被重新赋值或者超出了其作用域，就无法再释放内存，导致泄漏。
3. 在使用智能指针时，如果存在循环引用（两个或多个对象相互持有对方的智能指针），就会导致对象无法被销毁，从而导致内存泄漏。

1. 使用智能指针：C++11引入的std::shared_ptr
   和std::unique_ptr
   可以自动管理内存的释放，确保在不再需要时正确释放内存。
2. 在使用new
   或malloc
   分配内存时，确保在不再需要内存时调用delete
   或free
   释放内存。
3. 避免丢失指针：确保在不再需要的时候将指针置为nullptr
   ，或者使用智能指针来自动管理。
4. 在使用智能指针时，避免形成循环引用，或者使用std::weak_ptr
   来打破循环引用。
5. 借助C++的对象生命周期管理，确保在对象的析构函数中释放资源（如内存），从而避免手动管理资源时出现错误。

1. 堆上的内存需要手动分配和释放，程序员负责管理其生命周期。通常使用new
   （C++）或malloc
   （C）来分配堆内存，并使用delete
   （C++）或free
   （C）来释放堆内存。
2. 堆上的内存可以根据需要动态分配，其大小通常比栈大得多，受系统总内存的限制。
3. 堆上的内存访问速度较慢，因为它是散列的，访问数据需要通过指针进行间接访问。
4. 堆上的数据的生命周期可以跨越函数调用和程序的不同部分，因此可以在程序的整个执行过程中保持有效。

1. 栈上的内存是自动分配和释放的，其生命周期由程序的函数调用栈控制。当一个函数被调用时，其局部变量被分配到栈上，当函数返回时，这些局部变量会被自动释放。
2. 栈的大小通常是有限的，它受到操作系统或编译器的限制。这意味着栈上的内存用于存储相对较小的数据，如基本数据类型和小型对象。
3. 栈上的内存访问速度很快，因为它是线性的，数据的存储和检索效率高。
4. 栈上的数据的生命周期通常与函数调用的生命周期相匹配，因此它们是短暂的。一旦函数返回，栈上的数据将被销毁。

1. 数组（Array）：
1. 特点：连续的内存存储，通过索引快速访问元素。
2. 适用场景：适用于元素数量已知且不经常插入或删除的情况。
2. 链表（Linked List）：
1. 特点：非连续的内存存储，通过指针链接节点。
2. 适用场景：适用于频繁插入或删除元素的情况，或者在内存不连续的情况下。
3. 栈（Stack）：
1. 特点：后进先出（LIFO）的数据结构，只能在栈顶进行插入和删除操作。
2. 适用场景：适用于需要遵循后进先出规则的情况，如函数调用栈。
4. 队列（Queue）：
1. 特点：先进先出（FIFO）的数据结构，只能在队首和队尾进行插入和删除操作。
2. 适用场景：适用于需要遵循先进先出规则的情况，如任务调度。
5. 树（Tree）：
1. 特点：层次结构，包括二叉树、二叉搜索树、平衡二叉树等。
2. 适用场景：用于表示层次关系的数据，如文件系统、组织结构等。
6. 图（Graph）：
1. 特点：由节点和边构成的数据结构，有向图和无向图。
2. 适用场景：用于表示复杂的关系和网络，如社交网络、路由算法等。
7. 哈希表（Hash Table）：
1. 特点：使用哈希函数将键映射到数组索引，实现快速的查找、插入和删除。
2. 适用场景：适用于需要高效查找的情况，如字典、缓存等。
8. 堆（Heap）：
1. 特点：用于实现优先级队列，包括最小堆和最大堆。
2. 适用场景：适用于需要快速查找最小或最大元素的情况，如堆排序、调度算法等。
9. 集合（Set）和映射（Map）：
1. 特点：集合用于存储唯一元素，映射用于键值对的存储。
2. 适用场景：用于去重、快速查找键值对的情况。
10. 栈和队列的变种（如双端队列、优先级队列等）：
1. 特点：根据需要实现不同的操作，如双端队列支持队首和队尾的插入和删除操作，优先级队列支持按优先级排序。

1. 链地址法（Separate Chaining）：
1. 在每个散列桶（哈希表中的每个槽位）上维护一个链表或其他数据结构，用于存储冲突的元素。
2. 当发生冲突时，将新元素插入到对应桶的链表中。
3. 优点：简单，容易实现；适用于元素分布不均匀的情况。
4. 缺点：链表过长时可能会影响查找性能，需要额外的内存空间。
2. 开放寻址法（Open Addressing）：
1. 在散列表中的每个槽位中存储元素，当发生冲突时，根据某种规则来寻找下一个可用的槽位。
2. 常见的开放寻址法包括线性探测、二次探测、双重散列等。
3. 优点：不需要额外的内存空间，适用于小规模散列表。
4. 缺点：容易出现聚集现象，影响性能；不适用于动态散列表。
3. 线性探测（Linear Probing）：
1. 当发生冲突时，线性探测依次查找下一个可用的槽位，直到找到一个空槽位或达到散列表的末尾。
2. 插入操作：尝试将元素插入到哈希桶，如果槽位已被占用，就线性查找下一个空槽位。
3. 查找操作：根据哈希值查找槽位，如果不是目标元素，就线性查找下一个槽位，直到找到目标元素或遇到空槽位。
4. 删除操作：标记被删除元素，而不是直接删除，以防止查找时出错。
4. 二次探测（Quadratic Probing）：
1. 当发生冲突时，二次探测以二次方的步长查找下一个可用的槽位。
2. 插入、查找和删除操作与线性探测类似，但步长不同。
5. 双重散列（Double Hashing）：
1. 当发生冲突时，使用第二个哈希函数来计算下一个槽位。
2. 插入操作：根据第一个哈希函数找到初始位置，然后使用第二个哈希函数来计算下一个槽位，直到找到空槽位。
3. 查找和删除操作也使用第二个哈希函数计算槽位。

#include <iostream>
#include <queue>
#include <vector>


using namespace std;


// 定义图的数据结构，这里使用邻接矩阵表示
class Graph {
public:
    Graph(int numNodes) : numNodes(numNodes), adjMatrix(numNodes, vector<int>(numNodes, 0)) {}


    void addEdge(int from, int to) {
        adjMatrix[from][to] = 1;
        adjMatrix[to][from] = 1; // 无向图，需要双向连接
    }


    vector<int> shortestPath(int start, int end) {
        vector<bool> visited(numNodes, false);
        vector<int> parent(numNodes, -1);
        queue<int> q;
        q.push(start);
        visited[start] = true;


        while (!q.empty()) {
            int current = q.front();
            q.pop();


            if (current == end) {
                // 构造最短路径
                vector<int> path;
                while (current != -1) {
                    path.insert(path.begin(), current);
                    current = parent[current];
                }
                return path;
            }


            for (int neighbor = 0; neighbor < numNodes; ++neighbor) {
                if (adjMatrix[current][neighbor] == 1 && !visited[neighbor]) {
                    q.push(neighbor);
                    visited[neighbor] = true;
                    parent[neighbor] = current;
                }
            }
        }


        // 若未找到路径，返回空路径
        return vector<int>();
    }


private:
    int numNodes;
    vector<vector<int>> adjMatrix;
};


int main() {
    Graph g(6); // 创建一个有6个节点的图


    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);
    g.addEdge(2, 4);
    g.addEdge(3, 5);


    int startNode = 0;
    int endNode = 5;
    vector<int> shortestPath = g.shortestPath(startNode, endNode);


    if (!shortestPath.empty()) {
        cout << "Shortest path from " << startNode << " to " << endNode << ": ";
        for (int node : shortestPath) {
            cout << node << " ";
        }
        cout << endl;
    } else {
        cout << "No path exists from " << startNode << " to " << endNode << endl;
    }


    return 0;
}

1. 定义：
1. 进程（Process）：进程是计算机中的一个独立的执行环境，它包含了一个程序的代码、数据、资源、以及一个执行线程。每个进程都有独立的内存空间，相互之间不会直接共享数据，需要通过进程间通信（Inter-Process Communication，IPC）来进行数据交换。
2. 线程（Thread）：线程是进程内的执行单元，一个进程可以包含多个线程。线程共享进程的内存空间和资源，它们可以直接访问相同的数据，因此线程之间的通信相对容易。
2. 资源占用：
1. 进程：每个进程都有独立的内存空间和系统资源（如文件描述符、网络连接等），因此进程的资源占用相对较高。
2. 线程：线程共享进程的内存空间和资源，因此线程的资源占用相对较低。
3. 创建和销毁：
1. 进程：创建和销毁进程相对较重，需要分配和释放独立的资源，通常比线程开销大。
2. 线程：创建和销毁线程相对较轻量，因为它们共享进程的资源，通常比进程开销小。
4. 切换代价：
1. 进程：进程切换的代价相对较高，因为需要保存和恢复进程的完整上下文信息，包括内存空间、寄存器状态等。
2. 线程：线程切换的代价相对较低，因为线程共享同一进程的地址空间和资源，切换时只需切换线程的上下文。
5. 并发性：
1. 进程：进程是独立的执行单元，不同进程之间的并发性相对较低，它们通常需要通过进程间通信来协调和共享数据。
2. 线程：线程是进程内的执行单元，不同线程之间的并发性相对较高，它们可以直接共享数据，但需要注意线程同步问题，以避免竞争条件和死锁。
6. 安全性：
1. 进程：进程之间的数据隔离较好，一个进程崩溃通常不会影响其他进程。
2. 线程：线程之间共享相同的内存空间，因此一个线程的错误可能会影响整个进程的稳定性。
7. 平台支持：
1. 进程：进程是操作系统级别的概念，可以跨平台使用。
2. 线程：线程通常依赖于特定的线程库和操作系统支持，跨平台性可能有限。

1. 互斥资源的竞争：

• 互斥性（Mutual Exclusion）：资源一次只能被一个线程占用。
• 持有和等待（Hold and Wait）：线程持有一些资源并等待其他线程的资源。
• 不可剥夺（No Preemption）：资源只能由占用它的线程主动释放，不能被强制剥夺。
• 循环等待（Circular Wait）：多个线程之间形成一个等待环路，每个线程都在等待另一个线程的资源。

1. 资源分配不当：

1. 线程调度问题：

1. 资源不足：

1. 管道（Pipe）：

• 匿名管道：创建后只能用于具有共同祖先的进程之间的通信。通常通过pipe
  系统调用来创建。
• 命名管道（FIFO）：可以用于不相关的进程之间的通信，通过文件系统中的一个特殊文件实现，通常通过mkfifo
  系统调用创建。

1. 消息队列（Message Queue）：

• 消息队列提供了一种异步通信方式，允许发送者和接收者以独立的速度进行通信。
• 可以通过消息队列发送结构化数据，而不仅仅是字节流。

1. 共享内存（Shared Memory）：

• 共享内存通常用于需要高速数据传输的场景，如图像处理或数据库管理系统。
• 需要谨慎管理共享内存，以避免竞争条件和数据一致性问题。

1. 信号（Signal）：

• 信号可以通过kill
  、raise
  和signal
  等函数发送和处理。
• 信号可以用于进程间通信，但通常不用于大量数据的传输。

1. 套接字（Socket）：

• 套接字提供了一种通用的跨网络或跨进程通信方式。
• 可以通过TCP或UDP协议在套接字上传输数据。

1. 信号量（Semaphore）和互斥锁（Mutex）：

• 信号量：用于控制多个进程对有限资源的访问。可以通过semget
  、semop
  等系统调用来操作。
• 互斥锁：用于确保在任何给定时刻只有一个进程可以访问共享资源。可以通过pthread_mutex_init
  、pthread_mutex_lock
  等函数来操作。

二面（40min）

这个当时面完忘记记录了，大部分问题都忘记了，主要问了我算法与数据结构以及c++基础（30min）+ 做题（10min）

#include <iostream>
#include <string>
#include <unordered_map>


using namespace std;


int lengthOfLongestSubstring(string s) {
    int n = s.length(); // 输入字符串的长度
    int maxLength = 0; // 最长不重复子序列的长度
    unordered_map<char, int> charIndex; // 用于记录字符最近出现的位置


    int left = 0; // 滑动窗口的左边界


    for (int right = 0; right < n; right++) {
        char c = s[right];
        // 如果字符已经出现过，并且出现的位置在当前窗口内
        if (charIndex.find(c) != charIndex.end() && charIndex[c] >= left) {
            left = charIndex[c] + 1; // 更新窗口的左边界，使窗口不包含重复字符
        }
        charIndex[c] = right; // 记录字符最近出现的位置
        int currentLength = right - left + 1; // 当前窗口的长度
        maxLength = max(maxLength, currentLength); // 更新最大长度
    }


    return maxLength;
}


int main() {
    string s = " "; // 示例输入字符串
    cin >> s;
    int result = lengthOfLongestSubstring(s); // 调用函数计算最长不重复子序列的长度
    cout << "最长不重复子序列的长度为: " << result << endl; // 输出结果
    return 0;
}

1. 定义一个变量 maxLength 用于存储最长不重复子序列的长度，初始化为0。
2. 使用一个哈希表 charIndex 用于记录字符最近一次出现的位置。
3. 初始化滑动窗口的左边界 left 为0。
4. 使用一个循环遍历字符串 s，其中 right 表示滑动窗口的右边界。
5. 在每一步中，检查当前字符 s[right] 是否在哈希表 charIndex 中已经出现过，并且它的位置在当前窗口内（即大于等于 left）。如果是，则需要更新窗口的左边界 left，将其设置为重复字符的下一个位置，以确保窗口内不包含重复字符。
6. 更新哈希表 charIndex 中字符 s[right] 的位置为 right，表示字符最近出现的位置。
7. 计算当前窗口的长度 currentLength，即 right - left + 1。
8. 更新 maxLength，将其设置为 maxLength 和 currentLength 中的较大值，以确保始终保持最长不重复子序列的长度。
9. 循环结束后，maxLength 即为最长不重复子序列的长度。

看完记得三连哦~