Groupon Interview Question for Software Engineer / Developers


Country: India
Interview Type: Phone Interview




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

The fact that we are only looking for even length palindrome makes it a lot easier.

For even length palindrome, the middle 2 characters are the same, so we can find all occasion and find the longest palindrome from there.
Record the max length and the start of of longest palindrome, and output using these data at the end.

char* leftmostOfPalindrome(char* r)
{
	char* l = r++;
	while(*(l-1) == *(r+1)){l--; r++;}
	return l;
}
char* longestPalindrome( char* s)
{
	char* cur = s, *cur_lt, *result, *palin;
	int l = 0, max_l = 0;
	while(*cur != '\0')
	{
		if(*cur == *(cur+1))
		{
			cur_lt = leftmostOfPalindrome(cur);
			l = (cur - cur_lt + 1) * 2;
			if(l > max_l){max_l = l; result = cur_lt;}
		}
		cur++;
	}
	palin = (char*) malloc (max_l+1);
	for(l = 0; l < max_l; l++) palin[l] = result[l];
	palin[l] = '\0'; //if max_l = 0, palin = "\0";
	return palin;
}

Code Tested for C++ using "testtsettesttset12312313", "1331", "11111111111111"

Worst case scenrio, "11111111111111", etc. It will have O(n^2). Barely any extra memory is allocated (you can't not use the malloc since you need to return it while not destroying the original data,

- Mo Lam May 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Manache's algorithm is the best for it after certain modification. You can read it on leetcode.com Its an O(n) time algorithm.

However, a method that strikes easily is DP.It take O(n2) time and space.

let l[i][j] denote the length of palindrome from ith index to jth index.
using dynamic programming, we can easily solve this.
if x1[i]==x1[i+1], then l[i][i+1]=1
for j<=i, l[i][j]=0 since we are looking for even length palindrome.
otherwise, if x1[i]==x1[j] then l[i][j]=l[i+1][j-1]+2 if the inner substring i.e. x1[i+1][j-1] is a palindrome i.e. l[i][j]!=l[i+1][j-1]
if x1[i]!=x1[j] then l[i][j]=l[i+1][j-1]


int calculatePalindrome(){
int max=0;
for(int i=0;i<16;i++)
for(int j=0;j<16;j++)
if(j<=i)
l[i][j]=0;
for(int i=0;i<16;i++)
if(x1[i]==x1[i+1]){
l[i][i+1]=2;
max=2;
}
for(int j=1;j<16;j++)
for(int i=0;i<j;i++){
if(x1[i]==x1[j]&&l[i][j]!=l[i+1][j-1]){

l[i][j]=l[i+1][j-1]+2;
if(max<l[i][j]){
max=l[i][j];
cout<<"ij"<<i<<j<<endl; }
}
else l[i][j]=l[i+1][j-1];
}
return max;
}

- alex May 10, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@alex: Nice algo but I think there is a typo.I think you meant in your comments
if x1[i]==x1[i+1], then l[i][i+1]=1 should be
if x1[i]==x1[i+1], then l[i][i+1]=2
no?

- aka January 21, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@alex it doesn't work.

#include <stdio.h>

#define SIZE(x1) sizeof x1/sizeof x1[0]
char x1[] = {"abedeedkbadddddo"};
int l[100][100] = {0};

int calculatePalindrome(){
        int max=0, i, j;
        for(i=0;i<SIZE(x1);i++)
                for(j=0;j<SIZE(x1);j++)
                        if(j<=i)
                                l[i][j]=0;
        for(i=0;i<SIZE(x1);i++)
                if(x1[i]==x1[i+1]){
                        l[i][i+1]=2;
                        max=2;
                }
        for(j=1;j<SIZE(x1);j++)
                for(i=0;i<j;i++){
                        if(x1[i]==x1[j]&&l[i][j]!=l[i+1][j-1]){
                                l[i][j]=l[i+1][j-1]+2;
                                if(max<l[i][j]){
                                        max=l[i][j];
                                }
                        }
                        else l[i][j]=l[i+1][j-1];
                }
        return max;
}

int main(void) {
        printf("%d", calculatePalindrome());
        return 0;
}

- aka January 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

@alex

Can you please explain your algorithm?

Below is the algorithm given by my friend.

Complexity: Time - O(n2), Space - O(1)

1) Have counters i and j point to first and second elements and mark them left and right of current largest palindrome.
2) Decrement left and increment right until left>0 and right<length of array and array[left]=array[right]
3) Store the longest palindrome and its count
4) Repeat the process by incrementing i and j till i points to length-1 and j points to length

