学习
实践
活动
专区
工具
TVP
写文章
专栏首页码农知识点一道有意思的腾讯算法面试题

一道有意思的腾讯算法面试题

这周233酱和多年未见的老友聚了聚,除了变秃了点,大家都还是当初的模样儿~

我只好把从果壳看来的防秃指南告诉她。虽然没有一招制胜的卵方法,但也打消了我写防秃水文的念头...

从知乎「有哪些令人拍案叫绝的算法?」话题下看到一个简单有趣的回答,是原作者「时宇电」面试腾讯的一道算法题。233酱的思考路线和作者的差不多,这里整理后分享给大家~

题目描述

有一种玻璃杯从一栋100层的大楼扔下,该种玻璃杯超过某一层楼会摔碎。 现在给你两个杯子,问确定最低摔碎的楼层需要摔多少次?

题目分析

这道题的假设是:最低摔碎的楼层可能是每一层楼,且概率相同。我们需要找一种方法,使得定位到[1-100]之间的任意一个数都是快速的。

解题思路

最简单的方法是用一个杯子从第一层开始,不断一层层的往上试。但是这样的时间复杂度是O(n)。直觉也告诉我们想放大步子扔

因为我们有两个杯子,可以考虑成一个杯子Cup1不断扔直到破碎,它用来确定最低摔碎的楼层在什么范围,

另一个杯子Cup2再此基础上一层层的扔。用来准确确定最低摔碎的楼层是多少。

如果凭空想象,我们可能会想到二分法,每次隔5个楼层扔,10个楼层扔...

可是我们马上也应该会想到这么分的不妥之处在于:

确定最低摔碎的楼层所需次数是不均匀分布的。

我们再来看:每次扔的楼层间隔会带来什么影响?

确定最低摔碎的楼层:

总次数 = Cup1扔的次数 + Cup2扔的次数

楼层间隔越大,Cup2需要扔的次数越多。

相同楼层间隔下:最低摔碎的楼层越高,Cup1需要扔的次数越多,Cup2需要扔的次数可认为相同。

我们的目的其实是需要尽可能保证:不管最低摔碎的楼层是第一层还是第99层,扔的总次数都尽可能一致且减少。

如果小伙伴有看我上篇文章中LSMT分层步隆过滤器的实现,有没有受到启发?

这里我们可以使Cup1需要扔的楼层间隔递减,这样可改善高楼层所需Cup1/Cup2扔的次数。

假设第一次扔的楼层间隔为X,此后依次递减1层,直到楼层间隔为2.则: x+(x-1)+(x-2)+...+2 >=100

求解出答案为14。

本文参与 腾讯云自媒体分享计划 ,欢迎热爱写作的你一起参与!
本文分享自作者个人站点/博客:https://www.jianshu.com/u/33d6034f5539复制
如有侵权,请联系 cloudcommunity@tencent.com 删除。
登录 后参与评论
0 条评论

相关文章

  • 一道有意思的面试题

    例如:现有3个字符串,分别为 a="abcaababcbccabc" b="abc" c="123"

    Wu_Candy
  • 一道有意思的面试算法题

    前阵子突发奇想,突然开始刷leetcode。其中刷到了一道有意思的题目,发现这道题是当时秋招的时候,腾讯面试官曾经问过我的题目。于是分享给大家看下。

    嘿嘿嘿
  • 一道有意思的 CSS 面试题,FizzBu​​zz ~

    如果遇见了 3 的倍数要说 Fizz,5 的倍数就说 Buzz,如果即是 3 的倍数又是 5 的倍数就说 FizzBuzz。

    Sb_Coco
  • 一道有意思的“初始化”面试题

    今天向大家分享一道Java面试题目,这道题是我自己设计的题目。题目原型来自于《Thinking in Java》中的“初始化与清理”一章,本来是一道简单的考察“...

    Java架构师必看
  • 一道腾讯面试题

    今天给大家分享一道腾讯面试算法题目(LeetCode62题),国庆假期一起充充电~

    程序员大彬
  • 记一道有意思的算法题Rotate Image(旋转图像)

    题出自https://leetcode.com/problems/rotate-image/ 内容为:

    深蓝studyzy
  • 记一道算法面试题

    前几天有个朋友去面试,面试官问了他一道链表相关的算法题,不过他一时之间没做出来,就来问了我一下,感觉这道题还不错,拿来讲一讲。

    Java团长
  • 解一道经典的腾讯算法面试题(小白也能看懂)

    算法,对于一个程序员还是非常重要的,它不单单能体现你的数学思维,还能体现出一种逻辑能力,如果你要进BAT这样的大厂,请一定重视算法,它是你的必经之路。

    用户1462769
  • 解一道经典的腾讯算法面试题(小白也能看懂)

    算法,对于一个程序员还是非常重要的,它不单单能体现你的数学思维,还能体现出一种逻辑能力,如果你要进BAT这样的大厂,请一定重视算法,它是你的必经之路。

    帅地
  • 记一道未能答出的算法面试题

    昨天晚上,参加了一场面试,有道算法题当时没答出来,痛心疾首!刚刚起床给娃娃换尿布的空当,突然间就想清楚了实现的办法,当时没答出来就是卡在构建多叉树这一点!本文会...

    用户1332428
  • 记一道字节跳动的算法面试题

    版权声明:本文为苦逼的码农原创。未经同意禁止任何形式转载,特别是那些复制粘贴到别的平台的,否则,必定追究。欢迎大家多多转发,谢谢。

    帅地
  • 记一道字节跳动的算法面试题

    前几天有个朋友去面试字节跳动,面试官问了他一道链表相关的算法题,不过他一时之间没做出来,就来问了我一下,感觉这道题还不错,拿来讲一讲。

    乔戈里
  • 一道腾讯面试题:不同路径

    一个机器人位于一个 m x n 网格的左上角 。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角。问总共有多少条不同的路径?

    程序员大彬
  • 一道腾讯面试题:厉害了我的杯

    有一种玻璃杯质量确定但未知,需要检测。 有一栋100层的大楼,该种玻璃杯从某一层楼扔下,刚好会碎。 现给你两个杯子,问怎样检测出这个杯子的质量,即找...

    五分钟学算法
  • 面试 | 卡掉不少人的一道腾讯算法面试题,高手来试试?

    给定一个不确定的 Json 对象,求 Json 子节点的最大深度(编程语言不限,不可写伪代码)。如下:

    霍格沃兹测试开发
  • 一道很有意思的笔试题(一)

    看到了一个interesting的题,和大家分享一下,如果大家有什么额外的见解欢迎大家公众号后台留言!

    根究FPGA
  • 这是一道算法面试题,不妨看看

    要想从start 点到 finish 点,那么,必然经过 h1 或 h2 点,所以,问题转化为:求 start 点到 h1 点,或 start 点到 h2点的路...

    double
  • 一道腾讯算法题,拿好不谢~

    今天分享的题目来源于 LeetCode 上的剑指 Offer 系列 面试题11.旋转数组的最小数字。根据统计,在腾讯的算法面试环节出现频率较高,属于简单中等难度...

    五分钟学算法
  • corCtf2022一道有意思的node题

    题目很短, flag在/app/flag.txt里,给了源码和Dockerfile,可以在本地测试

    pankas

扫码关注腾讯云开发者

领取腾讯云代金券