东风草堂博客

2G内存在20亿个整数中找出次数最多的数？

kv来描述一个数，一个整数4byte，两个整数8byte，20亿个整数需要16G内存。
数据结构存储：平衡二叉树map、散列表unordered_map。
分治：20亿个整数拆分成若干个范围，分别统计若干个范围中的次数多最大值，汇总若干个范围中的次数最大值，找出次数最大值对应的树。
逆向分析：
2GB = 2 * 2^10 * 2^10 * 2^10 B = 2^31 B，小范围的数字最多 2^31 / 8 = 2^28
有多少个小范围？整数4个字节共32bit，范围为-2^31～2^31，共2^32个整数，2^32/2^28 = 2^4
正向解决：

• 将20亿个数拆分为16个范围
• 将20亿个数依次除以2^28，得到一个0-15的值，放在一个小文件中，另外一种解法：hash分流，相同的key，经过多次hash总是得到相同的值，hash具备随机性，crc16、md5、murmurhash2、siphash、cityhash
• 每个小文件unordered_map[k]++，散列表进行词频统计，如果某一个key出现次数超过10亿，就不必要统计了，这样也可以控制value的范围

40亿个非负整数中算中位数和找出现两次的数

1. 最多使用1GB的内存，找出所有出现了两次的数
   出现了两次，共三种状态：

如果中序遍历为有序的话则为二叉搜索树，为了避免退化为单链表，加入平衡规则后保持平衡则为平衡二叉树，搜索的时间复杂度为O(lgn).
满二叉树、完全二叉树又推出最大堆、最小堆（堆排序、定时器）。平衡二叉树又推出avl、红黑树。
对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

二叉树的递归遍历

前序遍历：根->左->右，1>2>4>5>3>6>7，245这棵树是作为一个整体子树从根节点遍历，这就是递归的思想。
中序遍历：左->根->右，4>2>5>1>6>3>7，每次遍历到子树也是重新左->根->右进行遍历。
后序遍历：左->右->根，4>5>2>6>7>3>1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

void PreOrder(TreeNode *root)
{
    if (root == nullptr) return;
    result.push_back(root->val);
    PreOrder(root->left);
    PreOrder(root->right);
}

void InOrder(TreeNode *root)
{
    if (root == nullptr) return;
    InOrder(root->left);
    result.push_back(root->val);
    InOrder(root->right);
}

void PostOrder(TreeNode *root)
{
    if (root == nullptr) return;
    PostOrder(root->left);
    PostOrder(root->right);
    result.push_back(root->val);
}

二叉树的迭代遍历

系统级IO

每个进程都有个umask，通过umask函数来设置的，当进程通过带某个mode参数的open函数来创建一个新文件时，文件的访问权限位被设置为mode & ~umask，也就是umask是程序设定的掩码，哪怕你open时mode为777，最后出来的权限有可能不是777了。

共享文件：

• 每个进程都有它独立的描述符表，它的表项是由进程打开的文件描述符来索引的。每个打开的描述符表项指向文件表中的一个表项。
• 打开文件的集合是由一张文件表来表示的，所有进程共享这张表。文件表表项包括当前的文件位置、引用计数即当前指向该表项的描述符表项数，以及一个指向v-node表中对应表项的指针。引用计数变为0内核才会删除这个文件表项。
• 所有进程共享v-node表。表项包含stat结构中的大部分信息，如st_mode、st_size成员。
  描述符1/4打开不同的文件，有不同的文件表项，以及相对应的v-node:
  
  子进程有父进程描述符的副本，父子进程共享相同的文件表，所以共享相同的文件位置，另外，内核删除相应文件表表项之前，父子进程都必须关闭了它们的文件描述符。
  
  同一个文件open两次，也有不同的文件表项，记录自己的文件位置，但v-node是同一个，这种属于文件共享：
  

IO重定向：

TCP/UDP应用场景分析

游戏行业（可以让业务定制化，比如自定义重传策略，有些包可以不需要重发）、音视频通话（比如超过1s的包可以不重发）、出于资源的考虑，比如dns解析，手机定位获取隐私，嵌入式设备发送信息(用电池的设备，比如家里的消防传感器，一个电池用5年)、大块数据下载，不考虑网络拥塞。
tcp相比于udp，主要是重发导致的延迟。

UDP sendto/recvfrom的坑

