题目重点：流式读取商铺地址与经纬度，按规范化地址去重调用 API，再逐行比较坐标；分析缓存规模、歧义地址与错误重试。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练版 API 对规范化的 (address,city,state,zip) 返回唯一可信 (lat,lon)；同一规范化键可跨记录复用一次结果。
- 比较采用球面距离≤0.1km 的训练阈值；题目未明确精度标准，应在真实面试先问。
- 商铺名称不影响地理编码地址键；但地址规范化只做空白折叠和大小写归一，不擅自把 Ave/St 等别名视为同址。
- 训练代码流式输出 (businessName,isValid)；API 失败如何标记、重试与断点续跑作为工程追问。
解题路线
- 把地址四字段做保守规范化形成 cache key；每条记录先查结果缓存，只有新键才调用昂贵 API。相同地址下多个商铺或重复行只支付一次调用成本。
- 将 API 坐标与当前行经纬度用 Haversine 距离比较，避免直接比较浮点值或把经纬度度数差当公里。
- 大文件不能假设不同地址结果全在内存：若 distinct 地址缓存超预算，可先做外部分区/排序，相同 key 聚到一起，一次查 API 后验证该组全部记录，再合并输出原序。
- 若 API 速率受限，按 key 去重后用受控并发与重试；失败不应当‘坐标正确’，需要 unknown 状态和重跑队列。
- 在没有第三方权威缓存、也不能从一个地址推导另一地址的前提下，每个不同规范化地址至少需要一次调用，故此去重达到该模型下的最少调用数。
手动走一遍
两行商铺 A/B 地址分别写 '1 Main St' 与 ' 1 MAIN ST '，其余城市/州/邮编一致。规范化后同键，仅一次 lookup；若 A 坐标贴近返回值而 B 偏离 5km，逐行判断仍分别给 True/False。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from collections.abc import Callable, Iterable, Iterator
from math import asin, cos, radians, sin, sqrt
def _normalize(*parts: str) -> tuple[str, ...]:
return tuple(" ".join(part.split()).casefold() for part in parts)
def _distance_km(a: tuple[float, float], b: tuple[float, float]) -> float:
lat1, lon1 = map(radians, a)
lat2, lon2 = map(radians, b)
x = sin((lat2 - lat1) / 2) ** 2 + cos(lat1) * cos(lat2) * sin((lon2 - lon1) / 2) ** 2
return 6371.0 * 2 * asin(min(1.0, sqrt(x)))
def validate_coordinates(
rows: Iterable[tuple[str, str, str, str, str, float, float]],
lookup: Callable[[str, str, str, str], tuple[float, float]],
tolerance_km: float = 0.1,
) -> Iterator[tuple[str, bool]]:
"""Yield (business_name, within_tolerance); memoize canonical address lookups."""
if tolerance_km < 0:
raise ValueError("negative tolerance")
cache: dict[tuple[str, ...], tuple[float, float]] = {}
for name, address, city, state, postal, lat, lon in rows:
key = _normalize(address, city, state, postal)
if key not in cache:
cache[key] = lookup(*key)
yield name, _distance_km((lat, lon), cache[key]) <= tolerance_km
if __name__ == "__main__":
records = [("A", "1 Main St", "X", "CA", "90000", 34.0, -118.0),
("B", " 1 MAIN ST ", "x", "ca", "90000", 34.0, -118.0)]
assert list(validate_coordinates(records, lambda *key: (34.0, -118.0))) == [("A", True), ("B", True)]
复杂度
N 行、D 个规范化地址时内存哈希方案 O(N) 本地处理与恰好 D 次 API 调用，缓存 O(D)；Haversine 每行 O(1)。外部排序/分区会增加磁盘 I/O，但把内存限制在单分区键量。API 费用主导时，应同时估计 D、重复率和失败重试率。
易错点与追问
容易失分的边界
- 用整行或商铺名当缓存键，同一地址多次调用。
- 把经纬度完全相等当正确性规则，忽略浮点误差与地理编码代表点差异。
- 过度规范化把不同门牌、套间或邮编错误合并。
- API 超时即判该行无效，混淆‘验证失败’与‘无法验证’。
- 未给 N/D 就声称内存 cache 必定足够。
继续深挖
- API 对同址返回多个候选时，如何定义验证通过？
- 缓存需要多久失效，地址数据更新如何处理？
- 外部排序后如何按原文件顺序输出结果？
- 如果只能做抽样审计而非全量，最少调用目标怎么改？
