2024深信服一面(一)

项目优化方式

红黑树是否了解

红黑树：红黑树是一种自平衡的二叉查找树，具有以下特点：

1. 每个节点要么是红色，要么是黑色
2. 根节点是黑色
3. 每个叶子节点（NIL节点，空节点）是黑色的
4. 不能有相邻接的两个红色节点
5. 从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点

单链表，双链表的特点，如何删除一个节点，删除效率

单链表：单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素 + 指针，指针指向下一个结点，最后一个结点指针指向空。单链表的特点是插入和删除的效率高，查找的效率低。
双链表：双链表是在单链表的每个结点中，再设置一个指向其前驱结点的指针域。双链表的特点是插入和删除的效率高，查找的效率低。
删除一个节点：单链表删除一个节点的效率为O(1)，双链表删除一个节点的效率为O(1)。

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
// 双链表数据结构
struct DoubleListNode{
    int val;
    DoubleListNode *pre;
    DoubleListNode *next;
    DoubleListNode(int x) : val(x), pre(NULL), next(NULL) {}
}
// 删除单链表中的一个节点
void deleteNode(ListNode* node){
    node->val = node->next->val;
    node->next = node->next->next;
}
// 删除双链表中的一个节点
void deleteNode(DoubleListNode* node){
    node->pre->next = node->next;
    node->next->pre = node->pre;
}

最小生成树

最小生成树：在一个连通的无向图中，找出一个边的子集，这个子集中的边连接了图中所有的顶点，并且权值之和最小。最小生成树的算法有Prim算法和Kruskal算法。

1. Prim算法：从一个顶点开始，每次选择一个与当前顶点相连的权值最小的边，直到所有的顶点都被选择。
2. Kruskal算法：将所有的边按照权值从小到大排序，然后从权值最小的边开始，如果这条边的两个顶点不在同一个连通分量中，就将这条边加入到最小生成树中，直到所有的顶点都在同一个连通分量中。

// Prim算法
int prim(int n, int m, vector<vector<int>>& edges){
    vector<vector<int>> graph(n, vector<int>(n, INT_MAX));
    for(int i = 0; i < m; i++){
        graph[edges[i][0]][edges[i][1]] = edges[i][2];
        graph[edges[i][1]][edges[i][0]] = edges[i][2];
    }
    vector<int> dist(n, INT_MAX);
    vector<bool> visited(n, false);
    dist[0] = 0;
    int res = 0;
    for(int i = 0; i < n; i++){
        int u = -1;
        for(int j = 0; j < n; j++){
            if(!visited[j] && (u == -1 || dist[j] < dist[u])){
                u = j;
            }
        }
        visited[u] = true;
        res += dist[u];
        for(int v = 0; v < n; v++){
            if(!visited[v] && graph[u][v] != INT_MAX){
                dist[v] = min(dist[v], graph[u][v]);
            }
        }
    }
    return res;
}
// Kruskal算法
int kruskal(int n, int m, vector<vector<int>>& edges){
    vector<int> parent(n);
    for(int i = 0; i < n; i++){
        parent[i] = i;
    }
    sort(edges.begin(), edges.end(), [](vector<int>& a, vector<int>& b){
        return a[2] < b[2];
    });
    int res = 0;
    for(int i = 0; i < m; i++){
        int x = edges[i][0];
        int y = edges[i][1];
        int w = edges[i][2];
        if(find(parent, x) != find(parent, y)){
            res += w;
            union(parent, x, y);
        }
    }
    return res;
}

int find(vector<int>& parent, int x){
    while(parent[x] != x){
        x = parent[x];
    }
    return x;
}

手写二分查找

int binarySearch(vector<int>& nums, int target){
    int l=0;
    int r=nums.size()-1;
    while(l<r){
        int mid=l+(r-l)/2;
        if(nums[mid]==target){
            return mid;
        }else if(nums[mid]<target){
            l=mid+1;
        }else{
            r=mid-1;
        }
    }
    return -1;
}

素数判断

bool isPrime(int n){
    if(n<2){
        return false;
    }
    for(int i=2;i*i<=n;i++){
        if(n%i==0){
            return false;
        }
    }
    return true;
}

爬楼梯问题

int climbStairs(int n){
    if(n<=2){
        return n;
    }
    // dp[i]表示爬到第i层楼梯的方法数
    vector<int> dp(n+1,0);
    dp[1]=1;
    dp[2]=2;
    for(int i=3;i<=n;i++){
        dp[i]=dp[i-1]+dp[i-2];
    }
    return dp[n];
}

项目数据库的设计和Redis设计

redis如何保证缓存高频数据

使用LRU算法，当缓存空间不足时，删除最近最少使用的数据。
持久化机制：可以将数据缓存到磁盘中，以防止服务器重启或者崩溃时数据丢失。