- arun_lisieux May 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Check this out:

bool IsPalindrome(char str[], int startIndex, int endIndex)
{
	while (startIndex < endIndex)
	{
		if (str[startIndex] != str[endIndex])
		{
			return false;
		}
		++startIndex;
		--endIndex;
	}
	return true;
}

int LargestEvenPalin(char str[], int* startIndex)
{
	int len = strlen(str);
	bool bEven = (len % 2 == 0);
	int j = 0;
	int lenResult = 0;
	for(int i = 0; i < len - 1; ++i)
	{
		j = len - (bEven ? 1 : 2);
		if (j - i > lenResult)
		{
			for(; i < j; j -= 2)
			{
				if (j - i > lenResult)
				{
					if (IsPalindrome(str, i, j))
					{
						if ((j - i) > lenResult)
						{
							*startIndex = i;
							lenResult = j - i;
						}
					}
				}
				else
				{
					break;
				}
			}
		}
		else
		{
			break;
		}
		bEven = !bEven;
	}

	return lenResult + 1;
}

void RunDriver()
{
	//input
	char str[1000];
	int startIndex = -1;
	cin.getline(str, 1000);

	int resLen = LargestEvenPalin(str, &startIndex);
	if (resLen > 1)
	{
		char* resultString = str + startIndex;
		resultString[resLen] = '\0';
		cout << endl << "Longest possible even palindrome is: " << resultString << endl;
	}
	else
	{
		cout << endl << "No Longest possible even palindrome exists." << endl;
	}
}

0(n^2) if no palindrome exists... :)

- coding.arya May 12, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I tried to shorten LargestEvenPalin()...

int LargestEvenPalin(char str[], int* startIndex)
{
	int len = strlen(str);
	bool bEven = (len % 2 == 0);
	int lenResult = 0;
	int j = len - (bEven ? 1 : 2);
	for(int i = 0; (j - i > lenResult); ++i)
	{
		for(; (j - i > lenResult); j -= 2)
		{
			if (IsPalindrome(str, i, j))
			{
				*startIndex = i;
				lenResult = j - i;
			}
		}
		bEven = !bEven;
		j = len - (bEven ? 1 : 2);
	}

	return lenResult + 1;
}

Let me know if there is any issue in this code... :)

- coding.arya May 12, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

package com.test;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class StringPallindrome {

	/**
	 * @param args
	 * @throws IOException
	 */
	static int maxindex=-1,maxcount=0;
	public static void main(String[] args) throws IOException {
		//BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String s = "aba";
		findLargestOddPallindrome(s);
		findLargestEvenPallindrome(s);
		System.out.println("Largest Palindrome:::"+s.substring(maxindex,maxindex+maxcount));
		
	}

	private static void findLargestOddPallindrome(String s) {
		int j = 0,l, count, index = -1;
		char[] a = s.toCharArray();
		for (int i = 0; i < a.length - 1; i++) {
			l=i;
			j = i;
			count=1;
			while (l > 0 && j < a.length-1) {
				if (a[--l] == a[++j]) {
					count+=2;
					index = l;
				} else {
					break;
				}
			}
			if (count > maxcount) {
				maxcount = count;
				maxindex=index;
			}
		}
		

	}
	
	private static void findLargestEvenPallindrome(String s) {
		int j = 0,l, count, index = -1;
		char[] a = s.toCharArray();
		for (int i = 0; i < a.length - 1; i++) {
			l=i;
			j = i+1;
			count=2;
			while (l > 0 && j < a.length-1 && a[l]==a[j]) {
				if (a[--l] == a[++j]) {
					count+=2;
					index = l;
				} else {
					break;
				}
			}
			if (count > maxcount) {
				maxcount = count;
				maxindex=index;
			}
		}
		

	}
	
	

}

