Dynamic Programming Solution

HardPython00:00

Practice interviewer

In session

5 left

00:00

Your question is Dynamic Programming Solution. Start with the requirements on the right.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

You need to log in / sign up to run or submit.

Problem

Cohere Health needs to compare tokenized clinical information from two authorization workflows. Given two sequences of tokens, return their longest common subsequence, preserving the original order but not requiring the tokens to be contiguous.

A subsequence may skip tokens, but it cannot reorder them. If multiple longest subsequences exist, return any one of them.

Formal Specification

Implement longest_common_subsequence(tokens_a, tokens_b):

Input: two lists of strings, tokens_a and tokens_b.
Output: a list of strings representing one longest common subsequence.
The result must contain tokens from both inputs in the same relative order.

Constraints

0 <= len(tokens_a), len(tokens_b) <= 2000
Each token is a non-empty string of at most 50 characters
Token comparison is case-sensitive
Return an empty list when either input is empty
Aim for better than exponential time

Function Signature

def longest_common_subsequence(tokens_a, tokens_b):

Your solutionPython 3

You need to log in / sign up to run or submit.

Run your code to see test output