大数据查询、秤球
- 有一个40亿不重复的unsigned int数据。给出几个数据，快速找出这些数据是否在所有数据中。
- 插入一个数x：将bit位x对应的值设为1。
- 删除一个数x：将bit位x对应的值设为0。
- 查找一个数x：查看bit位x对应的值。
- 插入： 对于要插入的元素，将其分别通过k个哈希函数计算得到k个哈希值，然后根据这些哈希值找到位数组中的k个位置，将这些位置的位设为1。
- 查询： 对于要查询的元素，同样将其通过k个哈希函数计算得到k个哈希值，然后根据这些哈希值找到位数组中的k个位置，如果所有这些位置的位都为1，那么认为这个元素可能在集合中；如果有任何一个位置的位为0，那么这个元素肯定不在集合中。
思路：
位图：如果数据量不太大，我们可以采用位图法，将每个数都映射到一个二进制位上，可以将所有的数放到一个长度为2^32的位图中，即使用一个unsigned int类型的数组来表示。时间复杂度为O(n) + 查找时间O(1)。
实现
位图（Bitmap）是一种非常高效的数据结构，它使用一个bit位来标记某个元素对应的值，而非整个int或者long的长度，所以空间效率非常高。假设我们有1到n的n个数据，我们就可以用n个bit表示。
以下是位图的基本操作：
这里假设数据范围为0到n-1，用一个n位的位图即可表示。以下是一个基本的Python实现：
在这个例子中，我们使用一个整型数组来存储bit位，每个整型数可以存储32个bit位（假设整数是32位的）。我们使用位操作来设置、重置和测试bit位。
需要注意的是，位图的主要限制是它只能处理非负整数，并且无法处理重复的数字。此外，如果数据的范围非常大，位图可能需要消耗大量的内存。例如，如果数据的范围是1到10^9，那么我们需要的位图大小将会是10^9 bit，大约120MB，这在很多情况下是可以接受的。但如果数据范围更大，例如1到10^12，那么位图的大小就会达到120GB，这对于绝大多数应用来说是无法接受的。
最高位二分（编程珠玑）：
将这40亿个数分成两类：1.最高位为0；2.最高位为1。
并将这两类分别写入到两个文件中，其中一个文件中数的个数<=20亿，而另一个>=20亿（这相当于折半了）；
与要查找的数的最高位比较并接着进入相应的文件再查找
再然后把这个文件为又分成两类：1.次最高位为0；2.次最高位为1。
并将这两类分别写入到两个文件中，其中一个文件中数的个数<=10亿，而另一个>=10亿（这相当于折半了）；与要查找的数的次最高位比较并接着进入相应的文件再查找。
.......
以此类推，就可以找到了,而且时间复杂度为O(logn)。
布隆过滤器：上述两种解法都默认数据范围在40亿左右，但这个假设可能不成立，40亿条数据，但数据范围可能更大的多。如果数据范围更大，例如1到10^12，那么位图的大小就会达到120GB。此时，我们可以使用Bloom Filter（布隆过滤器），一种快速判断一个元素是否存在于一个集合中的算法。Bloom Filter可以利用位图和哈希函数，将所有的数哈希到一个长度为k的位数组中，并将每一位都置为1。当给出一个数时，我们可以将这个数哈希到这个位数组中，并检查哈希到的k个位置是否都为1，若都为1，则说明该数在这40亿个数中。Bloom Filter具有空间效率高、时间效率高、支持动态增加元素等特点，被广泛应用于大数据场景下的快速查找和去重。
实现
在构造布隆过滤器时，需要定义位数组的大小（m位）和哈希函数的个数（k个）。以下是其基本操作：
下面是一个简单的Python实现：
在这个例子中，我们首先创建了一个大小为
size的位数组。然后，对于每个要插入或查询的元素，我们使用hash_num个哈希函数（在这个例子中，我们使用Python的内置hash函数和不同的种子模拟多个哈希函数）计算哈希值，然后根据哈希值找到位数组中的位置。需要注意的是，由于布隆过滤器的误报率，它通常用在需要快速判断元素是否可能在集合中的场景，例如网页爬虫判断一个URL是否被访问过，或者垃圾邮件过滤等。如果需要精确的判断，那么可能需要结合其他数据结构或方法。
具体实现中，可实现到误判率为0.03这个程度。
ref：
- 20个球。有一个不及格的。用最少的称法，找出不及格的。
公式：只找不及格的：log3(2N+1)，要找出轻重log3(2N+3)
构造方式：动态构造：
问题的核心便是：在每一次称重后，我们都需要把解答的空间缩小到原来的 1/3。
方法是：把 可能较轻的集合L 和 可能较重的集合H 包含的所有球中取出 2/3（四舍五入），放在天平两端，然后用正常的球补上其他空缺让两边球数相同，使得：无论天平是哪一边重或者平衡，解的空间都可以缩小到原来的 1/3。
归并多个有序链表
字节八股
- HTTP实现一个多线程下载器。如何知道一个文件大小的，如何进行切割。
核心：要知道文件的大小，先通过HTTP HEAD请求获取Content-Length长度，然后根据这个长度分块，分到不同线程中分别下载。分段下载核心是，流式下载，在请求头添加开始和结束。
实现
实现一个多线程下载器涉及到HTTP请求的使用、文件I/O操作，以及多线程的管理。这里我将使用Python语言并使用其内置的
requests库进行HTTP请求，threading库来实现多线程，并使用os和shutil库进行文件操作。这种简化的多线程下载器将从指定的URL下载文件，并将其分割成若干部分，每个线程下载一部分。首先，我们需要确定远程文件的大小，这样我们才能将其分割成相等的部分供每个线程下载。我们可以通过发送
HEAD请求并检查Content-Length头来实现这一点。然后，我们将文件分割成相等的部分，并为每个线程分配一个部分。每个线程将向服务器发送一个带有
Range头的GET请求，该头指示服务器只发送文件的特定部分。最后，每个线程将其部分写入一个临时文件。当所有线程都完成下载后，主线程将所有部分合并到一个文件中。
以下是一个简单的实现：
这是一个非常简化的多线程下载器。在实际应用中，你可能需要添加错误处理代码，例如处理网络错误和文件I/O错误，以及更复杂的线程管理代码。你还可能需要调整代码以更好地适应大文件和慢速网络。
- DNS协议。传输层协议用的什么。
UDP是DNS协议的首选传输层协议，因为UDP是一种无连接的、不可靠的协议，它的开销比TCP小，在DNS查询过程中可以提供更快的响应速度。在使用UDP协议时，DNS服务器将响应数据包发送到请求方的IP地址和端口号，而不会进行连接的建立和断开。
在某些情况下，DNS协议需要使用TCP协议来进行数据传输。例如，在传输大型DNS数据包或进行DNS区域传输时，DNS协议需要使用TCP协议进行数据传输。
视频、会议等实时通信应用一般使用UDP协议作为传输层协议，以实现低延迟和高吞吐量的数据传输。
- TCP中Close Wait状态服务器还能不能发送数据。
能。
- 键入一个网站的完整处理过程。2.2 键入网址到网页显示，期间发生了什么？ | 小林coding (xiaolincoding.com)
- 数据库不同分类是否了解。关系型、非关系型、KV等，怎么使用的，如何选择。
- 关系型数据库：基于关系模型的数据库，例如MySQL、Oracle、SQL Server等。
- 非关系型数据库：不基于关系模型的数据库，例如MongoDB、Redis、Cassandra等。
- 结构化数据： 如果你的数据结构固定且不易改变，关系型数据库通常是一个很好的选择。关系型数据库使用评估过的表结构（即表的列是预定义的），所以它们最适合于存储结构化数据。
- 事务性：如果你的应用需要执行复杂的事务，例如银行转账，关系型数据库通常是最佳选择。这是因为它们支持ACID（原子性，一致性，隔离性，持久性）事务。
- 数据一致性：如果需要严格的数据一致性，关系型数据库可能是最好的选择。例如，在一个电子商务应用中，库存，订单，和支付系统之间的数据必须始终保持一致。
- 复杂的查询：关系型数据库使用SQL（结构化查询语言）进行数据查询，它支持复杂的查询，包括联接操作，子查询等。
- 灵活的数据模型：如果你的数据结构经常变化，或者你想避免复杂的数据库模型设计，那么非关系型数据库可能是一个好选择。例如，MongoDB允许你存储灵活的、JSON-like的文档，这些文档可以包含任何类型的数据。
- 水平可扩展性：如果你有大量的数据（例如，TB或PB级别）或者非常高的读/写负载，非关系型数据库可能是更好的选择。许多非关系型数据库都设计成可以在廉价的硬件集群上水平扩展。
- 高性能：如果你的应用需要非常高的性能，非关系型数据库可能是一个好选择。例如，Redis是一个在内存中存储数据的键值存储，它可以提供非常高的读写速度。
- 非结构化数据：如果你的应用需要处理非结构化数据，例如图像，音频，视频，或者半结构化数据，例如JSON或XML文档，非关系型数据库可能是一个好选择。
选择关系型数据库（RDBMS）还是非关系型数据库（NoSQL）通常取决于你的应用程序的数据需求，这包括数据的结构、数据量、读写操作的比例和频率，以及数据的一致性和可扩展性需求等等。
以下是一些关于何时选择关系型数据库（例如 MySQL, PostgreSQL, Oracle）或非关系型数据库（例如 MongoDB, Cassandra, Redis）的指导原则。
关系型数据库：
非关系型数据库：
不过值得注意的是，每个数据库系统都有其特定的优势，一种数据库可能不适合所有的情况。且现在很多应用采用多数据库的策略，例如，他们可能会同时使用关系型数据库和非关系型数据库，以便根据不同的需求选择最合适的工具。
- Linux IO多路复用。select、epoll的核心区别。
- select：这可能是最早的I/O多路复用机制，它可以监视文件描述符集合的读、写和异常事件。当调用
select函数时，线程会阻塞，直到至少有一个文件描述符准备好I/O操作，或者超时。select的主要弊端是它只能监视的文件描述符数量有限（通常最多1024），并且每次调用select都需要重新指定监视的文件描述符集合。 - poll：
poll与select类似，但它没有监视文件描述符数量的限制。然而，poll的效率在处理大量文件描述符时会降低，因为它需要遍历整个文件描述符列表。 - epoll：
epoll是Linux特有的I/O多路复用机制，它旨在解决select和poll在处理大量文件描述符时的效率问题。与select和poll不同，epoll使用一种称为事件驱动的方式，当我们添加或删除文件描述符时，只需要通知内核一次，而且它可以处理的文件描述符数量几乎没有限制。 - select：
select函数通过内核来查询每个socket看它是否处于就绪状态。如果处于就绪状态，就可以开始进行I/O操作，否则就等待。在这个过程中，select会被阻塞。当有一个socket就绪，或者达到用户设置的超时时间时，select就会返回。这种方法的缺点是每次调用select，都需要传入所有的socket，而且最大数目也受到限制。 - poll：
poll的工作方式与select类似，不过poll并没有最大文件描述符的限制。poll采用链表的方式存储和管理socket，因此它的性能并不会随着监控的socket数量的增加而降低。但是，poll还是需要遍历和检查所有的socket，如果这些socket并没有就绪，那么这个操作就是浪费的。 - epoll：
epoll是Linux特有的I/O多路复用机制，它通过内核和用户空间共享一块内存来避免了select和poll的缺点。在调用epoll_wait时，如果没有已经就绪的文件描述符，epoll会被阻塞，而当某个文件描述符就绪时，内核会采用回调的方式激活该文件描述符，epoll_wait就会返回。这样，就避免了无效的遍历，提高了效率。 - 效率：
select在每次调用时都需要遍历整个文件描述符集，来查找就绪的文件描述符。而epoll只关注那些实际发送了事件的文件描述符。因此，epoll在处理大量文件描述符时的效率要高于select。 - 扩展性：
select有一个固定的限制在文件描述符的数量上(通常为1024)，这对于需要处理大量连接的高并发服务器来说是不够的。而epoll没有这样的限制，它可以处理数以万计的并发连接。 - 触发方式：
select采用水平触发（Level Triggered，LT）方式。也就是说，只要有一个文件描述符就绪，select就会返回，即使这个文件描述符在上一次查询后仍然没有被处理。而epoll既支持水平触发也支持边缘触发（Edge Triggered，ET）。边缘触发模式下，只有当状态发生变化时才会通知应用程序。这意味着如果你忘记了处理一个事件，你可能就会丢失它。 - API的复杂性：
select的API相对简单。只需要一个select函数，你就可以设置监视的文件描述符集，以及超时时间。然而，epoll的API更复杂。你需要使用epoll_create创建一个epoll对象，然后使用epoll_ctl添加、修改或删除要监视的文件描述符，最后使用epoll_wait等待事件的发生。
在Linux系统中，I/O多路复用技术允许单个线程监视多个文件描述符（比如套接字）的I/O事件。常用的I/O多路复用机制包括
select，poll，epoll，在某些系统中还包括kqueue。以下是每种技术的简介：
在选择使用哪种I/O多路复用技术时，应考虑你的应用的需求。如果你只需要监视少量的文件描述符，并且跨平台性是一个重要因素，那么
select或poll可能是一个好选择。如果你需要监视大量的文件描述符，并且应用运行在Linux系统上，那么epoll可能是一个更好的选择。以下是Linux I/O多路复用的几种技术的实现原理：
select和epoll都是Linux系统的I/O多路复用技术，但它们的工作机制有着显著的区别。以下是它们的主要区别：总的来说，
epoll提供了比select更高的效率和扩展性，但是使用起来也更复杂。你应该根据你的具体需求选择最适合的技术。- Linux定时器的实现。比如TCP中发送一个ACK包后有一个超时等待，如何去做。
- 内核定时器：
timer_list是Linux内核中的一种定时器，它在内核空间中实现。你可以通过init_timer初始化一个定时器，add_timer添加一个定时器，del_timer删除一个定时器。当一个定时器到期时，内核会调用该定时器的回调函数。 - POSIX定时器：POSIX定时器是在用户空间的定时器，它是按照POSIX.1b实时扩展标准设计的。你可以通过
timer_create创建一个定时器，timer_settime设置一个定时器，timer_gettime获取一个定时器的剩余时间，timer_delete删除一个定时器。当一个POSIX定时器到期时，它会生成一个信号，你可以在信号处理程序中处理该事件。
自己想的思路是做一个调度的时钟线程，去调度等待线程。
在Linux中，定时器的实现主要有两种方式：内核定时器和POSIX定时器。下面是它们的简单介绍：
在TCP中，如果你发送了一个ACK包，然后需要等待一段时间，你可以使用上述的任何一种定时器。一种可能的方法是，当你发送一个ACK包时，设置一个定时器。然后在定时器的回调函数或信号处理程序中检查是否收到了响应。如果没有收到响应，你可以重新发送ACK包，或者进行其他的错误处理。
例如，以下是一个使用内核定时器的简单示例：
这是一个非常基本的示例，实际的使用可能会更复杂，比如你可能需要在定时器的回调函数中访问共享数据，或者需要处理多个定时器。
- 作者:Olimi
- 链接:https://olimi.icu/article/26177229-6bf9-4946-b3dd-8a98e25e8238
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。