Linkedin Interview Question Software Engineer / Developers
Country: United States
Good try! It's dynamic programming.
Your implemtation is recursive, and it's much worse than O(n^2). Should use recursive with memorization, then can improve to O(n^2).
However, recursive memorization doesn't improve over bottom-up and it has costly overhead. Bottom-up is better in this problem.
As ninhnnsoc pointed out, your solution has a worse complexity than O(n^2). Your time complexity is exponential. The code with the memoization technique which produces O(n^2) complexity is,
public int dpLps(int[] a, int i, int j, Integer[][] lps) {
if (i > j)
return 0;
if (lps[i][j] == null) {
if (i == j)
lps[i][j] = 1;
else {
if (a[i] == a[j])
lps[i][j] = 2 + dpLps(a, i + 1, j - 1, lps);
else
lps[i][j] = Math.max(dpLps(a, i + 1, j, lps),
dpLps(a, i, j - 1, lps));
}
}
return lps[i][j];
}
you have to call the function as,
dpLps(a, 0, a.length - 1,new Integer[a.length][a.length])
Dynamic programming approach:
Define OPT function
OPT(i,j) be the maximum length of palindromes considering in the input array A from i to j.
Recursive formula is:
OPT(i,j) = 2 + OPT(i+1, j-1) if A[i] = A[j],
= max (OPT(i,j-1), OPT(i+1,j), otherwise.
Initial values:
OPT(i,i) =1 for all i.
The final answer is OPT(1,n).
How to calculate the table OPT:
Consider each length k of a range, k = 2..n
For each length k, calculate all OPT(i, i+k) entries using the previously calculated entries with shorter length.
This bottom-up implementation is O(n^2).
Thanks for the comment. I have modified my function. Let me know if there is further scope for improvement.
//Java version for DP as proposed above
public static void main(String[] args) {
int arr[] = new int[] { 4, 1, 2, 3, 4, 5, 6, 5, 4, 3, 4, 4, 4, 4, 4, 4,
4 };
int n = arr.length;
int[][] DP = new int[n + 1][n + 1];
int[][] backPointers = new int[n + 1][n + 1];
for (int i = 1; i < DP.length; i++) {
DP[i][i] = 1;
}
for (int l = 2; l <= n; l++) {
for (int i = 1; i <= n - l + 1; i++) {
int j = i + l - 1;
if (arr[i - 1] == arr[j - 1]) {
DP[i][j] = 2 + DP[i + 1][j - 1];
backPointers[i][j] = 1;
} else {
if (DP[i][j - 1] > DP[i + 1][j]) {
DP[i][j] = DP[i][j - 1];
} else {
DP[i][j] = DP[i + 1][j];
}
}
}
}
System.out.println("max palindrome length " + DP[1][n]);
}
2 + OPT(i+1, j-1) if A[i] = A[j] is incorrect it would fail a test case "HabobeH" - it will return 5 as the answer, while it should have been 3.
it is
2 + OPT(i+1, j-1) if j > i + 1 and A[i]=A[j] and OPT(i+1,j-1) == j-i-1)
2 if j == i + 1 and A[i]=A[j]
Initialise mem matrix of size*size to -1.
public static int DPmaxLengthPalindrome(int[] values, int i, int j, int[][] mem) {
if(j<=i) return j-i+1;
if(mem[i][j]!=-1) return mem[i][j];
if(values[i]==values[j]) return 2 + DPmaxLengthPalindrome(values, i+1, j-1, mem);
else return Math.max(DPmaxLengthPalindrome(values, i+1, j, mem), DPmaxLengthPalindrome(values, i, j-1, mem));
}
Use the values array and mem array as global, no need to pass them into the function. This can reduce overhead a lot in recursive call.
package com.company;
class PalindromSolution {
int [] values;
int [][] solved;
PalindromSolution(int [] values) {
this.values = values;
// provide correct order of execution
solved = new int[values.length][values.length];
}
public int solve() {
// solve problems in correct order
for (int len = 2; len <= values.length; ++len) {
for (int i = 0; i < values.length - len; ++i) {
solve(i, i+len-1);
}
}
// solve final problem
return solve(0, values.length-1);
}
private int solve(int i, int j) {
//check if indexes cross each other
//return 1 if index overlap for else condition below
//return 0 if index i<j for condition if below
if(j == i) return 1;
if (j < i) return 0;
if (solved[i][j] > 0) return solved[i][j];
int solution;
if (values[i] == values[j]) solution = 2 + solve(i+1,j-1);
else solution = Math.max(solve(i+1, j), solve(i, j-1));
solved[i][j] = solution;
return solution;
}
}
public class Main {
public static void main(String[] args) {
int arr[] = new int[] {4,1,2,3,4,5,6,5,4,3,4,4,4,4,4,4,4};
PalindromSolution pal = new PalindromSolution(arr);
System.out.println(pal.solve());
}
}
public class MaxLengthPalindrome {
public static int[] a= {4,12,3,4,5,6,4,3,4,4,4,4,4,4,4};
public static int maxLength(int i, int j) {
if (Math.abs(i-j)==1 || Math.abs(i-j)==0) return a[i]==a[j]?2:1;
System.out.println(i + " " + j);
if (a[i]==a[j])
return 2+maxLength(i+1,j-1);
return Math.max(maxLength(i+1,j), maxLength(i,j-1));
}
public static void main(String[] args) {
System.out.println(maxLength(0,a.length-1));
}
}
public class MaxLengthPalindrome {
public static int[] a= {4,12,3,4,5,6,4,3,4,4,4,4,4,4,4};
public static int maxLength(int i, int j) {
if (Math.abs(i-j)==1 || Math.abs(i-j)==0) return a[i]==a[j]?2:1;
System.out.println(i + " " + j);
if (a[i]==a[j])
return 2+maxLength(i+1,j-1);
return Math.max(maxLength(i+1,j), maxLength(i,j-1));
}
public static void main(String[] args) {
System.out.println(maxLength(0,a.length-1));
}
}
Algorithm: Iterating over array, detecting sequences of same value and for each sequence find longest palindrome around it in bottom->up method.
Comlexity: O(N^2) in worst case.
int FindMaxPalindromeSubseqLen(int arr[], int N)
{
int maxLen = 1;
for (int i=0; i<N-1; i++)
{
int j=i;
while (j<N && arr[j+1] == arr[i])
j++;
if (j>i)
{
int L = GetPalindromeLen(arr, N, i, j);
maxLen = max(maxLen, L);
i = j+1;
}
}
return maxLen;
}
int GetPalindromeLen(int arr[], int N, int s, int e)
{
while (s>0 && e<N-1 && arr[s-1] == arr[e+1])
{
s--;
e++;
}
return e-s+1;
}
C# solution using Manacher's algorithm O(n)
public static string preProcess(string s)
{
int n = s.Length;
if (n == 0)
return "^$";
string ret = "^";
for (int i = 0; i < n; i++)
ret += "#" + s.Substring(i, 1);
ret += "#$";
return ret;
}
public static string LPS(string s)
{
string T = preProcess(s);
int n = T.Length;
int[]P = new int[n];
int C = 0,
R = 0;
for (int i = 1; i < n - 1; i++)
{
int i_mirror = 2 * C - i; // equals to i' = C - (i-C)
P[i] = (R > i) ? Math.Min(R - i, P[i_mirror]) : 0;
// Attempt to expand palindrome centered at i
while (T[i + 1 + P[i]] == T[i - 1 - P[i]])
P[i]++;
// If palindrome centered at i expand past R,
// adjust center based on expanded palindrome.
if (i + P[i] > R) {
C = i;
R = i + P[i];
}
}
// Find the maximum element in P.
int maxLen = 0;
int centerIndex = 0;
for (int i = 1; i < n - 1; i++)
{
if (P[i] > maxLen) {
maxLen = P[i];
centerIndex = i;
}
}
return s.Substring((centerIndex - 1 - maxLen) / 2, maxLen);
}
int getPalin(vector<int>& num) {
int n = num.size();
if (n == 0) {
return 0;
}
vector<vector<bool> > palin;
for (int i = 0; i < n; ++i) {
cout << "n : " << n << "\n";
vector<bool> cur_vec(n+1,false);
cout << "cur vec size : " << cur_vec.size() << "\n";
cur_vec[1] = true;
palin.push_back(cur_vec);
}
int max = 1;
for (int l = 2; l <= n; ++l) {
for (int i = 0; i <= n-l; ++i) {
if (palin[i+1][l-2] == true && num[i] == num[i+l-1]) {
palin[i][l] = true;
max = l;
}
}
}
return max;
}
public class SequenceNumber {
static int[] count = {0,2,2,2};
static int[] positions;
static{
positions = new int[6+1];
}
public static void main(String[] args)
{
initSequence();
}
public static void initSequence()
{
generateSequence(positions,1,count);
}
private static void generateSequence(int[] positions, int index, int[] count) {
// System.out.println("------------generateSequence-------------------index = "+index);
// System.out.println("positions===");
// print(positions,-1);
// System.out.println("count====");
// print(count,-1);
// System.out.println("-------------------------");
//
if (index >= positions.length){
// System.out.println("####################");
print(positions,index);
// System.out.println("return^^^");
return;
}
if (allCountZeroorExceptOne(count,index,positions) )
{
// System.out.println("####################");
print(positions,index);
// System.out.println("return^^^");
return;
}
int[] newcount = new int[count.length];
for (int i = 1; i < count.length ; i++)
{
// System.out.println("index ="+i);
if (count[i] > 0 )
{
if (index > 1 )
{
//previous index should not be the same element
if ( positions[index-1] == i)
{
continue;
}
}
positions[index] = i;
// makeHigherPositionsZero(positions);
System.arraycopy( count, 0, newcount, 0, count.length );
newcount[i] = newcount[i] - 1;
generateSequence(positions,index+1,newcount);
}
}
// System.out.println("return****");
}
private static void print(int[] positions,int until) {
int newcount = until;
if (until == -1 )
{
newcount = positions.length;
}
for (int i= 1 ; i < newcount ; i++)
{
System.out.print(positions[i]+"");
}
System.out.print("\n");
}
private static boolean allCountZeroorExceptOne(int[] count,int index,int[] positions) {
int numberZero =0;
for (int i=1 ; i < count.length ; i++){
if (count[i]== 0 )
{
numberZero++;
}
}
//System.out.println("Number of zero="+numberZero);
if (numberZero == count.length-1 )
{
//System.out.println("Returning true");
return true;
}
// if (numberZero == count.length -2)
// {
//
// //which number does not have zero
// for (int k =0 ; k < count.length;k++)
// {
// if (count[k] != 0 )
// {
// if (index > 1 )
// {
// if ( positions[index-1] == k )
// {
// System.out.println("Returning true");
// return true;
// }
//
// }
//
// }
////
//// }
//
//
// }
return false;
}
}
public int findMaximumPalindromeLength(int[] number){
int[] noOfOccurences = new int[10];
int palindromeLength = 0;
for(int i=0;i<number.length;i++){
int num = number[i];
noOfOccurences[num] += 1;
}
for(int i=0 ; i<10; i++){
System.out.println("noOfOccurences of "+i+" is "+noOfOccurences[i]);
double division = (double)noOfOccurences[i]%2;
System.out.println("division value is "+division);
if(division>0){
palindromeLength += noOfOccurences[i]-1;
}else{
palindromeLength += noOfOccurences[i];
}
}
return palindromeLength+1;
}
O(n^2) complexity solution
- hsnaansh November 06, 2014public class Solution { public static void main(String[] args) { int arr[] = new int[] {4,1,2,3,4,5,6,5,4,3,4,4,4,4,4,4,4}; System.out.println(maxLengthPalindrome(arr, 0, arr.length-1)); } public static int maxLengthPalindrome(int[] values, int i, int j) { //check if indexes cross each other //return 1 if index overlap for else condition below //return 0 if index i<j for condition if below if(j<=i) return j-i+1; if(values[i]==values[j]) return 2 + maxLengthPalindrome(values, i+1, j-1); else return Math.max(maxLengthPalindrome(values, i+1, j), maxLengthPalindrome(values, i, j-1)); } }