JP Morgan Chase & Co. NAMR Software Engineer Program 2026 校招 OA 限時 60 分鐘，共兩道算法題。以下為完整題意與解題思路。
題目一：Reduction 3 — 數組縮減總代價
題意
給定 n 個整數的陣列 arr，每次操作從當前陣列取出最小值 min 和最大值 max，將它們的和放回陣列。操作代價為：
cost = ceil((min + max) / (max - min + 1))
共執行 n-1 次操作，最終陣列只剩一個元素，求總代價。
範例
arr = [2, 3, 4, 5, 7]，操作過程：
| 步驟 | 選取 min/max | 代價計算 | 當前陣列 | 累計代價 |
|---|---|---|---|---|
| 1 | 2, 7 | ceil(9/6) = 2 | [3,4,5,9] | 2 |
| 2 | 3, 9 | ceil(12/7) = 2 | [4,5,12] | 4 |
| 3 | 4, 12 | ceil(16/9) = 2 | [5,16] | 6 |
| 4 | 5, 16 | ceil(21/12) = 2 | [21] | 8 |
輸出：8
Sample Case 0
輸入：arr = [3, 5, 2, 1, 9, 6]，輸出：10
解題思路
每次都需要取當前陣列的最小值和最大值，天然適合用有序結構動態維護。
from math import ceil
def findTotalCost(arr):
arr = sorted(arr)
total = 0
while len(arr) > 1:
mn, mx = arr[0], arr[-1]
cost = ceil((mn + mx) / (mx - mn + 1))
total += cost
arr = arr[1:-1]
s = mn + mx
lo, hi = 0, len(arr)
while lo < hi:
mid = (lo + hi) // 2
if arr[mid] < s:
lo = mid + 1
else:
hi = mid
arr.insert(lo, s)
return total
複雜度：O(n²)，若使用 SortedList 可優化至 O(n log n)。
關鍵點
- 整數向上取整：
ceil(a/b)=(a + b - 1) // b，避免浮點誤差。 - 新的和永遠是下一輪的最大值（mn + mx > mx），因此總在陣列最右端。
題目二：Meeting Scheduler — 最少會議室數
題意
給定 n 場會議的起止時間 meetingTimings[i] = [start, end]，同一會議室內會議不得重疊（但允許 end == start 時連續使用同一間）。求最少需要幾間會議室。
範例
meetingTimings = [[1,4],[1,5],[5,6],[6,10],[7,9]] → 2 間
Sample Case 0
輸入：[[2,8],[3,9],[5,11],[3,4],[11,15],[8,20]]，輸出：3
分配方案：
- Room 1: [2,8] → [8,20]
- Room 2: [3,4] → [5,11] → [11,15]
- Room 3: [3,9]
解題思路
經典貪心 + 最小堆（掃描線）：
- 按會議開始時間排序。
- 用最小堆維護已分配會議室的最早結束時間。
- 遍歷每場會議：
- 若堆頂結束時間 ≤ 當前會議開始時間，彈出堆頂（複用會議室），壓入當前結束時間。
- 否則直接壓入當前結束時間（新開一間）。
- 堆的大小即為所需會議室數。
import heapq
def getMinRooms(meetingTimings):
meetings = sorted(meetingTimings, key=lambda x: x[0])
heap = []
for start, end in meetings:
if heap and heap[0] <= start:
heapq.heapreplace(heap, end)
else:
heapq.heappush(heap, end)
return len(heap)
複雜度：O(n log n)，排序主導。
關鍵點
- 注意題目明確：
end == start可以共用同一間（用<=而非<）。 - 堆只存結束時間，大小天然等於當前使用的房間數。
總結
| 題目 | 核心思路 | 複雜度 |
|---|---|---|
| Reduction 3 | 有序結構動態維護 min/max，逐步合併 | O(n²) 或 O(n log n) |
| Meeting Scheduler | 排序 + 最小堆掃描線 | O(n log n) |
兩題都是經典貪心/堆題，60 分鐘內穩定完成沒有問題。
需要 OA / VO 輔助？
JP Morgan、Goldman Sachs、Citadel、Two Sigma 等量化與金融科技方向的筆試題型持續整理中。有不確定的題歡迎直接來問。
微信：Coding0201
#留學生找工作 #JPMorgan校招 #北美求職 #OA代做 #算法面試 #面經
聯繫方式
Email: [email protected]
Telegram: @OAVOProxy