CS Interview Question: Uncrossed Lines aka Longest Common Subsequence (LCS)
We write the integers of
B (in the order they are given) on two separate horizontal lines.
Now, we may draw connecting lines: a straight line connecting two numbers
B[j] such that:
A[i] == B[j];
- The line we draw does not intersect any other connecting (non-horizontal) line.
Note that a connecting lines cannot intersect even at the endpoints: each number can…