哈喽~，大家好，我是千羽。
以下分享一份面经，也是我认识的一位华中科技大学的大佬，
面微软亚洲研究院暑期实习面经，口头上说pass了但是一直没发offer。最后发现被其他人截胡了。
属实可惜~~~
- 1.英文的自我介绍
- 2.手撕算法：Leetcode 210课程表2。
- 3.拓展性的问题：如何实现后端的扩展性？
- 1. 微服务架构：
- 2. 使用消息队列：
- 3. 数据库水平分片：
- 4. 缓存策略：
- 5. 负载均衡和水平扩展：
- 6. 自动化和监控：
- 7. 设计数据一致性策略：
- 4.算法：Leetcode207
MSRA-一面(pass)
1.英文的自我介绍
代码语言：javascript复制Hello,
I am XXX, a passionate Java developer eager to contribute my skills and expertise to dynamic projects in the tech industry.
With 2 years of experience in Java development, I have cultivated a strong foundation in building robust and scalable applications. My proficiency includes expertise in Spring frameworks or technologies, allowing me to craft efficient solutions aligned with project goals.
In my previous roles, I actively participated in Distributed project, honing my ability to collaborate within diverse teams and adapt to new challenges swiftly. I thrive in problem-solving and embrace continuous learning to stay updated with evolving technologies.
I am excited about the opportunity to bring my Java expertise to ByteDance and contribute to innovative solutions that drive technological advancement.
Thank you for considering my application. I am looking forward to discussing how my skills align with the needs of your team.
2.手撕算法：Leetcode 210课程表2。
题目：
现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前 必须 先选修 bi 。
- 例如，想要学习课程
0，你需要先完成课程1，我们用一个匹配来表示：[0,1]。
返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 。
示例 1：
代码语言：javascript复制输入：numCourses = 2, prerequisites = [[1,0]]
输出：[0,1]
解释：总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。
示例 2：
代码语言：javascript复制输入：numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
输出：[0,2,1,3]
解释：总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。
示例 3：
代码语言：javascript复制输入：numCourses = 1, prerequisites = []
输出：[0]
思路：拓扑排序
代码语言：javascript复制class Solution {
// 主函数
public int[] findOrder(int numCourses, int[][] prerequisites) {
// 建图，和环检测算法相同
List<Integer>[] graph = buildGraph(numCourses, prerequisites);
// 计算入度，和环检测算法相同
int[] indegree = new int[numCourses];
for (int[] edge : prerequisites) {
int from = edge[1], to = edge[0];
indegree[to] ;
}
// 根据入度初始化队列中的节点，和环检测算法相同
Queue<Integer> q = new LinkedList<>();
for (int i = 0; i < numCourses; i ) {
if (indegree[i] == 0) {
q.offer(i);
}
}
// 记录拓扑排序结果
int[] res = new int[numCourses];
// 记录遍历节点的顺序（索引）
int count = 0;
// 开始执行 BFS 算法
while (!q.isEmpty()) {
int cur = q.poll();
// 弹出节点的顺序即为拓扑排序结果
res[count] = cur;
count ;
for (int next : graph[cur]) {
indegree[next]--;
if (indegree[next] == 0) {
q.offer(next);
}
}
}
if (count != numCourses) {
// 存在环，拓扑排序不存在
return new int[]{};
}
return res;
}
// 建图函数
List<Integer>[] buildGraph(int numCourses, int[][] prerequisites) {
// 图中共有 numCourses 个节点
List<Integer>[] graph = new LinkedList[numCourses];
for (int i = 0; i < numCourses; i ) {
graph[i] = new LinkedList<>();
}
for (int[] edge : prerequisites) {
int from = edge[1], to = edge[0];
// 修完课程 from 才能修课程 to
// 在图中添加一条从 from 指向 to 的有向边
graph[from].add(to);
}
return graph;
}
}
3.拓展性的问题：如何实现后端的扩展性？
我的回答：在Dao层可以实现分布式的缓存（分布式redis或者自己实现一个分布式cache），以及需要注意数据的一致性问题。（当然还有很多很多其他的回答）
1. 微服务架构：
- 拆分服务： 将系统划分为小型、自治的服务单元，每个服务专注于一个特定的业务功能。这样可以独立开发、部署、扩展和管理服务。
- 容器化部署： 使用容器技术（例如 Docker、Kubernetes）部署和管理微服务，有助于快速扩展和水平扩展。
2. 使用消息队列：
- 异步通信： 使用消息队列（如Kafka、RabbitMQ）进行异步通信，减少系统组件之间的耦合性，并提高系统的响应性和可扩展性。
3. 数据库水平分片：
- 分片数据库： 对数据进行水平分片，将数据存储在不同的节点上，有助于分担数据库的读写压力，并提高数据处理能力。
4. 缓存策略：
- 使用缓存： 采用缓存（如 Redis、Memcached）来存储频繁访问的数据，减轻数据库负载，提高系统性能。
- CDN 缓存： 如果是处理静态资源，考虑使用CDN进行缓存，减少服务器压力。
5. 负载均衡和水平扩展：
- 负载均衡器： 使用负载均衡器（如 Nginx、HAProxy）将流量分发到多个服务器上，避免单点故障，提高系统的可用性和性能。
- 水平扩展： 根据系统负载情况，动态添加或移除服务器节点，以应对不同负载需求。
6. 自动化和监控：
- 自动化部署： 采用持续集成和持续部署（CI/CD）工具，实现自动化构建、测试和部署，提高开发效率和部署稳定性。
- 系统监控： 使用监控工具（例如 Prometheus、Grafana）对系统进行实时监控，及时发现和解决潜在问题。
7. 设计数据一致性策略：
- 分布式事务： 如有必要，采用分布式事务（如分布式事务管理器）来确保不同数据源之间的一致性。
- 异步处理： 对于对一致性要求不高的操作，可以采用异步处理，例如异步数据同步。
MSRA-二面(pass)
1.算法：Leetcode207
题目
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。
- 例如，先修课程对
[0, 1]表示：想要学习课程0，你需要先完成课程1。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
示例 1：
代码语言：javascript复制输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。
示例 2：
代码语言：javascript复制输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。
思路：拓扑排序
代码语言：javascript复制class Solution {
// 记录一次 traverse 递归经过的节点
boolean[] onPath;
// 记录遍历过的节点，防止走回头路
boolean[] visited;
// 记录图中是否有环
boolean hasCycle = false;
public boolean canFinish(int numCourses, int[][] prerequisites) {
List<Integer>[] graph = buildGraph(numCourses, prerequisites);
visited = new boolean[numCourses];
onPath = new boolean[numCourses];
for (int i = 0; i < numCourses; i ) {
// 遍历图中的所有节点
traverse(graph, i);
}
// 只要没有循环依赖可以完成所有课程
return !hasCycle;
}
void traverse(List<Integer>[] graph, int s) {
if (onPath[s]) {
// 出现环
hasCycle = true;
}
if (visited[s] || hasCycle) {
// 如果已经找到了环，也不用再遍历了
return;
}
// 前序遍历代码位置
visited[s] = true;
onPath[s] = true;
for (int t : graph[s]) {
traverse(graph, t);
}
// 后序遍历代码位置
onPath[s] = false;
}
List<Integer>[] buildGraph(int numCourses, int[][] prerequisites) {
// 图中共有 numCourses 个节点
List<Integer>[] graph = new LinkedList[numCourses];
for (int i = 0; i < numCourses; i ) {
graph[i] = new LinkedList<>();
}
for (int[] edge : prerequisites) {
int from = edge[1];
int to = edge[0];
// 修完课程 from 才能修课程 to
// 在图中添加一条从 from 指向 to 的有向边
graph[from].add(to);
}
return graph;
}
}
- 原文链接：https://github.com/warthecatalyst/What-to-in-Graduate-School/blob/main/秋招的面经/华科计科第二人的秋招报告.md
