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/