当前位置: 首页 > news >正文

谷歌面试-扔鸡蛋

今天想跟大家分享一个有意思的面试题,这让我再一次感叹思维的奇妙,接下来我们一起看看吧~

首先来看看题目:

你有2颗鸡蛋,需要以最少的尝试次数来判断在100层的高楼上,哪一层楼是鸡蛋的安全层。

换句话说,就是需要确定我们从哪一层楼扔鸡蛋下去,鸡蛋恰好不会摔碎。高于安全层鸡蛋都会碎,低于安全层都不会碎。比如鸡蛋在第1层没有摔碎,在第2层摔碎了,那么鸡蛋的安全层就是第1层。

这里有几个假设条件:

  1. 没有摔碎的鸡蛋可以重复使用;

  2. 每颗鸡蛋的坚硬程度都是相同的。

在这里插入图片描述

这道题乍一看挺简单的,但其实解答相对复杂,而且解法多种多样,要在面试时逻辑清楚地表达完整思路,不仅要求面试者的知识储备要广、反应能力要快,逻辑思维和语言表达能力也是必不可少的。

成为经典可谓当之无愧。

解法1:简单粗暴

我们先来个最省事儿的方法:假设我们只有一颗鸡蛋,显然只有从一楼开始扔,逐层试探,直到鸡蛋摔碎,安全层就是第N-1层。

但是缺点想必大家也看出来了,这是拼运气啊,最坏情况需要扔100次。

用一颗鸡蛋的方法虽然简单粗暴,但也是给两颗鸡蛋的情况缕清一些思路。

简单写一下如何实现:

// 假设arr表示100层楼,每层楼鸡蛋会不会碎,如果arr[i] === 1 表示i层楼的鸡蛋会碎,arr[i] === 0表示第i层楼的鸡蛋不会碎// 简单暴力
const throwEggs1 = (arr) => {for(let i = 1; i <= 100; i++) {if (arr[i] === 1) {return i}}
}

解法2:常规二分

有两颗鸡蛋,二分法想必是大多数同学脑海里浮现的第一个念头吧?

我们先从50楼扔一颗鸡蛋,如果没碎,就往上继续二分,到75楼继续扔······

这是比较顺利的情况,如果不顺利呢,比如我们从50楼扔鸡蛋,直接碎了,那就只有一颗鸡蛋了。

这时候我们就回到解法1了,只能从1楼开始遍历,又是拼运气的时候了,要是运气好,1楼鸡蛋就没了,那测试次数就是1+1=2次,但最坏情况就是1+49=50次。

这么多次,显然是不能通过google面试的。

// 常规二分const throwEggs2 = (arr) => {let left = 1let right = 100let mid = 0while(left <= right) {mid = Math.floor(left + right) / 2if (arr[mid] === 0) {left = mid + 1} else {right = mid - 1}}return mid
}

解法3:均衡切割

虽然二分法不够优秀,但体现了切分范围的思想。

我们的基本思路是,将100层切分成两个维度,由两个鸡蛋分别控制一个维度。

一个维度是用第一颗鸡蛋分金定穴,另一个维度是用第二颗鸡蛋在前蛋的基础上进行遍历。

换言之,我们是将100层切分成若干个区块,由第一颗鸡蛋确定最高安全楼层所属的区块,再由第二颗鸡蛋逐层确定其具体的位置。

在1-100层楼之间,假设我们从上往下尝试,即从100层开始扔第一颗蛋,大概率是碎了,那第二颗蛋便又回到了解法1

所以,我们应该从下往上进行划分、尝试,这样即使第一颗鸡蛋碎了,用第二颗蛋遍历的成本也比较低。

比如第一颗蛋每10层扔一次,第一次从10层扔,第二次从20层扔,第三次从30层扔……一直扔到100层。

第二颗蛋就只用在第一颗蛋摔碎的层数和前一次的安全层之间的9层进行范围遍历。

也就是说,要是第一颗鸡蛋在第30层摔碎了,那就拿第二颗蛋从21层到29层逐层尝试。

