題干與適用場景
公開面試紀錄把題目拆成兩個短任務：只呼叫回傳 0 到 1 之間均勻隨機數的 rand01()，在邊長為 side 的正方形內取樣一個點；給定陣列，找出最長嚴格遞增的連續片段。本文約定正方形左下角為 (0, 0)，邊界點可以出現但機率為零；陣列為空時回傳空區間。
面試官考察點
題目同時考察機率建模、邊界映射、單次掃描與結果定義。Cornell 課程講義說明兩個相互獨立的 [0,1] 均勻變數會形成單位正方形上的均勻點；MIT 的正方形機率教材也用面積解釋這個構造。掃描部分要求區分「連續」與「非連續」，並在相同長度時給出穩定的 tie-break。
回答前需要澄清的問題
rand01()的取值範圍是閉區間還是半開區間？本文按[0, 1)處理。- 正方形是否允許平移？本文從原點開始；平移只需把偏移量加到座標。
- 遞增是否嚴格？本文要求
a[i] > a[i-1]，相等值會切斷區間。 - 並列最長片段回傳哪一個？本文回傳最早開始的片段。
- 是否要求重複取樣去重或安全隨機？基礎題不要求；密碼學場景應改用合適的隨機來源。
30 秒回答框架
「先獨立呼叫兩次 rand01()，把結果乘以邊長得到 x、y；獨立均勻座標的聯合分布在正方形面積上均勻。陣列掃描維護目前片段起點和長度，若目前值嚴格大於前值就延長，否則從目前位置重設；每次達到更長時記錄起止索引。取樣是 O(1)，掃描是 O(n)，額外空間 O(1)。我會測試邊界、單元素、相等值、全遞增、全遞減與並列答案。」
分步驟深入解答
1. 均勻取樣的推導
設 U、V 獨立且都服從 [0,1) 均勻分布。對任意邊界矩形 [a,b) × [c,d)，落入該矩形的機率是 (b-a)(d-c)，等於矩形面積；因此 (side × U, side × V) 在邊長為 side 的正方形中均勻。不要只生成一個隨機數再重複使用，否則兩個座標完全相關，聯合分布會落在對角線上。
2. 線性掃描不變量
掃描到索引 i 時，currentStart 是以 i 結尾的最長嚴格遞增片段起點；bestStart、bestEnd 是前綴中的最佳片段。若 a[i] > a[i-1]，目前長度增加一；否則把 currentStart 設為 i。只在新長度嚴格更大時更新答案，因此自然保留最早的並列片段。
3. 參考實作
from typing import Callable
def sample_square(side: float, rand01: Callable[[], float]) -> tuple[float, float]:
if side < 0:
raise ValueError("side must be non-negative")
u, v = rand01(), rand01()
if not (0 <= u < 1 and 0 <= v < 1):
raise ValueError("rand01 must return values in [0, 1)")
return side * u, side * v
def longest_increasing_run(values: list[int]) -> tuple[int, int] | None:
if not values:
return None
current_start = best_start = best_end = 0
for i in range(1, len(values)):
if values[i] <= values[i - 1]:
current_start = i
current_length = i - current_start + 1
best_length = best_end - best_start + 1
if current_length > best_length:
best_start, best_end = current_start, i
return best_start, best_end4. 複雜度與測試
取樣固定呼叫兩次隨機來源，時間和額外空間都是 O(1)。掃描每個元素一次，時間 O(n)，額外空間 O(1)；若要回傳值而非索引，再切片會額外佔用 O(k)。測試應固定 rand01 序列驗證座標映射，使用 [1, 2, 2, 3] 檢查嚴格性，使用 [5, 4, 3] 檢查單元素答案，並驗證大陣列不會遞迴或配置隨 n 增長的狀態。
高品質示範回答
「我把兩個座標建模為獨立的均勻變數：分別呼叫 rand01，再乘以邊長；如此任意小矩形的機率等於它的面積。遞增片段用一個起點和一組最佳索引在線性掃描中維護，遇到不嚴格遞增就重設，只在更長時更新，所以並列結果穩定取最早者。取樣 O(1)、掃描 O(n)，空間都為 O(1)。我會特別驗證隨機來源範圍、負邊長、相等值和空陣列。」
常見錯誤
- 重複使用同一個隨機數 → 兩個座標相關，點只在對角線上 → 分別呼叫兩次
rand01()。 - 把
rand01()當作任意範圍 → 座標可能越界 → 明確[0,1)合約並檢查輸入。 - 用排序或動態規劃找連續片段 → 遺失原順序或增加不必要空間 → 單次維護目前起點。
- 把
>=當作遞增 → 相等元素被錯誤連接 → 使用嚴格的>。 - 每次長度相等都覆蓋答案 → 並列結果依賴實作細節 → 只在嚴格更長時更新。
- 遞迴掃描陣列 → 深度隨 n 增長 → 使用迭代指標。
追問及應對
如何取樣矩形或平移後的正方形？
對矩形分別使用 x = xmin + (xmax-xmin)U、y = ymin + (ymax-ymin)V。平移正方形等價於在兩個座標上增加偏移量，獨立性保持不變。
如何估計取樣是否均勻？
把正方形劃分為相同面積的網格，生成足夠樣本後比較各格計數；這是診斷工具，不是數學證明。固定隨機種子只用於回歸，不應把單次樣本的視覺均勻當作保證。
如果要求回傳所有並列最長片段？
仍做一次掃描，維護目前最長長度和結果列表。發現更長時清空列表，發現相等時追加起止索引；空間變為 O(r)，其中 r 是並列片段數量。
如果陣列是串流輸入？
保留前一個值、目前起點、最佳起止索引和目前位置即可。輸入結束時回傳最佳區間，記憶體不隨總長度增長。