题干与适用场景
公开面试记录把题目拆成两个短任务：只调用返回 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 是并列片段数量。
如果数组是流式输入？
保留前一个值、当前起点、最佳起止下标和当前位置即可。输入结束时返回最佳区间，内存不随总长度增长。