手撕字符串压缩

string compressString(string S){
    string res;
    int n=S.size();
    int i=0;
    while(i<n){
        int j=i;
        while(j<n&&S[j]==S[i]){
            j++;
        }
        res+=S[i];
        res+=to_string(j-i);
        i=j;
    }
    return res.size()<n?res:S;
}

手撕算法链表逆序

struct ListNode{
    int val;
    ListNode* next;
    ListNode(int x):val(x),next(NULL){}
};
ListNode* reverseList(ListNode* head){
    ListNode* pre=NULL;
    ListNode* cur=head;
    while(cur){
        ListNode* next=cur->next;
        cur->next=pre;
        pre=cur;
        cur=next;
    }
    return pre;
}

判断链表是否相交

struct ListNode{
    int val;
    ListNode* next;
    ListNode(int x):val(x),next(NULL){}
};
bool isIntersect(ListNode* headA, ListNode* headB){
    ListNode* p=headA;
    ListNode* q=headB;
    while(p&&q){
        p=p->next;
        q=q->next;
    }
    if(p){
        while(p){
            p=p->next;
            headA=headA->next;
        }
    }else{
        while(q){
            q=q->next;
            headB=headB->next;
        }
    }
    while(headA&&headB){
        if(headA==headB){
            return true;
        }
        headA=headA->next;
        headB=headB->next;
    }
    return false;
}
// 第二种方法
bool isIntersect(ListNode* headA, ListNode* headB){
    ListNode* p=headA;
    ListNode* q=headB;
    while(p!=q){
        p=p?p->next:headB;
        q=q?q->next:headA;
    }
    return p!=NULL;
}

// 第三种方法hash表法
bool isIntersect(ListNode* headA, ListNode* headB){
    unordered_set<ListNode*> hash;
    while(headA){
        hash.insert(headA);
        headA=headA->next;
    }
    while(headB){
        if(hash.count(headB)){
            return true;
        }
        headB=headB->next;
    }
    return false;
}

丢带水瓶问题

手撕有最大容量的队列，实现push和pop函数

class MyQueue{
public:
    MyQueue(int capacity){
        this->capacity=capacity;
        this->size=0;
        this->head=0;
        this->tail=0;
        this->data=new int[capacity];
    }
    ~MyQueue(){
        delete[] data;
    }
    bool push(int x){
        if(size==capacity){
            return false;
        }
        data[tail]=x;
        tail=(tail+1)%capacity;
        size++;
        return true;
    }
    bool pop(){
        if(size==0){
            return false;
        }
        head=(head+1)%capacity;
        size--;
        return true;
    }
private:
    int capacity;
    int size;
    int head;
    int tail;
    int* data;
};

缓存击穿，缓存雪崩，缓存穿透

缓存穿透：

访问一个缓存和数据库中不存在的key，此时请求会直接访问到数据库，并且查不到数据，没法写缓存，所以下次请求同样会访问到数据库上，此时缓存起不到作用，请求每次都会走到数据库，流量大时数据库可能会被打挂掉，这就是缓存穿透。
解决方法：参数校验，布隆过滤器，缓存空对象

缓存雪崩：

大量热点数据key设置了相同的过期时间，导致缓存在同一时刻全部失效，造成了数据库请求量激增，压垮数据库。还有一种情况是redis挂了，此时所有请求都会走到数据库上，造成数据库压力过大。
解决方法：第一种情况下可以给不同的key设置不同的过期时间，第二种情况下可以使用redis集群，保证redis的高可用性。

缓存击穿：

缓存击穿是指一个key非常热点，在不停的扛着大并发，大并发集中对这一个点进行访问，当这个key在失效的瞬间，持续的大并发就穿破缓存，直接请求数据库，就像在一个屏障上凿开了一个洞。
解决方法：设置热点数据永不过期，或者加互斥锁，只让一个线程去访问数据库，其他线程等待。

合并两个有序链表

struct ListNode{
    int val;
    ListNode* next;
    ListNode(int x):val(x),next(NULL){}
};
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2){
    ListNode* dummy=new ListNode(-1);
    ListNode* cur=dummy;
    while(l1&&l2){
        if(l1->val<l2->val){
            cur->next=l1;
            l1=l1->next;
        }else{
            cur->next=l2;
            l2=l2->next;
        }
        cur=cur->next;
    }
    cur->next=l1?l1:l2;
    return dummy->next;
}

二叉树的类别

二叉树：每个节点最多有两个子节点，分别称为左子节点和右子节点。
满二叉树：每个节点都有两个子节点，除了叶子节点。
完全二叉树：叶子节点只能出现在最下层和次下层，并且最下面一层的节点都集中在该层最左边的若干位置的二叉树。
二叉搜索树：左子树上所有节点的值均小于它的根节点的值，右子树上所有节点的值均大于它的根节点的值。
平衡二叉树：左右子树的高度差不超过1的二叉树。
红黑树：红黑树是一种自平衡的二叉查找树

