Linkedin Interview Question Software Engineers
Country: United States
Interview Type: Phone Interview
I may be missing something here but the question simply says that we need to find max length of subset which can form palindrome (it doesn't care about the order). As long as we have elements in pair, we can form a palindrome, with the exception of middle element.
Here's the java code. Please comment if I am missing something.
int maxPalindrome(int[] nums) {
int maxLength = 0;
int oddPresent = false; // Keeps track whether there is an element which is not in pair
HashMap<Integer, Integer> map = new HashMap<>();
for(int num: nums) {
if (map.containsKey(num)) {
int value = map.get(num);
map.put(num, value + 1);
} else {
map.put(num, 1);
}
}
for (int value: map.values()) {
if (value % 2) {
maxLength += 2;
} else {
oddPresent = true;
}
}
if (oddPresent) {
maxLength++;
}
return maxLength;
}
this is LCS problem, where in 2D array 1st dimension is a given array, and 2nd dimension is the same array but in reverse order.
c#.
private static int GetLengthOfMaximumPalindrome( int[] arrIn ) {
int[,] arr = new int[ arrIn.Length + 1, arrIn.Length + 1 ];
int maxVal = 0;
for ( int row = 0; row < arrIn.Length; row++ ) {
for ( int col = 0; col < arrIn.Length; col++ ) {
var leftCell = arr[ row + 1, col ];
var upCell = arr[ row, col + 1 ];
var leftDiagonalCell = arr[ row, col ];
if ( arrIn[ row ] != arrIn[ arrIn.Length - col - 1 ] ) {
arr[ row + 1, col + 1 ] = Math.Max( leftCell, upCell );
} else {
arr[ row + 1, col + 1 ] = leftDiagonalCell + 1;
}
var currVal = arr[ row + 1, col + 1 ];
if ( currVal > maxVal ) { maxVal = currVal; }
}
}
return maxVal;
}
Scala implementation:
def main(args: Array[String]) {
count(Array[Int](1, 2, 4, 1))
count(Array[Int](1, 2, 4, 1, 2))
count(Array[Int](1, 2, 4, 1, 2, 4))
count(Array[Int](1, 2, 4, 1, 2, 4, 4))
count(Array[Int](1, 2, 4, 1, 2, 4, 5))
}
def count(arr: Array[Int]) = {
val counts: Map[Int, Int] = arr
.toList
.groupBy(x => x)
.mapValues(_.size)
val evenValues = counts.map{case (x, size) => (x, size/2)}.values
val middle = counts.find(_._2 % 2 == 1).map(x => 1).getOrElse(0)
println(evenValues.sum * 2 + middle)
}
#include<iostream>
using namespace std;
int max(int x,int y)
{
return (x>y)?x:y;
}
int max_len(int *arr,int i,int j)
{
if(i==j)
return 1;
else if(arr[i]==arr[j]&&i+1==j)
return 2;
else if(arr[i]==arr[j])
return lps(arr,1,j-1)+2;
else
return max(lps(arr,i,j-1),lps(arr,i+1,j));
}
int main()
{
int *arr,n,i;
//cout<<"\nEnter n: ";
cin>>n;
arr=new int[n];
//cout<<"\nEnter array elements: ";
for(i=0;i<n;i++)
cin>>arr[i];
cout<<"\n"<<max_len(arr,0,n-1);
delete []arr;
return 0;
}
You can convert this problem to DP using array DP[n][n];
#include <stdio.h>
int max(int* arr, int i, int j)
{
if (i == j) {
return 1;
}
if (i > j) {
return 0;
}
int x = max(arr, i + 1, j);
int itr = 0;
for (itr = j; itr >= (i + 1); --itr) {
if (arr[itr] != arr[i]) continue;
int y = max(arr, i + 1, itr - 1) + 2;
if (y > x) {
x = y;
}
break;
}
return x;
}
int main()
{
int arr[100];
int n = 5;
int i = 0;
scanf("%d", &n);
for (i = 0; i < n; ++i) {
scanf("%d", &arr[i]);//populate(arr, &n);
}
printf("%d\n", max(arr, 0, n - 1));
return 0;
}
// similar problem of longest palindrome subsequence
public static int findMaxPalindromeSubSet(int[] input)
{
int n = input.length;
int T[][] = new int[n][n];
for(int i=0;i<input.length;i++)
T[i][i] = 1;
for(int len = 2;len<=input.length;len++)
{
for(int j=0;j<=input.length-len;j++)
{
int k = j+len-1;
if(input[j] == input[k] && len == 2) // same but only two length
T[j][k] = 2;
else if(input[j] == input[k]) // same
T[j][k] = Math.max(T[j+1][k-1] + 2 ,T[j][k]);
else // not same
T[j][k] = Math.max( T[j][k], Math.max(T[j+1][k], T[j][k-1]));
}
}
return T[0][n-1];
}
public static void main(String[] args)
{
System.out.println(findMaxPalindromeSubSet(new int[]{1,2,4,1}));
System.out.println(findMaxPalindromeSubSet(new int[]{1,1,1,2,0,1,1,1}));
System.out.println(findMaxPalindromeSubSet(new int[]{1,2,4,1,4,2,3,6,7,1}));
}
One more DP solution:
{{
#include <stdio.h>
#include <algorithm>
int cache[100][100] = {-1};
int maxPalindrome(int start, int end, int* array, int lenght)
{
int returnValue = 0;
if (start > end || lenght == 0)
{
returnValue = 0;
}
else if (start == end)
{
returnValue = 1;
}
else if (cache[start][end] != -1)
{
returnValue = cache[start][end];
}
else
{
returnValue = maxPalindrome(start + 1, end - 1, array, lenght);
returnValue = std::max(returnValue, maxPalindrome(start + 1, end, array, lenght));
returnValue = std::max(returnValue, maxPalindrome(start, end - 1, array, lenght));
returnValue += array[start] == array[end] ? 2 : 0;
cache[start][end] = returnValue;
}
return returnValue;
}
int main(int argc, const char * argv[])
{
memset(cache, -1, sizeof(cache[0][0]) * 100 * 100);
int array[] = {1, 2, 4, 3};
int lenght = sizeof(array) / sizeof(int);
printf("%d\n", maxPalindrome(0, lenght - 1, array, lenght));
return 0;
}
}}
This is exactly the solution I came up. I don't see need of DP solution here.
One comment when count per char is more than 2, say 4 or 5.
There are 2 cases, either count is odd or even.
If even add entire count and not just 2, if odd add even number upto that odd number.
if (value >= 2) {
if ((value % 2) == 0) {
maxLength += value;
} else {
oddPresent = true;
maxLength += ((value / 2) * 2);
}
} else if (value == 1) {
oddPresent = true;
}
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;
}
This is my code in Python, it took me awhile but it seems to work:
def longest_pal(arr, val=0):
if len(arr)==0:
return val
if len(arr)==1:
val+=1
return val
if len(arr)==2:
if arr[0]==arr[1]:
val+=2
else:
val+=1
return val
else:
if arr[0]==arr[len(arr)-1]:
val+=2
arr=arr[1:len(arr)-1]
return longest_pal(arr, val)
return max(longest_pal(arr[:len(arr)-1], val), longest_pal(arr[1:], val))
public int len(int[] str){
var mat = new int[str.Length,str.Length];
for(int i = 0 ; i <= str.Length-1;i++)
mat[i,i] = 1;
var win = 2;
while(win <= str.Length){
//start with length 2
for(int i = 0; i <= str.Length - win; i++ ) {
var j = i + (win-1);
if(i == j){
mat[i,j] = 1;
}
else if(str[i] == str[j]){
if( Math.Abs( i - j ) == 1)
mat[i,j] = 2;
else{
mat[i,j] = 2 + mat[i+1,j-1];
}
}else{
mat[i,j] = Math.Max( mat[i,j-1] , mat[i+1,j]);
}
}
++win;
}
return mat[0,str.Length-1];
}
public class MaxPalindrome {
public static void main(String args[]){
System.out.println(maxPalindrome(new int[]{1, 2, 2, 1, 2, 2, 1}));
}
static int maxPalindrome(int[] nums) {
int maxLength = 0;
boolean oddPresent = false; // Keeps track whether there is an element which is not in pair
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for(int num: nums) {
if (map.containsKey(num)) {
int value = map.get(num);
map.put(num, value + 1);
} else {
map.put(num, 1);
}
}
for (int value: map.values()) {
if (value % 2 == 0) {
maxLength += value;
} else {
if(value != 1){
maxLength += value-1;
}
oddPresent = true;
}
}
if (oddPresent) {
maxLength++;
}
return maxLength;
}
}
public class MaximumPalindromeInArray {
public static void main(String[] args) {
int[] a0 = new int[] {};
int[] a1 = new int[] {1};
int[] a2 = new int[] {1, 1};
int[] a21 = new int[] {1, 2};
int[] a3 = new int[] {1, 2, 1};
int[] a31 = new int[] {0, 1, 1};
int[] a32 = new int[] {1, 1, 0};
int[] a33 = new int[] {2, 1, 0};
int[] a41 = new int[] {1, 2, 3, 2};
int[] a5 = new int[] {2, 3, 3, 2, 2};
int[] a51 = new int[] {2, 3, 3, 1, 2};
System.out.println(maxPalindrome(a0));
System.out.println(maxPalindrome(a1));
System.out.println(maxPalindrome(a2));
System.out.println(maxPalindrome(a21));
System.out.println(maxPalindrome(a3));
System.out.println(maxPalindrome(a31));
System.out.println(maxPalindrome(a32));
System.out.println(maxPalindrome(a33));
System.out.println(maxPalindrome(a41));
System.out.println(maxPalindrome(a5));
System.out.println(maxPalindrome(a51));
}
private static LinkedList<Integer> maxPalindrome(int[] a) {
LinkedList<Integer> result = new LinkedList<Integer>();
maxPalindrome(0, a.length, a, result, false);
return result;
}
private static void maxPalindrome(int start, int end, int[] a, LinkedList<Integer> l, boolean nested) {
for (int i = start; i < end; i++) {
for (int j = end-1; j > i; j--) {
if (a[j] == a[i]) {
maxPalindrome(i+1, j, a, l, true);
l.add(0, a[i]);
l.add(a[i]);
return;
}
}
}
if ((start == end-1) && nested
||
!nested && a.length == 1) {
l.add(a[start]);
}
}
}
int GetClosest(char look, std::string sequence, int initial, int increment)
{
int limit = increment > 0 ? sequence.size() : -1;
for (int i=initial; i != limit; i+=increment)
{
if (sequence[i] == look)
{
return i;
}
}
// It should never get here since it should find the original at least.
return -1;
}
std::string FindLongPalindromicSubSequence(std::string sequence)
{
std::string palindrome;
int start_i = 0;
int end_i = sequence.size() -1;
while (start_i <= end_i)
{
if (sequence[start_i] == sequence[end_i])
{
std::string character = sequence.substr(start_i, 1);
if (start_i != end_i)
{
palindrome.insert(palindrome.size()/2, character);
palindrome.insert(palindrome.size()/2, character);
}
else
{
palindrome.insert(palindrome.size()/2, character);
}
start_i++;
end_i--;
}
int index_from_end = GetClosest(sequence[start_i], sequence, end_i, -1);
int index_from_start = GetClosest(sequence[end_i], sequence, start_i, 1);
if ((index_from_start - start_i) > (end_i - index_from_end))
{
end_i = index_from_end;
}
else
{
start_i = index_from_start;
}
}
return palindrome;
}
Dynamic programming, similar to LCS problem. Problem space is defined via maxSub[i,] maximum length of palindrom subset in sub array [i,j];
- EPavlova January 27, 2016int maxPlaindromSubseq(int[] nums) { int maxSub[][] = new int[nums.length][nums.length]; for (int i = 0; i < nums.length; i++ ) { maxSub[i][i] = 1; } for (int len = 2; len <= nums.length; len++) { for (int i = 0; i <=nums.length - len; i++ ) { int j = i + len - 1; if (nums[i] == nums[j]) { maxSub[i][j] = Math.max(maxSub[i + 1][j - 1] + 2, maxSub[i][j]); } else { maxSub[i][j] = Math.max(maxSub[i][j - 1] , maxSub[i][j]); maxSub[i][j] = Math.max(maxSub[i+1][j], maxSub[i][j]); } } } return maxSub[0][nums.length - 1]; }