【2022-08-10】ZOOM秋招笔试两道编程题

恭喜发现宝藏！搜索公众号【TechGuide】回复公司名，解锁更多新鲜好文和互联网大厂的笔经面经。
作者@TechGuide【全网同名】
点赞再看，养成习惯，您动动手指对原创作者意义非凡欄

第一题：树结点染色计算总体权重

题目：

给你一棵树，树上每个节点要么是红色要么是黑色，根节点为1。每个节点的权重值为根节点到该节点路径上红色节点个数和蓝色节点个数的差的绝对值。求所有节点权重值之和。

输入

第一行输入n个节点 第二行为每个节点的颜色 接下来n-1行为a b节点之间有一条线

5
RBBRB
1 5
2 5
1 3
5 4

输出

3

思路：

建树，dfs模拟

代码

CPP版本

// Java题解可私信微信公众号TechGuide回复公司名获取
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
vector<int> mp[N];
int cred[N], cblue[N], n;
string color;
ll ans;
void dfs(int u,int fa){
    cred[u] = cred[fa];
    cblue[u] = cblue[fa];
    if(color[u] == 'R'){
        cred[u]++;
    }else{
        cblue[u]++;
    }
    // cout<<u<<" "<<cred[u]<<" "<<cblue[u]<<endl;
    ans += abs(cred[u] - cblue[u]);
    for(auto v:mp[u]){
        if(v == fa) continue;
        dfs(v, u);
    }
    return;
}
int main() {
    cin >> n >> color;
    color = " "+color;
    for (int i = 0, u, v; i < n - 1; i++) {
        cin >> u >> v;
        mp[u].push_back(v);
        mp[v].push_back(u);
    }
    dfs(1,0);
    cout<<ans<<endl;
}
// Java题解可私信微信公众号TechGuide回复公司名获取

第二题：股票推荐

题目：

完成股票推荐系统设计，每个用户可能关注几个公司，比如A,B,C，如果有另一个用户只关注了A，那么就会给他推荐B，C。这时候如果来了一个用户关注C，D，那么后来关注C的用户，都会推荐A，B，关注A的用户都会推荐BCD。
在有上面的关系后，求用户查询的时候，会给它推荐的公司的个数。

输入

第一行输入q表示操作次数
接下来输入一次操作
共有两种操作
1.注册
格式为
1 name n 表示有一个name的人关注了n个股票
第二行输入n个字符串表示这n个股票 n个字符串不相同
2.查询
格式为
输入2 name 表示查询系统会给此人推荐多少股票
保证至少有一次查询
例
5
1 Alice 2
Zoom Apple
2 Bob
2 Alice
1 Bob 2
Apple MicroSoft
2 Bob

输出

error
0
1

思路：

并查集模拟。

题解

CPP版本

// Java题解可私信微信公众号TechGuide回复公司名获取
#include <iostream>
#include <vector>
#include <map>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
int tot, ptot;
map<string, int> name;// 公司name
map<string, int> pname;// 人name
map<int, int> mp;
int fa[N], sz[N];
int getfa(int u){
    return fa[u] != u ? fa[u] = getfa(fa[u]) : u;
}
void join(int u,int v){
    int f1 = getfa(u), f2 = getfa(v);
    if(f1 != f2){
        fa[f2] = fa[f1];
        sz[f1] += sz[f2];
        sz[f2] = 0;
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int q;
    cin >> q;
    int type, m;
    string in, bu;
    tot = q;
    for(int i = 1; i <= q; i++){
        cin >> type;
        if(type == 1){
            cin >> in >> m;
            int thisroot = i;
            pname[in] = thisroot;
            fa[thisroot] = thisroot;
            sz[thisroot] = 0;
            vector<int> tonari;
            
            for(int i = 0; i < m; i++){
                cin >> bu;
                if(name.find(bu) == name.end()){
                    name[bu] = ++tot;
                    fa[name[bu]] = name[bu];
                    sz[name[bu]] = 1;
                }
                tonari.push_back(name[bu]);
                join(thisroot, name[bu]);
            }
            mp[thisroot] = tonari.size();
        }else{
            cin >> in;
            if(pname.find(in) == pname.end()){
                cout<<"error\n";
                continue;
            }
            int pid = pname[in];
            int total = sz[getfa(pid)];
            int tonari = mp[pid];
            cout<<total - tonari<<"\n";
        }
    }
}
/*
5
1 Alice 2
Zoom Apple
2 Bob
2 Alice
1 Bob 2
Apple Microsoft
2 Bob
*/