二叉树的遍历

前序遍历：根节点->左子树->右子树
中序遍历：左子树->根节点->右子树
后序遍历：左子树->右子树->根节点
层序遍历：从上到下，从左到右

struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x):val(x),left(NULL),right(NULL){}
};
// 前序遍历
void preorder(TreeNode* root){
    if(root==NULL){
        return;
    }
    cout<<root->val<<endl;
    preorder(root->left);
    preorder(root->right);
}
// 中序遍历
void inorder(TreeNode* root){
    if(root==NULL){
        return;
    }
    inorder(root->left);
    cout<<root->val<<endl;
    inorder(root->right);
}
// 后序遍历
void postorder(TreeNode* root){
    if(root==NULL){
        return;
    }
    postorder(root->left);
    postorder(root->right);
    cout<<root->val<<endl;
}
// 层序遍历
void levelorder(TreeNode* root){
    queue<TreeNode*> q;
    q.push(root);
    while(!q.empty()){
        TreeNode* node=q.front();
        q.pop();
        cout<<node->val<<endl;
        if(node->left){
            q.push(node->left);
        }
        if(node->right){
            q.push(node->right);
        }
    }
}

手撕最长递增子序列

int lengthOfLIS(vector<int>& nums){
    int n=nums.size();
    vector<int> dp(n,1);
    for(int i=0;i<n;i++){
        for(int j=0;j<i;j++){
            if(nums[i]>nums[j]){
                dp[i]=max(dp[i],dp[j]+1);
            }
        }
    }
    int res=0;
    for(int i=0;i<n;i++){
        res=max(res,dp[i]);
    }
    return res;
}

分布式id

分布式id：分布式系统中，为了保证数据的唯一性，需要为每条数据生成一个唯一的id。分布式id的生成有以下几种方式：

1. UUID：UUID是一种由网络上的计算机生成的唯一标识符，标准的UUID格式为：xxxxxxxx-xxxx-Mxxx-Nxxx-xxxxxxxxxxxx，其中M表示UUID版本，N表示UUID变体。UUID的优点是简单易用，缺点是占用空间大，且无序。
2. 数据库自增ID：数据库自增ID的优点是简单易用，缺点是需要访问数据库，性能较差。
3. Redis自增ID：Redis自增ID的优点是简单易用，缺点是需要访问Redis，性能较差。
4. 雪花算法：雪花算法是Twitter开源的分布式ID生成算法，其核心思想是：使用一个64位的long型的数字作为全局唯一id，其结构如下：

   1. 第1位：符号位，0表示正数，1表示负数
   2. 第2-42位：时间戳，毫秒级
   3. 第43-52位：工作机器id，5位，32个机房，每个机房32台机器
   4. 第53-64位：序列号，12位，每个机器每毫秒最多生成4096个id

介绍一下布隆过滤器

布隆过滤器：布隆过滤器是一种数据结构，用来判断一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。

mysql和mongodb的区别

mysql是关系型数据库，mongodb是非关系型数据库。
mysql的数据存储在表中，mongodb的数据存储在集合中。
mysql的数据结构是行列式的，mongodb的数据结构是键值对的。
mysql的数据类型是固定的，mongodb的数据类型是动态的。
mysql的数据支持事务，mongodb的数据不支持事务。

mysql和postgresql的区别

数据类型：MySQL支持更多的数据类型，包括整数、浮点数、字符串、日期时间等。PostgreSQL支持更多的数据类型，包括数组、JSON、XML等。

查询语言：MySQL使用标准的SQL语言，但有一些特定的语法和函数。PostgreSQL也使用标准的SQL语言，但支持更多的高级特性，如窗口函数、递归查询等。

扩展性：MySQL在大规模数据处理和高并发访问方面表现较好，适合于Web应用和数据仓库等场景。PostgreSQL在复杂查询和数据完整性方面表现较好，适合于企业级应用和科学研究等场景。

可定制性：PostgreSQL提供了更多的可定制性选项，可以通过插件和扩展来增加功能和性能。MySQL的可定制性相对较少，但也有一些可选的存储引擎可以选择。

复制和高可用性：MySQL提供了多种复制方式和高可用性解决方案，如主从复制、主主复制、MySQL Cluster等。PostgreSQL也提供了复制功能和高可用性解决方案，如流复制、逻辑复制等。

社区和生态系统：MySQL拥有较大的用户

rabbitmq和rocketmq的区别，消息堆积如何处理

