腾讯一面

1、内联函数，优点及缺点？

是C++中的一个编译器指令，它用于告诉编译器在调用函数时将函数体的代码插入到调用点，而不是通过正常的函数调用机制来执行函数。内联函数的目的是提高程序的执行效率。

内联函数的主要目的是减少函数调用的开销。在函数调用时，通常需要保存当前函数的上下文、跳转到被调用函数、执行函数体，然后再返回到调用点。内联函数通过将函数体嵌入到调用点，消除了这些开销。

inline int add(int a, int b) {
    return a + b;
}

优点：

inline定义的内联函数，函数代码被放入符号表中，在使用时进行替换（像宏一样展开），效率很高；
类的内联函数也是函数。编辑器在调用一个内联函数，首先会检查参数问题，保证调用正确，像对待真正函数一样，消除了隐患及局限性；
inline可以作为类的成员函数，也可以使用所在类的保护成员及私有成员。

缺点：

内联函数以复制为代价，活动产函数开销；
如果函数的代码较长，使用内联将消耗过多内存；
果函数体内有循环，那么执行函数代码时间比调用开销大。

2、容器：map，set？

map？

C++ 中的 std::map 是标准库中的一个关联容器，提供了一种键-值（key-value）映射的数据结构，其中每个键都唯一，用于快速查找和访问与之关联的值。std::map 基于红黑树（Red-Black Tree）实现，因此具有较快的查找、插入和删除操作。

定义和声明：

std::map<KeyType, ValueType> myMap;

插入元素：

myMap.insert(std::make_pair(key, value));

查找元素：

auto it = myMap.find(key);
if (it != myMap.end()) {
    // not found
    ValueType value = it->second;
} else {
    // found
}

set？

C++ 中的 std::set 是标准库中的关联容器，它表示一组唯一的元素，通常按照升序排列。std::set 基于二叉搜索树（通常是红黑树）实现，因此具有快速的查找、插入和删除操作，并确保元素的唯一性的情况。

定义和声明：

std::set<ElementType> mySet;

插入元素：

mySet.insert(element);

查找元素：

auto it = mySet.find(element);
if (it != mySet.end()) {
    // not found
} else {
    // found
}

你了解红黑树吗？

一种特殊的二叉查找树。也就意味着它满足二叉查找树的特征：任意一个节点所包含的键值，大于等于左孩子的键值，小于等于右孩子的键值。

红黑树的每个节点上都有存储位表示节点的颜色，颜色是红(Red)或黑(Black)。

红黑树特性：

每个节点或者是黑色，或者是红色。
根节点是黑色。
每个叶子节点是黑色（为空的结点）。
不能出现两个连续的红色结点（如果一个节点是红色的，那么它的两个子节点都是黑色的）。
从一个节点开始所有路径上包含相同数目的黑节点。

3、unordered_map unordered_set？哈希表解决冲突办法

unordered_map？

是一种无序关联容器，用于存储键值对（key-value pairs）。std::unordered_map 提供了快速的查找、插入和删除操作，其底层实现是基于哈希表（hash table）的。

unordered_map是一个将key和value关联起来的容器，它可以高效的根据单个key值查找对应的value。
key值应该是唯一的，key和value的数据类型可以不相同。
unordered_map存储元素时是没有顺序的，只是根据key的哈希值，将元素存在指定位置，所以根据key查找单个value时非常高效，平均可以在常数时间内完成。
unordered_map查询单个key的时候效率比map高，但是要查询某一范围内的key值时比map效率低。
可以使用[]操作符来访问key值对应的value值。

优点：

快速查找和插入：哈希表的主要优点是快速的查找、插入和删除操作。平均情况下，这些操作的时间复杂度是 O(1)，即常数时间。
灵活的键类型： std::unordered_map 支持各种不同类型的键，包括内置类型、自定义类和标准库类型。
动态大小：哈希表的大小可以根据需要自动调整，因此不需要手动管理容器大小。
哈希函数自定义：你可以自定义键的哈希函数，以适应特定的键类型和哈希分布。

缺点：

