字节面试疯狂拷打网络和手撕!

讲一下多路io复用;讲一下Linux中进程是怎么管理的;Linux怎么实现多线程的;Pthread库中怎么实现的;如何用多进程模拟多线程;僵尸进程和孤儿进程,如何解决;孤儿进程被init进程收留的过程,数据结构角度讲;从数据结构讲一下父子进程关系,PCB里有没有相关内容。缓存:Redis用的什么数据结构;如何用Redis实现一个消息队列,如何实现异步返回。

手撕:给出二叉树中两个子节点,子节点中有指向父节点的指针,找出两个子节点的祖先节点,要求常量级空间复杂度。

#一人分享一道面试手撕题#
全部评论
手撕的话应该是考察LCA吧,O(h)复杂度h树高。O(1)的话不管怎么样都要预处理吧,或者完全二叉树用数学确定这样算O(1)。 我这倒是有个很邪门的方法:我们假设这个地方存了我们所有的祖先节点用位图表示比如1234567这7个节点我们查询67的祖先。我6有这样的位图1010010,7有1010001。把这个存储位置的数相&,我们也公共祖先的位图也就是1010000,反转得到101也就是5,取log2,得到2,这个就是其最近的公共祖先的索引号(0,1,2)正好是我们存储的3号节点。
1 回复 分享
发布于 01-06 18:27 江苏
不是相当于两个链表第一个相交节点吗?
点赞 回复 分享
发布于 01-08 11:45 北京
点赞 回复 分享
发布于 01-05 14:51 四川
如何常量空间复杂度?递归不算吗?
点赞 回复 分享
发布于 2025-12-22 13:25 浙江

相关推荐

01-12 22:27
武汉大学 Java
点赞 评论 收藏
分享
评论
3
9
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务