- Ashutosh May 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Brute force way.. no use of past result why do you have to proceed to the right if you already have a max pallindrome which is greater than the twice of the number of elements to the right of the center vertex.
n square times if the whole string is pallindrome and other optimization possible.

- murlikrishna.b June 20, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Using a stack, and set a flag to record whether this time pop some elements.
flag == 0 means there is no element being poped in prior loop,
flag == 1 means there is one element being poped in prior loog.
1. Input an element, when the stack is empty
1)if the element is equal to the stack[top]
2)if the element is not equal to the stack[top]
2. Input an element, when the stack is not empty

You can find the detail logic in the following code segments.
The time complexity is O(n).

int getLongestEvenPalindrome(char source[], int& end)
{
    int i = 0, top = -1;
    int max = -1, pop = 0;
    int tmp = 0, tend = 0;
    int len = strlen(source);
    char stack[MAX];

    for(i = 0; i < len; i++)
    {
        if(top > -1)
        {
            if(source[i] == stack[top])
            {
                if(pop == 0)
                {
                    pop = 1;
                    tmp = 2;
                    tend = i;
                }
                else if(pop == 1)
                {
                    tmp += 2;
                    tend = i;
                }
                top--;
            }
            else if(source[i] != stack[top])
            {
                if(pop == 1)
                {
                    top = -1;
                    pop = 0;
                    stack[++top] = source[i];

                    if(tmp > max)
                    {
                        max = tmp;
                        end = tend;
                    }
                    tmp = 0;
                }
                else if(pop == 0)
                {
                    stack[++top] = source[i];
                }
            }
        }
        else if(top == -1)
        {
            stack[++top] = source[i];
        }
    }
    if(tmp > max)
    {
        max = tmp;
        end = tend;
    }

    return max;
}

int main()
{
    int end = 0;
    char source[MAX] = "abcicbbcdefggfed";
    int max = getLongestEvenPalindrome(source, end);

    cout << max << endl;
    for(int i = max - 1; i >= 0; i--)
    {
        cout << source[end - i];
    }

    return 0;
}

- Gabriel May 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The below code is simple and has only O(n) time complexity.

def calculate_longest_palindrome(s, start, end, palindrome):
    new_palindrome = s[start : end]
    if not palindrome or len(new_palindrome) > len(palindrome):
        return new_palindrome
    return palindrome

def get_longest_even_palindrome(s):
    position      = -1
    in_palindrome = False
    palindrome    = None
    for i in range(0, len(s)):
        if position == -1:
            position = i
            continue
 
        if s[i] == s[position]:
            position      -= 1
            in_palindrome  = True
        else:
            if in_palindrome:
                palindrome    = calculate_longest_palindrome(s, position + 1, i, palindrome)
                in_palindrome = False
            position = i

    # Final check...
    if in_palindrome:
        palindrome = calculate_longest_palindrome(s, position + 1, len(s), palindrome)

    return palindrome

print get_longest_even_palindrome('abcicbbcdefggfed')

- Young K Bell May 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

O(n)? Are you sure? I am not used to this language that you use so I am having a very hard time to read, but I don't think this gives O(n).

What is the time complexity for "11111111...11111" ? It looks like O(n^2) to me.
In fact, I can't understand what it does for "111111111111111".