rabbitmq和rocketmq都是消息中间件，rabbitmq是AMQP协议的实现，rocketmq是MQTT协议的实现。
RabbitMQ使用AMQP（高级消息队列协议），是一个轻量级的消息代理，易于安装和配置，并且提供强大的消息处理能力。它支持多种消息模式和路由策略，例如直接、发布/订阅、主题等，同时提供了可靠的消息传递，包括消息持久化、确认和重试等功能。RabbitMQ具有强大的社区支持和广泛的应用。

RocketMQ是阿里巴巴开源的一款分布式消息系统，使用可扩展的发布/订阅模式，支持大规模消息处理和分布式事务。与RabbitMQ相比，RocketMQ更适用于高并发、持久化、共享访问、集群部署等需求。RocketMQ提供更加灵活的消息路由和队列管理功能，支持按时间维度进行消费进度回溯，适用于业务上需求需要重新消费的场景。

在消息堆积方面，RabbitMQ和RocketMQ都支持消息持久化，即将消息保存到磁盘上，以便在系统故障时能够恢复消息。RabbitMQ使用交换类型（Exchange Type）中的“持久化”类型来达到此目的。RocketMQ通过将消息在一定时间范围内保留在broker中，以便消费者可以按照需要回溯消费进度。在面对消息堆积时，两者都适合业务上能容忍丢弃消息的场景，这种情况下消息的堆积能力主要在于内存Buffer大小。当消息堆积后，RabbitMQ和RocketMQ的性能下降不会太大，因为内存中数据多少对于对外提供的访问能力影响有限。

对于RabbitMQ和RocketMQ的消息堆积处理，可以采取以下一些策略：
优化消息路由策略：通过合理配置交换器和队列的绑定关系，以及使用主题、标签等模式，将消息路由到合适的队列，避免消息的堆积。
持久化消息：通过将消息进行持久化存储，保证在系统故障时能够恢复消息，避免消息丢失。
限流和排队策略：通过限制生产者发送消息的速度或者使用排队机制，避免消息的快速堆积。
消费者消费速度调整：根据业务需要和实际情况调整消费者的消费速度，以匹配生产者的发送速度，避免消息的堆积。
优化系统性能：通过优化系统性能，提高消息处理速度和吞吐量，避免消息的堆积

redis为什么快

redis是基于内存的，内存的读写速度非常快，而且redis是单线程的，避免了线程切换的开销，所以redis的读写速度非常快。

多路复用

多路复用：多路复用是指通过一条线路同时传输多路信号，即在一条线路上同时传输多路信号。在操作系统中，多路复用是指通过一条线程同时处理多个请求，即在一个线程中同时处理多个请求。多路复用的实现方式有以下几种：

1. select：select是一种多路复用的实现方式，它的原理是：将所有的socket放入一个集合中，然后调用select函数，select函数会阻塞，直到集合中的某个socket有数据到达，select函数返回，然后遍历集合中的所有socket，找到有数据到达的socket，然后处理数据。select的缺点是：每次调用select函数都需要遍历集合中的所有socket，效率较低。
2. poll：poll是select的改进版，它使用一个pollfd结构体数组来表示待监听的文件描述符集合，并通过poll系统调用来等待这些文件描述符中的任意一个变为可读或可写。poll的优点是可以监听的文件描述符数量没有上限，但仍然需要遍历整个文件描述符集合。
3. epoll：epoll是Linux特有的多路复用机制，它使用一个epoll_event结构体数组来表示待监听的文件描述符集合，并通过epoll_ctl和epoll_wait系统调用来进行操作。epoll的优点是效率高，它使用红黑树来存储文件描述符，可以快速定位到发生事件的文件描述符。
4. kqueue：kqueue是BSD和Mac OS X中的多路复用机制，它使用一个kevent结构体数组来表示待监听的文件描述符集合，并通过kqueue系统调用来进行操作。kqueue的优点是可以同时监听多种事件类型，包括读、写、异常等。

介绍一下redis的数据结构

redis的数据结构有以下几种：

1. 字符串：字符串是redis最基本的数据结构，它的底层实现是简单动态字符串，字符串的最大长度为512M。
2. 列表：列表是一种有序的字符串列表，它的底层实现是双向链表，列表的最大长度为2^32-1。
3. 集合：集合是一种无序的字符串集合，它的底层实现是哈希表，集合的最大长度为2^32-1。
4. 有序集合：有序集合是一种有序的字符串集合，它的底层实现是跳跃表和哈希表，有序集合的最大长度为2^32-1。
5. 哈希表：哈希表是一种键值对的无序散列表，它的底层实现是哈希表，哈希表的最大长度为2^32-1。
6. 地理位置：地理位置是一种存储地理位置信息的数据结构，它的底层实现是二维的GeoHash编码，地理位置的最大长度为2^32-1。

lru算法

LRU算法：LRU算法是一种缓存淘汰算法，它的原理是：当缓存空间不足时，删除最近最少使用的数据。LRU算法的实现方式有以下几种：

