Intuit OA 题目解析：最小生成树、中位数与区间 DP

这次整理了三道 Intuit OA 真题，涵盖带权无向图删边后的最小生成树、合同工津贴总额的中位数，以及压力隔离关闭顺序的最大得分与方案数计算。题目涉及 Graph、Minimum Spanning Tree（MST）、SQL 窗口函数和 Interval DP 等知识点，既考察基础算法与数据处理能力，也需要处理复杂的状态转移和边界情况。

下文将结合每道题的具体要求，分析题目描述与解题思路，帮助准备 Intuit OA 的同学了解相关考点，熟悉不同类型编程题的解题方法，为线上测评做好准备。

第一题：带权无向图删边后的最小生成树

题目描述

给定一个连通的带权无向图，每条边代表一条独立的连接。对于图中的每条边，依次临时删除该边，并计算删除后剩余图的最小生成树权重。每次计算完成后，需要恢复该边，再测试下一条边。如果删除某条边后图变得不连通，则该边对应的结果为 -1。最终按照边在输入中的原始顺序返回所有结果。

解题思路

先求出原图的最小生成树（MST），记录其总权重。然后重置并查集，逐条处理输入中的边。对于原最小生成树中的树边，可以直接跳过；对于不在原最小生成树中的边，将其加入生成树，相当于形成一个环。此时，需要找到树上 $u$u 到 $v$v 路径中的最大边权，并用当前边替换这条最大权值边，更新最小生成树的总权重即可。

第二题：合同工津贴总额的中位数

题目描述

统计每位合同工获得的各项津贴（allowance）总额，包括额外津贴、每小时津贴、每日津贴和奖金津贴，并计算所有合同工津贴总额的中位数。

解题思路

先计算每条数据中各项 allowance 的总和，再求出所有合同工 allowance 总额的中位数。筛选并整理数据后，使用 ROW_NUMBER() 为每条记录按津贴总额排序并分配排名，最后根据数据量的奇偶性，取对应排名的值作为中位数。

第三题：压力隔离关闭顺序

题目描述

某海上加工平台上有 n 个压力阀，沿直线排列。第 $i$ 个阀门具有一个带符号的压力系数 $A[i]$。在这排阀门的左右两侧，各有一个固定的边界调节器，其系数分别为 $l$和 $r$。这两个边界调节器始终保持启用状态，不会被关闭。所有阀门都必须依次关闭，每次关闭一个阀门。当关闭第 $i$ 个阀门时，找到其左侧和右侧最近的、仍处于启用状态的阀门或边界调节器，设它们的系数分别为 $x$ 和 $y$。

本次关闭操作对总稳定性得分的贡献为：x×A[i]×y 随后，该阀门会从序列中移除，因此在后续关闭操作中，其他阀门的相邻对象可能发生变化。

解题思路

考虑使用区间 DP，枚举区间内最后关闭的阀门。关闭该阀门时，其左右两侧最近的仍启用阀门或边界调节器就确定了，因此可以计算本次操作的得分，并结合左右子区间的最优结果更新当前区间的最大总得分。在统计方案数时，左右子区间的关闭顺序可以任意交错，因此还需要乘上对应的组合数 $\binom{len-1}{leftLen}$，计算左右两部分操作顺序的组合方式，最终得到达到最大总得分的不同关闭顺序数量。

总结

这三道 Intuit OA 题目分别涉及图论、SQL 和动态规划。练习时，除了掌握对应算法，还要确认题目要求的计算对象和边界条件：删边后是否仍然连通、偶数条记录的中位数如何计算，以及 Interval DP 如何统计所有最优关闭顺序。把这些细节理清楚，才能避免思路正确但实现结果出错。

如果你正在准备Intuit或其他大厂的 OA 或面试，除了刷题，也可以结合真实面经熟悉常见题型和考察方向。InterviewShow 整理了 Microsoft、Amazon、Google、Stripe、TikTok 等科技公司的面试资料，并提供 OA 辅助和面试辅助，可以查看服务介绍，覆盖 Coding、System Design 和 BQ。需要的话，可以直接联系我们。

FAQ

1. Intuit OA 通常考哪些内容？

Intuit OA 的题目会因岗位和测评形式而异。本文整理的题目涉及 Graph、Minimum Spanning Tree（MST）、SQL 窗口函数和 Interval DP，可用于练习图论算法、数据处理和动态规划。

2. Intuit OA 难吗？

难度取决于具体岗位和题目。本文第一题需要分析删边后的 MST，第三题需要同时维护最大得分和最优方案数，除了理解算法，还需要处理好边界条件与实现细节。

3. Intuit OA 应该如何备考？

建议针对不同题型分开练习。Graph 题重点掌握连通性、MST 和替代边；SQL 题熟悉聚合查询、排序与窗口函数；Interval DP 则需要练习状态定义、转移条件和方案数统计。完成题目后，再检查复杂度和特殊输入下的结果。