- Mo Lam May 15, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

if the length of the string is even,then the problem can be solved easily.
if the length of the string is odd,
eg.
cdefggfed

tansform to a another string #c#d#e#f#g#g#f#e#d#

- AangsEmail May 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.*;

public class SubString {
public static String s = "abcicbbcdefggfed ";
public static String out1;
public static int max=0;
public static void main(String args[]) {
int l = s.length();
LinkedList<String> l1 = new LinkedList();
for (int i = 0; i < l; i++) {
for (int j = 1; j <= l - i; j++) {
StringBuffer br = new StringBuffer();
br.append(s.substring(i, j + i));
if (s.substring(i, i + j).equals(br.reverse().toString())
&& s.substring(i, i + j).length() % 2 == 0) {
l1.add(s.substring(i,i+j));
}

}
}
if(l1.size()>0){
for(int k=0;k<l1.size()-1;k++){
if(l1.get(k).length()<l1.get(k+1).length()){ max=k+1;}
}
System.out.println(l1.get(max)); }
else {
System.out.println("i am sorry i cannot find even palindrome in given string tryother");
}
}
}

- Anonymous May 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

let the number of even palindromes = j and k be the length of the longest even palindrome.
The below code takes O(n) + O(jk)
and a space complexity of O(j) + O(j)

//Find the longest even palindrome in a string

#include<iostream>
using namespace std;

int main() {
    char string[50];
    int n,j,k;
    int arr[50], arrlen[50];
    cin>>string;
    for (n=0; string[n]!='\0'; n++);
    j=0;
    for (int i=0; i<n; i++) {
        if (string[i] == string[i+1]) {  
           arr[j]=i;
           j++;
        }
    }
    if (j>0) {
        for (int i=0; i<j; i++) {
            k=1;
            while (string[arr[i]-k] == string[arr[i]+1+k])
                  k++;
            arrlen[i] = k;
        }
        int maxLength = arrlen[0];
        k=0;
        for (int i=1; i<j; i++) {
            if (arrlen[i]>maxLength) {
               maxLength = arrlen[i];
               k = i;
             }
        }
        for (int i= (arr[k] - maxLength + 1); i < (arr[k] + 1 + maxLength); i++)
            cout<<string[i];
    }
    cout<<endl<<endl;
    system("pause");
    return 0;
}

- swapna.sugunendiran June 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Why can't we start finding from the middle and widen the string if pallindrome else shift the center element or vertex. We are interested in max Pallindrom so we can always decide if we really need to look further for a pallindrome or not if we use this approach.

- murlikrishna.b June 20, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Will this approach handle multiple palindromes in a given string?

- arun_lisieux June 25, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

A more readable solution that makes use of recursion. Hope it helps somebody out there

package algorithm.palyndrom;

public class LengthLongestPalyndrom {

    public int longestPalyndrom(char[] string) {
        return longestPalyndromLoop(string, 0);
    }


    private int longestPalyndromLoop(char[] string, int begin) {
        int nextCentre = findNextCentre(string, begin);
        if (nextCentre != -1) {
            return Math.max(calculatePalyndromLenght(string, nextCentre), longestPalyndromLoop(string, nextCentre + 1));
        }
        return 0;
    }

    private int findNextCentre(char[] string, int begin) {
        for (int i = begin; i < string.length - 1; i++) {
            if (string[i] == string[i + 1]) {
                return i;
            }
        }
        return -1;
    }

    private int calculatePalyndromLenght(char[] string, int centre) {
        int palindromeLength = 2;

        int leftIndex = centre - 1;
        int rightIndex = centre + 2;

        while (leftIndex >= 0 && rightIndex < string.length) {
            if (string[leftIndex] == string[rightIndex]) {
                palindromeLength += 2;
                leftIndex--;
                rightIndex++;
            } else {
                break;
            }
        }
        return palindromeLength;

    }


}

