微软上海C+AI 挂经

一面2.21
全程中文面。
首先花了大概20分钟时间聊简历。主要是聊简历中面试官感兴趣的部分。
Basic questions
介绍一下你在实验室做的这个项目。
这个项目主要包含了几个部分，你负责的主要的模块是什么？
你觉得你负责的模块中最困难的部分是什么，为什么觉得他困难。
Coding
题目描述如下：
在方法执行开始和结束都会打印一条log 信息。输入的是一个log 信息数组。数组如下所示
log 信息里面有输入时的时间戳。
start a
start b
start d
end d
end b
start c
end c
end a
要求建立方法调用树。其中定义方法节点为 MethodNode = {duration, child = {}}. 建立方法的树结构。最后返回root 节点。
一听到题目之后我就感觉不妙。好像是树的反序列化题目。之前从来没有处理过Log 信息。硬着头皮往下分析。
题目要求在本地IDE 完成，并设计节点结构。打开IDE 反应比较慢浪费了几分钟。之后我做的是设计MethodNode 结构。面试官反问我为什么时长用int 不用 Date，因为这里没有复习..... 设计完Node 类型之后，开始尝试写递归。因为对log 不知道怎么处理，中间安静了十分钟我没有思路。感觉面试官也比较失望。我的思路是用HashMap 存储一个方法的起始位置和结束位置。面试官没有表示认可。之后我说了下自己的递归建树的过程。位于index 0 也就是最开始打印出log信息的肯定是根节点。再利用map 找到它的结束节点。中间的节点都是他的子节点，面试官说我的思路是正确的但是没有写代码。结束本场面试。
😢大家有遇到过这道题目码，力扣没有找到原题，能不能给一下思路。
第一场面试的coding 部分没有提前打开ide，也没有提前打开白板，交流全靠谈话，很困难
二面2.22
Basic Questions
1. HashMap 的底层实现逻辑
2. 说一下Java1.7 到1.8 HashMap 做了哪些改进
3. 说一下HashSet 的底层实现逻辑
4. 看到你用了MySQL，说一下ACID 分别是什么
5. 说一下I，也就是隔离性，你知道隔离级别吗？项目中事务的控制如何设置隔离级别？
Coding
求两个带环的链表的链表的相交节点。
说实话拿到题目的一瞬间很懵，感觉这道题目是判断是否有环，求链表相交节点的一个复合题目。
这回我提前做好了准备，准备好了IDE 和 白板。


我只想到了这种情况，面试官提示我还有其他的情况，但是我没有想出来。面试官看我卡住了让我先去coding。 我先编写了判断是否有环的方法，之后又写了判断两个普通链表相交节点的方法。之后面试官让我自己写测试用例判断求相交链表的节点。解决完之后继续返回思考给的题目，面试官说我已经提示你好几次了😂😂😂还是没有想出来。最后时间到了停在这里没有继续coding。发现面试官竟然是吉大的师兄哈哈。
面试结束之后发现大家对于题目的完成程度以及解题速度都比我快很多，哈哈，收到感谢信也不惊讶。再接再厉💪。如果大家有做过这两道题目的或者有解题思路的麻烦告诉我一下，谢谢啦~





















补充内容 (2022-02-25 15:40 +8:00):
第二题可以这么解答：两个环形链表相交，交点要么在环内，要么在环外，在环内的话就有两个，在环外就只有一个。先分别找出两链表的环入口，相同则在环外--将入口指向Null然后按照两正常链表找重合即可，不同则在环内且就是这两个入口。

第一题：第一题可以同栈来解决，事务start时入栈，end时出栈。出栈的时候建立一个新的MethodNode 节点，计算duration。当前start的事务的父节点应该是在栈顶的。当栈为空的时候就是根节点。

天啊 这个Basic Questions 面试官是直接百度的吧。这不是烂大街的问题吗。这种问了能体现出什么能力么。。看到ava1.7 到1.8 HashMap 做了哪些改进就知道是网上随便找的面试题。培训班最喜欢讲的内容

> 说一下Java1.7 到1.8 HashMap 做了哪些改进

这个问题实在是太无聊了...

链表那道莉蔻药六零啊…… 感觉lz题没刷好

补充内容 (2022-02-25 14:51 +08:00):
对不起lz我没看清题目🧎‍♂️ 别喷我

第一个用递归，读到start 就new 一个node，读到end就写duration 然后返回node。中间有别的start，就调用自己，把返回的node添加到child里。

链表的一定要O(1)space 吗？不是的话直接用set存第一个链表的所有node，然后读第二个链表。

补充内容 (2022-02-25 03:42 +08:00):
第一题可以建一个variable 记录读到哪一行。

微软还面java？

palsword 发表于 2022-02-24 11:40:03
第一个用递归，读到start 就new 一个node，读到end就写duration 然后返回node。中间有别的start，就调用自己，把返回的node添加到child里。

链表的一定要O(1)s

第二个有点搞，我想不出不用额外空间的做法

hahaio 发表于 2022-02-24 21:57:59
第二个有点搞，我想不出不用额外空间的做法

那就先分别算出两个链表的环的起点。如果相等说明交点在环之前或者就是环的起点，那就把环的起点当做链表终点，计算这两个链表的交点。如果不相等，看怎么定义的交点。这两个环的起点都可以当做交点。

kimyx7 发表于 2022-2-25 02:48
链表那道莉蔻药六零啊…… 感觉lz题没刷好

补充内容 (2022-02-25 14:51 +08:00):

emmm，蠡口yaoliuling 保证无环

张张ZELN 发表于 2022-03-28 14:24:11
emmm，蠡口yaoliuling 保证无环

emmm看我补充的了吗……我看错了题了已经下跪道歉了