1. 数组：数组是一种实现LRU算法的简单方式，它的原理是：将最近访问的数据放到数组的最后，当缓存空间不足时，删除数组的第一个数据。数组的缺点是删除数据的时间复杂度为O(n)。
2. 链表：链表是一种实现LRU算法的简单方式，它的原理是：将最近访问的数据放到链表的最后，当缓存空间不足时，删除链表的第一个数据。链表的缺点是删除数据的时间复杂度为O(n)。
3. 哈希表+双向链表：哈希表+双向链表是一种实现LRU算法的高效方式，它的原理是：使用哈希表存储数据，使用双向链表存储数据的访问顺序，当缓存空间不足时，删除双向链表的第一个数据。哈希表+双向链表的优点是删除数据的时间复杂度为O(1)。

判断链表是否有环

struct ListNode{
    int val;
    ListNode* next;
    ListNode(int x):val(x),next(NULL){}
};
bool hasCycle(ListNode* head){
    ListNode* fast=head;
    ListNode* slow=head;
    while(fast&&fast->next){
        fast=fast->next->next;
        slow=slow->next;
        if(fast==slow){
            return true;
        }
    }
    return false;
}
// 环的入口
ListNode* detectCycle(ListNode* head){
    ListNode* fast=head;
    ListNode* slow=head;
    while(fast&&fast->next){
        fast=fast->next->next;
        slow=slow->next;
        if(fast==slow){
            break;
        }
    }
    if(!fast||!fast->next){
        return NULL;
    }
    slow=head;
    while(slow!=fast){
        slow=slow->next;
        fast=fast->next;
    }
    return slow;
}

削峰

削峰：削峰是指通过一些手段，将流量的峰值削平，使得流量的峰值不会超过一定的阈值。削峰的实现方式有以下几种：

1. 限流：限流是指限制流量的大小，使得流量的峰值不会超过一定的阈值。限流的实现方式有令牌桶算法和漏桶算法。
2. 缓存：缓存是指将流量缓存起来，使得流量的峰值不会超过一定的阈值。缓存的实现方式有本地缓存和分布式缓存。
3. 降级：降级是指将流量降级，使得流量的峰值不会超过一定的阈值。降级的实现方式有降级页面和降级服务。
4. 异步：异步是指将流量异步处理，使得流量的峰值不会超过一定的阈值。异步的实现方式有消息队列和线程池。

JWT单点登录

JWT单点登录：JWT是一种无状态的认证方式，它的原理是：用户登录后，服务器生成一个JSON对象，将JSON对象加密后生成一个字符串，然后将字符串返回给客户端，客户端将字符串保存在Cookie中，以后每次请求都将Cookie中的字符串放到请求头中，服务器通过解密字符串来判断用户是否登录。JWT单点登录的优点是：无状态、跨域、可扩展，缺点是：不支持退出登录、不支持修改密码、不支持多端登录。

auth2.0

OAuth 2.0是一种授权框架，用于允许用户通过第三方应用程序访问受保护的资源，而无需共享其凭据。它提供了一种安全且标准化的方式，使用户可以通过授权服务器授予第三方应用程序访问其资源的权限。

在使用OAuth 2.0进行登录时，用户首先会被重定向到认证服务器，以进行身份验证。认证服务器会要求用户提供其凭证（例如用户名和密码），以验证其身份。一旦用户通过身份验证，认证服务器将生成一个访问令牌（access token），并将其返回给用户。

用户随后将访问令牌传递给第三方应用程序，以证明其身份并请求访问受保护的资源。第三方应用程序将使用该访问令牌向授权服务器发送请求，以验证其有效性和权限。如果访问令牌有效且具有所请求资源的适当权限，授权服务器将向第三方应用程序提供所需的访问权限。

通过OAuth 2.0进行登录具有以下优点：

用户无需共享其凭证，可以安全地访问受保护的资源。
用户可以选择授予或撤销第三方应用程序对其资源的访问权限。
第三方应用程序无需存储用户的凭证，减少了安全风险。
总之，OAuth 2.0是一种安全且灵活的授权框架，可用于实现用户在第三方应用程序中的登录和访问受保护资源

mysql的索引结构

mysql的索引结构有以下几种：

1. B+树：B+树是一种平衡的多路搜索树，它的特点是：所有的叶子节点都在同一层，且叶子节点之间通过指针连接，可以快速定位到叶子节点。B+树的优点是查询效率高，缺点是插入和删除效率低。
2. 哈希表：哈希表是一种根据键值（Key-Value）直接进行访问的数据结构，它的特点是：通过哈希函数将键值映射到哈希表中的一个位置，然后在该位置存储键值对。哈希表的优点是查询效率高，缺点是不支持范围查询。
3. full-text：full-text是一种全文索引，它的特点是：通过分词器将文本分词，然后将分词结果存储到倒排索引中。full-text的优点是支持全文检索，缺点是查询效率低。

