专栏首页码农知识点一道有意思的腾讯算法面试题

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

这周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。

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

我来说两句

0 条评论
登录 后参与评论

相关文章

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

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

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

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

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

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

    程序员大彬
  • 一道很有意思的笔试题(一)

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

    根究FPGA
  • 从外由内剖析一道腾讯面试算法题

    前几天在网上看到一份鹅场的面试题,算法部分大半是动态规划,最后一题就是写一个计算编辑距离的函数,今天就专门写一篇文章来探讨一下这个经典问题。

    五分钟学算法
  • 从外由内剖析一道腾讯面试算法题

    前几天在网上看到一份鹅场的面试题,算法部分大半是动态规划,最后一题就是写一个计算编辑距离的函数,今天就专门写一篇文章来探讨一下这个经典问题。

    帅地
  • 面试 | 卡掉不少人的一道腾讯算法面试题,高手来试试?

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

    霍格沃兹测试开发
  • 解一道经典的腾讯算法面试题(小白也能看懂)

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

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

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

    用户1462769
  • 10道腾讯的Java面试题

    下面总结10道面试腾讯的Java面试题。 1、说几种常见的攻击方式及预防手段。 2、http1.x和http2.x的区别。 3、mysql查询语句怎么做性能分...

    Java技术栈
  • 记一道算法面试题

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

    Java团长
  • 8个有意思的JavaScript面试题

    JavaScript 是一种有趣的语言,我们都喜欢它,因为它的性质。浏览器是JavaScript的主要运行的地方,两者在我们的服务中协同工作。JS有一些概念,人...

    Fundebug
  • 一道面试题的思考

    在继承中new和override相同点和区别?看下面的代码,有一个基类A,B1和B2都继承自A,并且使用不同的方式改变了父类方法Print()的行为。测试代码...

    圣杰
  • 对一道【脉脉】上 头条 算法面试题的思考

    经过测试发现 只要从序号0开始,如果打开则跳过,如果是灭灯,则点击i+1 得到如下效果

    super.x
  • 一道腾讯面试题:厉害了我的杯

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

    五分钟学算法
  • 一道腾讯算法题,拿好不谢~

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

    五分钟学算法
  • 一道很有意思的Redis面试题,我选出了一些优质评论

    起源于我在一个短视频中分享的一道面试题,当然,这道面试题我确实在工作中用过,只是业务场景不同。

    Java艺术
  • 分享一道有十分有意思的JS面试题,附愚人节逻辑题答案

    前段时间,有一学生问了我一道十分有意思的JS面试题,现拿出来与大家进行下分享,题目如下:

    用户1272076
  • 一道有趣的面试题

      前两天在刷leetcode的时候,遇到了一题Implement Rand10() Using Rand7(),rand7()可以给你等概率返回1-7的任意一...

    xindoo

扫码关注云+社区

领取腾讯云代金券