腾讯音乐笔试2022-4-7场

腾讯音乐笔试2022-4-7场

Tans 3,196 2022-04-07

总共3道编程题和一道场景题,总的来说,编程题后两题水题,第一题是组合数学,也有可能是动态规划。

1. k-size字符串的数量(组合数学)

给定字符串总数n,组数 K:

  • 先求出放入 2k2 * k个字符的数量,也就是说第一位是AA那么第二组只能是BB,CC.........ZZ,以此往后每一组也是25种情况。 也就是 first=262525.....25first = 26 * 25 * 25 * ..... * 25 % mod (总共 k个),
  • 然后我们剩下last=n2klast = n-2*k个字符,那么我们需要last个字符分为K组的总情况,将分组好的数据去插入步骤一的相应位置,计算出分组结果为second种情况, 这个操作类似n个小球放入m个箱子里面的总情况数量Cm+n1m1C_{m+n-1}^{m-1}(允许空箱子的存在)。然后结果就是 secondfirstsecond * first % mod;

由于计算组合数的时候有些问题(中间结果会溢出long,需要使用逆元等方式来解决),计算second的时候出现失误只对了60%, 以上是我的理解,如有失误,还请各位大佬斧正。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param k int整型 
     * @return int整型
     */
    ll c[1001][1001];
    void init(){
        int mod = 1e6;

        for(int i = 0; i < 1001; i++){
            for(int j = 0; j < 1001; j++){

                if(not j) c[i][j] = 1;
                else c[i][j] = (c[i-1][j] + c[i-1][j-1]) % mod;
            }
        }
    }
    int numsOfStrings(int n, int k) {
        ll ans = 0;
        int mod = 1e6;
        init();
        if(k == 1) return 26;
        for(int i = 0; i < k; i++){
            if(i == 0) ans = 26;
            else ans = ans * 25 % mod;
        }
        int last = n - 2 * k;
        //可能有些问题.....
        if(last != 0) ans = ans * c[last+k-1][k-1] % mod;
        else return ans;
    }
};
int main(){
    Solution s = Solution();

    cout << s.numsOfStrings(6,2);
    // s.minMax();
}

2. 计算最后最大值(贪心)

贪心,维护一个大顶堆,每次取出最大值减去x重新放入堆中即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param a int整型vector 
     * @param k int整型 
     * @param x int整型 
     * @return int整型
     */
    int minMax(vector<int>& a, int k, int x) {
        priority_queue<int> q;
        for(auto num : a) q.push(num);
        while(k--){
            int maxx = q.top();
            cout << maxx << endl;
            q.pop();
            q.push(maxx - x);
        }
        return q.top();
        // write code here
    }
};

3.幂的删除多少(构造)

啊这?好水呀。不会真的有人不知道只有一个1才是2的幂吧…

int minCnt(string s) {
        int cnt = 0;
        for(auto ch : s) if(ch == '1') cnt++;
        return cnt-1;
}

4.大文件传输

需求: 大文件,确保效率和可靠性
解决方法:断点续传分片传输并行传输。这里类比了下载工具IDM的强大功能。

  1. 文件先要压缩呀,一般图片用webp格式啥的,就选个效率好的压缩算法先压缩一下,就可以压缩60%左右了(视文件类型决定)。
  2. 具体做法是先进行信息传输(文件名,文件大小,双方带宽,预计时间),客户端可以开多个线程并发去请求每个小文件,每个线程offset起始位置和该片段大小。
  3. 然后服务端要提升IO效率了,比如说IO多路复用之类的,或者带宽不够,集群来凑,一定要把带宽提上去,而且要跑满。
  4. 可靠性,尽量不使用TCP,因为受MTU限制,单次传输的有效数据大小比UDP小,同时为了保证可靠性,可以上QUIC协议啊之类的,或者我们在应用层去做一个可靠性,对于每个请求维护分别维护offset来实现。
  5. 如果够壕,那么直接提升硬件!磁盘升固态硬盘呗,磁盘IO提上来了,或者多搞几台服务器
  6. 最后注意,传输速率的因素是个水桶效应,不能仅仅提升某一个阶段,应该雨露均沾。比如说不能单单提供网络IO带宽,磁盘读速率提不上来等于白忙活了。
  7. 想到了类似迅雷那种,种子传输!老司机都懂的,不需要去访问服务器,而是互相从各个存有资源的客户端下载!(拼友越多,车更快!别说了,快上车!)

最后附上一张,IDM工具的截图,大家可以理解,这也确实个好工具!
image-1649336262183