真不容易，腾讯给一面了！！！

阿Q正砖 2023-09-15

177

大家好，我是阿Q。

先给大家分享一个第一时间收到新文章的小妙招~

划重点：

第一步点进主页找到右上角“...”；

第二步点击“设为星标”。就这么简单！！赶紧操作起来吧~

给大家说说我为什么要开始分享面经，作为一个过来人，我觉得总结面经对于我们在面试找工作中应该是非常重要的一个环节。

首先，它可以让我们复盘一下我们在面试过程中哪些答得好，哪些答得差那么点意思。以便于我们在下一次面试中更加关注那些问题，不至于在同一个石头绊倒两次。。。

再就是我们可以根据面经继续复习自己的知识点，做更全面的了解、更充分的准备！

这个时间点也正是找工作的大好时机，各大公司都开启了自己一年一度的大型校招模式。所谓“金九银十”，我们一定要抓住这个时候拿到自己心仪的offer。

今天来分享一位同学在腾讯面试中遇到的问题~

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

哈希表解决冲突办法？

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

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

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

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

LRU？

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

工作原理：

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

实现方式：

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

双向链表 + 哈希表：

使用一个双向链表来维护数据项的顺序，链表的头部表示最近访问的数据项，尾部表示最早访问的数据项。
使用一个哈希表来实现从数据项到链表节点的快速查找。
当需要访问一个数据项时，首先在哈希表中查找是否存在，如果存在，将该数据项移到链表头部，表示最近使用，如果不存在，则需要从链表尾部淘汰一个数据项，然后将新数据项添加到链表头部，并在哈希表中建立映射关系。

数组 + 位图：

使用一个数组来存储数据项，数组的索引表示数据项的标识。
使用一个位图来记录数据项的访问情况，每个位对应一个数据项。
当需要访问一个数据项时，首先在位图中查找是否存在，如果存在，将该数据项标记为最近使用，如果不存在，则需要查找位图中最早未被访问的数据项，将其标记为最近使用，并更新位图。

优点：

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

缺点：

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

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


#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算法可能会失效，导致缓存不命中率增加。

参考代码实现：


#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位的倍数，以对齐数据。

了解更多TCP的知识点，可点击：计算机网络-TCP/UDP详解（最全）

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、进程间通信？

另一篇文章有详细解释：Linux进程间通信详解（最全）

11、git相关？

直达Git文档：Git命令大全（硬核）

12、了解哪些设计模式

设计模式：浅谈设计模式

上边面试问到的但是我之前有文章总结的，就不在这儿浪费时间多讲一遍了，大家可以直接看看之前的文章进行学习，如果有不详细或者不准确的地方，大家还是也书为准。。

哈希表数据项链表哈希函数查找算法

文章转载自阿Q正砖，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

真不容易，腾讯给一面了！！！

评论