报一个Jet Karat电面顺便求问一道题最优解

前几分钟讲一下背景
然后限时20分钟给一段大概150-200行的代码做code review，把问题和解决方案写在代码边上

LZ这里做review过于仔细，comment也写得太细，最后时间不太够，最后有一个大的问题只能说一说，没来得及写

然后给了一道题：
给两个用户访问一个网站各网页的list（有序），求这两个list的

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

相同，但是在list B里不是连续的

这道题我想了20分钟没想出比暴力解更好的方法，最后无奈之下把暴力解写了，复杂度是M*N，求问版上大神此题有没有比M*N更好的解法

顺便贴个应该符合面试官心意的DP代码好了

1. class Solution {
   
2. public:
   
3.     int longestCommonSubstring(string &A, string &B) {
   
4.         vector<vector<int>> dp(A.length() + 1, vector<int>(B.length() + 1));
   
5.         int ans=0;
   
6.         for(int i=0;i<=A.length();i++)dp[i][0]=0;
   
7.         for(int i=0;i<=B.length();i++)dp[0][i]=0;
   
8.         for(int i=0;i<A.length();i++){
   
9.             for(int j=0;j<B.length();j++){
   
10.                 if(A[i]==B[j]){
    
11.                     ans=max(ans,dp[i][j]+1);
    
12.                     dp[i+1][j+1]=dp[i][j]+1;
    
13.                 }
    
14.             }
    
15.         }
    
16.         return ans;
    
17.     }
    
18. };

复制代码

最优解是用后缀数组（https://en.wikipedia.org/wiki/Suffix_array），找各种公共子串基本都会用到它
理论上最快可以O(n)，实际应用（算法竞赛）里O(n)算法很难写，竞赛一般写O(nlogn)或O(nlog^2n)的算法
不过面试大概不需要这样程度的算法知识，楼上很多人提到的O(mn)的DP应该就是面试官想要的答案

补充内容 (2018-3-14 10:12):
在Lintcode上用后缀数组AC了，但是很慢。我怀疑是评测端编译没开优化，或者是数据太弱
本地测试后缀数组vs动态规划的结果（C++，编译开-O3）：
n=m=1w 20ms vs 400ms
n=m=3w 70ms vs 4000ms
n=m=10w 300ms vs 爆内存

这题用DP才是MN，参考longest substring。不知道你说的暴力是什么样的可以弄到MN。

请问lz这是申请jet什么职位的电面呢

需要连续，那就类似于substring/subarray题了

leetcode没有lintcode有:
http://www.jiuzhang.com/solutions/longest-common-substring/
不知道是不是这样？


lz的暴力写法应该不是M*N吧…M有O(|M|^2)个substring (continuous subsequence / subarray)

我intuit的oa是这道题。
最优的应该是用dp，m*n的时间，constant的空间（不建二维表，只记录i - 1，j - 1的结果）。

Liddy_L 发表于 2018-2-22 16:08
我intuit的oa是这道题。
最优的应该是用dp，m*n的时间，constant的空间（不建二维表，只记录i - 1，j - 1 ...

不建二維表的話，需要一維表然後從后往前掃，是麽？

cai_lw 发表于 2018-3-14 10:20
顺便贴个应该符合面试官心意的DP代码好了

这里应该要输出的是list，然后其实也可以优化空间吧，2D->1D，经典背包优化