## Directi Interview Question for Software Engineer / Developers

• 0

Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
4
of 4 vote

it equals with finding the longest common subsequence between one word (e.g. XAYBZBA) and its reverse (e.g. ABZBYAX).

Comment hidden because of low score. Click to expand.
-1
of 1 vote

@wangbingold..
your approach is correct but it requires a bit caution.
In standard LCS we assume a sequence is obtained by dropping letters from any string, while in palindrome we cannot drop characters.

So the optimum substructure equation will change a bit

Comment hidden because of low score. Click to expand.
2
of 2 vote

This problem can be solved by using dynamic programming
Let LP(i,j)= length of longest palindromic subsequence in array X from index i to j
LP(i,j) = LP(i+1,j-1) + 2 if X[i] = X[j]
= max [ LP(i+1,j), LP(i,j-1) ] if X[i]!=X[j]
= 1 if i=j
= 1 if i=j-1 and X[i]!=X[j]
=2 if i=j-1 and X[i] = X[j]

To understand this solution you can watch this wonderful video lecture

Comment hidden because of low score. Click to expand.
0
of 0 vote

this algo will only return length......can anyone post running code along with length and longest palindrome string?

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public int LongestPalindrome(char[] str, int i, int j)
{
if (str == null)
{
throw new ArgumentNullException("str");
}

if (str.Length == 0)
{
return 0;
}

if (str[i] == str[j] && i == j - 1)
{
return 2;
}

if (str[i] == str[j] && i == j)
{
return 1;
}

if (str[i] == str[j])
{
return this.LongestPalindrome(str, i + 1, j - 1) + 2;
}

return Math.Max(this.LongestPalindrome(str, i + 1, j), this.LongestPalindrome(str, i, j - 1));
}``````

Comment hidden because of low score. Click to expand.
0

cud u post the call to this method

if its:
test= "abcbba";
longestpalindrome(test, 0, test.length() - 1), it fails

Comment hidden because of low score. Click to expand.
0
of 0 vote

yeah it is easy in java...........i need c/c++ code

Comment hidden because of low score. Click to expand.
0

My code above can be easily implemented in C/C++.

Comment hidden because of low score. Click to expand.
0
of 0 vote

ur code only return max length but i need to return max palindrome string

Comment hidden because of low score. Click to expand.
0
of 0 vote

Let A be the input string and B is its reverse, then following DP algo can be used to solve this problem

``````public static void evaluate(String A, String B) {

int x = A.length() + 1;
int y = B.length() + 1;
int[][] M = new int[x][y];

for (int i = 1; i < x; i++) {
for (int j = 1; j < y; j++) {
if (A.charAt(i - 1) == B.charAt(j - 1))
M[i][j] = M[i - 1][j - 1] + 1;
else
M[i][j] = Math.max(M[i - 1][j], M[i][j - 1]);
}
}

Stack<Character> stack = new Stack<Character>();

int startX = x - 1;
int startY = y - 1;

while(startX >= 1 && startY >= 1) {
if(A.charAt(startX - 1) == B.charAt(startY - 1)) {

startX--;
startY--;
} else {
if(M[startX - 1][startY] >= M[startX][startY - 1])
startX--;
else
startY--;
}
}

while (!stack.isEmpty())
System.out.print(stack.pop());
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

geeksforgeeks(dot)org/dynamic-programming-set-12-longest-palindromic-subsequence/

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````static String LPS(int i, int j, String s) {
if (i > j) return "";
if (i == j) return s.charAt(i) + "";
if (s.charAt(i) == s.charAt(j))
return s.charAt(i) + LPS(i + 1, j - 1, s) + s.charAt(j);
String a = LPS(i + 1, j, s);
String b = LPS(i, j - 1, s);
return (a.length() > b.length()) ? a : b;
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.