题目重点：oracle只回答某位置是否是某字符，字典能帮助减少查询。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练词典有限同长度且包含答案，查询(position,char)返回布尔、无噪声。
- 代码用等先验、当前最均衡二分贪心；不声称最少最坏次数或最小期望次数。词频先验与查询计费方式未明确。
解题路线
- 维护候选集合，枚举有信息量的位置/字符，计算yes候选数，选|N−2yes|最小者。按oracle真值过滤，直到唯一候选即可识别答案。
- 每次有信息量查询都排掉至少一个候选，因此至多D−1次；均衡选择只是局部启发式。字母频率最高不一定最好，接近一半比接近全部的信息更多。
- 要求真正最优策略时，最坏深度递推F(S)=1+min_query max(F(Syes),F(Sno))，单候选0；期望版使用归一化概率加权。状态为候选子集，可能指数级，不能保证贪心最优。
手动走一遍
候选cat/car/dog，问首位c真留下cat/car，再问末位t即可区分；假则dog。若隐藏词不在词典，候选可能被筛空，应报合同矛盾而非猜词。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
def guess(dictionary,oracle):
# Uniform prior heuristic: split the remaining candidates as evenly as possible.
candidates=set(dictionary);queries=[]
if not candidates or len({len(w) for w in candidates})!=1:raise ValueError("same-length dictionary required")
while len(candidates)>1:
n=len(candidates);options=[]
for i in range(len(next(iter(candidates)))):
for char in sorted({w[i] for w in candidates}):
yes=sum(w[i]==char for w in candidates)
if yes<n:options.append((abs(n-2*yes),i,char))
_,position,char=min(options);result=bool(oracle(position,char));queries.append((position,char,result))
candidates={w for w in candidates if (w[position]==char)==result}
if not candidates:raise ValueError("oracle contradicts dictionary")
return next(iter(candidates)),queries
复杂度
一次选择O(LD²)简单实现，至多D−1轮，保守O(LD³)时间，O(LD)词典+候选空间，oracle调用≤D−1。
易错点与追问
容易失分的边界
- 把完整单词猜测与单位置布尔查询混为同一次调用会算错成本。
- 利用词频优化期望值不保证最坏次数最小。
继续深挖
- 怎样memo候选mask并用决策树递推精确优化小词典？
- 答案有不同先验时查询分割概率怎样计算？
