启云方 AI 应用开发工程师笔试 C 卷

《面试题目》

1. 给定投资上限 m、每款产品的投资上限 y、能接受的最大风险 x 和产品数量 n，每款产品有收益率 e 与风险等级 r，如何求投资能获得的最大回报？
2. n 个服务器之间存在依赖关系，如何求所有服务器启动完成的最短时间？
3. 给定起点与终点（如 1 到 5）和 n 条无向路径（如 1234、2568、3789），如何求起点到终点的最短距离？

《参考解析》

1. 带风险约束的投资回报最大化：这是一个带多重约束的背包类问题。约束有三层——总投入不超过 m、单款产品投入不超过 y、累计风险不超过 x，目标是把收益率 e 最大化。标准解法是把它写成多维 DP：以「已投入金额」和「已用风险」为状态，逐款产品做 0/1 或完全背包式的转移，复杂度是 O(n·m·x)；如果投入金额与风险都是小整数、n 也不大，这个规模可以接受。只过 80% 通常不是算法选错，而是边界没抠干净：风险恰好等于 x、投入恰好等于 m 时要取等号；收益率可能是浮点，比较时要用 eps 或统一放大成整数；单款产品的上限 y 是「每款最多投 y」而不是「不超过 y 的整数倍」，这两者意味着不同的状态转移。

2. 依赖关系下的最短启动时间：把服务器建成有向图（A 依赖 B 就是 B → A 的边），这是一个 DAG 上的关键路径问题。做法是拓扑排序，同时维护 dp[v] = max(dp[u]) + t[v]，其中 u 取遍 v 的所有前置，答案是所有节点 dp 值的最大值；也可以从各起点 DFS 记忆化，效果一样。本题只给出依赖关系、没有各自耗时，等价于每个节点耗时为 1，答案就是最长依赖链的长度。容易丢分的地方：一是入度为 0 的节点有多个，答案要取全局最大而不是某个起点的时间；二是要判断有没有环（有环说明依赖写错或无解）；三是「所有起点开始的最大值」这个直觉只有在忽略不同链可以并行时才成立——正确说法是所有链里最长的那条决定总时间。

3. 无向图上的最短距离：题面把路径写成「1234」「2568」这种数字串，本质是把串里相邻的两个节点连一条无向边。如果每条边权重视为 1，直接 BFS 从起点出发求最短路即可；如果边权不唯一，用 Dijkstra；节点编号范围只有 0 到 101，等权时也可以直接用邻接矩阵做 Floyd，几十行代码就能写对，是最稳的兜底。建图时容易踩的坑是路径串的方向性——题面说了无向，两个方向都要加边；另外字符串里的数字可能不连续（比如 2 到 15 这种多位编号），要确认是按字符切还是按数字切，这类输入解析错误往往比算法本身更容易丢分。

4. 笔试复盘：先保过题率，再抠边界：三个小时的编程笔试，理性策略是先把三道题的暴力或标准解都写出来跑通样例，再回头处理边界与优化，而不是在一道题上死磕满分。前两题都卡在 80%，通常意味着主逻辑没问题、错在边界与数据范围——写完后自己造几组极端数据（取等号、空输入、只有一条依赖、起点等于终点）自测一遍，比反复读题有用。另外要注意多组输入和输出格式，很多笔试的「答案错误」其实是没处理多 case 或最后一行没换行。