华为机试&面经c++

机试三道题

第一题：简单的数组题，具体内容忘了。只记得输出是类似“1 2 3”这样用空格隔开的一个个结果。我本来在循环中直接计算完每一个答案以后cout<<ans<<' '; 结果最后面多了一个空格答案不通过，无奈给最后一个结果单独输出。

第二题：最大拓扑网络。给定n个节点（0~n-1），每个节点都有其对应的层级（1<=level<=1000)。节点之间有链路连接，比如{0，2}表示节点0和节点2之间可以连接，这个连接是双向的。每个节点可以有多条链路，但只能属于一个层级。最大拓扑网络表示在同一层级下，能用链路直接连接起来的最大节点数量。（比如共有3个节点，节点0，1，2都属于层级1，且给定链路{0，1}，{1，2}，则它们组成了大小为3的拓扑网络。如果节点0，2属于层级1，节点1属于层级2，则最大拓扑网络大小为1）。

输入：n（代表n个节点）

n个数字（代表每个节点所属的层级）

m（代表共有m条链路）

m行，每行为两个数字（代表每条链路连接的两个节点）

输出：最大拓扑网络的大小

这道题我用广度搜素写的，测试用例增减了几条链路完全没问题，结果通过率只有10%，百思不得其解。贴一下代码希望有大佬解惑。

#include <vector>
#include <queue>
#include <iostream>
using namespace std;
int main()
{
    int n;
    cin >> n;
    vector<int> level;
    for (int i = 0; i < n; i++) {
        int l;
        cin >> l;
        level.push_back(l);
    }
    int linkNum;
    cin >> linkNum;
    vector<vector<int>> link(n);
    for (int i = 0; i < linkNum; i++) {
        int left, right;
        cin >> left >> right;
        link[left].push_back(right);
        link[right].push_back(left);
    }

    int ans = 1;
    queue<int> visit;
    for (int i = 0; i < n; i++) {
        if (level[i] == -1) { continue; }
        visit.push(i);
        int nowLevel = level[i];
        int size = 1;
        while (!visit.empty()) {
            int nowVisit = visit.front();
            level[nowVisit] = -1;
            for (auto it : link[nowVisit]) {
                if (level[it] == nowLevel) {
                    visit.push(it);
                    size++;
                }
            }
            visit.pop();
        }
        ans = max(ans, size);
    }
    cout << ans << endl;

第三题：菜单组合种类。为了科学饮食，控制每天摄入的卡路里数。最低值应不低于kcal_low, 最高值应不高于kcal_high。现在给出n个菜品的卡路里数，菜品可以重复选择。为满足总共摄入的卡路里数在规定的区间，可以有多少种菜品选择方式？

输入：kcal_low kcal_high

n行，表示每个菜品的卡路里数。

输出：所有合理的菜品组合方式数量。

例：输入350 500

100

200

500

输出：7

解释：500*1，200*2，200*1+100*2，200*2+100*1，100*4，100*3+200，100*5共7种选择。

完全背包问题，动态规划。代码没存。

----------------------------------------------------------------------------------------------------------------------------------

一面：开局经典自我介绍。然后让介绍一个代码量最多的项目，并且问了一些相关问题。

做题：输入hello world world

输出world 2

hello 1

按出现频次最多的单词排序。相同频次按字母表排序。哈希表解决。

之后问了一些c++八股文。后悔没好好背，答的磕磕绊绊。主要是面向对象相关，多态虚函数之类。还有指针和引用、内存等等。

二面：大体和一面内容差不多。八股+手撕代码。简历上每个项目都延申问了点相关知识，一路深入，直到我答不出来。但是面试官人很好，试出我的深浅之后就换话题，态度很友善类似闲聊，所以压力不大。

主管面：本来以为会压力面，结果还好。主管虽然比较严肃但没给太多压力。主要问了实习相关：碰到的最喜欢的人和最讨厌的人？遇到那些困难如何解决？如果重来一次实习有那些地方可以改进？实习收获？如何看待工作和学习的区别？介绍你认为最有效的学习方法？未来的职业规划？你认为作为技术专家/管理人员应该具备什么能力？最后问了华为企业文化的认识。总共30min。