无序性： std::unordered_map 不会按照键的顺序来存储键值对，因此不适合需要有序存储的情况。
空间开销：哈希表需要额外的内存来存储哈希表本身，因此可能会占用较多的内存空间。
哈希冲突：哈希表中可能会出现哈希冲突，需要额外的处理来解决冲突，例如使用链地址法。
性能退化：在极端情况下，哈希表的性能可能会退化，导致查找、插入和删除操作的时间复杂度不再是常数时间。
复杂度分析：哈希表的性能取决于哈希函数的质量、负载因子和键的分布情况。不当选择哈希函数或者负载因子设置不当可能会影响性能。

unordered_set？

std::unordered_set 是 C++ 标准库中的一个关联容器，它实现了无序集合（unordered set），用于存储不重复的元素。无序集合是一种数据结构，它包含一组不重复的元素，这些元素没有明确定义的顺序。你可以将元素插入集合中，查找集合中是否包含某个元素，删除集合中的元素等等。 std::unordered_set 内部使用哈希表来实现。

优点：

快速查找和插入：哈希表的主要优点是快速的查找、插入和删除操作。平均情况下，这些操作的时间复杂度是 O(1)，即常数时间。
灵活的元素类型： std::unordered_set 支持各种不同类型的元素，包括内置类型、自定义类和标准库类型。
动态大小：哈希表的大小可以根据需要自动调整，因此不需要手动管理容器大小。
哈希函数自定义：你可以自定义元素的哈希函数，以适应特定的元素类型和哈希分布。

缺点：

无序性： std::unordered_set 不会按照元素的插入顺序来存储元素，因此不适合需要有序存储的情况。
空间开销：哈希表需要额外的内存来存储哈希表本身，因此可能会占用较多的内存空间。
哈希冲突：哈希表中可能会出现哈希冲突，需要额外的处理来解决冲突，例如使用链地址法。
性能退化：在极端情况下，哈希表的性能可能会退化，导致查找和插入操作的时间复杂度不再是常数时间。
复杂度分析：哈希表的性能取决于哈希函数的质量、负载因子和元素的分布情况。不当选择哈希函数或者负载因子设置不当可能会影响性能。

哈希表解决冲突办法？

开放寻址法（Open Addressing）：在开放寻址法中，当发生冲突时，会在哈希表中的其他位置寻找空槽位来存储冲突的元素。这可以通过线性探测、二次探测、双重散列等方法来实现。开放寻址法的优点是节省内存，但可能导致聚集（clustering）问题，即冲突的元素趋向于在相邻的位置堆积，影响性能。
链地址法（Chaining）：在链地址法中，每个槽位都连接一个链表或其他数据结构，当冲突发生时，将元素插入到相应槽位的链表中。链地址法的优点是容易实现，冲突的元素可以动态增长，但可能会浪费一些内存用于存储链表的指针。
二次散列法（Double Hashing）：这是开放寻址法的一种变种，当发生冲突时，使用第二个哈希函数来计算下一个可能的槽位，而不是简单地递增。这样可以减少聚集问题。
线性探测法（Linear Probing）：在线性探测法中，当发生冲突时，会线性地查找下一个可用的槽位，直到找到一个空槽位来存储冲突的元素。这个过程会很快，但可能导致聚集问题。
伪随机探测法（Pseudo-Random Probing）：这是一种改进的开放寻址法，使用伪随机数生成器来计算下一个槽位，以减少聚集问题。
拉链法（Separate Chaining）：这是链地址法的一种常见形式，每个槽位都关联一个链表，当发生冲突时，元素被插入到链表的末尾。拉链法的优点是容易实现，并且可以处理大量的冲突，但需要额外的内存来存储链表。

4、拉链法太长了查找复杂度高，有什么办法缓解？