tcp时流式传输，而udp是报文传输，发完的数据需要对端一次性读取完整，否则会造成数据丢失，所以一次性最多只能发送1500-20-8=1472的数据量（1500为网卡MTU的大小），避免拆包，加上PPPOE的协议头，一般发送1400就够了，在游戏领域，由于发送的数据量少，一般为572或者500就行了，如果发超过了，tcpdump可以看到会报bad length。

UDP如何实现可靠性设计

漏桶算法

把请求比作是水，水来了都先放进桶里，并以限定的速度出水，当水来得过猛而出水不够快时就会导致水直接溢出，即拒绝服务。

可以看出，漏桶算法可以很好的控制流量的访问速度，一旦超过该速度就拒绝服务。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

#include <iostream>
#include <chrono>
#include <thread>
using namespace std;
using namespace std::chrono;

class LeakyBucket {
public:
    LeakyBucket(int capacity, int rate){
        this->capacity = capacity;
        this->rate = rate;
        this->water_count = 0;
        this->last_leak_time = duration_cast<milliseconds>(system_clock::now().time_since_epoch());
    }

    bool take_request(){
        auto now = duration_cast<milliseconds>(system_clock::now().time_since_epoch());
        int passed_time = (int)(now - last_leak_time).count();

        water_count -= passed_time * rate; // 固定的速度流水
        if(water_count < 0){
            water_count = 0;
        }

        if(water_count < capacity){ // 请求就是加入的水，加满了就拒绝服务
            water_count++;
            last_leak_time = now;
            return true;
        }

        return false;
    }

private:
    int capacity;
    int rate;
    int water_count;
    time_point<system_clock> last_leak_time;
};

int main() {
    LeakyBucket bucket(10, 2);

    for(int i = 0; i < 20; i++){
        if(bucket.take_request()){
            cout << "request " << i + 1<< " passed" << endl;
        } else {
            cout << "request " << i + 1 << " discarded" << endl;
        }
        if(i != 19){
            std::this_thread::sleep_for(100ms);
        }
    }

    return 0;
}

令牌桶算法

令牌桶算法的原理是系统会以一个恒定的速度往桶里放入令牌，而如果请求需要被处理，则需要先从桶里获取一个令牌，当桶里没有令牌可取时，则拒绝服务。从原理上看，令牌桶算法和漏桶算法是相反的，一个“进水”，一个是“漏水”。

进程和线程的区别？

1. 一个线程只能属于一个进程，而一个进程可以有多个线程，但至少有一个线程。线程依赖于进程而存在。
2. 进程在执行过程中拥有独立的内存单元，而多个线程共享进程的内存。（资源分配给进程，同一进程的所有线程共享该进程的所有资源。同一进程中的多个线程共享代码段（代码和常量），数据段（全局变量和静态变量），扩展段（堆存储）。但是每个线程拥有自己的栈段，栈段又叫运行时段，用来存放所有局部变量和临时变量。）
3. 进程是资源分配的最小单位，线程是CPU调度的最小单位；
4. 系统开销： 由于在创建或撤消进程时，系统都要为之分配或回收资源，如内存空间、I／o设备等。因此，操作系统所付出的开销将显著地大于在创建或撤消线程时的开销。类似地，在进行进程切换时，涉及到整个当前进程CPU环境的保存以及新被调度运行的进程的CPU环境的设置。而线程切换只须保存和设置少量寄存器的内容，并不涉及存储器管理方面的操作。可见，进程切换的开销也远大于线程切换的开销。
5. 通信：由于同一进程中的多个线程具有相同的地址空间，致使它们之间的同步和通信的实现，也变得比较容易。进程间通信IPC，线程间可以直接读写进程数据段（如全局变量）来进行通信——需要进程同步和互斥手段的辅助，以保证数据的一致性。在有的系统中，线程的切换、同步和通信都无须操作系统内核的干预。
6. 进程编程调试简单可靠性高，但是创建销毁开销大；线程正相反，开销小，切换速度快，但是编程调试相对复杂。
7. 进程间不会相互影响 ；线程一个线程挂掉将导致整个进程挂掉。
8. 进程适应于多核、多机分布；线程适用于多核。
9. 线程必须放在fork之后，因为fork之前创建的线程不会被继承.

