CareerCup

static int[] maxLCS(int[] a, int[] b) {
        int[][] op = new int[a.length + 1][b.length + 1];
        for(int i = 1; i < a.length + 1; i++) {
            for(int j = 1 ;j < b.length + 1; j++) {
                if(a[i-1] == b[j-1]){
                    op[i][j] = op[i-1][j-1] + 1;
                }else {
                    op[i][j] = Math.max(op[i-1][j], op[i][j-1]);
                }
            }
        }
        int maxLen = op[a.length][b.length];
        int[] result = new int[maxLen];
        int ap = a.length;
        int bp = b.length;
        while(ap > 0 && bp > 0) {
            if(a[ap-1] == b[bp-1]) {
                result[maxLen-1] = a[ap-1];
                maxLen--;
                ap--;
                bp--;
            }else if(op[ap-1][bp] <= op[ap][bp-1]) {
                bp--;
            }else {
                ap--;
            }
        }
        return result;
    }

Looking for interview experience sharing and mentors?
Visit A++ Coding Bootcamp at aonecode.com.

Taught by experienced engineers/interviewers from FB, Google and Uber,
our ONE TO ONE courses cover everything in an interview including
latest interview questions sorted by companies,
SYSTEM DESIGN Courses (highly recommended for people interviewing with FLAG)
ALGORITHMS (conquer DP, Graph, Greed and other advanced algo problems),
and mock interviews.

Our students got offers from Google, Uber, Facebook, Amazon and other top companies after a few weeks of training.

Welcome to email us with any questions. Thanks for reading.

// JavaScript version
class LongestCommonSub {
    findSequence(str1, str2) {
        if(!str1 || !str2) throw Error('Invalid input');
        let result = [];
        let op = new Array(str1.length + 1); // the +1 is to store the 0 in the table

        // set the 2D arrays
        for(let i = 0; i <= str1.length; i++) {
            op[i] = new Array(str2.length + 1);
            for(let j = 0; j <= str2.length; j++) {
                op[i][j] = 0;
            }
        }

        for(let i = 1; i < str1.length + 1; i++) {
            for(let j = 1; j < str2.length + 1; j++) {
                if(str1[i-1] === str2[j-1]) {
                    op[i][j] = op[i-1][j-1] + 1;
                }else{
                    // We get the max value between top cell and left cell of current cell
                    op[i][j] = Math.max(op[i-1][j], op[i][j-1]);
                }
            }
        }
        // maxLen is the size of the maximum subsequence
        let maxLen = op[str1.length][str2.length];
        let ap = str1.length;
        let bp = str2.length;
        while(ap > 0 && bp > 0) {
            if(str1[ap-1] == str2[bp-1]) {
                result[maxLen-1] = str1[ap-1];
                maxLen--;
                ap--;
                bp--;
            }else if(op[ap-1][bp] <= op[ap][bp-1]) {
                bp--;
            }else{
                ap--;
            }
        }
        return result;
    }
}

@Test
public void test(){
int[] a = new int[]{1,5,2,6,3,7};
int[] b = new int[]{5,6,7,1,2,3,5};

longestSeq(a,b);

System.out.println();


int[] c = new int[]{1,5,2,6,3,4,7};
int[] d = new int[]{5,6,7,1,2,3,5,4};

longestSeq(c,d);
}

class Node{
int index;
int data;
List<Node> kids;

Node(int index, int data){
this.index = index;
this.data = data;
kids = new ArrayList<>();
}
}

private void longestSeq(int[] a, int[] b) {
Node root = seq(a, b);
printLongestPath(root, maxPath(root, 1), new ArrayList<>());

System.out.println();

root = seq(b,a);
printLongestPath(root, maxPath(root, 1), new ArrayList<>());
}

private int maxPath(Node n, int length){
if(n==null) return length;
int max = length;
for (Node kid: n.kids) {
int next = maxPath(kid, length+1);
if(next>max){
max = next;
}
}
return max;
}

private void printLongestPath(Node n, int max, List<Node> list){
if(n==null) return;
list.add(n);
if(list.size()>=max){
list.stream().filter(node-> node.data!=-100).forEach(node -> System.out.print(node.data+" "));
System.out.println();
}
for (Node kid: n.kids) {
printLongestPath(kid, max, list);
}
list.remove(n);
}





private Node seq(int[] a, int[] b) {
Node root = new Node(-100, -100);
for (int i = 0; i < a.length; i++) {
int j = find( a[i], b);
insert2Tree( root , j, a[i]);
}
return root;
}

private void insert2Tree(Node next, int index, int data) {
if(next.index < index) {
for (Node kid : next.kids) {
if(kid.index < index){
insert2Tree(kid, index, data);
return;
}
}
}
next.kids.add(new Node(index, data));

}

private int find(int element, int[] array) {
for (int i = 0 ; i < array.length; i++) {
if(element == array[i]){
return i;
}
}
return -1;
}

@Test
    public void test(){
        int[] a = new int[]{1,5,2,6,3,7};
        int[] b = new int[]{5,6,7,1,2,3,5};

        longestSeq(a,b);

        System.out.println();


        int[] c = new int[]{1,5,2,6,3,4,7};
        int[] d = new int[]{5,6,7,1,2,3,5,4};

        longestSeq(c,d);
    }

    class Node{
        int index;
        int data;
        List<Node> kids;

        Node(int index, int data){
            this.index = index;
            this.data = data;
            kids = new ArrayList<>();
        }
    }

    private void longestSeq(int[] a, int[] b) {
        Node root = seq(a, b);
        printLongestPath(root,  maxPath(root, 1), new ArrayList<>());

        System.out.println();

        root = seq(b,a);
        printLongestPath(root,  maxPath(root, 1), new ArrayList<>());
    }

    private int maxPath(Node n, int length){
        if(n==null) return length;
        int max = length;
        for (Node kid: n.kids) {
            int next = maxPath(kid, length+1);
            if(next>max){
                max = next;
            }
        }
        return max;
    }

    private void printLongestPath(Node n, int max, List<Node> list){
        if(n==null) return;
        list.add(n);
        if(list.size()>=max){
            list.stream().filter(node-> node.data!=-100).forEach(node -> System.out.print(node.data+" "));
            System.out.println();
        }
        for (Node kid: n.kids) {
            printLongestPath(kid, max, list);
        }
        list.remove(n);
    }





    private Node seq(int[] a, int[] b) {
        Node root = new Node(-100, -100);
        for (int i = 0; i < a.length; i++) {
            int j = find( a[i], b);
            insert2Tree( root , j, a[i]);
        }
        return root;
    }

    private void insert2Tree(Node next, int index, int data) {
        if(next.index < index) {
            for (Node kid : next.kids) {
                if(kid.index < index){
                    insert2Tree(kid, index, data);
                    return;
                }
            }
        }
        next.kids.add(new Node(index, data));

    }

    private int find(int element, int[] array) {
        for (int i = 0 ; i < array.length; i++) {
            if(element == array[i]){
                return i;
            }
        }
        return -1;
    }