2021-09-16

2023-11-23 16:15:04

美团2020部分笔试题解析

博主步入大四了，最近忙着各种东奔西跑，参加宣讲会，为校招做准备ing…为了各大招聘的笔试，博主最近在牛客刷一些大公司的历年笔试题目，以下是2020美团校招系统开发方向的部分笔试题解析：

1.如果线上某台虚机CPU Load过高，该如何快速排查原因？只介绍思路和涉及的Linux命令即可。

答：造成cpu load过高的原因： Full gc次数的增大、代码中存在Bug（例如死循环、正则的不恰当使用等）都有可能造成cpu load 增高。

jps -v：查看java进程号
top -Hp [java进程号]：查看当前进程下最耗费CPU的线程
printf “%x\n” [步骤2中的线程号]：得到线程的16进制表示
jstack [java进程号] | grep -A100 [步骤3的结果]：查看线程堆栈，定位代码行。参考：如何使用JStack分析线程状态

2.请简要描述MySQL数据库联合索引的命中规则，可举例说明。

答：1) MySQL联合索引遵循最左前缀匹配规则，即从联合索引的最左列开始向右匹配，直到遇到匹配终止条件。例如联合索引(col1, col2, col3), where条件为col1=a AND col2=b可命中该联合索引的(col1,col2)前缀部分, where条件为col2=b AND col3=c不符合最左前缀匹配，不能命中该联合索引。

匹配终止条件为范围操作符(如>, <, between, like等)或函数等不能应用索引的情况。例如联合索引(col1, col2, col3), where条件为col1=a AND col2>1 AND col3=c, 在col2列上为范围查询，匹配即终止，只会匹配到col1，不能匹配到(col1, col2, col3).
where条件中的顺序不影响索引命中。例如联合索引(col1, col2, col3), where条件为col3=c AND col2=b AND col1=a, MySQL优化器会自行进行优化，可命中联合索引(col1, col2, col3).

3.什么是分布式事务，分布式事务产生的原因是什么？分布式事务的解决方案有哪些？分别有哪些优缺点？

答：具体的解析博主觉得这位博主解释的比较全面：

https://www.cnblogs.com/hujinshui/p/11482208.html

4.请描述https的请求过程。

答：

客户端向服务器发起HTTPS请求，连接到服务器的443端口；
服务器端有一个密钥对，即公钥（即数字证书）和私钥，是用来进行非对称加密使用的，服务器端保存着私钥，不能将其泄露，公钥可以发送给任何人；
服务器将自己的公钥发送给客户端；
客户端收到服务器端的公钥之后，检查其合法性，如果发现发现公钥有问题，那么HTTPS传输就无法继续，如果公钥合格，则客户端会生成一个客户端密钥，然后用服务器的公钥对客户端密钥进行非对称加密成密文，至此，HTTPS中的第一次HTTP请求结束；
客户端发起HTTPS中的第二个HTTP请求，将加密之后的客户端密钥发送给服务器；
服务器接收到客户端发来的密文之后，会用自己的私钥对其进行非对称解密，解密之后的明文就是客户端密钥，然后用客户端密钥对数据进行对称加密，这样数据就变成了密文；
然后服务器将加密后的密文发送给客户端；
客户端收到服务器发送来的密文，用客户端密钥对其进行对称解密，得到服务器发送的数据。这样HTTPS中的第二个HTTP请求结束，整个HTTPS传输完成。

5.什么是事务传播行为？你知道Spring事务中都有哪些传播类型吗？如何使用/指定传播类型？

答：

1）事务传播用于描述当一个由事务传播行为修饰的方法被嵌套入另外一个方法时，事务如何传播。常用于定义发生事务嵌套时，如何继续执行。

2） Spring *定义了7中事务传播类型，明细如下表，需答出3~4种常见类型即可：

a) PROPAGATION_REQUIRED：当前没有事务时开启新事务，如果有则加入；

b) PROPAGATION_REQUIRES_NEW：强制开启新事务，挂起已有事务（如有）；

c) PROPAGATION_SUPPORTS：当前有事务时加入，没有则以非事务方式执行；

d) PROPAGATION_NOT_SUPPORTED：以非事务方式执行，挂起当前事务（如有）；

3）可以在注解或者XML中指定传播类型，如 “@Transactional(Propagation=xxx)”

6.IO设计中Reactor 和 Proactor 区别。

答：

1、 Reactor被动的等待指示事件的到来并作出反应，有一个等待的过程，做什么都要先放入到监听事件集合中等待handler可用时再进行操作，实现相对简单，对于耗时短的处理场景比较高效，但Reactor处理耗时长的操作会造成事件分发的阻塞，影响到后续事件的处理。

