笔试编程题0401

前言

201958同城春招实习机试题，一共两道编程题，解答题热搜top10问题，用topK来实现的，TCP和UDP在直播中的优缺点，简单的介绍了下TCP和UDP的特点和区别，还涉及到SQL和事务，重复读问题。

应用题是海量数据问题，统计UID出现的次数并排序，用了hashtable来实现的，并用Introspective sort（内省排序）进行排序，总体来说，难度还可以，主要是一个半小时，时间略少，题量略多。

最后记录两道编程题。

编程题

找出符合条件的子字符串

比如字符串为“aabbbccddddeeffggghh”，给定大小为n，输出所有长度为n的重复子串，比如n=2，输出(0,1,aa)(5,6,cc)(11,12,ee)(13,14,ff)(18,19,hh)。

通过设置两个指针first和last，通过cnt记录每个字符出现的次数，找到满足次数的字符输出即可。

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

void GetSubstr(const string &str,int n){
    int length = str.size();
    int first = 0;
    int last = 0;
    int cnt = 1;
    char tem = str[0];
    for(int i=1;i<length;++i){
        if(str[i]==str[i-1]){
            ++last;
            ++cnt;
        }else{
            if(cnt == n){
                cout<<"("<<first<<","<<last<<",";
                for(int j=0;j<n;++j) cout<<tem;
                cout<<")";
            }
            tem = str[i];
            first = i;
            last = i;
            cnt = 1;
        }
    }
    if(cnt == n){
        cout<<"("<<first<<","<<last<<",";
        for(int j=0;j<n;++j) cout<<tem;
        cout<<")";
    }
}

int main()
{
    string str = "aabbbccddddeeffggghh";
    GetSubstr(str,2);
    return 0;
}

最大连续字数组的和

比如输入：2,-3,4,11,-5,8,3,-6

则输出：21

f(i) = max(f(i-1)+ivec[i],ivec[i]);
res = max(res,f(i));

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

int GetMaxSubSum(vector<int> &ivec){
    int len = ivec.size();
    int f1 = ivec[0];
    int res = ivec[0];
    for(int i=1;i<len;++i){
        f1 = max(f1+ivec[i],ivec[i]);
        res = max(f1,res);
    }
    return res;
}

int GetMaxSubSum1(vector<int> &ivec){
    int len = ivec.size();
    int res = ivec[0];
    int sum = 0;
    for(int i=0;i<len;++i){
        sum += ivec[i];
        if(sum>res) res = sum;
        if(sum<0){
            sum = 0;
        }
    }
    return res;
}

int main(){
    vector<int> ivec = {2,-3,4,11,-5,8,3,-6};
    int result = GetMaxSubSum(ivec);
    cout<<result<<endl;
    result = GetMaxSubSum1(ivec);
    cout<<result<<endl;
    return 0;
}