动态扩容：一旦链表的平均长度达到一定阈值，就对哈希表进行动态扩容。这会增加哈希表的槽位数量，从而降低平均链表长度，提高查找效率。扩容通常需要重新哈希（rehashing）现有的元素到新的槽位中，这个过程需要一定的时间，但可以在继续插入新元素时叠加进行。
良好的哈希函数：使用更好的哈希函数可以降低冲突的概率，使元素更均匀地分布在各个槽位上。一个好的哈希函数应该能够将元素均匀地分散到不同的槽位上，以减少链表的长度。
链表优化：如果链表的长度仍然很长，可以考虑对链表进行优化，例如使用更高效的数据结构，如跳表（Skip List）或平衡树（Balanced Tree）。这些数据结构可以在链表中提供更快的查找时间，但会占用更多的内存。
二次哈希法：在拉链法中，可以考虑使用第二个哈希函数来进一步分散冲突的元素。这种方法被称为"二次哈希法"，它可以降低链表的平均长度。
删除不必要的元素：定期清理或删除哈希表中不再需要的元素，以减少链表的长度。这对于一些缓存应用来说是有帮助的，可以删除不经常使用的元素。

5、LRU算法：最近最少使用。LFU：使用频率最少？

LRU？

LRU（Least Recently Used）是一种常见的页面置换算法，通常用于操作系统中管理物理内存中的页面或缓存中的数据。LRU算法的核心思想是基于访问时间来淘汰最近最少使用的数据，即最近一段时间内未被访问的数据将被置换出去。

工作原理：

LRU算法维护一个缓存（或页面表），其中存储了最近被访问过的数据项。当需要访问一个数据项时，LRU算法首先检查该数据项是否已经在缓存中。如果在缓存中，那么它被标记为最近使用的，同时它的位置被移动到缓存的头部（或者其他合适的位置，取决于实现方式）。如果数据项不在缓存中，那么需要将一个数据项从缓存中移除，然后将新的数据项添加到缓存的头部。

实现方式：

LRU算法可以通过多种数据结构实现，包括双向链表和哈希表。以下是两种常见的实现方式：

双向链表 + 哈希表：
1. 使用一个双向链表来维护数据项的顺序，链表的头部表示最近访问的数据项，尾部表示最早访问的数据项。
2. 使用一个哈希表来实现从数据项到链表节点的快速查找。
3. 当需要访问一个数据项时，首先在哈希表中查找是否存在，如果存在，将该数据项移到链表头部，表示最近使用，如果不存在，则需要从链表尾部淘汰一个数据项，然后将新数据项添加到链表头部，并在哈希表中建立映射关系。
数组 + 位图：
1. 使用一个数组来存储数据项，数组的索引表示数据项的标识。
2. 使用一个位图来记录数据项的访问情况，每个位对应一个数据项。
3. 当需要访问一个数据项时，首先在位图中查找是否存在，如果存在，将该数据项标记为最近使用，如果不存在，则需要查找位图中最早未被访问的数据项，将其标记为最近使用，并更新位图。

优点：

LRU算法可以有效地利用缓存空间，确保缓存中的数据是最有可能被访问的数据。
在一些场景下，LRU算法能够提供相对较好的性能，特别是在缓存中的数据具有明显的访问模式时。

缺点：

实现LRU算法需要维护额外的数据结构，增加了一定的空间复杂度。
如果数据项的访问模式发生剧烈变化，LRU算法可能会失效，导致缓存不命中率增加。

参考代码实现：（哈希+链表）

c++

#include <iostream>
#include <unordered_map>
#include <list>

using namespace std;

class LRUCache {
private:
    int capacity;
    unordered_map<int, pair<int, list<int>::iterator>> cache; // key -> {value, iterator}
    list<int> lruList; // Doubly linked list to maintain LRU order

public:
    LRUCache(int capacity) {
        this->capacity = capacity;
    }

    int get(int key) {
        if (cache.find(key) != cache.end()) {
            // Move the accessed key to the front of the list (most recently used)
            lruList.splice(lruList.begin(), lruList, cache[key].second);
            return cache[key].first;
        }
        return -1;
    }

    void put(int key, int value) {
        if (cache.find(key) != cache.end()) {
            // Update the value and move the key to the front
            cache[key].first = value;
            lruList.splice(lruList.begin(), lruList, cache[key].second);
        } else {
            // Check if the cache is full
            if (cache.size() >= capacity) {
                // Remove the least recently used key from both the cache and the list
                int lruKey = lruList.back();
                cache.erase(lruKey);
                lruList.pop_back();
            }
            // Add the new key-value pair to the cache and list
            lruList.push_front(key);
            cache[key] = {value, lruList.begin()};
        }
    }
};