2、Proactor直接调用异步读写操作，调用完后立刻返回，实现了一个主动的事件分离和分发模型；这种设计允许多个任务并发的执行，从而提高吞吐量；并可执行耗时长的任务（各个任务间互不影响），Proactor性能更高，能够处理耗时长的并发场景，但Proactor实现逻辑复杂；依赖操作系统对异步的支持，目前实现了纯异步操作的操作系统少，实现优秀的如windows IOCP，但由于其windows系统用于服务器的局限性，目前应用范围较小；而Unix/Linux系统对纯异步的支持有限，应用事件驱动的主流还是通过select/epoll来实现。

7.以字符串的形式读入两个数字，再以字符串的形式输出两个数字的和。

#include<iostream>
#include<string>
#include<vector>
 
using namespace std;

// 两个字符串相加，模拟手算。两个字符串只有数字，没有符号
string addString(string str1,string str2){
    string res="";
    int pos1=str1.size()-1, pos2=str2.size()-1;
    int C=0, num1=0, num2=0, sum=0;
    // 从后向前逐个相加。
    for(;pos1>=0||pos2>=0; pos1--, pos2--){
        num1=pos1>=0? str1[pos1]-'0': 0;
        num2=pos2>=0? str2[pos2]-'0': 0;
        sum=num1+num2+C;
        res= to_string(sum%10) + res;
        C=sum/10;
    }
    if(C){
        res= to_string(C)+res;
    }
    return res;
}
// 两个字符串相减，模拟手算。两个字符串只有数字，没有符号
string minusString(string str1, string str2){
    bool res_positive=true;
    // 若str1表示的数字小于str2的，两者交换，并将结果符号设为负。
    if(str1.size()<str2.size() || (str1.size()==str2.size()&& str1<str2)){
        res_positive=false;
        string temp=str2;
        str2=str1;
        str1=temp;
    }
    string res="";
    int pos1=str1.size()-1, pos2=str2.size()-1;
    int C=0, num1=0, num2=0;
    // 从后向前逐个相减
    for(;pos1>=0||pos2>=0; pos1--, pos2--){
        num1=pos1>=0? str1[pos1]-'0': 0;
        num2=pos2>=0? str2[pos2]-'0': 0;
        if(num1-C<num2){
            num1= num1-C+10;
            C=1;
        }else{
            num1=num1-C;
            C=0;
        }
        res= to_string(num1-num2) + res;
    }
    pos1=0;
    // 找到第一个非零位置
    while(pos1<res.size()&& res[pos1]=='0'){
        pos1++;
    }
    if(pos1==res.size()){ // res都是0
        res="0";
    }else if(pos1>0){  // res前缀部分是0
        res=res.substr(pos1);
    }
    if(res_positive==false){ // 结果res是负数
        res= "-"+res;
    }
    return res;
}
 
int main(){
    string str1, str2;
    getline(cin, str1);
    getline(cin, str2);
    // 去掉引号
    str1=str1.substr(1, str1.size()-2);
    str2=str2.substr(1, str2.size()-2);
    // 去掉正负号，记录数值正负
    bool positive1=true, positive2=true;
    if(str1[0]=='-'){
        positive1=false;
        str1=str1.substr(1);
    }else if(str1[0]=='+')
        str1=str1.substr(1);
    if(str2[0]=='-'){
        positive2=false;
        str2=str2.substr(1);
    }else if(str2[0]=='+')
        str2=str2.substr(1);
     
    string res;
    // 这两个字符串异号
    if(positive1 ^ positive2){
        if(positive1==false){ // 第一个字符串是负数
            res=minusString(str2, str1);
        }else { // 第二个字符串是负数
            res=minusString(str1,str2);
        }
    }else{ // 同号
        res=addString(str1,str2);
        if(positive1==false)
            res="-"+res;
    }
    cout<<"\"" <<res<<"\""<<endl;
     
    return 0;
}

8.给定一个字符串，你的任务是计算这个字符串中有多少个回文子串（回文串是一个正读和反读都一样的字符串）。具有不同开始位置或结束位置的回文串，即使是由相同的字符组成，也会被计为是不同的子串。

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main()
{
    string str;
    cin >> str;
    int len = str.length();
    
    int count = 1; 
    for (int i = 1; i < str.length(); i++)
    {
        string x = "";
        x+= str[i];
        for (int j =1; j <= i;j++)
        {
            x+=str[i - j];
            string tem = x;
            reverse(tem.begin(), tem.end());
            if (x == tem)
                count++;
        }
        count++;
    }
    cout << count << endl;
    return 0;
}

拓展：reverse()函数的使用

reverse()函数可以对字符串进行反转操作，头文件#include