- Anonymous June 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think the task is to find longest palindrome from a given set of characters, that is the string input. The logic which I think is to be used is, that an even palindrome can be formed by even number of characters, like abba, or aabbaa . So my logic would be to first count the number of characters and their occurrence in the string and then find the characters with even number of occurrences. The length of the max string is sum of all even occurrences of Characters.

- Anonymous July 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Find the occurrence of repeating characters and expand from there. Keep track of the longest seen palindrome.

public static String longestEvenPalindrome(String s){
		if(s.length() == 0 || s.length() == 1){
			return "";
		}
		
		
		String longestSoFar = "";
		for(int i=1;i<s.length();i++){
			if(s.charAt(i) == s.charAt(i-1)){
				String temp = expand(s, i-1, i);
				if(temp.length() > longestSoFar.length()){
					longestSoFar = temp;
				}
			}
		}
		
		return longestSoFar;
	}

	private static String expand(String s, int i, int i2) {
		StringBuilder sb = new StringBuilder();
		while(i>=0 && i2<s.length()){
			if(s.charAt(i) == s.charAt(i2)){
				sb.insert(0, s.charAt(i));
				sb.append(s.charAt(i));
				i--; i2++;
			}else{
				break;
			}
		}
		return sb.toString();
	}

- Punit July 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is my solution. I have checked it. It works. Please do find the code below its written in c.

#include<stdio.h>
#include<string.h>

int main()
{
	char c[] = "abcicbbcdefggfed",*ptr = c,*c1,*c2,*prev,*str;
	int count,maxcount = 0;
	while(*ptr != '\0') {
		count = 0;
		if(*ptr == *(ptr+1)) {
			count = 2;
			c1 = ptr - 1;
			c2 = ptr + 2;
			while(*c1 == *c2) {
				count = count +2;
				prev = c1;
				c1--;
				c2++;
			}	
			if(count > maxcount) {
				maxcount = count;
				str = prev;
			}
		}
		ptr++;
	}
	printf("\n");/*lets print the biggest even palindrome*/
	while(maxcount != 0) {
		printf("%c",*str);
		str++;
		maxcount--;
	}
	printf("\n");
	return 0;
}

- agmegharaj November 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public String largestEvenPalindrome()
	{
		int low=0,high=0,count=0;
		//values for the highest length palindrome
		int pLow=0,pHigh=0,pHighestCount=0;
		for(int i=0;i<s.length()-1;i++)
		{
			//low and high correspond to the adjacent cells 
			low=i;
			high=i+1;
			count=0;
			while((low>=0)&&(high<=s.length()-1))
			{
				if(s.charAt(low)!=s.charAt(high))
					break;
				else
				{
					//if 2 adjacent cells have the same character, we move low and high 			//away from each other each time as long as there is a match
					low--;
					high++;
					count+=2;
				}
				if(count>pHighestCount)
				{
					pHighestCount=count;
					pLow=low+1;
					pHigh=high-1;
				}
			}
		}
		if(pHigh!=0)
			return s.substring(pLow, pHigh+1);
		else
			return null;

}

- GReeky January 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This will take O(n) time.

#include<iostream>
#include<string.h>
using namespace std;

string update_input(string s)
{
	int length=s.length();
	if(length==0)
		return "^$";
	string ret="^";
	for(int i=0;i<length;i++)
	{
		ret=ret+"#"+s.substr(i,1);
	}
	ret=ret+"#$";
	return ret;	
}

string process_input(string s)
{
string T=update_input(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;

p[i]=(R>i)?min(R-i,p[i_mirror]):0;

	while(T[i+1+p[i]]==T[i-1-p[i]])
		p[i]++;

	if(i+p[i]>R)
	{
		C=i;
		R=i+p[i];
	}

}
  int maxLen=0;
  int centerIndex=0;
  for(int i=1;i<n-1;i++) 
  {
    if(p[i]>maxLen) 
    {
	if(p[i]%2==0)//this if is only for printing even length palindrom
	{
	      maxLen=p[i];
	      centerIndex=i;
	}
    }
  }
  delete[] p;
  
  return s.substr((centerIndex - 1 - maxLen)/2, maxLen);

}




