面试问到红黑树,B 树这种原理性的问题,怎么回答比较好?不啰嗦,又能回答到点子上
1
0ZXYDDu796nVCFxq 2021-04-11 11:54:36 +08:00
能回答概念、原理、应用场景就差不多了
如果能结合业务回答就更好 |
2
securityCoding 2021-04-11 11:55:44 +08:00 via Android 2
从具体的问题入手吧。
比如数据库索引采用 B 树会有什么问题改成 B+有什么效果。很多 hashmap 冲突时为什么会链表转红黑树。 每个面试官并不一样,但是都不希望你在背理论,能结合问题把技术的演进过程串起来就非常不错了。 |
3
sagaxu 2021-04-11 12:06:19 +08:00 via Android 15
问问面试官,你们在业务中是如何使用红黑树和 B 树的
|
4
janus77 2021-04-11 12:25:30 +08:00 via iPhone
我觉得面试这个场景不需要考虑语言是否啰嗦,曾经我也像你那样认为,后来我发现说太少很容易被面试官误解成你答的不好。所以只管多点说,啰嗦也没关系,甚至啰嗦是必须的,不要去考虑语言精炼的事
|
5
geebos 2021-04-11 12:29:48 +08:00 3
一般不会问原理吧,记住主要的特性和典型的应用场景就差不多了,当然想要流畅回答还是得把原理搞懂,但是我觉得这些原理能口述讲清楚还真有点难度。比如:
问:B+树的特点是什么 答:B+树的特点就是子节点多,层数少。子节点深度一致。所有子节点组成一个链表。 问:为啥这样搞 答:因为层数少减少 IO 次数。子节点深度一致,查询性能稳定。链表更好地支持范围查询。 我觉得这样基本够用了,可能再和 B 树或者红黑树比较一下,顺便问问红黑树。 |
8
ufan0 2021-04-11 12:53:58 +08:00 via Android
反向面试一波
|
9
marcushbs 2021-04-11 13:02:22 +08:00 4
除非是做数据库或者 OS 的公司,面试问红黑树就是不想好好说话
|
10
asanelder 2021-04-11 13:50:58 +08:00 65
别给面试官感觉是背理论,背八股文就行.
可以不必记细节. 但要回答出, 红黑树, B 树是什么? 用来解决什么问题的? 该问题如何不使用红黑树, B 树, 可以使用什么来解决? 俺比较赞同 2 楼老哥的, 你把技术演进过程串起来就很不错了. 比如说. 想以下这样回答 ---------------- 无论红黑还是 B 树, 都是用来解决搜索问题的, 搜索越快越好嘛. 其实最初的, 就是二叉搜索树. 如果这颗树比较平衡的话, 其搜索效率就等同于二分查找了. 但是呢? 现实是, 二叉搜索树不平衡, 如果不平衡, 你想想, 搜索效率就很差了. 所以呢? 能不能构建二叉搜索树时能让它尽量平衡一些? 于是就有了平衡二叉搜索树. 但是呢, 平衡二叉搜索树插入删除比较麻烦. 为了这种平衡, 付出代价太大(如果你就创建一次, 不经常变动也没事, 反正只有变动时才有代价) 为了即要平衡, 又不想付出太大代价, 就有了红黑树了 当然, 红黑树消除了插入删除的代价, 所以, 对于 HashMap 的某一个 bucket, 如果元素很多, 使用红黑树是很适合了.(因为 HashMap 一般经常要删除和修改) 到了这里, 红黑树还是二叉树, 层还是比较深的, 和搜索的过程是和层的深度是有关的, 每一次要到某一层的节点加载到内存来比较. 如果所有数据都在内存没问题, 但数据要是在磁盘呢? 每加载一次就是从磁盘到内存的一次 IO, 你也知道, 磁盘读写是很慢的. 所以能不能尽量减少这种 IO 呢? B 树就可以了, B 树不是二叉树, B 树是一种多叉搜索树, 每一个节点都有多个元素. 这样, 对于全部节点固定情况下, B 树肯定比红黑树要浅了, 这样, 潜在的最大 IO 次数一定少了啊. 所以 B 树就应用在数据库的场景下. 同理, 如果你的搜索涉及到多种速度不一的存储介质, 也是可以考虑 B 树的. ----------------------- 俺觉得答成以上这样, 就很好了. 至于现场手写红黑, B 树, 或者问你红黑 B 树的细节的, 俺觉得这是面试官的问题. 你想想, 这些算法是什么人想出来的? 是数学家, 计算机科学家啊? 如果不是你自已想出来的, 你怎么可能熟记于心? 如果你能熟悉写出来, 只有一种情况, 你基本上每隔几天就写一遍, 可能自己默写了几十遍, 几百遍. 只一种算法你就要花这么多时间熟记于心, 还有很多算法呢? 你也能做到每天写一遍? 所以, 遇到什么都不问, 就让你手写红黑或细节的. 都是面试官的问题. 可能是以下几种情况 1. 面试官是天才, 其智商和数学家一样, 这些红黑树对于他们就像 1+1 一样简单 2. 面试官什么也不会, 就是最近背了几遍红黑树, 在你面前炫耀罢了 3. 面试官根本不想要你 以上三种, 这种公司不进也罢. |
11
enchilada2020 2021-04-11 14:00:41 +08:00 via Android
@asanelder 大佬🐮🍺 受教了 感谢
|
12
asanelder 2021-04-11 14:05:02 +08:00 1
@enchilada2020 #11 哈哈, 能对别人有帮助俺就欣慰了.
其实细节很多人都记不住, 这没关系, 主要是梳理清来龙去脉, 知道它们的应用场景, 面对问题给出方案和方向就可以了嘛. 方向方案对了, 细节可以在实施过程中补充就行. 而且很多时候, 细节也不用管呢, 这些通用的, 都有成熟的实现, 咱们这些普通人, 就别想着写出更好的实现了. |
13
geebos 2021-04-11 14:14:56 +08:00
@myBatis 确实不太准确,B+树的内部节点只保存了指针数据都在叶子节点上, 所以 B+树的内部节点比 B 树要小一些,因此同样的页大小能够保存更多的内部节点,所以 IO 的次数会更少一些。但是你说的磁盘随机访问时间我没太搞懂。
|
14
ReferenceE 2021-04-11 14:15:23 +08:00
都已经内卷到这个地步了吗?(这玩意 99.9%的人都用不上
背八股文得了 |
16
dorentus 2021-04-11 14:20:15 +08:00 via iPhone
|
17
asanelder 2021-04-11 14:38:45 +08:00
还有, 俺还补充一点.
俺上面的回答其实是以一种简化的模型为前提的, 不考虑 OS 的虚拟内存以及缓存等. 真实情况肯定会更复杂, 但理解一个东西最好还是现简化模型, 抛开无关的, 否则会太复杂. |
18
w169q169 2021-04-11 15:21:53 +08:00
天生 hell 模式。。为啥人家都是要我写 b+树的呢?
|
19
Erichailong 2021-04-11 15:26:19 +08:00
就像算法导论上上原理型介绍,不要具体细节,核心思想,为什么要用 B+树,他的使用场景。。。
|
20
Erichailong 2021-04-11 15:28:16 +08:00
@asanelder good 大佬
|
22
kikione OP 谢谢大哥,耐心的解答
@securityCoding |
23
clrss 2021-04-11 15:45:17 +08:00 via iPhone
红色的算法第四版看看,核心要义是 2-3 树。
|
25
domodomo 2021-04-11 16:42:41 +08:00 4
问这种问题的面试官一般都是没实际应用过的人才会问出来,他只是想找一个“他觉得”高级的问题来震慑你,显得他有资格当面试官而已,因为他自己不懂才会觉得这个问题高级,你就背课本给他听就好了
我面试的时候如果招业务程序员,我都不会问他算法问题 如果招算法程序员,我会问他实现某个功能他会用哪几个算法,各自优点在哪里缺点在哪里,而不会问他算法原理 问算法原理的面试官一般都是傻 x 好吧,又不是学校的理论考试。 我最讨厌发张纸要你用笔写程序的傻 x 们了。 |
26
bz5314520 2021-04-11 23:45:42 +08:00
建议手写一个红黑树丢他脸上🤡
|
27
serverABCD 2021-04-12 00:02:36 +08:00 via iPhone
@asanelder 人家问的是 B+和 B,你答 B 的演变,上来就被面试官给弊了
|
28
ningfan120 2021-04-12 09:56:37 +08:00
刚好看到了,顺手推一波,一个文章吧,我觉得写的很详细,并且很浅显易懂了 https://github.com/allentofight/easy-cs/blob/main/算法 /红黑树杀人事件始末.md
|