## Linkedin Interview Question for Software Engineers

Country: United States
Interview Type: Phone Interview

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

Dynamic programming, similar to LCS problem. Problem space is defined via maxSub[i,] maximum length of palindrom subset in sub array [i,j];

``````int 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];
}``````

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

I think one correction is require,

``````// other code
if (nums[i] == nums[j] && len == 2)
{
maxSub[i][j]  = 2;
}
else if (nums[i] == nums[j] )
{
maxSub[i][j] = Math.max(maxSub[i + 1][j - 1] + 2, maxSub[i][j]);
}
/// other code``````

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

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;
}``````

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

doesnot work for {1, 2, 1, 2} : maxLength is 4, but need to be 3.

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

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;
}``````

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

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)
}``````

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

``````// From ZoomBA , with Love
def len_of_max_subset_palindrome( a ){
m = mset( a )
has_odd = [ false ]
sum( m ) -> {
count = \$.o.value
even = ( 2 /? count ) // 2 divides value ?
if( !even ){
has_odd.0 = true
count -=1
}
count
} + (has_odd.0 ? 1:0 ) // adds 1 for the max odd guy
}``````

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

#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;
}

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

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;
}``````

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

``````// 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}));
}``````

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

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;
}
}}

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

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;
}``````

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

``````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;
}``````

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

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))``````

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

``````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){

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];
}``````

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

``````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;
}
}``````

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

What should be the expected result for - {1, 34, 43, 1}?
2 for {1, 1}
or 4 for the complete array?

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

``````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) {

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);
return;
}
}
}

if ((start == end-1) && nested
||
!nested && a.length == 1) {
}
}
}``````

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

``````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;
}``````

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.