int main()
{
string input="zabbacabc";
string z=process_input(input);
cout<<z<<"\n";
return 0;
}

- himanshughadiya February 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String[] args) {
        System.out.println("The longest even palidrome is "
                + findLongestPalindrome("testtsettesttset12312313"));
    }

    private static String findLongestPalindrome(String string) {
        String palindrome = null;
        int counter = 0;

        int index = 0, maxCounter = -1;

        while (index >= 0) {
            counter = 0;
            string = string.substring(index);
            index = findDoubleLetter(string);
            counter = +2;
            if (index != -1) {
                int start = index - 2;
                int end = index + 1;
                while (start > 0 && end < string.length() - 1) {
                    if (string.charAt(start) == string.charAt(end)) {
                        counter += 2;
                        end++;
                        start--;
                    } else {
                        break;
                    }
                }
                if (counter > maxCounter) {
                    palindrome = string.substring(start, end + 1);
                    maxCounter = counter;
                }

            }
            if (index != -1) {
                index++;
            }
        }

        return palindrome;
    }

    private static int findDoubleLetter(String string) {
        for (int i = 0; i < string.length() - 1; i++) {
            if (string.charAt(i) == string.charAt(i + 1)) {
                return (i + 1);

            }
        }
        return -1;
    }

- Anonymous March 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

can anyone provide a simple algo for this, i don't want the code but just a blueprint.

- Batman August 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int findLongestPalindromeOfEvenLength() {
		int i = 0, j = 0, l = 0;
		int palStrLen = getPalIp().length();
		int newPalLen = 0, oldPalLen = 0;
		System.out.println("Length of the original string is " + palStrLen);
		l = palStrLen - 1;
		for(int k = 0;k<palStrLen;k++)
		{
			for (i = 0, j = l; i < j;) {
				if(isPalindrome(getPalIp(), i, j))
				{
					newPalLen = (j+1) - i;
					break;
				}
				else
				{
					i++;
					j = l;
				}
			}
			if((newPalLen > oldPalLen) && (newPalLen % 2 == 0)) //Omit %2 if the question is not for longest even palindrome
				oldPalLen = newPalLen;
			l--;
		}
		
		System.out.println("length of longest palindrome is "+oldPalLen);
		return 0;
	}
	
	public Boolean isPalindrome(String s, int i, int j)
	{
		while(i<=j)
		{
			if(s.charAt(i) == s.charAt(j))
			{
				i++; j--;
			}
			else return false;
		}
		return true;

}

- Anonymous September 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int findLongestPalindromeOfEvenLength() {
		int i = 0, j = 0, l = 0;
		int palStrLen = getPalIp().length();
		int newPalLen = 0, oldPalLen = 0;
		System.out.println("Length of the original string is " + palStrLen);
		l = palStrLen - 1;
		for(int k = 0;k<palStrLen;k++)
		{
			for (i = 0, j = l; i < j;) {
				if(isPalindrome(getPalIp(), i, j))
				{
					newPalLen = (j+1) - i;
					break;
				}
				else
				{
					i++;
					j = l;
				}
			}
			if((newPalLen > oldPalLen) && (newPalLen % 2 == 0)) //Omit %2 if the question is not for longest even palindrome
				oldPalLen = newPalLen;
			l--;
		}
		
		System.out.println("length of longest palindrome is "+oldPalLen);
		return 0;
	}
	
	public Boolean isPalindrome(String s, int i, int j)
	{
		while(i<=j)
		{
			if(s.charAt(i) == s.charAt(j))
			{
				i++; j--;
			}
			else return false;
		}
		return true;
	}

