Longest Common Subsequence

Image placeholder 9899

(This question has been seen in the interviews of the following companies: Google)

Given two two integer arrays. Find the longest common subsequence.
eg: a =[1 5 2 6 3 7], b = [5 6 7 1 2 3]. return [1 2 3] or [5 6 7]
Solution:

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;
    }



Get one-to-one training from Google Facebook engineers

Top-notch Professionals

Learn from Facebook and Google senior engineers interviewed 100+ candidates.
Most recent interview questions and system design topics gathered from aonecode alumnus.
One-to-one online classes. Get feedbacks from real interviewers.

Customized Private Class

Already a coding expert? - Advance straight to hard interview topics of your interest.
New to the ground? - Develop basic coding skills with your own designated mentor.
Days before interview? - Focus on most important problems in target company question bank.