You're given two sequences of integers. Your task is to write a function that finds the Longest Common Subsequence (LCS) of the two sequences. def find_lcs(seq1: list, seq2: list) -> list: pass Inputs seq1: A list of integers representing the first sequence. seq2: A list of integers representing the second sequence. Output Return a list of integers representing the Longest Common Subsequence of seq1 and seq2. Example Given the sequences seq1 = [1, 2, 3, 4, 5] and seq2 = [6, 7, 1, 2, 8], your function should return [1, 2].

Q: Longest Common Subsequence (LCS)

# Implementing the Longest Common Subsequence (LCS) using Dynamic Programming def find_lcs(seq1, seq2): n = len(seq1) m = len(seq2) # Initialize a DP table with zeros dp = [[0] * (m + 1) for _ in range(n + 1)] # DP step: fill in the table for i in range(1, n + 1): for j in range(1, m + 1): if seq1[i-1] == seq2[j-1]: dp[i][j] = dp[i-1][j-1] + 1 else: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) # Reconstruct the LCS lcs = [] i, j = n, m while i > 0 and j > 0: if seq1[i-1] == seq2[j-1]: lcs.append(seq1[i-1]) i -= 1 j -= 1 elif dp[i-1][j] > dp[i][j-1]: i -= 1 else: j -= 1 return lcs[::-1] # Reverse the LCS to get it in the correct order # Test the function seq1 = [1, 2, 3, 4, 5] seq2 = [6, 7, 1, 2, 8] print(find_lcs(seq1, seq2)) # Should return [1, 2]

Longest Common Subsequence (LCS) | Array And List Processing

Interview Questions Programming Longest Common Subsequence (LCS)

You're given two sequences of integers. Your task is to write a function that finds the Longest Common Subsequence (LCS) of the two sequences.

def find_lcs(seq1: list, seq2: list) -> list:

    pass

Inputs

seq1: A list of integers representing the first sequence.
seq2: A list of integers representing the second sequence.

Output
Return a list of integers representing the Longest Common Subsequence of seq1 and seq2.

Example
Given the sequences seq1 = [1, 2, 3, 4, 5] and seq2 = [6, 7, 1, 2, 8], your function should return [1, 2].

Make use of a Dynamic Programming table (DP table). It's a data structure, often implemented as a 2D array (or sometimes higher dimensions depending on the problem), used to store intermediate results of subproblems so that they can be reused later. This is a key aspect of dynamic programming that helps to improve computational efficiency by avoiding redundant calculations.

In the context of the Longest Common Subsequence (LCS) problem, the DP table dp is a 2D array where dp[i][j]stores the length of the LCS of the prefixes seq1[0..i-1] and seq2[0..j-1]. This table is filled iteratively based on the relations between smaller subproblems, and the final answer is constructed by backtracking through this table. The use of a DP table allows us to solve the problem in significantly less time compared to using

a different naive recursive approach.

# Implementing the Longest Common Subsequence (LCS) using Dynamic Programming

def find_lcs(seq1, seq2):

    n = len(seq1)

    m = len(seq2)

    

    # Initialize a DP table with zeros

    dp = [[0] * (m + 1) for _ in range(n + 1)]

    

    # DP step: fill in the table

    for i in range(1, n + 1):

        for j in range(1, m + 1):

            if seq1[i-1] == seq2[j-1]:

                dp[i][j] = dp[i-1][j-1] + 1

            else:

                dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    

    # Reconstruct the LCS

    lcs = []

    i, j = n, m

    while i > 0 and j > 0:

        if seq1[i-1] == seq2[j-1]:

            lcs.append(seq1[i-1])

            i -= 1

            j -= 1

        elif dp[i-1][j] > dp[i][j-1]:

            i -= 1

        else:

            j -= 1

    

    return lcs[::-1]  # Reverse the LCS to get it in the correct order



# Test the function

seq1 = [1, 2, 3, 4, 5]

seq2 = [6, 7, 1, 2, 8]

print(find_lcs(seq1, seq2))  # Should return [1, 2]

Python scratchpad

# Run Python right here in your browser
def two_sum(nums, target):
    seen = {}
    for i, n in enumerate(nums):
        if target - n in seen:
            return [seen[target - n], i]
        seen[n] = i
    return []

print(two_sum([2, 7, 11, 15], 9))  # [0, 1]

Run Python in your browser

Write and execute code — numpy, pandas & scikit-learn included — right on the question page.

My Notes

Notes are saved in this browser only. Sign up to keep them in your account.

Related Questions (16)

Title	Category	Subcategory	Difficulty	Status
All Pairs	Programming	Array and List Processing	Easy	Example
All Permutations	Programming	Array and List Processing	Medium	Unlock with a membership
Arithmetic Mean	Programming	Array and List Processing	Hard	Unlock with a membership
Binary Search Tree (BST)	Programming	Array and List Processing	Hard	Unlock with a membership
Counting Inversions	Programming	Array and List Processing	Hard	Unlock with a membership
Crate Loading	Programming	Array and List Processing	Easy	Unlock with a membership
Find the Missing Number	Programming	Array and List Processing	Easy	Unlock with a membership
Finding the Largest Possible Number	Programming	Array and List Processing	Easy	Unlock with a membership
Longest Increasing Subsequence	Programming	Array and List Processing	Hard	Unlock with a membership
Majority Element	Programming	Array and List Processing	Medium	Unlock with a membership
Maximum Subarray Sum	Programming	Array and List Processing	Medium	Unlock with a membership
Search a Rotated Array	Programming	Array and List Processing	Medium	Unlock with a membership
Settling Array	Programming	Array and List Processing	Medium	Unlock with a membership
Sorting Without Sort()	Programming	Array and List Processing	Hard	Unlock with a membership
Subarray Sum Equals Zero	Programming	Array and List Processing	Medium	Unlock with a membership
Sudoku	Programming	Array and List Processing	Hard	Unlock with a membership

Discussion (1)

Please log in to see the discussion.

Back to all Questions

The Interview Guide for Quants and Traders

Longest Common Subsequence (LCS)

What do you think of this page?