搜索
写经验 领红包
 > 地理

科技公司面试题目(科技公司面试技巧)

在生活中,很多人可能想了解和弄清楚烧脑的科技公司面试题的相关问题?那么关于科技公司面试题目的答案我来给大家详细解答下。

科技公司面试题目(科技公司面试技巧)

据说是某科技公司面试题:1000个瓶子,其中只有1瓶是毒药,其他都是水,外观无法区别,现在有10只小白鼠和无限多干净试管,怎样找出那瓶毒药。

(一)

最直接的办法,挨个试。但是问题呢,很明显,就是效率低下。因为你不能连续喂,需要观察时间,要不然不成了于谦吃蘑菇了...

假定每次喂水间隔半小时观察时间,每次可以试10个,最好的结果是第一次就试出来了,最差的结果就是第100次才试出来,期望就是50次,需要25小时,啥也不干,4天的时间,效率非常底下。

(二)

有人说,这题就是二进制的问题。正好10只小白鼠,2的10次方等于1024,大于1000,刚刚好能解出。此解法的核心思路就是分组。

我们推演一下,第一次,1000瓶子平均分为两组,每组的500瓶每瓶取一滴混合,喂小白鼠,小白鼠中毒,看是否中毒;第二次,把500再平均分为两组,重复以上操作;第三次分每组125,第四次分向上取整63,第五次分向上取整32,第六次16,第七次8,第八次4,第九次2,第十次,2选1,完美!

是真完美了吗?不见得吧!存在的问题,还是效率!10次需要5个小时,而且小白鼠全军覆没,消耗高!

(三)

如何才能提高效率呢?我先分析一下二进制的问题,最大的缺陷就是,每次只试验一组,是一维的,扩展维度是不是就可以有效提高效率了?那么维度扩展到多少?对,小白鼠有10只,那就扩展到10维。

推演一下。第一步,分10组每组100个,每瓶取一滴混合,喂小白鼠,筛选出1组100瓶;第二步,100瓶分为9组,筛选出1组向上取整12瓶;第三步,12瓶分8组,筛选出1组向上取整2瓶,第四步,筛选出毒药。

只需要4步4只小白鼠,完美!

(四)

真完美了吗?有人说,上面第三种方法还可以优化一下。第二步不能整分,我们可以整分为10组,9只小白鼠去试其中9组,能试到最好,如果小白鼠都没中毒,说明没试那组有问题!逻辑很严密,perfect!第三步,10瓶分8组筛选出1组向上取整还是2瓶,虽然还得需要第四步,但是,我们仔细分析一下,还是有八成以上的概率在三步之内完成!

(五)

完美了吗?三步完成的概率能不能再提高?

从上面的优化我们看到,维度还可以再扩展!就是优化关键的第一步,从原来的10维扩展为11维,逻辑上没问题,perfect!

推演一下。第一步,1000瓶分为11组筛选出一组向上取整为91瓶;第二步,91瓶分10组,这一步需要展开分析,9组9瓶,1组10瓶,9只小白鼠试验9瓶的9组,如果中毒,则第三步9瓶8只小白鼠;如果没中毒,那么第三步是剩余的一组10瓶9只小白鼠,可见第三步一定能完成确认!

真完美了吗?没有!因为考虑概率的的影响后,我们不一定非得等分,实际上我可以适当减小需要喂小白鼠的样本组的样本数量,例如上面第一步,我们分成90瓶10组和100瓶1组,这样分组的结果就是,小白鼠中毒,那么下一步是9只小白鼠验证90瓶子,如果没有中毒,那么下一步是10只小白鼠验证100瓶子,这种优化在样本空间增大时效果才能显现出来,就我们此时需求,效果不明显。

通过上面分析,经过不断的优化,方案越来越来完美,然而,这是科技公司的面试题,我们应该从代码实现的角度再看看上面的问题,随着不断优化,需要的逻辑越来越复杂,代码实现的难度反而也越来越大,纵观这五步的逻辑,第三步实现起来最简单。因此我们在编程的时候,不要一味追求完美,允许缺憾存在才是解脱,或许,世间万事亦如此吧!

温馨提示:通过以上关于烧脑的科技公司面试题内容介绍后,相信大家有新的了解,更希望可以对你有所帮助。