首页 / 元戎启行2024秋招
#

元戎启行2024秋招

#
6908次浏览 181人互动
此刻你想和大家分享什么
热门 最新
元戎启行一面凉
自我介绍 聊项目2.手撕代码遍历一棵N个点的树,需要选一个起点,遍历整棵树,计算走的路径长度最短为多少。输入: N N-1条长度为1的边,表示为(a,b)输出: 2NNN例子: 1-2 2-3 可能的长度是2和3,所以答案是2.思路:在这个问题中,给定的是一棵N个节点的树,每个边的长度均为1。问题要求找到一个起点,通过这个起点遍历整棵树的路径长度最短为多少。一棵树的遍历问题中,如果所有边的长度相等,那么遍历全树的最短路径长度就等于2*(N-1) - h,其中h是树的高度。因为在遍历过程中,每一个节点(除了根节点)都需要被访问两次(一次进,一次出),所以总路径长度至少是2*(N-1)。然后我们可以减去树的高度h,因为在从根节点到最深的叶节点这段路径中,每个节点只被访问了一次。所以,为了得到最短的路径长度,我们需要选择一个使树高度最小的节点作为起点。这个节点就是树的中心点,也就是树的直径的两个端点。树的直径可以通过以下步骤计算:1. 从任意一个节点开始,进行深度优先搜索(DFS),找到距离这个节点最远的节点A。2. 从节点A开始,进行深度优先搜索,找到距离节点A最远的节点B。那么,节点A到节点B的距离就是树的直径。3. 选择节点A和节点B中的任意一个作为起点,遍历整棵树,就能得到路径长度最短的结果。这个算法的时间复杂度是O(N),因此对于N#2024届校园招聘#  #元戎启行2024秋招#  #2022届毕业生现状#
投递元戎启行等公司6个岗位
点赞 评论 收藏
转发
元戎启行软件开发岗面经
  投递链接:https://app.mokahr.com/m/campus_apply/deeproute/6487#/jobs【内推码】NTAW9FW岗位:软件开发工程师一面:(1)聊项目(2)算法:回文子串(可以不连在一起,******** 上substr和subsequence的区别,一开始理解错意思了,写了一段错误的代码)的数量,二维dp,而且不是按照ij递增顺序来推导的,没写出来。面试官把代码放上来讲了一下dp[i][j]的含义和状态方程什么意思。二面:delete会把内存还给操作系统吗 虚拟内存和物理内存 tcmalloc和malloc 复制构造函数,拷贝构造,移动语义 vector的底层原理 算法:二叉树寻找最小路径(回溯比较简单)。三面:介绍raft---->与paxos协议区别,raft与分布式事务区别(不太明白分布式事务,建议我读数据密集型应用系统设计这本书) 虚函数,多重继承下的虚函数(多重继承下编译器的实现可能不一样,这点答错了) 智能指针 继续问make_shared(应该没答好,只是从内存角度上说了一点点,大家可以参考boost库的文档),shared_ptr线程安全吗 左值右值,继续问std::move 和std::forward(讲了一下perfect_forwarding) map和unordered_map,继续问为什么map用红黑树不用AVL树(不清楚红黑树平衡的原理和优势) B+树 #面经# #秋招提前批启动你开冲了吗# #设计人秋招体验最好的公司# #秋招# #大厂# #自动驾驶# #元戎启行2024秋招# #软件开发# #软开#  #提前批# #提前批真的不会影响正式批吗# #图森未来内推#
投递元戎启行等公司6个岗位
点赞 评论 收藏
转发
玩命加载中
牛客网
牛客企业服务