int main() {
    LRUCache cache(2); // Create an LRU cache with capacity 2

    cache.put(1, 1);  // Cache: {1=1}
    cache.put(2, 2);  // Cache: {1=1, 2=2}
    cout << cache.get(1) << endl; // Output: 1 (1 is the most recently used)
    cache.put(3, 3);  // Cache: {2=2, 3=3} (1 is removed as it's the least recently used)
    cout << cache.get(2) << endl; // Output: -1 (2 was removed)
    cout << cache.get(3) << endl; // Output: 3 (3 is the most recently used)

    return 0;
}

LFU？

LFU（Least Frequently Used）是一种页面置换算法，通常用于操作系统中管理物理内存中的页面或缓存中的数据。LFU算法的核心思想是淘汰最近最不经常使用的数据。

工作原理：

LFU算法维护一个缓存（或页面表），其中存储了被访问的数据项及其访问频率。当需要访问一个数据项时，LFU算法首先检查该数据项是否已经在缓存中。如果在缓存中，那么它的访问频率会增加，并且它的位置可能会根据新的频率进行更新。如果数据项不在缓存中，那么需要淘汰掉访问频率最低的数据项，然后将新的数据项添加到缓存中。

实现方式：

LFU算法可以通过多种数据结构实现，其中最常见的是使用一个最小堆（或优先队列）来维护数据项及其访问频率。

步骤：

使用一个哈希表来映射数据项到其在堆中的位置。
使用一个最小堆（或优先队列）来存储数据项及其访问频率，按照访问频率从小到大的顺序排列。
当需要访问一个数据项时，首先在哈希表中查找是否存在。如果存在，更新该数据项的访问频率，并调整堆中的位置。
如果数据项不在缓存中，需要淘汰堆顶的数据项，即访问频率最低的数据项。
将新的数据项添加到堆中，并在哈希表中建立映射关系。

优点：

LFU算法能够有效地淘汰那些访问频率低的数据项，确保缓存中的数据是相对频繁访问的数据。
在一些场景下，LFU算法能够提供相对较好的性能，特别是在缓存中的数据项的访问频率分布相对均匀的情况下。

缺点：

实现LFU算法需要维护额外的数据结构，增加了一定的空间复杂度。
LFU算法对于数据项的访问频率分布敏感，如果数据项的访问频率分布发生剧烈变化，LFU算法可能会失效，导致缓存不命中率增加。

参考代码实现：

c++

#include <iostream>
#include <unordered_map>
#include <list>

using namespace std;

class LFUCache {
private:
    int capacity;
    unordered_map<int, pair<int, int>> cache; // key -> {value, frequency}
    unordered_map<int, list<int>::iterator> keyToIter; // key -> iterator in freqList
    unordered_map<int, list<int>> freqToList; // frequency -> list of keys
    int minFreq;

public:
    LFUCache(int capacity) {
        this->capacity = capacity;
        minFreq = 0;
    }

    int get(int key) {
        if (cache.find(key) != cache.end()) {
            // Update frequency
            int value = cache[key].first;
            int freq = cache[key].second;
            cache[key].second++;
            freqToList[freq].erase(keyToIter[key]);
            freqToList[freq + 1].push_back(key);
            keyToIter[key] = --freqToList[freq + 1].end();
            // Update minFreq
            if (freqToList[minFreq].empty()) {
                minFreq++;
            }
            return value;
        }
        return -1;
    }

    void put(int key, int value) {
        if (capacity == 0) {
            return;
        }
        if (cache.find(key) != cache.end()) {
            // Update value and frequency
            cache[key].first = value;
            cache[key].second++;
            int freq = cache[key].second;
            freqToList[freq - 1].erase(keyToIter[key]);
            freqToList[freq].push_back(key);
            keyToIter[key] = --freqToList[freq].end();
            // Update minFreq
            if (freqToList[minFreq].empty()) {
                minFreq++;
            }
        } else {
            // Evict least frequent item if capacity is reached
            if (cache.size() >= capacity) {
                int evictKey = freqToList[minFreq].front();
                freqToList[minFreq].pop_front();
                keyToIter.erase(evictKey);
                cache.erase(evictKey);
            }
            // Add new item
            cache[key] = {value, 1};
            freqToList[1].push_back(key);
            keyToIter[key] = --freqToList[1].end();
            minFreq = 1;
        }
    }
};

