比起北美其他大厂，脸书的国人数量确实是最多的，所以你在面试很容易碰到“自己人”。

于是很多人在问，脸书好不好“放水”…… 这个问题见仁见智，因为通常国人都会非常认真准备面试，基本功也比较扎实，所以在技术考察上一般不存在放水。

不过遇到国人面试官，现场的压力还是要小一些，毕竟看到同胞会有一定归属感和安全感。

在题目方面，FB 比较爱考原题，比较看重最优解，不是很 care 一定要先暴力解，然后再逐步代码优化。

扒了一道高频题，感兴趣的朋友可以试试看。

给出两个字符串，找到最长公共子序列(LCS)，返回 LCS 的长度。

点此做题

说明

最长公共子序列的定义：

• 最长公共子序列问题是在一组序列（通常 2 个）中找到最长公共子序列（注意：不同于子串，LCS 不需要是连续的子串）。该问题是典型的计算机科学问题，是文件差异比较程序的基础，在生物信息学中也有所应用。
• 维基百科参考

样例 1:

        输入:  "ABCD" and "EDCA"         输出:  1                  解释:         LCS 是 'A' 或  'D' 或 'C' 

样例 2:

    输入: "ABCD" and "EACB"     输出:  2          解释:      LCS 是 "AC" 

算法：动态规划(dp)

算法思路

• 设 X=(x1,x2,…..xn) 和 Y={y1,y2,…..ym} 是两个序列，将 X 和 Y 的最长公共子序列记为 LCS(X,Y)
• 找出 LCS(X,Y)就是一个最优化问题。因为，我们需要找到 X 和 Y 中最长的那个公共子序列。而要找 X 和 Y 的 LCS，首先考虑 X 的最后一个元素和 Y 的最后一个元素。
  1. xn = ym，即 X 的最后一个元素与 Y 的最后一个元素相同，这说明该元素一定位于公共子序列中。因此，现在只需要找：LCS(Xn-1，Ym-1)。
  2. xn != ym，这下要麻烦一点，因为它产生了两个子问题：LCS(Xn-1，Ym) 和 LCS(Xn，Ym-1)。因为序列 X 和 序列 Y 的最后一个元素不相等，那说明最后一个元素不可能是最长公共子序列中的元素。求解上面两个子问题，得到的公共子序列谁最长，那谁就是 LCS （ X,Y ）。用数学表示就是 LCS=max(LCS(Xn−1，Ym)，LCS(Xn，Ym−1))LCS=max(LCS(Xn−1，Ym)，LCS(Xn，Ym−1))
• 我们成功地把原问题转化成了三个规模更小的子问题。 这样就可以用动态规划的方法来解决这个问题

代码思路

• dp[i][j]dp[i][j]表示表示 A 序列前 i 个，与 B 序列的前 j 个的 LCS 长度
• 状态转移方程

复杂度分析

N 表示序列 S 的长度，M 表示序列 B 的长度

• 空间复杂度：O(NM)
• 时间复杂度：O(NM)

public class Solution {     /**      * @param A: A string      * @param B: A string      * @return: The length of longest common subsequence of A and B      */     public int longestCommonSubsequence(String A, String B) {         int n = A.length();         int m = B.length();                  // state: dp[i][j]表示表示 A 序列前 i 个，与 B 序列的前 j 个的 LCS 长度         // initialization: 初始值为 0         int dp[][] = new int[n + 1][m + 1];                  // function         for (int i = 1; i <= n; i++) {             for (int j = 1; j <= m; j++) {                 dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);                 if (A.charAt(i - 1) == B.charAt(j - 1)) {                     dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + 1);                 }             }         }                  // answer         return dp[n][m];     } } 

大佬有話說 (0)