- Anonymous September 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int findLongestPalindromeOfEvenLength() {
		int i = 0, j = 0, l = 0;
		int palStrLen = getPalIp().length();
		int newPalLen = 0, oldPalLen = 0;
		System.out.println("Length of the original string is " + palStrLen);
		l = palStrLen - 1;
		for(int k = 0;k<palStrLen;k++)
		{
			for (i = 0, j = l; i < j;) {
				if(isPalindrome(getPalIp(), i, j))
				{
					newPalLen = (j+1) - i;
					break;
				}
				else
				{
					i++;
					j = l;
				}
			}
			if((newPalLen > oldPalLen) && (newPalLen % 2 == 0)) //Omit %2 if the question is not for longest even palindrome
				oldPalLen = newPalLen;
			l--;
		}
		
		System.out.println("length of longest palindrome is "+oldPalLen);
		return 0;
	}
	
	public Boolean isPalindrome(String s, int i, int j)
	{
		while(i<=j)
		{
			if(s.charAt(i) == s.charAt(j))
			{
				i++; j--;
			}
			else return false;
		}
		return true;
	}

- Anonymous September 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int findLongestPalindromeOfEvenLength() {
		int i = 0, j = 0, l = 0;
		int palStrLen = getPalIp().length();
		int newPalLen = 0, oldPalLen = 0;
		System.out.println("Length of the original string is " + palStrLen);
		l = palStrLen - 1;
		for(int k = 0;k<palStrLen;k++)
		{
			for (i = 0, j = l; i < j;) {
				if(isPalindrome(getPalIp(), i, j))
				{
					newPalLen = (j+1) - i;
					break;
				}
				else
				{
					i++;
					j = l;
				}
			}
			if((newPalLen > oldPalLen) && (newPalLen % 2 == 0)) //Omit %2 if the question is not for longest even palindrome
				oldPalLen = newPalLen;
			l--;
		}
		
		System.out.println("length of longest palindrome is "+oldPalLen);
		return 0;
	}
	
	public Boolean isPalindrome(String s, int i, int j)
	{
		while(i<=j)
		{
			if(s.charAt(i) == s.charAt(j))
			{
				i++; j--;
			}
			else return false;
		}
		return true;
	}

- Anonymous September 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int findLongestPalindromeOfEvenLength() {
		int i = 0, j = 0, l = 0;
		int palStrLen = getPalIp().length();
		int newPalLen = 0, oldPalLen = 0;
		System.out.println("Length of the original string is " + palStrLen);
		l = palStrLen - 1;
		for(int k = 0;k<palStrLen;k++)
		{
			for (i = 0, j = l; i < j;) {
				if(isPalindrome(getPalIp(), i, j))
				{
					newPalLen = (j+1) - i;
					break;
				}
				else
				{
					i++;
					j = l;
				}
			}
			if((newPalLen > oldPalLen) && (newPalLen % 2 == 0)) //Omit %2 if the question is not for longest even palindrome
				oldPalLen = newPalLen;
			l--;
		}
		
		System.out.println("length of longest palindrome is "+oldPalLen);
		return 0;
	}
	
	public Boolean isPalindrome(String s, int i, int j)
	{
		while(i<=j)
		{
			if(s.charAt(i) == s.charAt(j))
			{
				i++; j--;
			}
			else return false;
		}
		return true;
	}

- Anonymous September 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

How about just sorting the input string and then walk up the sorted string extracting pairs of chars and adding them to the beginning and end of a string, so build it from the inside out. If the problem were relaxed to allow odd, then first scan the sorted string for odd numbered set and use that as the middle of the result.

- dn May 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@dn

This algorithm will not work. The problem is to find existing palindromes from the input string. Not form palindromes from available characters?

Input: abab
should return null, but your code will return abba

- arun_lisieux May 13, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

ah,ok. Sorry misunderstood that then.

- dn May 13, 2013 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More