int main() {
    LFUCache cache(2); // Create a cache with capacity 2

    cache.put(1, 1);  // cache = {1=1}
    cache.put(2, 2);  // cache = {1=1, 2=2}
    cout << cache.get(1) << endl; // Output: 1
    cache.put(3, 3);  // cache = {2=2, 3=3} (1 is removed because it's the least frequently used)
    cout << cache.get(2) << endl; // Output: -1 (not found)
    cout << cache.get(3) << endl; // Output: 3

    return 0;
}

6、浏览器输入网址，直到打开网页的过程？（太典了）

DNS解析：
- 浏览器首先会检查网址中的域名部分（例如，www.xxxxx.com）。
- 浏览器会向本地DNS缓存查询，如果之前已经解析过这个域名，就可以跳过后续步骤。
- 如果没有找到缓存，浏览器会向操作系统的DNS解析器发送请求，请求解析该域名的IP地址。
- DNS解析器可能会向根域名服务器、顶级域名服务器、权威域名服务器等层级进行查询，直到找到该域名对应的IP地址。
- 一旦获取到IP地址，浏览器就知道要连接的服务器位置。
建立TCP连接：
- 浏览器使用获取到的IP地址和HTTP默认端口（通常是80，或者443用于HTTPS）来建立与Web服务器的TCP连接。
- 这个过程包括TCP的三次握手，确保浏览器和服务器之间的可靠通信。
发送HTTP请求：
- 浏览器向服务器发送一个HTTP请求，该请求包括请求的资源、请求方法（GET、POST等）、HTTP协议版本以及其他一些头部信息。
- 服务器根据请求的资源路径和方法来响应请求，通常会检查请求头中的一些信息，如Cookie、User-Agent等。
服务器处理请求：
- 服务器根据HTTP请求的内容来执行相应的处理，这可能包括查询数据库、调用应用程序、生成动态内容等。
- 服务器生成HTTP响应，包括响应状态码、响应头和响应正文。
接收响应：
- 浏览器接收到来自服务器的HTTP响应。
- 如果响应状态码指示成功（例如，200 OK），浏览器将继续处理响应。
渲染页面：
- 浏览器根据响应中的HTML、CSS和JavaScript开始渲染页面。
- 浏览器解析HTML文档，构建DOM（文档对象模型）树。
- 浏览器解析CSS，构建CSSOM（CSS对象模型）树。
- 浏览器将DOM和CSSOM合并成一个渲染树，用于确定页面上各个元素的布局和样式。
- 浏览器执行JavaScript，可以修改DOM和CSSOM，以及处理用户交互。
- 浏览器根据渲染树绘制页面。
显示页面：
- 浏览器将渲染页面的结果显示在用户的屏幕上。
- 这包括文本、图像、多媒体元素等。
- 浏览器还处理用户的交互事件，如鼠标点击和键盘输入。
持续通信：
- 如果页面包含与服务器的WebSocket或长轮询等通信，浏览器将保持与服务器的连接，以接收实时数据。

7、tcp头有哪些字段？

源端口号（Source Port）：占用16位，表示数据包的发送方使用的端口号。
目标端口号（Destination Port）：占用16位，表示数据包的接收方使用的端口号。
序列号（Sequence Number）：占用32位，用于标识发送的数据字节在数据流中的位置。在建立连接时，用于初始化序列号。
确认号（Acknowledgment Number）：占用32位，如果ACK标志被设置，表示期望接收到的下一个序列号。它用于确认已成功接收的数据。
数据偏移（Data Offset）：占用4位，指示TCP头部的长度，以32位字为单位。这个字段指示了TCP头部中包含多少个32位的字。
保留（Reserved）：占用6位，保留用于将来的扩展，目前应设置为0。
标志位（Flags）：TCP头部包含多个标志位，包括：
- URG：紧急指针（Urgent Pointer）有效。
- ACK：确认字段有效。
- PSH：接收方应立即将数据推送给应用程序。
- RST：复位连接。
- SYN：用于建立连接。
- FIN：用于关闭连接。
窗口大小（Window Size）：占用16位，表示发送方可以接收的字节数。它允许接收方控制流量，避免发送方发送过多数据。
校验和（Checksum）：占用16位，用于检测TCP头部和数据的完整性，以防数据在传输过程中被损坏。
紧急指针（Urgent Pointer）：占用16位，仅在URG标志被设置时才有效。它指示紧急数据的末尾位置。
选项（Options）：可选字段，用于包含各种TCP选项，如最大报文大小、时间戳等。
填充（Padding）：用于将TCP头部的长度扩展到32位的倍数，以对齐数据。

