我如何在大型图书馆中找到一本书？

Question

我在准备面试时发现了以下问题:

你在一个非常庞大的图书馆,没有计算机访问权限,你正在寻找一本特定的书.

你从卡片目录中查找书籍所在的位置,然后去书架X找到它.

然而,这本书不存在.

只有一个人可以回答问题,即自由主义者,但他只回答是/否回答.另外,他的答案可能不正确.

你找到这本书的策略是什么？

你会如何回答这个问题？你会用什么搜索方法？

Answer 1

使用二进制搜索类型问题来缩小书籍的位置.

每个问题都应该将搜索范围缩小一半.

"图书馆的这一半是书吗？" (指向正确的方向).

将作为一个初步问题.

您也可以使用The Knight和Knave作为询问此人的方法的一部分.你的前5个问题(建立一个基线)可能与你所知道的事情有关.你可以从那里确定他的错误率.之后,您可以使用二元搜索式问题来确定书籍的位置.

Answer 2

1. 向面试官询问有关图书管理员的更多信息,并从那里开始.特别是,找出他是否容易受到贿赂(我的意思是图书管理员,但想到这一点,这也可能适用于面试官).
2. 仔细检查愚蠢的错误(错误的卡,错误的货架,"661-88"是重新"88-199"等等).
3. 搜索借书卡的抽屉.如果是借来的,请记下截止日期并稍后再回来,或者记下借款人的家庭住址并转到B计划.
4. 看看附近,几个方向的书和上下架子,以防它被错误地重新装上.
5. 检查桌子,地板,复印机和回程车.
6. 寻找货架上的空隙.如果在正确的位置有一个间隙,那么至少你知道你正在寻找正确的地方.如果没有差距,那就找一本不属于该书架的书 - 有人可能错误地换了它们.如果没有这样一本错放的书,那么这本书就永远不会放在这个书架上,见下文.
7. 寻找架子上的灰尘.它可能表明过去一个月内是否删除了一本书.同样检查索引卡上的年龄标志.流程图有点复杂,但这本书可能在几年前就丢失了.
8. 检查索引系统:如果该书没有正确的主题/标题/作者/编号,那么索引卡上就会出现拼写错误,您必须自己计算出正确的数字,以找出该书真正的位置.
9. 出去买这本该死的书,你的时间比这更有价值.

Answer 3

步骤A:校准你的图书馆员.

在图书馆挑选一本随机书,走到一个随机的地方,然后向图书馆员询问这本书(你知道它的位置)是否在你的左边.继续测试图书馆员,直到你对图书馆员正确回答的概率p有一个很好的估计.请注意,如果p <0.5那么你最好跟随图书管理员告诉你的相反.如果p = 0.5,那么放弃图书管理员 - 她的反应并不比翻硬币更好.

如果您发现p取决于所提出的问题(例如,如果图书馆员总是正确回答某些问题,但其他问题总是错误的),那么请转到步骤B1.

步骤B1:如果p == 0.5或p取决于问题,请开始在方框外思考,就像Beta建议的那样.

步骤B2:如果p <0.5,则反转图书管理员给出的答案,并进入步骤B3.

步骤B3:如果p> 0.5:选择N.如果p接近1,则N可以是10的低数.如果p非常接近0.5,则选择N large,如1000.N的正确值取决于在p和你希望有多自信.

向图书馆员询问N次相同的问题("我正在向左边寻找这本书").暂时假设更频繁地给出任何响应是"正确答案".计算平均响应,为"正确答案"指定1,为错误答案指定0.称之为"观察到的平均值".

回答类似于从具有2张票的方框中抽取(正确答案和错误答案).N抽样样本的标准差将是sqrt(p q),其中q = 1-p.平均值的标准误差是sqrt(p q/N).

将零假设视为p = 0.5 - 图书馆员只是给出随机响应."预期平均值"(假设无效假设)为1/2.

z统计是 (observed average - expected average)/(standard error of the average) = (observed average - 0.5)*sqrt(N)/(sqrt(p*q))

z统计量遵循正态分布.如果z统计量> 1.65那么你有95%的可能性,图书馆员的平均反应具有统计学意义.如果在N个问题z之后小于1.65,重复步骤B3直到获得统计上显着的响应.请注意,选择N越大,z统计量越大,获得统计上显着的结果就越容易.

步骤C:一旦你得到统计上显着的回应,你就采取行动(使用乔治斯托克的二元搜索理念)并希望你没有统计上的不幸.:)

PS.虽然库可能是三维的,但您可以沿x轴播放二进制搜索游戏,然后是y轴,然后是z轴.因此,可以将三维问题简化为求解3(1维问题).