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

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

这周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 条评论
登录 后参与评论

相关文章

  • disconf客户端使用篇

    此时,当更新disconf-web管理台对应的remote.properties文件时,会重新在disconf/config目录下下载最新文件,RemoteSe...

    Monica2333
  • disconf-client原理分析

    com.baidu.disconf.client.DisconfMgrBean:第一个加载的bean

    Monica2333
  • disconf配置crud交互流程

    整体的实现是用zk watch作为轻量级的实时推送。当配置更新时, disconf-web推送最新配置到zk上,disconf-client获取到zk事件通知时...

    Monica2333
  • kali2020 永久性网络配置

    查看ip:ip address(ip a) (kali2020 不支持ifconfig查看ip)

    宸寰客
  • 机器学习/深度学习书单推荐及学习方法

    本人是个对数学和人工智能极其感兴趣的人。平时,我也在线上线下经常与国内外的朋友讨论人工智能的各种方面,无论是技术方面还是哲学方面。我帮助过很多实习生和网上的学生...

    用户1737318
  • hive 插入parquet二级分区表数据倾斜优化

    错误: Java Heap Space。或者GC overhead limit exceeded。 原因: Parquet和ORC是列式批处理文件格式。这...

    YG
  • ES6 写法示例

    Joel
  • 智能搜索框实现思路--源码和流程图详解

    我们在浏览各大网站的时候,包括百度、淘宝、京东、雅虎等等网站,当我们输入一个单词或者文字的时候,下面会有一行行待选项供我们选择,很多的公司在做网站的时候也会考虑...

    何处锦绣不灰堆
  • OpenGL ES (iOS) 学习笔记 — 基础篇(一)

    最近一直在做视频相关的工作,结合最近很火的AR技术,所以准备好好学习一下3D渲染的相关知识。因为一直在iOS移动端开发,所以学习一下OpenGL ES 技术。 ...

    MelonTeam
  • 需要知识的后深度学习时代,如何高效自动构建知识图谱?

    二者展示的信息量是差不多的,但右边这种看起来更加直观。而且,随着文本篇幅的增长,这种优势会体现得更加明显。

    机器之心

扫码关注云+社区

领取腾讯云代金券