这样的最好情况就是第一颗蛋在第10层碎掉,总的尝试次数为1+1=2次。

最坏的情况是在第100层碎掉,总尝试次数为10+9=19次。

在这里插入图片描述

// 均衡切割
const throwEggs3 = (arr) => {let count = 0// 第一个鸡蛋for (let i = 1; i < 10; i++) {if (arr[i * 10] === 1) {count = i * 10break}}// 第二个鸡蛋for(let i = count - 1; i >= count - 10; i--) {if (arr[i] !== 1) {return i}}
}

解法4:微妙平衡

上面的方法,看似已经比较完美了。

但是我们再具像化一点,就能发现问题:第一颗鸡蛋能快速定位安全楼层低的情况,但如果安全楼层位置越高,耗时就会越久,而第二颗鸡蛋在每个区块内的消耗,都是一样的。

如果鸡蛋的最高安全层为18或者98,用解法3的思路的话,这两种情况的总尝试次数并不一样:

最高安全楼层为18时,第一颗鸡蛋试了2次就定位了区块;而最高安全楼层为98时,第一颗鸡蛋试了10次才定位了区块。

虽然第二颗鸡蛋在区块内部的逐层尝试次数是一样的,但98层对应的总尝试次数就多太多了。

原因就是区块完全均匀划分对大数不利

明白了这个缺陷,也就知道了改进的基本思想:要对100找出一种二维区块划分,但不是均匀划分。

对于比较小的区块部分,其包含的楼层范围可以适当增加;越向大数部分走,其包含的楼层范围越来越小。从下往上,每一个区块内所含楼层递减。

在最高安全楼层比较低的情况下,第一颗鸡蛋尝试的次数少;在最高安全楼层比较高的情况下,则第二颗鸡蛋尝试的次数少。

就是用第二颗鸡蛋尝试次数的减少来弥补第一颗鸡蛋需要的尝试次数的递增,使两颗鸡蛋在不同维度上的尝试次数此消彼长,达到一种总体上的平衡。

每上一个区块,第一颗鸡蛋消耗的次数就+1,我们索性就假设每个区块包含的楼层数逐级递减1,以达到平衡。

那么每个区块包含的层数应该如何划分呢?

我们假设第一个区块有X层,那么第二个就是X-1,以此类推,我们就得到了一个方程式:

X+(X-1)+(X-2)+···+3+2+1≥100

可以看出来,这时候区块个数和第一个区块包含的层数其实是相等的。

在这里插入图片描述

现在我们回过头来,再仔细看看方程式,是不是有点熟悉,不就是等差数列求和么!

所以我们化简方程式:

X(X+1)/2≥100

这里X最小值我们向上取整,得到14。

有同学会问为什么一定到1呢,最后一个区块一定只有1层吗?

不是的,到1是表示在X个区块的情况下,最多能覆盖的层数。

比如我们这个例子,X是14,求出的楼层总数是105,也就是可以覆盖105层,题目要求的100层当然绰绰有余。

由此,第一个区块包含14层楼,即1到14层;

第二个区块包含13层楼,即15到27层;

第三个区块包含12层楼,即28到39层;

······

第一颗鸡蛋依次试第14、27、39、50、60、69、77、84、90、95、99、100层。只要期间任何一次鸡蛋碎了,就拿第二颗鸡蛋从上一次的安全层之后开始逐层尝试,直至第二颗鸡蛋也摔碎为止。

用这个方法,总次数一定不会超过14次

因为最高安全楼层越高,第一颗鸡蛋的尝试次数也就越多,但第二颗鸡蛋的尝试次数随之越来越少,两者始终维持着一种微妙的平衡,最后总的尝试次数波动也不会太大。

在这里插入图片描述

下面是全部的代码实现:

// 假设arr表示100层楼,每层楼鸡蛋会不会碎,如果arr[i] === 1 表示i层楼的鸡蛋会碎,arr[i] === 0表示第i层楼的鸡蛋不会碎// 暴力
const throwEggs1 = (arr) => {for(let i = 1; i <= 100; i++) {if (arr[i] === 1) {return i}}
}// 常规二分const throwEggs2 = (arr) => {let left = 1let right = 100let mid = 0while(left <= right) {mid = Math.floor(left + right) / 2if (arr[mid] === 0) {left = mid + 1} else {right = mid - 1}}return mid
}// 均衡切割
const throwEggs3 = (arr) => {let count = 0// 第一个鸡蛋for (let i = 1; i < 10; i++) {if (arr[i * 10] === 1) {count = i * 10break}}// 第二个鸡蛋for(let i = count - 1; i >= count - 10; i--) {if (arr[i] !== 1) {return i}}
}// 微妙平衡
const throwEggs4 = (arr) => {let block = 10let count = 0// block(block + 1) / 2 >= 100while(block * block + block < 100 * 2) {block++}// 第一个鸡蛋的尝试let temp = block // 每层区块的最后一个while(temp <= 100) {if (arr[temp] === 1) {count = tempbreak}--blocktemp += block}// 第二个鸡蛋的尝试for(let i = count - 1; i >= count - block; i--) {if (arr[i] === 0) {return i}}
}

除了文中我们讨论的解法,这道题也还有其他解法可以选择,如果感兴趣大家可以自己研究研究,也欢迎来一起讨论!

凭心而论,要是在毫无准备的情况下,一般人只能想到第一种,做过算法题的,应该能够想到第二种,想到解法三已经是最优解了,能在这么短的时间内想到解法四的大神是凤毛麟角。

好了,祝大家周末愉快!

最后,希望大家读完这篇文章都能有所收获!

相关文章:

谷歌面试-扔鸡蛋

今天想跟大家分享一个有意思的面试题&#xff0c;这让我再一次感叹思维的奇妙&#xff0c;接下来我们一起看看吧~ 首先来看看题目&#xff1a; 你有2颗鸡蛋&#xff0c;需要以最少的尝试次数来判断在100层的高楼上&#xff0c;哪一层楼是鸡蛋的安全层。 换句话说&#xff0c…...

Unity血条制作

一、使用UGUI制作血条 我一般使用image制作血条&#xff0c;当然&#xff0c;也可以使用滑动组件Slider。image的具体操作步骤如下 普通血条 1、在Hierarchy面板中&#xff0c;创建两个image组件&#xff0c;将其中一个设置为另外一个的子节点 2、在Inspector面板中&#…...

vue,uniapp生成二维码

话不多说直接开干 先是vue的 1&#xff0c;首先按照一下依赖 npm install --save qrcode 2,在需要使用的页面引入 import QRCode from qrcode; 3,使用 const codeDetail (item) > {//这个item.code是要生成的数据&#xff0c;我的是一串数字QRCode.toDataURL(item.co…...

分类预测 | MATLAB实现SSA-CNN-SVM基于麻雀算法优化卷积支持向量机分类预测

分类预测 | MATLAB实现SSA-CNN-SVM基于麻雀算法优化卷积支持向量机分类预测 目录 分类预测 | MATLAB实现SSA-CNN-SVM基于麻雀算法优化卷积支持向量机分类预测预测效果基本介绍程序设计参考资料 预测效果 基本介绍 MATLAB实现SSA-CNN-SVM基于麻雀算法优化卷积支持向量机分类预测…...

STM32启动模式详解

文章目录 前置知识1. 单片机最小系统组成2. BOOT电路3. 三种启动模式4. 存储器映射 从主FLASH启动从系统存储区启动从SRAM启动 前置知识 1. 单片机最小系统组成 一个单片机最小系统由电源、晶振、下载电路、BOOT电路、和复位电路组成。少一个单片机都启动不了。 2. BOOT电路 …...

go语言中的切片

切片底层 切片&#xff08;Slice&#xff09;是一个拥有相同类型元素的可变长度的序列。它是基于数组类型做的一层封装。它非常灵活&#xff0c;支持自动扩容。 切片是一个引用类型&#xff0c;它的内部结构包含地址、长度和容量。切片一般用于快速地操作一块数据集合。 切片…...

HTML-常见标签、HTML5新特性