8、IPV4与IPV6？

IPV4？

Pv4是互联网上广泛使用的第四版互联网协议。它采用32位地址，通常以点分十进制表示（例如，192.168.0.1）。IPv4定义了互联网上的数据包格式和路由规则。

IPV6？

IPv6是IPv4的下一代协议，旨在解决IPv4的地址短缺问题。IPv6采用128位地址，通常以冒号分隔的十六进制表示（例如，2001:0db8:85a3:0000:0000:8a2e:0370:7334）。

区别：

地址类型。IPv4具有三种不同类型的地址：多播，广播和单播。IPv6还具有三种不同类型的地址：任意广播，单播和多播。
数据包大小。对于IPv4，最小数据包大小为576字节。对于IPv6，最小数据包大小为1208字节。
header区域字段数。IPv4具有12个标头字段，而IPv6支持8个标头字段。
可选字段。IPv4具有可选字段，而IPv6没有。但是，IPv6具有扩展header，可以在将来扩展协议而不会影响主包结构。
配置。在IPv4中，新装的系统必须配置好才能与其他系统通信。在IPv6中，配置是可选的，它允许根据所需功能进行选择。
安全性。在IPv4中，安全性主要取决于网站和应用程序。它不是针对安全性而开发的IP协议。而IPv6集成了Internet协议安全标准（IPSec）。IPv6的网络安全不像IPv4是可选项，IPv6里的网络安全项是强制性的。
与移动设备的兼容性。IPv4不适合移动网络，因为正如我们前面提到的，它使用点分十进制表示法，而IPv6使用冒号，是移动设备的更好选择。
主要功能。IPv6允许直接寻址，因为存在大量可能的地址。但是，IPv4已经广泛传播并得到许多设备的支持，这使其更易于使用。

9、网络号怎么计算？

根据IP地址和子网掩码来计算。网络号指示了一个IP地址属于哪个网络。

假设您有一个IPv4地址（例如，192.168.1.100）和一个子网掩码（例如，255.255.255.0），要计算网络号，可以执行以下步骤：

将IP地址和子网掩码转换为二进制形式。例如：

IP地址：192.168.1.100 => 11000000.10101000.00000001.01100100 子网掩码：255.255.255.0 => 11111111.11111111.11111111.00000000

使用按位与（AND）操作将IP地址和子网掩码相结合。在每个相应的二进制位上，AND操作都会生成一个新的二进制位，结果是网络号的二进制形式。例如：

IP地址： 11000000.10101000.00000001.01100100 子网掩码：11111111.11111111.11111111.00000000 网络号： 11000000.10101000.00000001.00000000

最后，将网络号的二进制形式转换回十进制形式。例如：

网络号：11000000.10101000.00000001.00000000 => 192.168.1.0

10、进程间通信？

11、git相关？

12、了解哪些设计模式

这个最起码要答出工厂模式、单例模式、观察者模式吧

微服务

文档

基础

腾讯一面 ​

1、内联函数，优点及缺点？ ​

2、容器：map，set？ ​

3、unordered_map unordered_set？哈希表解决冲突办法 ​

4、拉链法太长了查找复杂度高，有什么办法缓解？ ​

5、LRU算法：最近最少使用。LFU：使用频率最少？ ​

6、浏览器输入网址，直到打开网页的过程？（太典了） ​

7、tcp头有哪些字段？ ​

8、IPV4与IPV6？ ​

9、网络号怎么计算？ ​

10、进程间通信？ ​

11、git相关？ ​

12、了解哪些设计模式 ​