mysql的事务隔离级别

mysql的事务隔离级别有以下几种：

1. 读未提交：读未提交是指一个事务可以读取另一个未提交事务的数据，它的优点是读取数据最新，缺点是会出现脏读、不可重复读和幻读。
2. 读已提交：读已提交是指一个事务要等另一个事务提交后才能读取数据，它的优点是避免了脏读，缺点是会出现不可重复读和幻读。
3. 可重复读：可重复读是指一个事务在执行过程中多次读取同一数据，它的优点是避免了脏读和不可重复读，缺点是会出现幻读。
4. 串行化：串行化是指一个事务在执行过程中对数据进行加锁，其他事务不能读取和修改数据，它的优点是避免了脏读、不可重复读和幻读，缺点是效率低下。

手撕求加密和解密两个函数

string encrypt(string s){
    string res;
    for(int i=0;i<s.size();i++){
        res+=s[i]^'a';
    }
    return res;
}
string decrypt(string s){
    string res;
    for(int i=0;i<s.size();i++){
        res-=s[i]^'a';
    }
    return res;
}

手撕不同任何条件语句判断数据大小

int getMax(int a, int b){
    int c=a-b;
    int sa=(c>>31)&1;
    int sb=sa^1;
    return a*sa+b*sb;
}

手写一个生成验证码的算法，要求验证码不能重复，必须由数字和字母随机生成的6位数，然后再写一个验证 验证码的算法。

string generateCode(){
    string res;
    for(int i=0;i<6;i++){
        int t=rand()%2;
        if(t==0){
            res+=rand()%10+'0';
        }else{
            res+=rand()%26+'a';
        }
    }
    return res;
}
bool verifyCode(string code){
    if(code.size()!=6){
        return false;
    }
    for(int i=0;i<code.size();i++){
        if(code[i]<'0'||code[i]>'9'){
            if(code[i]<'a'||code[i]>'z'){
                return false;
            }
        }
    }
    return true;
}

spring事务传播机制

spring事务传播机制有以下几种：

1. REQUIRED：如果当前存在事务，则加入该事务；如果当前没有事务，则创建一个新的事务。这是最常用的传播机制。
2. SUPPORTS：如果当前存在事务，则加入该事务；如果当前没有事务，则以非事务的方式执行
3. MANDATORY：如果当前存在事务，则加入该事务；如果当前没有事务，则抛出异常。
4. REQUIRES_NEW：创建一个新的事务，如果当前存在事务，则把当前事务挂起。
5. NOT_SUPPORTED：以非事务的方式执行操作，如果当前存在事务，则把当前事务挂起。
6. NEVER：以非事务的方式执行操作，如果当前存在事务，则抛出异常。
7. NESTED：如果当前存在事务，则在嵌套事务内执行；如果当前没有事务，则创建一个新的事务。

Java相比于其他语言的优势

Java是一种面向对象的编程语言，它的优点是：

1. 简单易学：Java语法与C语言和C++语言很接近，易于学习。
2. 面向对象：Java是一种面向对象的编程语言，支持封装、继承和多态。
3. 平台无关性：Java可以编译生成字节码，然后可以在任意平台上运行。
4. 可靠性：Java是一种强类型的编程语言，它提供了一种垃圾回收机制，可以自动管理内存。
5. 安全性：Java可以运行在沙箱环境中，可以在沙箱中执行不可信代码，保证系统的安全性。
6. 支持多线程：Java提供了多线程支持，可以编写多线程程序。

跨平台语言有很多，为什么Java最流行

可扩展性和向后兼容性：Java是一种静态类型的语言，它的可维护速度更快，更易于维护，而且还具有向后兼容性，这意味着旧版本的语言即使在新版本发布后也能够完美运行。
可移植性：由于Java与平台无关，它几乎可以在所有系统上运行，这使得开发人员可以更容易地开发和部署应用程序。
面向对象编程：Java不仅支持封装、继承和多态等面向对象编程的基本特征，而且具有良好的安全性，包括自动内存管理、沙箱安全模型和类加载器等机制，使得Java成为一个相对安全的编程语言。
大型社区支持：Java拥有庞大的用户群和丰富的资源，包括Stack Overflow、开源中国和GitHub等大型社区的存在，使得Java开发人员遇到任何问题都能很快的找到解决方案，这进一步促进了Java的流行。

说说你对一次编译，到处运行的理解

“一次编译，处处运行”是指Java语言的一种特性，即Java源代码只需编译一次，就可以在任何支持Java虚拟机的平台上运行，不需要再次编译。

这一特性的实现主要归功于Java虚拟机（JVM）。Java源代码首先被编译成字节码，这是一种与特定平台无关的中间代码。然后，JVM在运行时将字节码解释成具体平台上的机器指令，从而实现了跨平台运行。