HTML 软件架构 1.C/S架构 (1) C/S架构即Client/Server&#xff08;客户机/服务器&#xff09;结构。 (2) C/S 架构特点 ​ C/S结构在技术上很成熟&#xff0c;它的主要特点是交互性强、具有安全的存取模式、网络通信量低、响应速度快、利于处理大量数据。但是该结构的程序是…...

微信有自己的“知乎”,微信问一问来了!

这几个月来&#xff0c;微信问一问一直挺火的&#xff0c;有人涨粉&#xff0c;有人变现&#xff0c;有人引流~ 这个全新的流量入口对流量玩家来说又是一波巨大的流量红利。 微信问一问就类似于微信版的知乎&#xff0c;未来将对知乎产生一定竞争压力。 依托于微信这个庞大的流…...

[MyBatis系列③]动态SQL

目录 1、简介 2、if标签 3、foreach标签 4、SQL抽取 ⭐MyBatis系列①&#xff1a;增删改查 ⭐MyBatis系列②&#xff1a;两种Dao开发方式 1、简介 开发中在MyBatis映射文件配置SQL语句&#xff0c;但是前面配置的都是比较简单的&#xff0c;不涉及稍复杂的业务场景。想要应…...

开始MySQL之路—— DDL语法、DML语法、DQL语法基本操作详解

DDL语法 DDL&#xff08;Data Definition Language&#xff09; 数据定义语言&#xff0c;该语言部分包括以下内容。 对数据库的常用操作 对表结构的常用操作 修改表结构 对数据库的常用操作 1: 查看当前所有的数据库 show databases; 2&#xff1a;创建数据库 create dat…...

Java“牵手”天猫整店商品API接口数据,通过店铺ID获取整店商品详情数据,天猫店铺所有商品API申请指南

天猫平台店铺所有商品数据接口是开放平台提供的一种API接口&#xff0c;通过调用API接口&#xff0c;开发者可以获取天猫整店的商品的标题、价格、库存、月销量、总销量、库存、详情描述、图片、价格信息等详细信息 。 获取店铺所有商品接口API是一种用于获取电商平台上商品详…...

用AI重构的钉钉,“钱”路在何方?

点击关注 文&#xff5c;郝 鑫&#xff0c;编&#xff5c;刘雨琦 钉钉2023年生态大会&#xff0c;离开了两年的无招&#xff0c;遇到了单飞9天的钉钉。 “做小钉钉、做好钉钉、做酷钉钉”&#xff0c;无招重申了钉钉的方向。 无招提到的三点&#xff0c;再加上“高质量增长”…...

批量根据excel数据绘制柱状图

要批量根据Excel数据绘制柱状图&#xff0c;可以使用Python中的pandas和matplotlib库来实现。下面是示例代码&#xff1a; import pandas as pd import matplotlib.pyplot as plt import os def draw_bar_chart_from_excel(file_path, x_column, y_column, output_folder): …...

浅谈 Java 中的 Lambda 表达式

更好的阅读体验 \huge{\color{red}{更好的阅读体验}} 更好的阅读体验 Lambda 表达式是一种匿名函数&#xff0c;它可以作为参数传递给方法或存储在变量中。在 Java8 中&#xff0c;它和函数式接口一起&#xff0c;共同构建了函数式编程的框架。 什么是函数式编程 函数式编程是…...

闭包的概念

概念 内层函数可以访问到外层函数的变量和参数&#xff0c;即一个函数和它周围状态捆绑在一起的组合。 举例 函数作为返回值 // 函数作为返回值 function test(){const a 1;return function() {console.log(a:,a);} }const fn test(); const a 6; fn(); // 1 2. 函数作…...

openGauss学习笔记-52 openGauss 高级特性-LLVM

文章目录 openGauss学习笔记-52 openGauss 高级特性-LLVM52.1 适用场景52.2 非适用场景52.3 其他因素对LLVM性能的影响52.4 LLVM使用建议 openGauss学习笔记-52 openGauss 高级特性-LLVM openGauss借助LLVM&#xff08;Low Level Virtual Machine&#xff09;提供的库函数&…...

