java编程有一筐鸡蛋,妙解谷歌压箱底面试题:如何正确的从楼上抛鸡蛋

本文主要是介绍java编程有一筐鸡蛋,妙解谷歌压箱底面试题:如何正确的从楼上抛鸡蛋,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

google-interview-question-2.html

作者:Marcin Moskala

编译:ShanLIU、笪洁琼、Harry

关于编程工作有很多很不错的面试谜题。新年之际,我把压箱底儿的一道好题,同时也是传说中谷歌招聘官最喜欢问的一道题找出来了!

今天我们来好好八一八这道题,如果你今年恰好想去谷歌面试,可以抓紧多读几遍!(绝对不会出现下图的情况,我们只放有口碑的神助攻

google-interview-question-2.html

题目如下:

你在一座100层的高楼大厦里工作,拿到了两个一模一样的鸡蛋。你得搞明白鸡蛋最高可以从几层楼扔出去还不摔坏。

请提出一个算法,能找到投掷鸡蛋却保证不摔坏的最少次数~

我们可以先做些假设:

如果鸡蛋从某一楼层跌落而不摔坏,那么当它从更低楼层跌落也不会有破损。

一个在被投掷之后完好无损的蛋可以被再利用。

一颗鸡蛋如果破损,则必会被丢弃。

跌落对于所有鸡蛋都具有同等效应。

如果一颗鸡蛋从某一楼层跌落之后受损,那么当它从更高楼层跌落后必定会摔坏。

如果一颗鸡蛋从一次跌落中存活下来,那么它一定会从更短程的降落中存活。

大多数人会写出算法来解决这个谜题(我们同样也是会用算法),然而实际上有更容易的办法。

敲黑板说重点啦!

google-interview-question-2.html

最简单的回答

最简单的方式来获取最少楼层数就是将鸡蛋从第一层扔出,然后第二层,然后依次往后叠加。这样一来,当鸡蛋破碎那一刻我们就知道是这一层了。这是一个可靠的算法,但是在最差的情况下它需要的投掷次数是100次。

需要注意的最重要的一点是,假如你只有一颗鸡蛋,这是唯一可靠的方法。所以在你打破第一颗鸡蛋时就需要开始运用这个算法。

直觉性的答案

这样,我们应该把这100层划分成更小数目的的区间,以尽可能有效地应用这第一颗鸡蛋。因此,一个凭直觉的而且颇受欢迎的方法是从1/第n层逐层检查。

比方说,从第一层到第三层。由此得出算法如下:

从33楼投掷出这颗鸡蛋。如果它破损了,那么我们用第二颗鸡蛋检查第32层楼。

否则,我们从33+ (67 *1/3) =55层楼扔,如果鸡蛋破损,我们再来用第二颗鸡蛋检查34层到55层。

对于1/3最坏的情况是最大值是33层,这样一来,我们可能可以找到一个完美的n,借助一些动态编程手段,来优化投掷次数。这是一个体现编程思维的有价值的解决方式,然而这不是最优解。

完美解决方案

为了理解完美解法,我们需要理解均衡状态,用于计算出在最坏情境下所需的投掷次数。

google-interview-question-2.html

这里,F(n) 是我们从开始投掷鸡蛋计算的下一层楼层。

假如我们引入以下的变量:

google-interview-question-2.html

那么均衡点将会是如下:

google-interview-question-2.html

2c501cacfd5945fcc881fa6709a4d31b.png最优解是当这个方程里的所有参数都相等。我们是如何取得的呢?从末尾开始看,最后的D(n)将会变成1,因为我们最终将会到达一个点,就是只有单一的一层楼用于投掷第一颗鸡蛋。所以D(n-1)应该等于2,因为它相比于第一颗鸡蛋少了一次投掷。

我们接着会发现第一颗鸡蛋最终应该是从第99层楼投掷,之前是从99-2=97层,再往前则是97-3=94层,90, 85, 79, 72, 64, 55, 45, 34, 22,然后是第九层。这是一个最优解!这样一来,我们需要在最坏的情况下投掷14次(最小的差别在于13,但是我们还需要在第九层额外投一次)。

检查

好啦,我们已经有了解决方案,可以无需任何其他帮助来解开它。现在是时候验证它是否正确了!为此,我们可以写一个Kotlin方程式。

首先,我们来解释一下对一些决策来说,是如何计算投掷次数的。当我们有2层或者更少的层数,那么我们需要按照剩余的楼层数来投掷尽量多的次数。否则我们应该调用如下方呈现的均衡函数:

google-interview-question-2.html

这里我们调用了bestMaxThrows 函数,这是一个假设函数,它会返回一个投掷次数的数值,假定接下来的一系列决策是完美的。

我们是这样定义它的:

google-interview-question-2.html

再一次的,我们刚刚授权给了bestNextStep 函数来计算“下一层的最优解”。这个函数很好的为我们指明了下一步的方向,我们可以简单地定义它:当只有二层或更少的楼层待检验,那我们会从第一层扔出鸡蛋,否则我们需要检查所有备选项以找到最优解。

下面是具体执行步骤:

google-interview-question-2.html

再一次的,我们刚刚授权给了bestNextStep 函数来计算“下一层的最优解”。这个函数很好的为我们指明了下一步的方向,我们可以简单地定义它:当只有二层或更少的楼层待检验,那我们会从第一层扔出鸡蛋,否则我们需要检查所有备选项以找到最优解。

下面是具体执行步骤:

google-interview-question-2.html

注意,这个函数使用了maxThrows 函数,所以涉及到了循环。这不是个问题,因为当bestNextStep 调用到maxThrows时,它总是调用一个小于floorsLeft 的数(因为nextFloor 总是大于0)。我们调用这个函数之前先加一些缓冲,用于加速这些运算。

google-interview-question-2.html

首先,我们看看它是否返回和之前计算相同的结果。

google-interview-question-2.html

结果看着不错,我们再看看下面几步:

google-interview-question-2.html

结果:

9, 22, 34, 45, 55, 64, 72, 79, 85, 90, 94, 97, 99, 100,

正是我们计算的结果!赞!

google-interview-question-2.html

拓展

现在我们有了一套可以解决很多相似问题的不错的算法。比如说,我们可以稍微修改一下来计算最随机的情况下的投掷次数。我们也可以看看这一最小数值如何根据建筑高度不同而有所区别。

下图回答了以上的问题:

google-interview-question-2.html

(该图展示了最坏情景的最少投掷次数,纵轴是楼层数,横轴是投掷次数,曲线代表最优投掷次数。)

结论

你现在对于谷歌的面试准备更充分了,但更重要的是,你相比以前更具备算法思想。这个算法呈现了一个很好的,高效型的方法。还可应用于解决我们每日工作中的许多问题。

这篇关于java编程有一筐鸡蛋,妙解谷歌压箱底面试题:如何正确的从楼上抛鸡蛋的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/325623

相关文章

SpringBoot UserAgentUtils获取用户浏览器的用法

《SpringBootUserAgentUtils获取用户浏览器的用法》UserAgentUtils是于处理用户代理(User-Agent)字符串的工具类,一般用于解析和处理浏览器、操作系统以及设备... 目录介绍效果图依赖封装客户端工具封装IP工具实体类获取设备信息入库介绍UserAgentUtils

Spring 中的循环引用问题解决方法

《Spring中的循环引用问题解决方法》:本文主要介绍Spring中的循环引用问题解决方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录什么是循环引用?循环依赖三级缓存解决循环依赖二级缓存三级缓存本章来聊聊Spring 中的循环引用问题该如何解决。这里聊

Java学习手册之Filter和Listener使用方法

《Java学习手册之Filter和Listener使用方法》:本文主要介绍Java学习手册之Filter和Listener使用方法的相关资料,Filter是一种拦截器,可以在请求到达Servl... 目录一、Filter(过滤器)1. Filter 的工作原理2. Filter 的配置与使用二、Listen

Spring Boot中JSON数值溢出问题从报错到优雅解决办法

《SpringBoot中JSON数值溢出问题从报错到优雅解决办法》:本文主要介绍SpringBoot中JSON数值溢出问题从报错到优雅的解决办法,通过修改字段类型为Long、添加全局异常处理和... 目录一、问题背景:为什么我的接口突然报错了?二、为什么会发生这个错误?1. Java 数据类型的“容量”限制

Java对象转换的实现方式汇总

《Java对象转换的实现方式汇总》:本文主要介绍Java对象转换的多种实现方式,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录Java对象转换的多种实现方式1. 手动映射(Manual Mapping)2. Builder模式3. 工具类辅助映

SpringBoot请求参数接收控制指南分享

《SpringBoot请求参数接收控制指南分享》:本文主要介绍SpringBoot请求参数接收控制指南,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Spring Boot 请求参数接收控制指南1. 概述2. 有注解时参数接收方式对比3. 无注解时接收参数默认位置

SpringBoot基于配置实现短信服务策略的动态切换

《SpringBoot基于配置实现短信服务策略的动态切换》这篇文章主要为大家详细介绍了SpringBoot在接入多个短信服务商(如阿里云、腾讯云、华为云)后,如何根据配置或环境切换使用不同的服务商,需... 目录目标功能示例配置(application.yml)配置类绑定短信发送策略接口示例:阿里云 & 腾

SpringBoot项目中报错The field screenShot exceeds its maximum permitted size of 1048576 bytes.的问题及解决

《SpringBoot项目中报错ThefieldscreenShotexceedsitsmaximumpermittedsizeof1048576bytes.的问题及解决》这篇文章... 目录项目场景问题描述原因分析解决方案总结项目场景javascript提示:项目相关背景:项目场景:基于Spring

Spring Boot 整合 SSE的高级实践(Server-Sent Events)

《SpringBoot整合SSE的高级实践(Server-SentEvents)》SSE(Server-SentEvents)是一种基于HTTP协议的单向通信机制,允许服务器向浏览器持续发送实... 目录1、简述2、Spring Boot 中的SSE实现2.1 添加依赖2.2 实现后端接口2.3 配置超时时

Spring Boot读取配置文件的五种方式小结

《SpringBoot读取配置文件的五种方式小结》SpringBoot提供了灵活多样的方式来读取配置文件,这篇文章为大家介绍了5种常见的读取方式,文中的示例代码简洁易懂,大家可以根据自己的需要进... 目录1. 配置文件位置与加载顺序2. 读取配置文件的方式汇总方式一:使用 @Value 注解读取配置方式二