容器类型的要用begin()和end()来指定反转的区域，数组类型的直接用int类型即可，示范如下：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int main()
{
    string s="hello";
    reverse(s.begin(),s.end());
    char c[]="hello";
    reverse(c,c+strlen(c));
    char x[6]={'h','e','l','l','o'};
    reverse(x,x+strlen(x));
    char str[11];
    for(int i=0;i<5;i++)cin>>str[i];
    reverse(str,str+5);
    cout<<s<<endl;
    cout<<c<<endl;
    cout<<x<<endl;
    for(int i=0;i<5;i++)cout<<str[i];
    return 0;
}

运行结果如下：

hello
olleh
olleh
olleh
olleh

9.有 N 堆金币排成一排，第 i 堆中有 C[i] 块金币。每次合并都会将相邻的两堆金币合并为一堆，成本为这两堆金币块数之和。经过N-1次合并，最终将所有金币合并为一堆。请找出将金币合并为一堆的最低成本。其中，1 <= N <= 30，1 <= C[i] <= 100

链接：https://www.nowcoder.com/questionTerminal/6d3ccbc5b6ad4f12b8fe4c97eaf969e0
来源：牛客网

#include<iostream>      //区间动态规划
#include<vector>
#include<climits>
#include<algorithm>
using namespace std;
int main()
{
    int N;
    cin>>N;
    vector<int> c(N);
    vector<vector<int>> f(N,vector<int>(N,INT_MAX));    //存放结果，f[i][j]表示从下标i堆到下标j堆的最小成本
    vector<int> sum(N);                                 //存放当前金币和，用于bp计算
    for(int i=0;i<N;i++)
    {
        cin>>c[i];
        f[i][i]=0;                    //对角线初始化为0，其余为INT_MAX
        if(i==0)
            sum[i]=c[i];
        else sum[i] = sum[i - 1]+c[i];
    }
    for(int len=1;len<=N;len++)     //枚举长度，长度为1表示本身
    {
        for(int j=0;j+len<N+1;j++)          //枚举起点
        {
            int end=j+len-1;               //计算终点
            for(int i=j;i<end;i++)            //枚举分割点
               f[j][end]=min(f[j][end],f[j][i]+f[i+1][end]+sum[end]-sum[j]+c[j]);
        }
    }
    cout<<f[0][N-1]<<endl;
    return 0;
}

10.给定一组个字符串，为每个字符串找出能够唯一识别该字符串的最小前缀。

以下是大神的解法：

#include<iostream>
#include<vector>
#include<string>
//c++前缀树解法
using namespace std;
class trie_node{
public:
    int cnt;
    trie_node* next[26];
    trie_node(){
        cnt=1;
        for(int i=0;i<26;i++){
            next[i]=nullptr;
        }
    }
};
int main(){
    trie_node* root=new trie_node();
    int n=0;
    cin>>n;
    vector<string> strs(n);
    for(int i=0;i<n;i++){
        string tmp;
        cin>>tmp;
        strs[i]=tmp;
        trie_node* p=root;
        for(int j=0;j<tmp.length();j++){
            if(p->next[tmp[j]-'a']!=nullptr){
                p->next[tmp[j]-'a']->cnt++;
            }
            else{
                p->next[tmp[j]-'a']=new trie_node();
            }
            p=p->next[tmp[j]-'a'];
        }
    }
    for(int i=0;i<n;i++){
        trie_node* p=root;
        int j=0;
        for(;j<strs[i].length();j++){
            if(p->next[strs[i][j]-'a']->cnt == 1){
                cout<<strs[i].substr(0,j+1)<<endl;
                break;
            }
            p=p->next[strs[i][j]-'a'];
        }
        if(j==strs[i].length()){
            cout<<strs[i]<<endl;
        }
    }
    return 0;
}

说实话，大神的做法没太看懂。。。以下是本菜鸡的解法，有没有大神能帮我看看怎么改改啊，虽然能运行出来，但感觉很笨啊，害，在线虚心求教

#include<stdio.h>
#include<string.h>
int main(){
    int n;
    scanf("%d", &n);
    char str[105][105];
    for(int i = 0; i < n; i++){
        scanf("%s", str[i]);
        getchar();
        //printf("%s\n",str[i]);
    }
    int k = 0;
    for(int i = 0; i < n; i++){
        k = 0;
        for(int j = 0; j < n; j++){
            for(int m = 0; m < strlen(str[i]); m++){
                if(str[j][m] != str[i][m]){
                    if(k < m){k = m;}
                    break;
                } 
            }
        }
        for(int t = 0; t <= k; t++){
            printf("%c", str[i][t]);
        }
        i == (n - 1) || printf("\n");
    }
    return 0;
}

以上就是本菜鸡本次做题的小总结，期待成为大神的那一天，啾咪啾咪~

码农公寓