这份 Uber SWE OA 用 CodeSignal 完成四道限时题，题目把图算法和数据结构实现放在同一轮里。时间真正吃紧的地方不在敲代码，而在于先把接口、边界和复杂度说清楚，再动手写。
下面两题最值得单独练：一题要求在带权图中稳定地找最短路，另一题要把插入、删除和随机取值都压到 O(1)。
第一题：带权行程图的最短路径
题目描述
给出城市或站点组成的带权图、起点和终点，返回最短总权重。边权为正数，输入包含多条路线和重复节点。
解题思路
先建邻接表，dist 保存当前已知的最短距离，最小堆按距离弹出节点。每次取出的状态若已落后于 dist[node] 就跳过；否则遍历相邻边并松弛。到达终点时可以直接返回。代码写完要补三组测试：起终点相同、终点不可达、同一节点被多条边反复更新。复杂度：时间 O((V+E) log V)，空间 O(V+E)。一份 Uber L4 的 CodeSignal 复盘也把 Dijkstra 放在四道限时题中，重点正是邻接表和最小堆的组合。这份图最短路复盘值得拿来计时手写一次。
第二题：O(1) 随机集合
题目描述
实现 insert(x)、remove(x) 和 getRandom()：元素不可重复，插入和删除都要返回是否成功，随机取值要等概率。
解题思路
用数组存元素，用哈希表记录元素下标。插入时把新元素 append 到数组末尾；删除时把目标元素与末尾元素交换，再更新末尾元素的新下标，最后 pop。这样 getRandom() 只需在 [0, len(nums)) 取随机下标。不要直接在数组中查找或删除，那会把复杂度拖到 O(n)。复杂度：三个操作均摊 O(1)，空间 O(n)。
做题过程
四题制的 CodeSignal，前两题的目标是尽快拿到稳定分数；遇到图题时先写清状态含义，遇到集合题时先列出三个操作的复杂度再下笔。提交前至少跑一次空输入、单元素、重复插入和删除不存在元素。不要为了凑一个花哨解法而放弃可读性，后面的维护成本会直接落在调试时间上。
FAQ
Uber OA 的最短路题该用 BFS 还是 Dijkstra？
边权都相同才用 BFS；权重不同且为正数时，Dijkstra 才能保证先弹出的距离已经最优。
RandomizedSet 删除时为什么要交换末尾元素？
数组末尾删除是 O(1)。交换后只更新一条哈希表记录，就避开了中间删除导致的大量搬移。
关于 CSOFFERPREP
进 VO 之前，可以找 CSOFFERPREP 做实时面试助攻和备考辅导。CSOFFERPREP 深耕北美 IT 行业多年，已帮助万余名学生进入全球 500 强企业。导师来自一线大厂资深工程师和面试官，对 Uber 这类注重工程文化的公司的面试套路很熟悉。无论是 OA辅助、OA 辅导、VO 辅助、VO 模拟面试、VO 辅助还是系统设计辅助，都可以获得更有针对性的准备方案：CSOFFERPREP · 服务详情