需要注意的是，虽然Java字节码是平台无关的，但不同的操作系统可能需要不同的JVM实现来解释和执行字节码。因此，“一次编译，处处运行”的前提是在每个目标平台上都有对应的JVM实现。

Java虚拟机的垃圾回收机制

Java虚拟机（JVM）的垃圾回收机制是一种自动的存储管理机制。当Java虚拟机运行时，它需要动态地分配内存空间来存储数据，包括对象和基本数据类型。然而，当这些内存空间中的数据不再需要时，应该及时释放这些内存以供其他用途，否则会导致内存溢出等问题。Java虚拟机的垃圾回收机制的主要目标是寻找那些不再被使用的对象，并清除掉这些对象所占用的内存空间。具体来说，垃圾回收机制通过以下步骤完成：

1. 寻找垃圾：垃圾回收机制通过跟踪程序中的所有引用关系，找到不再被使用的对象，这些对象被称为垃圾。
2. 清除垃圾：一旦找到垃圾对象，垃圾回收机制就会释放掉它们所占用的内存空间，使这些内存空间可以被重新利用。

Java虚拟机的垃圾回收机制具有自动性、动态性和及时性等特点。它能够帮助程序员减轻内存管理的负担，减少内存溢出的风险，提高程序的可靠性和稳定性。然而，由于垃圾回收机制的运行需要一定的时间和资源，因此也可能会对程序的性能产生一定的影响。此外，Java虚拟机的垃圾回收机制也存在一些限制和挑战，例如无法处理循环引用等问题。主要实现方式有以下几种：

1. 标记-清除：标记-清除是一种基本的垃圾回收算法，它的原理是：首先标记出所有需要回收的对象，然后统一回收所有被标记的对象。标记-清除的缺点是效率低，会产生大量的内存碎片。
2. 复制：复制是一种基本的垃圾回收算法，它的原理是：将内存空间分为两块，每次只使用其中的一块，当这一块内存用完了，就将还存活的对象复制到另一块上面，然后再把已使用过的内存空间一次清理掉。复制的缺点是只能使用内存空间的一半。
3. 标记-整理：标记-整理是一种基本的垃圾回收算法，它的原理是：首先标记出所有需要回收的对象，然后将所有存活的对象都向一端移动，然后直接清理掉端边界以外的内存。标记-整理算法是一种比较高效的垃圾回收方式，因为它只需要对存活的对象进行移动和整理，而不需要像复制算法一样将所有的对象进行复制。此外，它也可以避免因内存碎片的产生而提前触发垃圾回收，提高了垃圾回收的效率和内存利用率。
4. 分代收集：分代收集是一种基本的垃圾回收算法，它的原理是：根据对象的存活周期，将内存分为新生代和老年代，然后根据各个年代的特点采用最适当的垃圾回收算法。分代收集的优点是提高了垃圾回收的效率，缺点是实现复杂。

现有一亿个IP地址，我需要判断当前我自己的IP地址是否在这一亿个数据集中，设计一个合理的数据结构来实现快速判断

哈希表或者字典树

手撕代码：不同路径

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m,vector<int>(n,0));
        for(int i=0;i<m;i++){
            dp[i][0]=1;
        }
        for(int i=0;i<n;i++){
            dp[0][i]=1;
        }
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
};

寻找小于某个树的最大质数

int func(int target){
    int j=target;
    while(j>1){
        if(isPrime(j)){
            return j;
        }
        j--;
    }
}

bool isprime(int n){
    if(n<2) return false;
    for(int i=2;i*i<=n;i++){
        if(n%i==0){
            return false;
        }
    }
    return true;
}

Spring AOP的几种通信方式

Spring AOP的几种通知方式有以下几种：

1. 前置通知：在目标方法执行前调用通知功能。
2. 后置通知：在目标方法执行后调用通知功能。
3. 返回通知：在目标方法返回后调用通知功能。
4. 异常通知：在目标方法抛出异常后调用通知功能。
5. 环绕通知：在目标方法执行前后调用通知功能。

快排

void quickSort(vector<int>& nums,int l,int r){
    if(l>=r){
        return;
    }
    else {
        int j=pation(nums,l,r);
        quickSort(nums,l,j-1);
        quickSort(nums,j+1,r);
    }
}
int pation(vector<int> nums, int low, int high){
    int p=nums[high];
    int i=low-1;
    for(int j=low;j<high;j++){
        if(nums[j]<p){
            i++;
            swap(nums[i],nums[j]);
        }
    }
    swap(nums[i+1],nums[high]);
    return i+1;
}

归并排序

