这套 Uber OA 是在 HackerRank 上考的，两题都不算偏门，但很吃实现稳定度。下面按面经思路做无代码复盘。
Q1：价格折扣（单调栈）
核心思路
直接单调栈，从后往前遍历数组：
- 栈里维护索引
- 保证栈内对应价格单调递增
- 对于第
i个商品，用栈顶得到可用折扣（第一个小于等于当前价格的右侧元素）
然后按题意维护三份结果：
discount[i]：第i个元素的折扣total：所有商品最终价格总和fullPriceIdx：没有折扣、按原价购买的商品索引
最后输出总价和全价商品下标即可。
复杂度
- 时间复杂度：
O(n) - 空间复杂度：
O(n)
Q2：点集连通时间（并查集）
本质
本质就是求连通分量数量，直接并查集（Union-Find）。
建图方式
按 x 和 y 分组：
- 同
x表示同一行 - 同
y表示同一列
然后做两类排序与合并：
- 同一行内按
y从小到大排序，满足题目约束就 union - 同一列内按
x从小到大排序，满足题目约束就 union
最后统计并查集里有多少个不同根节点（多少个不连通分量），再按题意转换成答案时间。
复杂度
设点数为 n：
- 分组 + 排序主导复杂度，一般是
O(n log n) - 并查集近似
O(n α(n)) - 总体可写
O(n log n)
面试里容易错的点
- Q1 单调栈条件写反：应维护“价格递增”的候选折扣栈
- Q1 忘记同步维护
total和fullPriceIdx - Q2 只做了同行合并，漏掉同列合并
- Q2 排序后没有按题目约束判断就直接 union，导致误连
一句话总结
Q1 是标准单调栈模板题，Q2 是“分组排序 + 并查集”的连通分量题。把状态维护干净，基本就能稳定过。
Uber OA 没把握可以辅助，其他公司也可以问问。
#uber #美国留学生 #北美求职 #留学生求职 #留学生实习 #留学生找工作 #hackerrank #面经
延伸阅读（外链）
需要面试真题？ 立刻联系微信 Coding0201，获取真题。
联系方式
Email: [email protected]
Telegram: @OAVOProxy