上周刚结束了Meta的远程一面，整个面试过程节奏很快，感觉面试官更想看到的是你清晰的思路和沟通能力，而不是单纯的埋头敲代码。感觉现在大厂面试越来越像一场开卷考试，题目本身可能你都见过，但重点考察的是你拿到问题后，是怎么跟面试官“聊”起来的。下面直接上题，附带我的思路和踩坑复盘。
面试官是个很干练的白人小哥，简单寒暄几句后，屏幕上就直接亮出了第一道题。
Given a binary tree root node, write a function that returns the tree diameter (represented by this node).
Definition: diameter of a tree is the number of nodes on the longest path between any two nodes.
Example:
1
/ \
2 3
/ \ \
4 5 6
\
7
Longest path is between node #4 and node #7, and we have 4 nodes on that path (#2, #1, #3, #6)
-- therefore tree diameter is 2 + 4 = 6.我看到这道题的第一反应不是急着写代码，而是先确认了几个关键点，比如题目定义的“直径”是路径上的节点数还是边数。从例子来看是节点数，但这是一个非常好的沟通点，能体现你的严谨。我的思路是利用深度优先搜索（DFS）自底向上地解决这个问题。对树里的任何一个节点来说，穿过它的最长路径，其实就是它左子树的最大深度加上右子树的最大深度。所以，我需要写一个递归函数，这个函数在计算每个节点深度的同时，顺便更新一个全局变量来记录当前发现的最大直径。这里有个小陷阱，最终的直径不一定非要经过根节点，所以这个“更新最大值”的动作必须在遍历每个节点时都进行。我还跟面试官提了一句，如果题目要求的是边的数量，那我的最终结果只需要在节点数的基础上减一即可，他对此表示赞同。整个过程下来，核心就是一次后序遍历，时间复杂度是O(n)，空间复杂度是递归栈的深度O(h)。
第一题聊完感觉还不错，小哥点点头，接着屏幕上就出现了第二道题，也是一道非常经典的高频题。
There are a total of n courses you have to take, labeled from 0 to n-1.
Some courses may have prerequisites, for example to take course 1 you have to first take course 0, which is expressed as a pair: [1,0]. The size of pair is fixed to 2.
Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
Example 1:
Input: 3, [[1,0], [2,1]]
Output: true
Explanation: There are a total of 3 courses to take. To take course 1 you should have finished course 0. Take course 2 have to finish course 1 first. So the order could be: 0, 1, 2
Example 2:
Input: 2, [[1,0], [0,1]]
Output: false
Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.这道题我一看，心里就有底了，是典型的有向图中的环检测问题。如果课程的依赖关系里存在一个环，比如A依赖B，B又依赖A，那就永远无法完成。解决它主要有两种经典方法，一种是基于拓扑排序的广度优先搜索（BFS），另一种是深度优先搜索（DFS）。我当时选择了DFS的方案，因为它写起来更直接。核心思路就是先把输入的依赖关系建成一个邻接表，然后用一个visited数组来追踪每个课程节点的三种状态：0代表未访问，1代表正在访问（在当前递归栈中），2代表已访问（从这个节点出发的所有路径都已探索完毕，且无环）。如果在DFS的探索路径上，遇到了一个状态为1的节点，那就说明找到了一个环，可以直接返回false。整个检查过程需要遍历所有课程，确保能覆盖到图中所有不连通的子图。
总的来说，Meta的面试非常注重对数据结构和算法基础的考察，题目本身不一定偏怪，但很看重你分析问题、沟通确认、以及权衡不同方案的能力。他们更想看到的，是你如何一步步把一个模糊的问题变得清晰，并给出一个健壮的解决方案。希望这次的分享能帮到正在求职路上的你，祝大家早日上岸！
本文的作者 石老师，在这里给大家打个硬广，csoahelp.com每日分享北美大厂面经，小红书也有更新，我们还提供种类多样的收费服务协助您进入北美科技大厂，有意向的微信扫码联系我，或者也可以通过其他方式联系我