// 归并排序
void mergeSort(vector<int>& nums,int l,int r){
    if(l>=r){
        return;
    }
    else{
        int mid=(l+r)/2;
        mergeSort(nums,l,mid);
        mergeSort(nums,mid+1,r);
        merge(nums,l,mid,r);
    }
}
void merge(vector<int>& nums,int l,int mid,int r){
    vector<int> temp(r-l+1);
    int i=l;
    int j=mid+1;
    int k=0;
    while(i<=mid&&j<=r){
        if(nums[i]<nums[j]){
            temp[k++]=nums[i++];
        }
        else{
            temp[k++]=nums[j++];
        }
    }
    while(i<=mid){
        temp[k++]=nums[i++];
    }
    while(j<=r){
        temp[k++]=nums[j++];
    }
    for(int i=0;i<temp.size();i++){
        nums[l+i]=temp[i];
    }
}
// 合并两个无序链表，使用归并排序
ListNode* merge(ListNode* l1,ListNode* l2){
    if(!l1){
        return l2;
    }
    if(!l2){
        return l1;
    }
    if(l1->val<l2->val){
        l1->next=merge(l1->next,l2);
        return l1;
    }
    else{
        l2->next=merge(l1,l2->next);
        return l2;
    }
}

常见的分布式事务解决方案

常见的分布式事务解决方案有以下几种：

1. XA分布式协议-2PC（两阶段提交实现）：协调者来开启事务，首先协调者会向所有的事务执行者发送事务内容，等待所有的事务执行者答复。各个事务执行者开始执行事务操作，但是不进行提交，并将undo和redo信息记录到事务日志中。如果事务执行者执行事务成功，那么就告诉协调者成功Yes，否则告诉协调者失败No，不能提交事务。当所有的执行者都反馈完成之后，协调者会检查各个执行者的反馈内容，如果所有的执行者都返回成功，那么就告诉所有的执行者可以提交事务了，最后再释放锁资源。如果有至少一个执行者返回失败或是超时，那么就让所有的执行者都回滚，分布式事务执行失败。
   缺点：2PC的缺点是性能低，阻塞时间长，容易造成死锁，不适合高并发场景。协调者单点故障，会造成整个系统不可用。

2. XA分布式事务协议3-PC(三阶段提交实现)：在两阶段的基础上加入了超时机制，同时在协调者和执行者中引入了超时机制。
   缺点：超时后的commit决策是带赌注性质的，可能造成数据不一致。

3. TCC：TCC是一种补偿型的分布式事务解决方案，它的原理是：将一个大事务拆分成若干个子事务，每个子事务都有三个操作：Try、Confirm和Cancel。Try操作用于执行业务，Confirm操作用于确认业务，Cancel操作用于取消业务。TCC的优点是性能高，适合高并发场景，缺点是实现复杂。与业务相关性过高，不适合通用场景。

OAuth2.0的授权模式

1. 客户端模式：直接向验证服务器请求一个Token，服务拿到Token后就可以直接访问资源服务器了。但是这种模式并不是为用户设计的，因为没有用户参与，所以也就没有办法确定用户是否同意授权。而是为了那些需要自己访问资源服务器的应用设计的，比如后端的微服务之间的调用。
2. 密码模式：用户将自己的用户名和密码发送给客户端，客户端使用这些信息向授权服务器请求Token，然后客户端就可以直接访问资源服务器了。这种模式的优点是用户不需要自己向授权服务器请求Token，缺点是客户端需要保存用户的用户名和密码，这样就增加了安全风险。
3. 隐式授权模式：首先用户访问页面时，会重定向到认证服务器，接着认证服务器会给用户一个认证页面，等待用户授权，用户填写信息完成授权后，认证服务器返回Token。
4. 授权码模式：客户端访问应用服务器时，应用服务器会重定向到认证服务器，接着认证服务器会给用户一个认证页面，等待用户授权，用户填写信息完成授权后，认证服务器会重定向到应用服务器，并且携带一个授权码，应用服务器拿到授权码后，再向认证服务器请求Token，最后应用服务器拿到Token后就可以直接访问资源服务器了。

手撕合并无序链表

struct ListNode{
    int val;
    ListNode* next;
    ListNode(int x):val(x),next(NULL){}
};
// 由于

给一个数组，有重复元素无序，让你查找第一个只出现一次的元素的位置（只遍历一遍如何解决）

int findFirst(vector<int> nums){
    unordered_map<int,int> m;
    unordered_map<int,int> index;
    int ans;
    for(int i=0;i<nums.size();i++){
        m[nums[i]]++;
        // index 记录对应出现次数的元素列表
        index[nums[i]]=i;
        // 如果出现次数超过1，就将index中首个元素删除
        if(m[nums[i]]>1){
            index.erase(nums[i]);
        }
    }
    // 如果index为空，说明没有只出现一次的元素
    if(index.empty()){
        return -1;
    }
    // 否则返回index中首个元素的位置
    return index.begin()->second;
    //return -1;
}