MySQL 8.0字符集校正

MySQL升级为8.0版本时&#xff0c;之前版本的字符集往往是不同的&#xff0c;需要校正。 执行下面的三个SQL语句的查询结果&#xff0c;可以从库、表、列三个层面对字符集进行校正。 库 select concat(alter database , schema_name, default character set utf8mb4 collate …...

软考:中级软件设计师:数据库恢复与备份,故障与恢复,反规范化

软考&#xff1a;中级软件设计师:数据库恢复与备份 提示&#xff1a;系列被面试官问的问题&#xff0c;我自己当时不会&#xff0c;所以下来自己复盘一下&#xff0c;认真学习和总结&#xff0c;以应对未来更多的可能性 关于互联网大厂的笔试面试&#xff0c;都是需要细心准备…...

Unbutu系统-Docker安装、JDK环境配置,Docker常用指令、Docker安装MySQL、Redis、Tomcat、Nginx,前端后分离项目部署

目录 1、防火墙 1.1、查看防火墙状态 1.2、开启防火墙 1.3、关闭防火墙 1.4、重启防火墙 1.5、查看防火墙版本 2、安装JDK 2.1、官网下载tar包 2.3、解压tar.gz文件 2.4、配置环境变量 2.4.1、查看安装路径 2.4.2、设置环境变量 2.4.3、执行该让环境变量生效 2.4…...

Python绘图系统10:在父组件中使用子组件的函数

文章目录 Combobox绑定事件互相调用源代码 Python绘图系统&#xff1a; &#x1f4c8;从0开始实现一个三维绘图系统自定义控件&#xff1a;坐标设置控件&#x1f4c9;坐标列表控件&#x1f4c9;支持多组数据的绘图系统图表类型和风格&#xff1a;散点图和条形图&#x1f4ca;混…...

铭豹扩展坞 USB转网口 突然无法识别解决方法

当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...

基于服务器使用 apt 安装、配置 Nginx

&#x1f9fe; 一、查看可安装的 Nginx 版本 首先&#xff0c;你可以运行以下命令查看可用版本&#xff1a; apt-cache madison nginx-core输出示例&#xff1a; nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...

高等数学(下)题型笔记(八)空间解析几何与向量代数

目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...

python如何将word的doc另存为docx

将 DOCX 文件另存为 DOCX 格式&#xff08;Python 实现&#xff09; 在 Python 中&#xff0c;你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是&#xff0c;.doc 是旧的 Word 格式&#xff0c;而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...

IT供电系统绝缘监测及故障定位解决方案

随着新能源的快速发展&#xff0c;光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域&#xff0c;IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选&#xff0c;但在长期运行中&#xff0c;例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...

C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。

1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj&#xff0c;再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...

蓝桥杯 冶炼金属

原题目链接 &#x1f527; 冶炼金属转换率推测题解 &#x1f4dc; 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V&#xff0c;是一个正整数&#xff0c;表示每 V V V 个普通金属 O O O 可以冶炼出 …...

20个超级好用的 CSS 动画库

分享 20 个最佳 CSS 动画库。 它们中的大多数将生成纯 CSS 代码&#xff0c;而不需要任何外部库。 1.Animate.css 一个开箱即用型的跨浏览器动画库&#xff0c;可供你在项目中使用。 2.Magic Animations CSS3 一组简单的动画&#xff0c;可以包含在你的网页或应用项目中。 3.An…...

HubSpot推出与ChatGPT的深度集成引发兴奋与担忧

上周三&#xff0c;HubSpot宣布已构建与ChatGPT的深度集成&#xff0c;这一消息在HubSpot用户和营销技术观察者中引发了极大的兴奋&#xff0c;但同时也存在一些关于数据安全的担忧。 许多网络声音声称&#xff0c;这对SaaS应用程序和人工智能而言是一场范式转变。 但向任何技…...

在 Spring Boot 中使用 JSP

jsp&#xff1f; 好多年没用了。重新整一下 还费了点时间&#xff0c;记录一下。 项目结构&#xff1a; pom: <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://ww…...