摩根士丹利信息技术部暑期实习终面（已OC）

一面（3月18日）完第二个工作日（3月21日）收到了终面通知，终面有点特别，分为4个part，总共3个小时，全英文笔面试。

Part1 (9:00-9:30)

加入会议室后，会有HR告诉你笔试链接（面试邮件中附了）的密码，30分钟2道代码题，核心代码模式，比较easy。笔试过程中HR会邀请你进入另外一个会议室，之后会有面试官进来。

题1

有一个停车场，共n个车位，均在一排。一些车位上停有一些车，给你一个list，记录了每个车的车位号。现在想要用一个roof覆盖k辆车，问这个roof的最小长度是多少？

输入：list = [6, 2, 7, 12], k = 2
输出：2
解释：共4辆车，想用一个roof覆盖2辆车。
覆盖2号车位和6号车位，len = 6 - 2 + 1 = 5；
覆盖6号车位和7号车位，len = 2；
覆盖7号车位和12号车位，len = 6

先对list排序，再维护一个长度是k的滑动窗口，记录窗口左右两端的差值，即为roof长度，取最小值即可。

题2

给你一个list，记录了一些仅以小写字母组成的字符串。另外有一个query数组，对于其中的每个字符串s，输出在list中以该字符串为前缀的字符串个数。

输入：list = ["steve","alex","jack","steves","jackson","jacks"],
query = ["steve","jack","alexs"]
输出：[1, 2, 0]
解释：以steve为前缀的有steves（steve自身不算）
以jack为前缀的有jackson、jacks
没有以alexs为前缀的字符串

构建一个字典树，先将list中所有字符串插入树中。对query中的每个字符串s，在树中进行搜索，找到最后一个字符所在节点（即以s为前缀），对此节点进行dfs即可。

Part2 (9:30-10:10)

9点半进来一个面试官，首先进行自我介绍，然后开启共享屏幕，需要给他展示一下笔试的结果，并解释思路。

第二道题你用到了dfs，对图算法了解多少
一般用什么数据结构存储图？
两道题的时间复杂度各是多少？
第一题你用到排序，你知道Java的排序用的哪个排序算法吗？介绍一下
快速排序的时间复杂度是多少？是稳定的吗？举一个不稳定的例子（这里我知道是不稳定的，但例子举不出来orz）
那你还知道有哪些不稳定的排序算法吗？举个例子（举了选排的例子）

这一轮主要就是聊笔试题，没有啥额外的问题了。

Part3 (10:30-11:10)

每轮面试结束后会有15分钟的休息时间，在会议室中等待下一个面试官的进入。第二轮面试同样需要打开共享屏幕，需要本地IDE。

对Java的optional了解吗（用的很少，没继续问了）
对stream了解吗？给你一个String stream，想要过滤其中以"a"开头的字符串，怎么写（用stream的filter方法，要求用lambda表达式，现场code）
如果还想要返回结果呢？并以List的形式返回（collect方法）
说一说hash table
String的hashcode怎么计算？如果让你实现，你会怎么实现？
Integer的hashcode怎么计算？
关系型数据库和非关系型数据库的区别？了解哪些非关系型数据库？
有两个表，一个表记录了员工id和员工姓名，另一个表记录了员工id和员工家庭住址，一个员工可能有多个家庭住址，现想查询所有员工的id、姓名和住址信息，怎么写SQL？
JVM的堆和栈分别存储了什么？
GC回收的是哪个区域的内存？

聊完之后写了两道题，还有反问环节。