微软面试体验|第108集（校园）

第一轮： 资质 第二轮： 来自数据结构的2个问题

第三轮：集体飞行

1. 在二叉树中找到两个节点的最小共同祖先。 确定当前根值是否与其中一个键值匹配。如果是，则返回该根。否则，将对左子树和右子树重复该过程。左子树中有一个键，右子树中有另一个键的节点是LCA。如果两个键都位于左子树中，则其值与其中一个键值匹配的第一个节点是LCA。右子树也是如此。时间复杂度为O（n）。面试官要求优化。我提出了一个更好的BST方法。
2. 给定两个排序数组（包含重复元素），从两个数组中找出第k个最小数。
3. 为每个数组维护一个索引，两个数组都初始化为各自数组的第一个元素。循环k次，在每次迭代中找到当前索引中的最小元素，并增加包含最小元素的数组的索引。如果元素相等，则增加两个索引。时间复杂性为O（k）。

第四轮：

1. 给定BST中的节点，将其删除。父链接不是节点结构的一部分。 如果该节点是叶节点，请删除该节点。 如果节点有一个子节点，则用该子节点的值替换该节点的值，并递归删除该子节点。 如果节点有两个子节点，则查找顺序后继节点，用顺序后继节点的值替换当前节点的值，并递归删除顺序后继节点。 时间复杂度为O（h）。采访者建议对一个孩子的情况进行可能的优化，即一个孩子不需要递归删除。我们只需要将它的左、右子指针复制到要删除的节点。 相关文章 : Geeksforgeks链接
2. 谜题——共有九枚硬币，其中一枚有缺陷（重量与其他硬币不同）。找到最大迭代次数以找到有缺陷的一个。 我建议采用分而治之的方法，最多迭代5次。

第五轮：

1. 项目讨论
2. 程序在系统中以无限循环运行。如果我们试图在这个无限循环执行时运行另一个好程序，那么这个好程序会运行吗？

   我回答说程序会运行，但CPU利用率会降低。

3. 编写一段代码在C中实现strtok（）函数。
4. 维护一个索引以表示下一个令牌的开始，并将其初始化为0。线性搜索字符串，如果找到匹配的模式，则将从开始索引到模式的前一个位置的子字符串存储在字符串数组中，并为下一个标记更新开始索引。时间复杂度为O（n）。 面试官想知道我为什么使用malloc（）而不是静态分配。

如果你喜欢Geeksforgek，并且想贡献自己的力量，你也可以使用 贡献极客。组织 或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。