微软访谈|第27集

第1轮：（1小时） ==============

1. 问题1。设计一个类似java的垃圾收集器。你将如何检测依赖的参考循环？ 历史：课堂设计， 不相交图的圈检测算法 （连通图列表）
2. 问题2。 在O（logn）复杂度的已排序旋转数组中查找一个元素。

第二轮：（1小时15分钟） ===================

1. 问题1。 给定一个有重复元素的排序数组，如何在O（logn）中找到给定元素的第一个索引。 为它编写代码。更改条件以查找该元素的最后一个索引。 [提示二进制搜索]
2. 问题2。 你有一本单词词典。给定一个单词，打印字典中的所有字谜。 说明用于解决此问题的数据结构。
3. 第三季度。设计了一个芯片加密系统。它将执行以下操作：
   • 从用户那里听到一句话
   • 通过一些私钥或公钥加密或任何其他算法对单词进行加密。
   • 通过TCP、UDp或SSL传输加密字。
4. 使用OOD设计类图。您正在使用哪种设计模式来实现这一点。

第三轮：（1小时15分钟） ===================

1. 问题1。在一个平面上，给出了n个点（X和Y）。你将如何找出最大的共线性点。扩展这个算法。它适用于3D平面中的点（x、y、z）。
2. 问题2。 反转32位整数。为它编写代码。
3. 问题3。 多线程中的不同问题是什么 ? 互斥和信号量之间的区别是什么。
4. 第四季度。你有一个百万字的文件。在该文件中查找最常见的10个单词。可以在内存中存储所有单词的节点。 （注：最小堆+列表）

第四轮： 跳过…

第五轮（2小时30分钟） ===================

1. 问题1。给你一个文本，其中所有空格、句号和标点符号都被删除。你想通过在单词之间加空格来重建文本。 并给出了一个dict。
   • 确定文本是否可以转换为带有有效单词的句子。
   • 找出重建文本的方法。
   • 找出可以用于重建的最小空间数。
   • 对于案例（c），找出你应该放置空格的索引。
   • 现在将文本恢复到句子中。
   后续问题：
   • 1.为什么贪婪的技术不适用于此？
   • 2.是的！回溯将起作用，使用回溯有什么问题？
   • 3.说明并解释如何从动态表中收缩解决方案？
   • 4.为（c）、（d）、（e）编写正确的工作代码。
2. 问题2。有了BST， 用S求出从根到叶的最小长度。 请注意：
   • 从根节点到叶节点的路径。
   • 路径的节点之和为S
   • 如果存在多个这样的路径，请打印最小长度路径。
   • 该算法使用BST而非BT的优点是什么，以及它如何提高性能。在BST中，是否需要探索双方？
   • 为它编写工作代码。

状态：选中！（面试电话是SDE-I，但他们给了我SDE-II（L61）的职位）

向作者表示祝贺。如果你喜欢Geeksforgek，并想贡献自己的力量，你也可以写一篇文章，然后把你的文章发到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。