刚做完一套 HRT OA ,和 TikTok、Uber、Visa、Capital One 这些一样,都在 CodeSignal 平台,70 分钟 4 题。这类 OA 有个很关键的规律:题目不依赖公司自己出,而是从 CodeSignal 的公共题库里抽,所以出题模式非常固定——前两题 easy、第三题矩阵模拟、第四题数据结构优化。把这个结构摸清,准备起来事半功倍。
下面把这次四道题的思路和复杂度整理出来。
第一题:最高「评分/价格」比商品(easy)
给两个正整数数组 prices 和 ratings(评分 1–5),下标一一对应。找出 rating / price 比值最大的商品,返回其下标;比值相同则返回下标最小的。
思路:直接一趟遍历,记录当前最大比值和对应下标即可,O(n)。有个小细节能避坑:比较两个分数 r1/p1 与 r2/p2 大小时,别用浮点除法(可能有精度误差),改用交叉相乘 r1 * p2 vs r2 * p1 比较,既精确又快。遍历时只在「严格更大」时更新下标,自然满足「比值相同取最小下标」。
第二题:bird 造巢模拟(easy)
给一个数组 forest(正整数是木棍长度、0 是空位)和 bird 的初始位置(保证是 0)。bird 按规则造巢:先向右飞到第一根木棍、取回;再向左飞到第一根木棍、取回;之后每次交替方向,直到巢里木棍总长度达到 100。
思路:纯模拟。从初始位置出发,用两个指针分别向左、向右扫,按「右、左、右、左……」交替找下一根还没被取走的木棍,累加长度,取走的位置标记为空(或直接跳过)。达到总长 100 就停。注意边界:某个方向可能已经没有木棍了,要处理指针越界。题目本身不难,细心处理「交替方向 + 已取走标记」就行。
第三题:最长对角线模式匹配(矩阵模拟)
给一个只含 0/1/2 的矩阵,找最长的一条对角线段,匹配模式 1, 2, 0, 2, 0, 2, 0, ...——即开头是 1,之后 2 和 0 无限交替重复。这条对角线段可以从任意格子起、朝任意一个对角方向走,但必须终止在矩阵边界(第一行/最后一行/第一列/最后一列)的格子上。返回最长长度。
这题最容易读错的是模式定义:不是 1,2,0 三个一组循环,而是一个 1 打头,后面全是 2,0 的无限循环(第 0 位是 1,第 1、3、5… 位是 2,第 2、4、6… 位是 0)。
思路:题目已经放宽复杂度到 O(matrix.length² × matrix[0].length²),所以不用太省。枚举每个值为 1 的格子作为起点(模式必须从 1 开始),再枚举四个对角方向,沿着方向一步步走、逐位比对模式,同时要求终点落在边界上,记录满足条件的最长段。用「从每个可能的起点朝四个方向暴力延伸」即可,配合按位置索引算出期望值(位置 0 期望 1,奇数位期望 2,偶数位期望 0)。例子里输出 3,对应某条 1→2→0 走到边界的对角段。
第四题:每个 segment 后的唯一字节总数(数据结构优化 —— 真难点)
一个文件按 segment 传输,每个 segments[i] = [start, end] 表示一段闭区间的字节下标(64 位整数、1-based、首尾都含)。segment 之间可能重叠、甚至完全重复。要求每接收一个 segment,就输出到目前为止收到的唯一字节总数。
这是整套里唯一的硬题,也是「第四题数据结构优化」的考点所在。 有两个陷阱:
- 字节下标是 64 位,范围可到 10^18,绝对不能开数组或 set 逐字节标记,内存直接爆。
- 每次要的是「增量后的总数」,不是最后一次性算,所以需要一个能动态维护并快速合并区间的结构。
思路:维护一组互不相交的区间(用有序结构存,比如 TreeMap / 平衡树 / 有序区间列表),同时维护一个「当前总覆盖长度」。每来一个新区间 [start, end]:
- 找到所有和它重叠或相邻的已有区间,把它们从结构里取出、和新区间合并成一个大区间;
- 合并时,总覆盖长度先减去被吞并的旧区间长度之和,再加上合并后新大区间的长度;
- 把合并后的区间放回结构,输出当前总长度。
这样每个区间最多被插入、删除各一次,均摊复杂度 O(n log n)。核心思想就是用不相交区间集合代替逐字节标记,把 10^18 级别的字节空间压缩到 O(区间数) 的存储。这题能不能想到区间合并,基本决定这套 OA 的上限。
整体感受与备考建议
HRT 这套 OA 印证了 CodeSignal 70 分钟 4 题的通用规律:前两题送分(直接模拟)、第三题矩阵暴力枚举、第四题才是真正拉开差距的数据结构题。 时间分配上,建议前两题各控制在 10 分钟内拿下,把时间留给第三题的边界处理和第四题的区间合并。第四题是这类 OA 的常见压轴形态(区间合并 / 并查集 / 堆 / 单调栈),平时把这几类「动态维护 + 快速查询」的模板练熟,考场会稳很多。
写在最后
这类 CodeSignal 70 分钟 4 题的 OA 规律性极强——题目基本都从平台公共题库里抽,提前刷过就是默写。我这边长期在跟进这个平台的真题更新,目前整理了 130+ 道 CodeSignal 平台真题和验证过的解法,基本能覆盖绝大部分考点(HRT、TikTok、Uber、Visa、Capital One 这些共用一套题库)。在准备这类 OA 的同学,可以提前对着题库把手感练出来;需要针对某家公司定向准备、或者笔试时想要面试支持的,也可以找我聊,按你的目标公司和时间给一份针对性的刷题清单。