在 Linux 内核中，0 号进程（也称为 idle 进程）是系统中唯一一个没有被正常进程显式创建的进程，它是在内核启动时创建的，负责消耗 CPU 时间，以保证系统不会浪费 CPU 资源。
1 号进程（也称为 init 进程）是 Linux 系统启动后第一个被创建的进程，它是所有进程的祖先进程。init 进程负责启动系统上其他进程和服务，并在系统关闭时关闭这些进程和服务。
2 号进程（也称为 kthreadd 进程）是一个守护进程，它是内核中的一个主要线程。它是内核线程的创建者，也是唯一的内核线程，其主要职责是协调内核中的各种子系统，如内存管理、进程管理、文件系统等。
需要注意的是，0 号进程、1 号进程和 2 号进程是内核级别的进程，它们不同于普通进程，不会被用户显式创建、销毁或操纵。

进程间通信的方式

进程间通信主要包括管道、系统IPC（包括消息队列、信号量、信号、共享内存等）、以及套接字socket。

缓存方案主要用于缓存用户定义的热点数据，用户可以通过缓存来获取数据，从而降低数据库的压力。
内存访问速度远大于磁盘访问速度，mysql缓存的数据跟业务无关，缓存的是最近操作的数据。mysql作为项目的主要数据库，缓存数据库只是辅助功能。

缓存一致性

• mysql有，redis无，正常
• mysql无，redis有，不正常
• 都有，数据不一致，不正常
• 都有，数据一致，正常
• 都没有，正常

读写策略

• 读策略：先读缓存，缓存存在直接返回，缓存不存在，去访问Mysql获取，若存在，再写缓存
• 写策略：
  • 安全：先删除缓存中数据，再写mysql，再同步到redis.这样mysql的压力会大
  • 效率：先写缓存，设置过期时间（防止mysql写失败），再写mysql，最后将mysql中的数据同步到redis中

找完全二叉树最底层最右边的结点

给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最右边 节点的值。
假设二叉树中至少有一个节点。

完全二叉树的特点，即除了最后一层外，每一层都是满的，并且最后一层上的节点都集中在该层最左边的若干位置上。所以，如果我们按照层次遍历这个完全二叉树，最后遍历到的节点即为底层最右节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

#include <iostream>
#include <queue>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// 求完全二叉树的底层最右节点
TreeNode* findBottomRightNode(TreeNode* root) {
    if (!root) return NULL;

    queue<TreeNode*> q;
    q.push(root);

    TreeNode* cur = NULL;
    while (!q.empty()) {
        int n = q.size();
        for (int i = 0; i < n; i++) {
            cur = q.front();
            q.pop();

            if (cur->left) q.push(cur->left);
            if (cur->right) q.push(cur->right);
        }
    }

    return cur;
}

int main() {
    // 手动构建一个完全二叉树
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->left = new TreeNode(6);

    TreeNode* br = findBottomRightNode(root);
    cout << "底层最右节点的值为：" << br->val << endl;

    return 0;
}

二叉树的最近公共祖先

网络通信模型

TCP/IP与OSI最大的不同在于：OSI是一个理论上的网络通信模型，而TCP/IP则是实际运行的网络协议。

为什么连接的时候是三次握手，关闭的时候却是四次挥手？

三次握手

第一次握手：第一次握手是客户端发送同步报文到服务端，这个时候客户端是知道自己具备发送数据的能力的，但是不知道服务端是否有接收和发送数据的能力；

自旋锁

自旋锁是最基本的一种无锁技术，采用基于 CAS（Compare-and-Swap）的操作，尝试获取锁，失败时采用轮询的方式等待资源，避免线程被阻塞，不需要系统调用，从而减少上下文切换和性能损耗。
原子操作使用 CPU 提供的原子性指令，属于硬件层面的，实现数据的原子性访问和修改，避免使用锁导致的线程阻塞和竞争，同时也避免了死锁的发生。
加锁区执行速度快的情况下可以使用该锁。
atomic提供的常见方法：

• store：原子写操作。
• load：原子读操作。
• compare_exchange_strong：传入[期望原值]和[设定值]，当前值与期望值相等时，修改当前值为设定值，返回true；当前值与期望值不等时，将期望值修改为当前值，返回false。
• compare_exchange_weak：同上，但允许偶然出乎意料的返回（比如在字段值和期待值一样的时候却返回了false），比strong性能更好些，但需要循环来保证逻辑的正确性。
• exchange：交换2个数值，并保证整个过程是原子的。

C++11标准中提供了 std::atomic 模板类，用于实现原子操作，可用于实现 CAS 操作，从而实现无锁编程。
在非并发条件下，实现一个栈的Push操作，通常有如下操作：

• 步骤1：新建一个节点，node* const new_node = new node(data);
• 步骤2：将该节点的next指针指向现有栈顶，new_node->next = head;
• 步骤3：更新栈顶，head = new_node