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