Goldman Sachs 的 OA 一向有点「不走寻常路」。不像其他金融公司偏爱数学推导或 SQL case，它出的题更像算法竞赛——逻辑清晰、实现要求高、还带点工程味。这次遇到的两道题，一道考数据结构，一道考数论优化，都挺巧妙，属于「做完还要回味半天」的类型。
一、OA 整体流程与难度
| 项目 | 内容 |
|---|---|
| 平台 | HackerRank |
| 时长 | 约 90 分钟（两道题） |
| 语言 | Python / C++ / Java 可选 |
| 难度 | 中上（偏硬核逻辑，不偏数学计算） |
GS 的 OA 通常看三方面：
- 数据结构与实现能力：看你能否灵活选对结构（queue、hash、有序表等）；
- 算法与复杂度控制：题目不大，但都要求在时限内高效实现；
- 逻辑与边界思维：尤其考虑数据流更新、同步删除、区间统计等细节。
二、Question 1：Log Buffer Analyzer（循环日志缓冲区）
题目
实现一个循环日志缓冲区，存储带时间戳和标签的日志。每来一条新日志：
- 如果缓冲区满了，先删除最旧的一条；
- 然后立即「发送」所有同标签且在指定时间窗口内的日志；
- 最后统计整个过程一共发送了多少条。
思路
表面是实现题，实质考数据结构组合的熟练度。我的做法：
- 用 queue 维护日志顺序，保证最旧的能快速删除；
- 为每个 tag 建一个有序列表保存时间戳；
- 新日志插入时，用二分查找找出同标签在「时间范围内」的日志数量并累加到结果；
- 缓冲区满时，队头日志及其时间戳记录同步删除。
from collections import deque
import bisect
class LogBufferAnalyzer:
def __init__(self, capacity: int, window: int):
self.capacity = capacity
self.window = window
self.buf = deque() # (timestamp, tag)，维护插入顺序
self.tag_times = {} # tag -> 有序时间戳列表
self.sent = 0
def _remove_oldest(self):
ts, tag = self.buf.popleft()
arr = self.tag_times[tag]
idx = bisect.bisect_left(arr, ts) # 同步删除该 tag 下的这个时间戳
if idx < len(arr) and arr[idx] == ts:
arr.pop(idx)
def add(self, ts: int, tag: str):
if len(self.buf) >= self.capacity:
self._remove_oldest()
self.buf.append((ts, tag))
arr = self.tag_times.setdefault(tag, [])
bisect.insort(arr, ts) # 保持有序，O(log n) 定位 + 插入
# 发送 [ts - window, ts] 内同标签日志
lo = bisect.bisect_left(arr, ts - self.window)
hi = bisect.bisect_right(arr, ts)
self.sent += (hi - lo)
def total_sent(self) -> int:
return self.sent
其实很像系统设计里「streaming log + 时间窗口」那类题，重点在更新同步和边界控制。心态稳的话，整个过程能压在 O(log n) 级别，写起来很顺。
三、Question 2：Password Lock Decryption（密码锁解密）
题目
给定一个整数数组和一个上界 upper。你可以花 1 单位成本把任意元素改成一个 ≤ upper 的数。要找一个候选数 candidate，使它与修改后的所有元素互质（coprime）。定义：
Lock Code = candidate - 总修改成本
目标：最大化 Lock Code。
思路
这题挺有意思，看着像脑筋急转弯，本质是数论 + 枚举优化。关键观察：
- candidate 与某元素互质 ⟺ 它们的
gcd == 1； - 对每个 candidate，已经与它互质的元素不用改（成本 0），不互质的才需要花 1 单位改成一个与 candidate 互质的数（只要 candidate > 1，总能改成 1 这种与任何数互质的值，所以每个不互质元素成本恒为 1）；
- 于是
cost(candidate) = 与 candidate 不互质的元素个数，Lock Code = candidate - cost。
from math import gcd
def max_lock_code(nums: list[int], upper: int) -> int:
best = float("-inf")
# candidate 越大 Lock Code 基数越高，但成本也可能上升；枚举到 upper
for candidate in range(1, upper + 1):
cost = sum(1 for x in nums if gcd(candidate, x) != 1)
best = max(best, candidate - cost)
return best
优化方向（面试官追问点）：
- 朴素枚举是 O(upper · n · log)。若 upper 很大，可按质因数分桶：预处理每个元素的质因子，candidate 的不互质元素数 = 与 candidate 共享任一质因子的元素数，用容斥或质因子计数加速。
- candidate 取质数时往往更优（与多数元素互质，成本低），可优先枚举质数缩小搜索空间。
四、总结
GS OA 两题风格很典型：Q1 系统实现 + 数据结构协同（queue + 有序表 + 二分），Q2 数论 + 思路优化（互质 + 成本建模）。准备时别只刷算法模板，要练选对数据结构和把业务/数学规则翻译成可优化模型的能力，并随时准备好复杂度优化的 followup。
FAQ
Q1：Goldman Sachs OA 考什么平台、几道题？
HackerRank 平台，约 90 分钟两道题，Python / C++ / Java 可选。难度中上，偏硬核逻辑而非数学计算，考数据结构、复杂度控制和边界思维。
Q2：Log Buffer 题的关键是什么？
数据结构组合：queue 维护顺序保证 O(1) 删最旧，每个 tag 一个有序时间戳表，二分查找统计时间窗口内同标签数量，删除时同步清理 tag 表。整体 O(log n)。
Q3：密码锁那题怎么建模？
把「互质」转成 gcd==1，发现每个不互质元素的修改成本恒为 1，于是 cost = 不互质元素个数，Lock Code = candidate - cost，枚举 candidate 取最大。upper 大时按质因子分桶 + 容斥加速。
Q4：怎么准备 GS OA？
练数据结构组合题（queue/堆/有序表/二分）和数论建模题，重点是把规则翻译成可优化模型，并准备复杂度优化的追问。如需这两道真题的限时陪练，可发岗位 JD 先做题型预测再排练习计划。
正在准备 Goldman Sachs OA？
GS OA 偏硬核逻辑 + 工程实现，考数据结构组合与数论建模。oavoservice 提供 GS 全流程陪练：日志缓冲区 / 数论优化题限时模拟、复杂度优化 followup 训练、HackerRank 节奏演练，按岗位线定制题型预测。教练含前大厂资深工程师，熟悉 GS 评分风格。
立即添加微信 Coding0201，获取 GS 真题与陪练。
联系方式
- 微信：Coding0201
- Email：[email protected]
- Telegram：@OAVOProxy