专栏首页苦逼的码农头条二面智力题!难受!

头条二面智力题!难受!

01

PART

量出4升水

这道题的答案并不难,但作为面试官,却可以通过这道题考察很多内容。

经典面试题:怎么用3升和5升的桶量出4升的水?

题目没什么补充的,直接分析,一个3升和5升的水桶:

首先用三升水桶装满水,倒入五升水桶:

再次倒满三升水桶,填满后继续倒入五升水桶,直到五升水桶倒满。

清空五升水桶,将三升水桶的一升水倒入:

再次填满三升水桶,倒入五升水桶中:

02

PART

最大的钻石

注意,下面是 n,不是 10。网上的题目好多是 1-10 楼。。。。应该都是被简化的,分析起来并不友好。

1 楼到 n 楼的每层电梯门口都放着一颗钻石,钻石大小不一。你乘坐电梯从 1 楼到 n 楼,每层楼电梯门都会打开一次,只能拿一次钻石,问怎样才能拿到「最大」的一颗?

不要认为这种题目不会出现在面试中,恰恰相反,这类题目出现的概率非常高。这不,有读者就碰到了。下面两个是知乎中也遇到该题的读者截图:

那这种问题主要考察面试者的什么能力呢?一个是面试临场随机应变的能力。第二就是分析问题的能力。

面试时如果被问到这种题目,其实大多数面试官心中并没有一个标准答案。(不排除有面试官深究的)事实是作为面试者,我们只要流畅的给出答案,大概率都是可以顺利过关。

回到题目。其实题中包含一个隐藏条件:随机放置。所有的分析都是基于随机放置给出的。换句话说,如果放置钻石是人为干预大小,那么本题的所以分析则全部不成立

其实这个问题的原型叫做秘书问题,该类问题全部属于最佳停止问题

这类问题都有着统一的解法:

所以到我们的题目里,我们也是可以直接给出答案:我们要选择先放弃前 37%(就是1/e)的钻石,此后选择比前 37% 都大的第一颗钻石。

其实该法则还有很多运用,比如一些常见的推文《谈恋爱拒绝掉前面37%的人》,其实就是一样的原因。

事实上也有人通过测试证明了这个数据:

当 n=30 时,测试一万次,可以看到有 4000 次我们拿到了最大的钻石。

改题目还有一些变种,比如:

一个活动,n个女生手里拿着长短不一的玫瑰花,无序的排成一排,一个男生从头走到尾,试图拿更长的玫瑰花,一旦拿了一朵就不能再拿其他的,错过了就不能回头,问最好的策略?

现在要聘请 1 名秘书,共有 n 个应聘者,每面试 1 人后,就知道了应聘者的好坏程度,且必须立刻决定是否聘用,不可重复面试。策略是拒绝前 k 个应聘者,而从第 k+1 个应聘者开始,一旦有比前 k 个都好的,就立刻聘用。如何决定 k 的值,使得聘用到最佳应聘者的概率最大?

等等。这里再给出一个严谨的推导过程:

本文分享自微信公众号 - 苦逼的码农(di201805)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-06-24

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 从0打卡leetcode之day 5 ---两个排序数组的中位数

    最简单粗暴的就是把这两个数组头尾连接起来,然后重新给他们排序一下,冒泡排序相信你信手拈来,当然,你也可以装逼用快速排序。

    帅地
  • SQL语句大全,所有的SQL都在这里(1.5万字长文)

    1、说明:创建数据库 CREATE DATABASE database-name

    帅地
  • 刷了几千道算法题,这些我私藏的刷题网站都在这里了!

    遥想当年,机缘巧合入了 ACM 的坑,周边巨擘林立,从此过上了"天天被虐似死狗"的生活...

    帅地
  • php中目录操作opendir()、readdir()及scandir()用法示例

    本文实例讲述了php中目录操作opendir()、readdir()及scandir()用法。分享给大家供大家参考,具体如下:

    砸漏
  • ECCV2020优秀论文汇总|涉及点云处理、3D检测识别、三维重建、立体视觉、姿态估计、深度估计、SFM等方向

    ECCV2020的oral和spotlight名单已经发布,与往年相比,accepted paper list中增加了很多3D方向相关的作品,实在值得鼓舞。

    3D视觉工坊
  • 【译】使用Apache的mod重写来保护你的C2 Empire

    背景 伴随着维基红色团队基础架构(Red Team Infrastructure Wiki)的发布,今年圣诞节早早来临。 它在Jeff Dimmock和Stev...

    安恒网络空间安全讲武堂
  • Kafka的日志管理模块--LogManagerKafka源码分析-汇总

    a. 如果kafka进程是优雅干净地退出的,会创建一个名为.kafka_cleanshutdown的文件作为标识; b. 启动kafka时, 如果不存在该文件...

    扫帚的影子
  • JavaScript适配器模式

    是完全不符合客户端的要求的。为了在保证客户端不变的情况下,又能使用新的类库,我们需要使用适配器模式。现在接口发生了变化,使用适配器兼容,以便适应客户端的不变

    wfaceboss
  • OD数据专题——能引发好几篇一般论文的专题

    所谓OD(Original, Destination)数据,本质上是记录“人移动”的一种数据类型,广泛应用于各类研究中,如城市公服设施分布的公平性分析、城市职住...

    Sidchen
  • ASP.NET 2.0 中 Web 事件

    ASP.NET 2.0 还提供了全功能的应用程序监视和健康监视。这个系统是由一个完全可扩展事件模型和一个能将事件发送到多种接收器的事件引擎组成的。举例来说,您可...

    张善友

扫码关注云+社区

领取腾讯云代金券