Wayfair
  • OA
    • Karat
      • 811. Subdomain Visit Count
      • Ads Conversion Rate
      • Recommend Movie
      • Longest Common Continuous Subarray
      • Course Overlap
      • Halfway courses
      • Find one rectangle
      • Find all rectangles
      • Find Multiple Shapes
      • word wrap
      • word processor
      • Basic Calculator
      • Basic Calculator with parenthesis
      • 带变量计算器
      • Valid Matrix
      • nonogram
      • Node with 0 or 1 parents
      • 两个节点是否有公共祖先
      • 最远祖先
      • invalid Badge Records
      • 一小时内access多次
      • canSchedule
      • spareTime
      • sparse vector
      • sparse vector 实现add,dot和cos
      • userlogs earliest and latest access time
      • resource Access with in 5 min
      • Find Word Path in Grid
      • Find legal moves
      • 找能去的所有0区域
      • 最短路径找treasure
  • VO
    • Coding
      • Valid Palindrome
      • Add String
      • Coupon
    • System design
    • BQ
    • OOD
  • SD
  • LeetCode Tag
  • VO Onsite
Powered by GitBook
On this page
  1. OA
  2. Karat

Longest Common Continuous Subarray

PreviousRecommend MovieNextCourse Overlap

Last updated 3 years ago

输入:

[
  ["3234.html", "xys.html", "7hsaa.html"], // user1
  ["3234.html", "sdhsfjdsh.html", "xys.html", "7hsaa.html"] // user2
]

输出两个user的最长连续且相同的访问记录。

["xys.html", "7hsaa.html"]

Solution:

和LCS 做法类似,如果当前两个string相等就把当前格子变成[i - 1][j - 1] + 1。不相等就保留0。

Same as

    public String[] longestCommonContinuousHistory(String[] history1, String[] history2)
    {
        int s1 = history1.length;
        int s2 = history2.length;
        
        int count = Integer.MAX_VALUE;
        int startIndex = 0;
        //int endIndex = 0;
        
        int[][] dp = new int[s1+1][s2+1];
        for(int i = 0; i<=s1; i++)
        {
            dp[i][0] = 0;
        }
        for(int j = 0; j<=s2; j++)
        {
            dp[0][j] = 0;
        }
        
        for(int i = 1; i<=s1; i++)
        {
            for(int j = 1; j<=s2; j++)
            {
                if(history1[i] == history2[j])
                {
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else
                {
                    dp[i][j] = 0;
                }
                
                
                if(dp[i][j] > count)
                {
                    count = dp[i][j];
                    startIndex = i-count;
                    //endIndex = i;
                }
            }
        }
        
        String[] result = new String[count];
        int index = 0;
        while(index < count)
        {
            result[index] = history1[startIndex];
            index++;
            startIndex++;
        }
        
        return result;
    }
https://leetcode.com/problems/longest-common-subsequence/
https://www.geeksforgeeks.org/longest-common-subarray-in-the-given-two-arrays/#:~:text=Given%20two%20arrays%20A%5B%5D,between%20the%20two%20given%20array.
https://leetcode.com/problems/maximum-length-of-repeated-subarray/
https://app.gitbook.com/s/-M33ghpQv0ZbnP8UX-Qg/9.dynamic-programming/1143.-longest-common-subsequence-m