Virtusa Polaris – Fresher Interview Questions with answers

   This blog explains about Virtusa Polaris – Fresher Interview Questions with answers . Some of them are discussed below : 

 _______________________________________________________

  LONGEST COMMON SEQUENCE

 Virtusa Core COE Version 1

Given two strings, ‘x’ and ‘y’ (1 <= lenth(x), length(y) <= 1000), find the length of their Longest Common Subsequence (LCS). The strings contains only lowercase letters.

You need to fill in a function that takes input two strings and sets the output variable to the length of their LCS.

Input

inputl the string ‘x’

input2: the string ‘y’

Output

Return the length of the LCS of ‘x’ and ‘y’

________________________________________________________________

/* A Naive recursive implementation of LCS problem in java*/

public class LongestCommonSubsequence

{

 

  /* Returns length of LCS for X[0..m-1], Y[0..n-1] */

  int lcs( char[] X, char[] Y, int m, int n )

  {

    if (m == 0 || n == 0)

      return 0;

    if (X[m-1] == Y[n-1])

      return 1 + lcs(X, Y, m-1, n-1);

    else

      return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n));

  }

 

  /* Utility function to get max of 2 integers */

  int max(int a, int b)

  {

    return (a > b)? a : b;

  }

 

  public static void main(String[] args)

  {

    LongestCommonSubsequence lcs = new LongestCommonSubsequence();

    String s1 = “aba”;

    String s2 = “ababa”;

 

    char[] X=s1.toCharArray();

    char[] Y=s2.toCharArray();

    int m = X.length;

    int n = Y.length;

 

    System.out.println(“Length of LCS is” + ” ” +

                                  lcs.lcs( X, Y, m, n ) );

  }

 

}

_________________________________________________________________

 

 LCS Problem Statement: 

2 ) Given two sequences, find the length of longest subsequence present in both of them. A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous.

For example, “abc”, “abg”, “bdf”, “aeg”, ‘”acefg”, .. etc are subsequences of “abcdefg”. So a string of length n has 2^n different possible subsequences.

Here is the source code of the Java Program to implement Longest Common Substring Algorithm. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

1. /**

2. ** Java Program to implement Longest Common Substring Algorithm

3.  **/

4.

 5. import java.io.BufferedReader;

6. import java.io.InputStreamReader;

7. import java.io.IOException;

8.  

9. /** Class  LongestCommonSubstring **/

10.          public class  LongestCommonSubstring

11.          {

12.              /** function lcs **/

13.              public String lcs(String str1, String str2)

14.              {

15.                  int l1 = str1.length();

16.                  int l2 = str2.length();

17.           

18.                  int[][] arr = new int[l1 + 1][l2 + 1];

19.                  int len = 0, pos = -1;

20.           

21.                  for (int x = 1; x < l1 + 1; x++)

22.                  {

23.                      for (int y = 1; y < l2 + 1; y++)

24.                      {

25.                          if (str1.charAt(x – 1) == str2.charAt(y – 1))

26.                          {

27.                                  arr[x][y] = arr[x – 1][y – 1] + 1;

28.                                  if (arr[x][y] > len)

29.                                  {

30.                                      len = arr[x][y];

31.                                      pos = x;

32.                                  }              

33.                          }

34.                          else

35.                              arr[x][y] = 0;

36.                      }

37.                  }       

38.           

39.                  return str1.substring(pos – len, pos);

40.              }

41.           

42.              /** Main Function **/

43.              public static void main(String[] args) throws IOException

44.              {   

45.                  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

46.                  System.out.println(“Longest Common Substring Algorithm Test\n”);

47.           

48.                  System.out.println(“\nEnter string 1”);

49.                  String str1 = br.readLine();

50.           

51.                  System.out.println(“\nEnter string 2”);

52.                  String str2 = br.readLine();

53.           

54.                  LongestCommonSubstring obj = new LongestCommonSubstring();

55.                  String result = obj.lcs(str1, str2);

56.           

57.                  System.out.println(“\nLongest Common Substring : “+ result);

58.              }

59.          }

_______________________________________________________________________

COURTESY  :

https://www.sanfoundry.com/java-program-longest-common-substring-algorithm/

https://www.geeksforgeeks.org/longest-common-subsequence-dp-4/

https://www.sanfoundry.com/java-program-generate-all-possible-combinations-given-list-numbers/

https://www.geeksforgeeks.org/printing-longest-common-subsequence/