这套 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和fullPriceIdxQ2 只做了同行合并漏掉同列合并Q2 排序后没有按题目约束判断就直接 union导致误连一句话总结Q1 是标准单调栈模板题Q2 是“分组排序 并查集”的连通分量题。把状态维护干净基本就能稳定过。Uber OA 没把握可以辅助其他公司也可以问问。#uber #美国留学生 #北美求职 #留学生求职 #留学生实习 #留学生找工作 #hackerrank #面经延伸阅读外链Uber CareersStack Tag (LeetCode)Disjoint-set Data Structure (Wikipedia)需要面试真题 立刻联系微信Coding0201获取真题。