QRT（Qube Research & Technologies）26NG 的 OA 做完了，HackerRank 平台，90 分钟，选择题加三道 coding。 QRT OA 难度整体一般，三道题各有一个关键转化，想通了都不难写。把三道题的题面和思路完整拆下来。
OA 基本信息
平台 HackerRank，90 分钟，结构是选择题 + 3 道 coding。三道题风格差异挺大——一道贪心统计、一道机器学习实操、一道二分答案，覆盖面比纯算法 OA 广，量化公司这点很典型。
第一题：Keep Them Apart（贪心 + 分组统计）
题意
给一个长度为 n 的数组 A 和一个整数 d ≥ 1。可以从任意位置删除元素。删除后，考虑剩余元素在原数组中的下标（不是删除后压缩的下标）。数组 valid 的条件是：对每个值 x，任意两个保留下来的 x，它们的原始下标 i < j 必须满足 j – i ≥ d。求让数组 valid 所需的最少删除次数。
例子：n=4，d=3，A = [1,2,2,1]。值 1 出现在下标 1 和 4，4-1=3 ≥ 3，两个都能留；值 2 出现在下标 2 和 3，间隔只有 1，必须删掉至少一个。所以最少删 1 个。
约束：n ≤ 10⁵，d ≤ 10⁵，A[i] ≤ 10⁹。
思路
正着算”最少删几个”不好算，反过来想——最少删除等价于最多保留，这是这题的破局点。
具体做法：先用哈希表存下每个值出现的所有下标（下标天然有序）。然后每个值单独处理，互不干扰。对某个值的下标序列，问题变成”从这个有序序列里最多能选多少个，使相邻选出的间隔 ≥ d”——经典的贪心：从第一个开始选，选了就把指针跳到下一个间隔 ≥ d 的位置，能选就选。这个贪心是最优的（选得越早，后面留的空间越大）。
把所有值能保留的个数加起来，n 减掉它就是最少删除数。整体 O(n)。
第二题：Random Forest（ML 实操）
题意
给一个含数值特征和类别特征的数据集，以及对应的二分类标签（0/1），用 scikit-learn 训练一个随机森林分类器，对未见过的测试集做预测。给了 train.csv、test.csv 和 sample_submission.csv 三个文件。对 test.csv 的每条记录预测 label，提交一个 CSV，含表头、每条测试记录一行、只有 label 一列。
评价指标是 Accuracy（正确预测数 / 总预测数），而且模型会在和训练集不同的数据集上测试，考察鲁棒性。
思路
标准的 sklearn 流水线，没有花活：feat_0 是类别特征，做编码处理；其余数值特征直接用。用 RandomForestClassifier 训练，然后预测 test.csv，按格式输出 submissions.csv。
要注意的是题目明说会在不同分布的数据上测鲁棒性，所以别为了在训练集上刷高分而过拟合——随机森林本身抗过拟合还行，参数不用调太激进，n_estimators 给足、树深适度限制就好。输出格式（表头、一列 label）严格照要求，格式错了分白丢。
第三题：Array Nullification（二分答案）
题意
给两个数组 change（长 n）和 arr（长 m）。每步操作可以二选一：把 arr 里任意一个元素减 1；或者，如果 change[i] > 0 且 arr[change[i]] = 0，就可以把那个元素置为 NULL。1-based 索引。求把 arr 全部变成 NULL 的最少操作数，不可能则返回 -1。
例子：n=4，m=2，change = [0,1,0,2]，arr = [1,1]。操作序列：先 arr[1] 减 1 变 [0,1]；用 change[2]=1 把 arr[1] 置 NULL；arr[2] 减 1 变 0；用 change[4]=2 把 arr[2] 置 NULL。共 4 步。
约束：n ≤ 10⁵。
思路
这题的信号是”最少操作数”加上单调性——操作次数越多越容易清空完，所以二分答案。
二分总操作步数 mid，check 的逻辑是：在前 mid 步这个前缀范围内，每个 arr 元素能被置空的最后机会是哪一步（即 change 里指向它的、下标最大的那个位置）。以这个作为截止时间，然后统计——把每个元素减到 0 需要的操作数（就是它的值），加上置空需要的操作数（每个元素一次），总数是否在 mid 以内且时序上可行。
check 通过说明 mid 可行，往小了二分；不通过往大了走。最后得到最小可行步数，全程不可行就返回 -1。
AC经验分享
我平时基本每天都在做各家的 OA（TikTok、Google、Amazon、Uber、微软这些），量化这条线的题池在 InterviewShow 有比较全的收录，QRT 这类算法加 ML 混合的题型也有分类。刷得多了会发现各家题池的重合度不低，摸清套路比死磕单题有用得多。可以联系领取真题，了解OA/VO更多帮助服务。