题目重点：从稀疏存储、维度检查和零向量边界实现 dot/cosine，并用稠密数组对照验证。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 本文把‘向量相乘’解释为点积：两个向量的维度必须相同，输入是 index→非零数值映射；若面试官要求逐元素乘积，应先确认并更换输出类型。
- 维度不合与越界索引抛 ValueError；题目只说 false return error，未固定错误协议。零向量余弦没有数学定义，本文抛错而非返回 0。
- 数值在 Python 浮点可表示范围内；生产版要约定 NaN/Infinity、精度与重复索引合并规则。
解题路线
- 构造时检查维度与索引范围，并移除零值，以哈希表保存非零坐标。
- dot 先核对维度，再迭代非零项更少的一侧；只查询另一侧同坐标，避免扫描全维度。
- cosine 使用 dot(a,b)/[sqrt(dot(a,a))sqrt(dot(b,b))]；检查两个范数平方是否为零。
- 对称性 dot(a,b)=dot(b,a)、cosine 对同比例缩放不变可做性质检查；本实现还用 7,381 组短向量对稠密参考值独立核对。
手动走一遍
a={0:3,4:4}、b={0:6,2:9,4:8}，维度都为 5，则点积=3×6+4×8=50；a 的范数是 5，b 的范数是 √181，因此余弦为 10/√181。若 b 的维度改为 6，即使非零索引相同也必须报维度错误。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from __future__ import annotations
from math import sqrt
class SparseVector:
"""One explicit training interface for the Apple sparse-vector prompt."""
def __init__(self, dimension: int, entries: dict[int, float]):
if dimension < 0:
raise ValueError("dimension must be non-negative")
if any(index < 0 or index >= dimension for index in entries):
raise ValueError("index outside vector dimension")
self.dimension = dimension
self.entries = {index: value for index, value in entries.items() if value != 0}
def dot(self, other: SparseVector) -> float:
if self.dimension != other.dimension:
raise ValueError("dimension mismatch")
smaller, larger = (self.entries, other.entries)
if len(smaller) > len(larger):
smaller, larger = larger, smaller
return sum(value * larger.get(index, 0) for index, value in smaller.items())
def cosine(self, other: SparseVector) -> float:
numerator = self.dot(other)
left_norm_sq = sum(value * value for value in self.entries.values())
right_norm_sq = sum(value * value for value in other.entries.values())
if left_norm_sq == 0 or right_norm_sq == 0:
raise ValueError("cosine is undefined for a zero vector")
return numerator / sqrt(left_norm_sq * right_norm_sq)
复杂度
构造 O(k) 时间/空间；dot 平均 O(min(k_a,k_b)) 哈希查询；cosine 加上两个范数扫描为 O(k_a+k_b)。若用有序坐标数组，可双指针 O(k_a+k_b) 且内存更紧凑。
易错点与追问
容易失分的边界
- 维度不等时仍对共有索引求和。
- 用全长稠密数组抵消稀疏输入的空间优势。
- 零向量直接除以零或悄悄把 undefined 当成相似度 0。
- 把点积与逐元素乘积混为一个接口。
- 默认 Python float 精确等式用于大量浮点乘加。
继续深挖
- 如果要返回逐元素乘积，怎样只遍历交集？
- 若 index 以有序数组输入，哈希表和双指针的缓存局部性如何取舍？
- 超高维但重复查询同一向量时能否缓存范数？
- 值包含 NaN/Infinity 时怎样定义验证与排序？
