Goldman CoderPad 四大題型拆解：演算法 / LRU 設計 / 程式碼優化 / 撮合

CoderPad 是 Goldman Sachs 首選的編程面試平台。這篇按真實候選人複盤整理，把 CoderPad 上四大題型和應對策略講清楚，幫你把準備的方向對上 GS 真正考的東西。

一、面試前準備

公司與技術調研：了解 GS 的業務領域（交易、風控、資料）和技術棧（Java、Python、C++）。
在 CoderPad 上練手：熟悉它的介面——執行程式碼、除錯、註解、快捷鍵，別在面試時第一次摸平台。
複習核心 CS 基礎：資料結構（鏈結串列、樹、雜湊表）和演算法（排序、查找、DP）。LeetCode、牛客刷題都推薦。

二、四大題型

1. 演算法題

中上難度、帶現實場景的變體（例如「找出所有和為 target 的不重複子陣列」）。用雜湊表 + 雙指標 / 前綴和，先講思路再寫帶註解的乾淨程式碼。

def subarrays_with_sum(nums, target):
    res, prefix = [], 0
    seen = {0: [-1]}                 # 前綴和 -> 左端索引列表
    for r, x in enumerate(nums):
        prefix += x
        for l in seen.get(prefix - target, []):
            res.append(nums[l + 1 : r + 1])
        seen.setdefault(prefix, []).append(r)
    return res

含負數時不能滑窗，前綴和 + 雜湊才是正解，整體 O(n)。

2. 資料結構設計

典型如 LRU 快取：要求 get / put 都 O(1)。做法是雜湊表 + 雙向鏈結串列——雜湊表存 key→節點定位，雙向鏈結串列維護使用順序，最近用的移到頭部，淘汰從尾部出。

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.cache = OrderedDict()            # key -> value，維護使用順序

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)           # 標記為最近使用
        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.cap:
            self.cache.popitem(last=False)    # 淘汰最久未用

面試時要能說清為什麼選這兩個結構、各操作的複雜度。如果面試官要求手寫雙向鏈結串列（不用 OrderedDict），也得能現場實現節點的插入 / 摘除。

3. 程式碼優化

給一段慢程式碼（如巢狀迴圈 O(n²)），讓你提優化方案：

減少冗餘計算：把迴圈內重複算的量提到外面，或用前綴和 / 快取中間結果。
換更優的資料結構：用雜湊表把「查找是否存在」從 O(n) 降到 O(1)，把兩層迴圈降成一層。
時間換空間或反之：明確說出 trade-off，讓面試官看到你權衡的過程。

例如「兩數之和」從雙重迴圈 O(n²) 優化到雜湊表一遍掃 O(n)，就是這類題的縮影。

4. 金融場景題

模擬交易撮合引擎：處理訂單的建立、撮合、撤單。要展現貼合業務的技術設計，包括可靠性與並發。

買賣盤各用一個優先佇列（堆）：買單按價格從高到低、賣單從低到高；
新訂單進來時，與對手盤價格能成交就撮合，部分成交要更新剩餘量；
撤單要能按 order id 快速定位（雜湊表輔助）；
追問點：並發下如何保證撮合的原子性（鎖 / 單執行緒撮合 + 佇列）、如何做冪等和持久化。

import heapq

class MatchingEngine:
    def __init__(self):
        self.buys = []    # 最大堆：存 (-price, ts, qty)
        self.sells = []   # 最小堆：存 (price, ts, qty)

    def submit_buy(self, price, ts, qty):
        while qty > 0 and self.sells and self.sells[0][0] <= price:
            sp, sts, sqty = heapq.heappop(self.sells)
            traded = min(qty, sqty)
            qty -= traded
            if sqty > traded:
                heapq.heappush(self.sells, (sp, sts, sqty - traded))
        if qty > 0:
            heapq.heappush(self.buys, (-price, ts, qty))

三、樣題速覽

演算法 / DS：整數陣列裡找所有和為 target 的不重複子陣列——前綴和（雜湊）+ 雙指標 O(n)。
編程：Excel 列號轉列名（27 → "AA"）——26 進位無 0，迴圈取模。
行為：用 STAR——講一個你設定並達成的高挑戰目標；講一次團隊分歧及你如何化解。

四、總結

GS CoderPad 的四大題型——演算法、資料結構設計、程式碼優化、金融場景——覆蓋了從基礎功底到工程權衡再到業務建模的完整光譜。準備時別只盯演算法，要練講清結構選型、複雜度和 trade-off 的能力。

FAQ

Q1：Goldman Sachs CoderPad 主要考哪幾類題？

四類：演算法（帶現實場景的中上難度題）、資料結構設計（如 LRU）、程式碼優化（給慢程式碼提速）、金融場景（如交易撮合）。

Q2：LRU 為什麼用雜湊表 + 雙向鏈結串列？

雜湊表負責 O(1) 定位節點，雙向鏈結串列維護使用順序、O(1) 移動和淘汰。兩者配合才能讓 get/put 都 O(1)。Python 裡可用 OrderedDict 簡化，但要能手寫底層。

Q3：撮合引擎題的關鍵追問是什麼？

並發下的原子性（鎖或單執行緒撮合 + 佇列）、撤單的快速定位、冪等與持久化。要把可靠性和並發講到位。

Q4：怎麼高效準備 GS CoderPad？

按四大題型分別準備，重點練「先講思路、說清複雜度與 trade-off」。如需按崗位線做題型預測 + CoderPad 限時 mock + 複盤，可聯繫 oavoservice 定制陪練計劃。

正在準備 Goldman Sachs CoderPad？

GS CoderPad 四大題型各有重點。oavoservice 提供 GS 全流程陪練：演算法 / LRU 設計 / 程式碼優化 / 撮合引擎題限時模擬，CoderPad 即時講思路演練，複雜度與 trade-off 表達訓練，按崗位線做題型預測。教練含前大廠資深工程師，熟悉 GS 判分風格。

立即添加微信 Coding0201，獲取 GS 真題與陪練。

聯繫方式

微信：Coding0201
Email：[email protected]
Telegram：@OAVOProxy