Google Interview Question for Software Engineer / Developers


Country: United States
Interview Type: Phone Interview




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

The thing is, the time complexity gets reduced by simply finding palindrome that start from first character. If we reduce the suffix tree implementation:

1. Create suffix tree from the reverse string (Ukkonen proved this is O(n))
2. Walk this tree from the beginning with the original string until there is path.

This is largest palindrome that starts with beginning. So you need to add [original string length] - [found polyndrome] characters in the front

- CT November 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I would slightly change the 2. point to: "until there is path and then take the last found node that led to the end". Because otherwise for example for ABDCBAF = it would be AB, even though it should be only A

- Demo April 24, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Here is psedocode mixed with code as solution.

Create new string that holds the reverse of given string and append the input string to it..

char [] newString = new char[s.length + (s.length - 1)]
char [] currentString = 'You' 

for (int i=0; i< currentString.length; i++)
{
	newstring[i] = 		currentString [currentString.length -i]
}

for (int i=currentString.length+1; i< newString.length ; i++)
{
	newstring[i] = 		currentString [i]
}


Console.WriteLine((string) newstring) ;

- Jai December 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Well, I believe the solution is very simple. You just need to compare suffixes of reverse string with prefixes of input string and find the longest in common. there is no need to construct a prefix/suffix tree (You can, but I didn't for sake of simplicity). Here is the code in Java, with O(n). Note that you can combine the last three loops in one, and avoid using additional space I used for tmp1[] and tmp2[].

public static int getMinCharToPalindrom2(String input){

		//Create the reverse of input string
		StringBuffer sb = new StringBuffer();
		for(int i=input.length()-1; i> -1; i--)
			sb.append(input.charAt(i));
		String reverse = sb.toString();
		String[] tmp1= new String[reverse.length()];
		String[] tmp2 = new String[input.length()];
		
		//Populate an array with suffixes of reverse string, such that array[0] contains the shortest suffix
		for(int i=reverse.length()-1; i>-1; i--)
			tmp1[reverse.length()-i-1] = reverse.substring(i,reverse.length());
		
		//Populate an array with prefixes of input string, such that array[0] contains the shortest prefix
		for(int i=0; i<input.length(); i++)
			tmp2[i] = input.substring(0,i+1);
		
		//Start from the end of arrays, and find the biggest sub-string in common
		for(int i=input.length()-1; i>-1; i--){
			if(tmp1[i].equals(tmp2[i])){
				return (2*input.length())-tmp1[i].length();
			}
		}
		return -1;
	}

- Reyhan JB July 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The solution is correct but complexity is not O(n), since you do comparison of two strings n times and the length of the strings varies from 1 to n. That gives O(n^2).

- Alex M. July 08, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

wrong answer for input "racexyzart"

- mrsurajpoudel.wordpress.com November 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

All you need it is to found the biggest such palindrone that s = prefix + palindrom.
You can do it in O(N^2), but it is better to use Manacher algorithm for finding all subpalindromes in O(N) and add reversed prefix to the and.

s = prefix + palindrome + reverse(prefix)

- glebstepanov1992 November 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You only need subpalindrom that start from the beginning of the string. It should simplify any subpolindrome finding technique.

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

BTW, the problem with Manacher it only searches for max subpalindrome. the one that start from the begining may not be the max.

- CT November 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

public int getShortestFrontModdedPalen(String str){
	if(str == null){
		throw new NullPointerException():
	}
	int definatelyAdd = 0;
	int nonChanges = 0;
	int endPos = str.length() -1;
	int frontPos = 0;
	while(endPos > frontPos){
		if(str.charAt(endPos) == str.charAt(frontPos)){
			nonChanges += 1;
			endPos--;
			frontPos++;
		}
		else{
			frontPos = 0;
			definatelyAdd+= 1 + nonChanges;
			nonChanges = 0;
			endPos--;
		}
	}
	return definatelyAdd + str.length();
}

- zortlord November 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

this code is wrong for case "aacecaaa",the right should be 9 for add 'a' in front.
but this code return 14 for add "aaacec" in front.

- Anonymous November 25, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

package google;

/**
 * 
 * @author nly22805
 *
 *  Given a string S, you are allowed to convert it to a palindrome by adding 0 or more characters in front of it. 
 *  Find the length of the shortest palindrome that you can create from S by applying the above transformation.
 */
public class Palindromes {

	private String str;
	
	public Palindromes(String s) {
		str = s;
	}
	
	private boolean isPalindrome(String s) {
		int start = (int)(s.length() / 2) - 1;
		
		for (int i = start, j = start + ((s.length() % 2 == 0) ? 1 : 2); (i >= 0) && (j < s.length()); i--, j++) {
			if (s.charAt(i) != s.charAt(j)) return false;
		}
		
		return true;
	}
	
	public String makePalindrome() {
		int index = 0;
		String subPalindrome = "";
		for (int i = 2; i <= str.length(); i++) {
			String subString = str.substring(0,  i);
			if (isPalindrome(subString)) {
				index = i;
				subPalindrome = subString;
				break;
			}
		}
		
		StringBuffer palindrome = new StringBuffer(str);
		if (index < str.length()) {
			for (int i = index; i < str.length(); i++) {
				palindrome.insert(0, str.charAt(i));
			}
		} 
		return palindrome.toString();
	}
	
	public static void main(String[] args) {
		Palindromes p = new Palindromes("racexyzart");
		System.out.println(p.makePalindrome());
	}
}

- Sorin November 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
 #include <list>
 
 using namespace std;

 
 void makePalindrome(char arr[],int len)
 {
	int front=0, end=len-1;
	char result[100];
	int i=0;
	while(front != end)
	{
		if( arr[front] == arr[end])
		{
			result[i]=arr[front];
			front++;
			end--;
			i++;
		}
		else
		{
			result[i]=arr[end];
			i++;
			end--;
		}
	}
	result[i]='\0';
	
	//printing the result for test
	i=0;
	while(result[i] != '\0')
		cout<<result[i++];
	i=0;
	while(arr[i] != '\0')
		cout<<arr[i++];
 }
 
 
 int main()
 {
	char a[]="racexyzart";
	makePalindrome(a,10);
	return 1;
	
 }

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

I look for the shortest Palindrome where the first char is the first char of String s. Then I find the length of the part of the string that isn't a palindrome and add it to the length of string s. This should be O(n) because the end pointer never resets

public int shortestPalindromePossible(String s)
	{
		if(s.length() == 0) return 0;
		int start = 0;
		int end = s.length() - 1;
		int realend = s.length() - 1;
		while(start < end) {
			if(s.charAt(start) == s.charAt(end))
			{
				start++;
				end--;
				continue;
			}
			if(start == 0) {
				end--;
			}
			start = 0;
			realend = end;
		}
		return (s.length() - (realend + 1)) + s.length();
	}

- lilzh4ng November 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

This isn't O(n). It is O(n^2). Consider this input: 10 1's a 2 then a 9 1s.

11111111112111111111

The algorithm first does 10 comparisons to check with pivot like below

1111111111 | 2111111111

Then 8 comparisons for this:

111111111 | 1211111111 1

Then 7 comparisons for this:

11111111 | 1121111111 11

And so on.

Generally

(n/2 + 1) * n/4

So O(n^2)

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

I'm confused about your explanation. I don't think that is what my algorithm is doing.

Let's use this example which is similar to yours: 3 1's a 2 then 2 1s.

111211

First you have a pointer at the first and last chars. This will be represented by brackets

[1]1121[1]

You compare these two chars. If they are the same, increment the first pointer and decrement the last pointer.

1[1]12[1]1

Compare again. Both are equal

11[1][2]11

These two chars are different. Now you set the start pointer back to the beginning and compare

[1]11[2]11

They aren't equal again, but with my logic you only decrement the last pointer

[1]1[1]211

These are the same pointers

1[[1]]1211

Now we know 111 is the smallest palindrome where the first char is the first char of the original string. Now we find the length of the string that isn't part of the palindrome and add it to the original length which will be your answer. This example answer is 9. (112111211)

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

Try 112111. The longest palindrome should be 11211 with length 5. The output of this algorithm is incorrect.

- wang891010 November 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

What? If the input is 112111 how can it be 5? The question states you can only added characters in front of it. The answer is 7: 1112111.

Am I going crazy? It's either I don't understand the question or no one here does

- lilzh4ng November 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

This can be done in O(n) time and O(n+e) space for the newly constructed string.
The input string might have palindrome as prefix or not.
palindrome prefix checking is simple and O(n).
If the input string does not have any palindrome as any part of prefix, we reverse the 1 to n-1 index string and append it at the front.
If there is any palindrome of size 2 or more as prefix, then the remaining string is reversed and appended at the front. that e is the part of the non-palindrome prefix. At the most, it can be n-1.

- docomp November 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

public class ShortestPalindrome {

    public int getShortestPalindromeLength(String str){
        if(str == null){
            throw new NullPointerException();
        }
        int count = 0;
        int endPos = str.length() -1;
        int frontPos = 0;
        StringBuilder sb = new StringBuilder();

        sb.append(str);

       while(!isPalindrome(sb.toString()) && frontPos < endPos){
           sb.insert(0,str.charAt(++frontPos));
           count++;
       }
      return count+ str.length();
    }

    private boolean isPalindrome(String str) {
        int endPos = str.length() -1;
        int frontPos = 0;
        while(endPos > frontPos){
            if(str.charAt(frontPos++) != str.charAt(endPos--)) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        ShortestPalindrome obj = new ShortestPalindrome();
        System.out.println(obj.getShortestPalindromeLength("racexyzart"));
    }

}

- beinrhythm November 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

"abaa" is wrong. It should be 5 but you output 7

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

I think for "abaa" the length should be 3, as we only need to append three more characters to the front to make this a palindrome.
"abaa" => "aab" + "abaa" which when combined is a palindrome.

- Rushabh December 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

No, for "abaa" you only need to append an "a" to the front, giving you "aabaa", which is a palindrome.

- rizhang December 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

public class ShortestPalindrome {

    public int getShortestPalindromeLength(String str){
        if(str == null){
            throw new NullPointerException();
        }
        int count = 0;
        int endPos = str.length() -1;
        int frontPos = 0;
        StringBuilder sb = new StringBuilder();

        sb.append(str);

       while(!isPalindrome(sb.toString()) && frontPos < endPos){
           sb.insert(0,str.charAt(++frontPos));
           count++;
       }
      return count+ str.length();
    }

    private boolean isPalindrome(String str) {
        int endPos = str.length() -1;
        int frontPos = 0;
        while(endPos > frontPos){
            if(str.charAt(frontPos++) != str.charAt(endPos--)) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        ShortestPalindrome obj = new ShortestPalindrome();
        System.out.println(obj.getShortestPalindromeLength("racexyzart"));
    }
}

- beinrhythm November 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Find the longest substring starting from the beginning that is a palindrome. The number of the left (non-palindrome) chars is the answer.

- danwu62 November 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static String makePalindrom(String s)
	{
		StringBuilder sb = new StringBuilder();
		
		for (int i = s.length() - 1; i > 0; i--) {
			// check if s[0..i] is a palindrom
			int j;
			for (j = 0; j < (i+1)/2; j++)
				if (s.charAt(j) != s.charAt(i-j))
					break;

			if (j == (i+1)/2)
				break; // [0..i] is a palindrom
			
			sb.append(s.charAt(i));
		}
		
		sb.append(s);
		return sb.toString();
	}

- erezef November 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 4 vote

Best solution here is to use a Knuth-Morris-Pratt algorithm. It runs in O(n) time, requires 2*n additional space and extremely fast and easy to code. The main idea is - we construct new string that contains our string + some symbol that can't be in our string, for instance '$' + reversed our string. After that we need to run KMP for that string to calculate prefix function. The answer is the length of our starting string minus prefix function value of the last element of the new string.

prefix function for every position i in the string shows the maximum length of prefix for the string s [0...i] that equals to suffix of the string s[0...i].
So if we construct new string in the way described above, prefix function for the last element will show the maximum size of the palindrome in the beginning of our string. All we have to do is to add in front of our string the rest of the characters.

int getPalindrome(string s) {
	int p[2000011], n = s.size();
	
	string current = s + '$';

	for (int i = 0; i < n; i++) {
		current += s[n - 1 - i];
	}

	p[0] = 0;
	for (int i = 1; i < 2 * n + 1; i++) {
		int j = p[i - 1];
		while (j > 0 && current[j] != current[i])
			j = p[j - 1];
		j += current[i] == current[j];
		p[i] = j;
	}
	return n - p[2 * n];
}

- Maxxx November 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

In this code I returned the number of characters you need to add. To get the final length of the palindrome:

return 2*n - p[2 * n];

- Maxxx November 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

What does 'p[2000011]' mean?
Very big size of int array?

- soodongStudying November 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes, I should have used a vector instead I guess.

- Maxxx November 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It seems your code is producing the wrong answers for :
abcb
abb

- Sauby December 08, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

In my view it should be failure value of last letter in the string given by rev(string)+string, for eg abcdc, so failure value for last letter for cdcbaabcdc is 3 so by answer is 5 -3

- Aditya June 21, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

looks like a dynamic programming question. you have few options:
The minimum number of insertions in the string str[l…..h] can be given as:
minInsertions(str[l+1…..h-1]) if str[l] is equal to str[h]
min(minInsertions(str[l…..h-1]), minInsertions(str[l+1…..h])) + 1 otherwise

here is a ruby answer:

def min_insert str, left=0, right=nil
  right ||= str.size-1
  return Float::INFINITY if left > right
  return 0 if left == right
  return 0 if left == right-1
  if str[left] == str[right] then min_insert(str, left+1, right-1) else [min_insert(str,left+1, right), min_insert(str,left,right-1)].min + 1 end
end

p min_insert 'geeks'
#return 3

- sagivo November 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

"aacecbaa" gives 1 but there is no way to add one character in front of "aacecbaa" to make it a palindrome.

- Anonymous February 04, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is a DP solution. O(n^2) time.
Given a string x1, x2, x3, ...,xn you can do the following:
Either add character at beginning, which will be xn
or pass if x1 == xn.
dp[1, n] = min (dp[2, n - 1] + COST_PASS, dp[1, n - 1] + COST_INSERT).
COST_INSERT = 1;
COST_PASS = 0 if the first and last characters of substring are equal, or INF.

Here is the code (it only returns the number of insertions. the total length will be length of string + number of insertions.).

public class MakePlindromic {
    private int[][] dp;
    private String x;
    public int Solve(String x) {
        this.x = x;
        dp = new int[x.length()][x.length()];
        for (int[] arr : dp) Arrays.fill(arr, -1);
        return makePalindromic(0, x.length() - 1);        
    }
    private int makePalindromic(int i, int j) {
        if (j <= 1) return 0;
        if (dp[i][j] == -1) {
            char first = x.charAt(i), last = x.charAt(j);
            int costInsert = 1, costPass = 1000000;
            if (first == last) {
                costPass = 0;
            }
            int pass = makePalindromic(i + 1, j - 1) + costPass;
            int ins = makePalindromic(i, j - 1) + costInsert;
            dp[i][j] = Math.min(pass, ins);
        }
        return dp[i][j];
    }
    public static void main(String[] args) {
        String test1 = "racexyzart";
        String test2 = "abddcdd";
        String test3 = "aacecaaa";
        MakePlindromic solve = new MakePlindromic();
        System.out.println(solve.Solve(test1));
        System.out.println(solve.Solve(test2));
        System.out.println(solve.Solve(test3));
    }
}
/// Returns: 5, 5, 1

- Ehsan November 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Change test3 in your test to "aacecbaa" instead of "aacecaaa" and it will still give result 1, which is incorrect - there is no way to add one character in front of "aacecbaa" to make it a palindrome.

- Anonymous February 04, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 4 vote

This is not as complex as you think. It is not the problem of adding characters to make a string a palindrome. It is much simpler. It is just adding characters only to the beginning of the string. Insertions are only in the beginning,
You just need to compare the last character to the first character. If these two are the same then you check if the rest of the string is a palindrome. If it is then no additions required.
Otherwise you add one to the count and check for the last but one character and so on.
Here is a recursive solution:

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

int is_pallin(char X[], int l, int h)
{
  while(l<h)
  {
    if(X[l] != X[h])
      return 0;
    ++l;
    --h;
  }
  return 1;
}

int no_pallin(char X[], int l, int h)
{
  if(l == h)
    return 0;
  if(X[l] == X[h])
    if(is_pallin(X, l+1, h-1))
      return 0;
  int t = (1 + no_pallin(X, l, h-1));
  return t;
}

int main()
{
  int n;
  char X[] = "aaacecaaa";
  n = strlen(X);
  printf("The result number of %s is : %d\n",X,no_pallin(X,0,n-1) + n);
  char Y[] = "acecaaa";
  n = strlen(Y);
  printf("The result number of %s is : %d\n",Y,no_pallin(Y,0,n-1) + n);
  char Z[] = "racexyzart";
  n = strlen(Z);
  printf("The result number of %s is : %d\n",Z,no_pallin(Z,0,n-1) + n);
}

This is an O(n) solution.
The output is:
The result number of aaacecaaa is : 9
The result number of acecaaa is : 9
The result number of racexyzart is : 19

- nhreddy@uci.edu November 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is not an O(n) solution. This is O(n^2) solution.

- Maxxx November 29, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Your solution fails for racexyzart, where the resultant string is trazyxcecxyzart whose length is 15.

- harishneit December 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

how do you get trazyxcecxyzart ? The problem says to add characters in FRONT of the string, not anywhere in the string.

So, racexyzart would be trazyxecaracexyzart = 19.

- Dan H December 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Please correct me if I am wrong:

public static int shortPalindrome(String s)
    {
        if(isPalindrome(s))
            return 0;
        else
        {
            int i = shortPalindrome(s.substring(1));
            int j=i+1;
            if(i!=0)//for prunning, if it is zero, nothing beats it
                j= s.length()-1;
            return 1+Math.min(i,j);
        }
    }

- Evan F December 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Start xorring the chats from left to right and note the longest string where it is 0. Then take the remainder of the string, reverse it and add it to the beginning.

- hellokitty November 30, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What if the longest substring palindrome is of odd length?

- mrsurajpoudel.wordpress.com November 30, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

good try, but order is important too. "abab" is not a palindrome but xor of all is 0

- hebele December 01, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class PalindromeFinder {
    public String findPalindrome(String s){
        if(s.isEmpty()) return s;
        int mid = s.length()/2;
        String left, right;
        while(mid>0){
            left = getReverse(s.substring(0, mid));
            right = s.substring(mid+1,s.length());
            if(right.length()>=left.length() && left.equals(right.substring(0,left.length()))){ //If the result is an odd length palindrome
                String append = right.substring(left.length(), right.length());
                return getReverse(append)+ s;
            } else if(s.charAt(mid-1)==s.charAt(mid)){ //if the result is an even length palindrome
                left = getReverse(s.substring(0, mid-1));
                if(left.equals(right.substring(0,left.length()))) {
                    String append = right.substring(left.length(), right.length());
                    return getReverse(append)+ s;
                }
            }
            mid--;
        }
        return getReverse(s.substring(1,s.length()))+s;
    }

    public String getReverse(String s){
        return new StringBuilder(s).reverse().toString();
    }
}

- darienurse December 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool isPalindrome(char* s, int n, int* i)
{
	if (n < 2)
		return true;
	int start = 0;
	int end = n - 1;
	while (start < end)
	{
		if (s[start] != s[end])
		{
			*i = start;
			return false;
		}
		start++;
		end--;
	}
	return true;
}
int sizeofPalindrome(char* s, int n)
{
	if (n < 2)
		return 0;

	int faultyIndex = 0;
	if (isPalindrome(s, n, &faultyIndex))
		return 0;
	else
		return n - faultyIndex;
}

- Rushabh Gosar December 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I might be thinking this wrong, but here's what I think..
If you have a palindrome string already. There's nothing there to do. If not, we find the first index of the non palindromic string, and we will have to append the rest of the string, as any other appends won't guarantee a palindromic string.

Please give me some edge cases to break my solution. It will help me improve and understand my fault (if any)

The above time is O(n) and just one traversal, without additional space. It just returns the length of the string that has to be prepended

- Rushabh Gosar December 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

The solution can be constructed thinking of the problem as

length(string, start_index, end_index)

and constructing the final solution from the subproblems.

A python implementation would be:

def finalLength(string):
    length = len(string)
    def genValue(i, j):
        if j < i:
            return -1
        elif j >= i:
            return 0
    cache = [[genValue(i, j) for i in xrange(length)] for j in xrange(length)]
    def additionCount(string, start, end):
        if cache[start][end] < 0:
            if string[start] == string[end]:
                cache[start][end] = additionCount(string, start+1, end-1)
                cache[start][end] = min(
                                        cache[start][end],
                                        1+min(
                                            additionCount(string, start+1, end),
                                            additionCount(string, start, end-1)
                                            )
                                        )
            else:
                cache[start][end] = 1+min(
                                        additionCount(string, start+1, end),
                                        additionCount(string, start, end-1))
        return cache[start][end]
    return additionCount(string, 0, length-1)

- harishneit December 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is a modified/simplified version of Maxxx's above. It contains two loops, but with worst case run time at O(n). The inner loop will not run more than n/2 times, so O(n + n/2) = O(n).
Ex. "aaaaaxyaaaaa".
When it gets to 'x' and 'y', it will be halfway through the string, and run n/2 times to find a new starting point.

Here's the code:

int FindPalindromeSize(string s)
{
	// n is the number of matching letters
	int n = 0;

	// r is the reverse string navigator
	for (int r = s.length() - 1; r >= 0; --r)
	{
		while(n > 0 && (s[r] != s[n]))
		{
			n--; // Keep subtracting n until we match again or reach the beginning again
		}
		// If we have a match, move to the next letter
		if (s[r] == s[n]) { n++; }
	}
	
	// original string, plus the difference of non-palindrome-y letters
	// s.length() + s.length() - n;
	return (s.length()*2) - n;
}

- Dan H December 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Python implementation

def isPalindrome(s):
	if len(s) < 2:
		return True
	if s[0] != s[-1]:
		return False
	elif s[0] == s[-1]:
		return isPalindrome(s[1:-1])

def longestPal(s):
	for i in range(len(s)):
		if isPalindrome(s[:len(s) - i]):
			return len(s) - i

def reverse(s):
	s_rev = ''
	for i in range(len(s)):
		s_rev += s[len(s) - 1 - i]
	return s_rev

def getRest(s):
	i = longestPal(s)
	rest = s[i:]
	return rest

def minPal(s):
	rest = getRest(s)
	rest = reverse(rest)
	s = rest + s
	return s, len(rest)

s = 'abccbadsf'
print minPal(s)

- cafertyildirim December 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Another Python Code:
def palindrome(string):
''' returns if a string is a palindrome or not'''
if len(string)%2==0:
return string[:len(string)/2]==string[len(string)/2:][::-1]
else:
return string[:len(string)/2]==string[(len(string)/2)+1:][::-1]

def makeAPalindrome(string):
if palindrome(string):
print '%s is a palindrome'%string
else:
temp=''
for i in range(len(string)):
newstr=string[:(len(string)-1)-i]
if palindrome(newstr):
temp=newstr
break
temp=string[(string.find(temp)+len(temp)):][::-1]+string
print 'By adding %d char(s), %s becomes a palindrome: %s'%(len(temp)-len(string),string,temp)

- Murali December 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Another Python Implementation:

def palindrome(string):
    ''' returns if a string is a palindrome or not'''
    if len(string)%2==0:
        return string[:len(string)/2]==string[len(string)/2:][::-1]
    else:
        return string[:len(string)/2]==string[(len(string)/2)+1:][::-1]

def makeAPalindrome(string):
    if palindrome(string):
        print '%s is a palindrome'%string
    else:
        temp=''
        for i in range(len(string)):
            newstr=string[:(len(string)-1)-i]
            if palindrome(newstr):
                temp=newstr
                break
        temp=string[(string.find(temp)+len(temp)):][::-1]+string
        print 'By adding %d char(s), %s becomes a palindrome: %s'%(len(temp)-len(string),string,temp)

- Murali December 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Solution
{
public int makeP(String s,int start,int end)
{
if(end<=start)//if the string has length less than or equal to 1
{
return 0;
}
//If the characters at 'start' and 'end' are the same increase 'start' by 1,
//decrease 'end' by 1, and make a recursive call.
if(s.charAt(start)==s.charAt(end))
{
return(makeP(s,++start,--end));
}
//If a mismatch between char at 'start' and char at 'end' occurrs at the terminal
//ends of the string (0 and s.length()-1).
if(start==0)
{
//Remove the character at s.length()-1
s=s.substring(start,end);
//Add 1 to the total count of characters to be replaced.
///make a recursive call with 'start'=0 and 'end'=s.length()-1
return 1 + makeP(s,0,s.length()-1);
}
//If character mismatch occurrs somewhere in the middle of the string
//(not at terminal ends).
//The number of characters to add is defined as:
// 1 Less than The number of characters before 'start'-- (start-1) +
//The number of characters from 'start' to the end of the string (s.length()-start)
return ((start-1)+(s.length()-start));
}
}

- divm01986 December 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This code has an O(n) time complexity and O(n) space complexity. Test cases with correct output include : ABBAT(returns 1), DSLJD(returns 4), MOM(returns 0), AKDIKA (returns 5).

- divm01986 December 17, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I found solution using palindromic tree data structure

import java.util.*;
import java.io.*;
	
public class Main{

    BufferedReader in;
    StringTokenizer str = null;
    PrintWriter out;

    private String next() throws Exception{
    	if (str == null || !str.hasMoreElements())
    	    str = new StringTokenizer(in.readLine());
    	return str.nextToken();
    }
	
    private int nextInt() throws Exception{
	   return Integer.parseInt(next());
    }
	
    char []s;
    int suff, n;
    int size = 0;
    Node []tree;

    final static int MAX = 100000;

    public void run() throws Exception{
    	in = new BufferedReader(new InputStreamReader(System.in));
    	out = new PrintWriter(System.out);

        StringBuilder sb = new StringBuilder();
        sb.append(next());
        sb.reverse();
        s = sb.toString().toCharArray();
        
        n = s.length;
        init();

        int len = tree[suff].len;
        out.println(n - len);
        out.close();
    }

    private boolean addLetter(int pos) {
        int cur = suff, curlen = -1;
        int to = s[pos] - 'a';

        while(true) {
            curlen = tree[cur].len;
            if (pos - curlen - 1 >= 0 && s[pos - curlen - 1] == s[pos]) {
                break;
            }
            cur = tree[cur].sufflink;
        }
        if (tree[cur].next[to] != -1) {
            suff = tree[cur].next[to];
            return false;
        }

        int v = size++;
        suff = v;
        tree[v] = new Node(tree[cur].len + 2);
        tree[cur].next[to] = v;

        if (tree[v].len == 1) {
            tree[v].sufflink = 1;
            return true;
        }

        while(true) {
            cur = tree[cur].sufflink;
            curlen = tree[cur].len;
            if (pos - curlen - 1 >= 0 && s[pos - curlen - 1] == s[pos]) {
                tree[v].sufflink = tree[cur].next[to];
                break;
            }
        }

        return true;
    }

    private void init() {
        tree = new Node[MAX];
        tree[size] = new Node(-1);
        tree[size].sufflink = size++;

        tree[size] = new Node(0);
        tree[size++].sufflink = 0;

        suff = size - 1;
    }

    class Node {
        int next[];
        int sufflink;
        int len;

        public Node(int len) {
            this.len = len;
            sufflink = -1;
            this.len = len;
            next = new int[26];
            Arrays.fill(next, -1);
        }

        public String toString() {
            return "[len=" + this.len + ", sufflink=" + this.sufflink + "]";
        }
    }

    public static void main(String args[]) throws Exception{
	   new Main().run();
    }
}

- darik December 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry, wrong body of algorithm. This is one is correct. O(n) - space, O(n) - complexity

public void run() throws Exception{
    	in = new BufferedReader(new InputStreamReader(System.in));
    	out = new PrintWriter(System.out);
        StringBuilder sb = new StringBuilder();
        sb.append(next());
        sb.reverse();
        s = sb.toString().toCharArray();
        System.out.println(Arrays.toString(s));
        n = s.length;
        init();

        for(int i = 0; i < n; ++i) addLetter(i);
        int len = tree[suff].len;
        out.println(n - len);
        out.close();
    }

- darik December 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

using System;

namespace CareerCup
{
    public class ShortestPalindrome
    {
        public int GetShortestPalindromeLength(string input)
        {
            if (string.IsNullOrEmpty(input))
            {
                throw new ArgumentNullException("input");
            }

            int leadingCharsNumber = 0;
            while (leadingCharsNumber < input.Length)
            {
                bool flag = true;
                for (int i = 0, j = input.Length - 1 - leadingCharsNumber;
                    i < j;
                    i++, j--)
                {
                    if (input[i] != input[j])
                    {
                        flag = false;
                        break;
                    }
                }

                if (flag)
                {
                    break;
                }

                leadingCharsNumber++;
            }

            return leadingCharsNumber + input.Length;
        }
    }
}

- stanislav.khalash January 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Start at the mid and check the two string from the mid ( [0---mid] vs [mid+1 ---input.Length]. if while checking starting the mid and we reach at the beginning , that mean we have the longest palindorm and fill the remaining from the second string to the front of the first string. Here is a c# code

string ConverteToPalindrom(string input)
{
int mid = (input.Length / 2);

for (int i = mid; i >= 0; i--)
{
int j = i, k = i + 1;
for (; j >= 0; j--, k++)
{
if (input[j] != input[k])
{
break;
}

}
if (j <= 0)
{
var temp = input;
while (k < temp.Length)
{
input = temp[k++] + input;
}
break;
}
}
return input;
}

- Enkoko January 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Algo:
First check if the string S is already a palindrome - mirror test (Ci==Cn-1-i, i=0 to n/2)
If Yes, the shortest length is S's length. i.e. n
If No, find the minimum addition to make it a palindrome:
Use the ith char as pivot (i = (n/2-1) to 0)
If S' left part is the mirror of S's right part with the ith char as pivot (Cj==Ci+i-j)
the minimum addition is: delta = (n-2*i-1) and thus the shortest length=n+delta=2*n-2*i-1
return the shortest length

Note: if want to ignore space in the string S, pre-process the S to make a new S' w/o space

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

Algo:
First check if the string S is already a palindrome - mirror test (Ci==Cn-1-i, i=0 to n/2)
If Yes, the shortest length is S's length. i.e. n
If No, find the minimum addition to make it a palindrome:
Use the ith char as pivot (i = (n/2-1) to 0)
If S' left part is the mirror of S's right part with the ith char as pivot (Cj==Ci+i-j)
the minimum addition is: delta = (n-2*i-1) and thus the shortest length=n+delta=2*n-2*i-1
return the shortest length

Note: if want to ignore space in the string S, pre-process the S to make a new S' w/o space

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

{Algo:
First check if the string S is already a palindrome - mirror test (Ci==Cn-1-i, i=0 to n/2)
If Yes, the shortest length is S's length. i.e. n
If No, find the minimum addition to make it a palindrome:
Use the ith char as pivot (i = (n/2-1) to 0)
If S' left part is the mirror of S's right part with the ith char as pivot (Cj==Ci+i-j)
the minimum addition is: delta = (n-2*i-1) and thus the shortest length=n+delta=2*n-2*i-1
return the shortest length

Note: if want to ignore space in the string S, pre-process the S to make a new S' w/o space }

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

{Algo:
First check if the string S is already a palindrome - mirror test (Ci==Cn-1-i, i=0 to n/2)
If Yes, the shortest length is S's length. i.e. n
If No, find the minimum addition to make it a palindrome:
Use the ith char as pivot (i = (n/2-1) to 0)
If S' left part is the mirror of S's right part with the ith char as pivot (Cj==Ci+i-j)
the minimum addition is: delta = (n-2*i-1) and thus the shortest length=n+delta=2*n-2*i-1
return the shortest length

Note: if want to ignore space in the string S, pre-process the S to make a new S' w/o space }

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

It's easy to get a O(n) solution. We only need to find the length of first k characters that it's already satisfy palindrome.
Just think about KMP.

Here is the solution:
1. String s = origin + reverse(origin);
2. make next[] array of s in KMP algorithm. Then next[s.length] will be the k.
3. return origin.length - k

For example:
The origin string is abacd, then s=abacddcaba, then next[s.length] will be 3.

- sakar2003 January 04, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

c#.

static private string MakePalindrome( string str ) {

    int index = 0;
    bool matchFound = true;
    for( int i = str.Length - 1; i >= 0; i-- ) {
        int k = i; int j = 0;
        while( k >= 0 ) {
            if( str[ j ] != str[ k ] ) {
                matchFound = false; break;
            }
            k--; j++;
        }
        if( matchFound ) { index = j; break; }
        matchFound = true;
    }
    var res = new StringBuilder();
    foreach ( var ch in str.Substring( index ).Reverse() ) {
        res.Append( ch );
    }
    return res.Append( str ).ToString();
}

- zr.roman January 15, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

#include<iostream>
 #include <list>
 
 using namespace std;

 
 void makePalindrome(char arr[],int len)
 {
	int front=0, end=len-1;
	char result[100];
	int i=0;
	while(front != end)
	{
		if( arr[front] == arr[end])
		{
			front++;
			end--;
		}
		else
		{
			result[i]=arr[end];
			i++;
			end--;
		}
	}
	result[i]='\0';
	
	//printing the result for test
	i=0;
	while(result[i] != '\0')
		cout<<result[i++];
	i=0;
	while(arr[i] != '\0')
		cout<<arr[i++];
 }
 
 
 int main()
 {
	char a[]="racecarart";
	makePalindrome(a,10);
	return 1;
	
 }

- Anonymous November 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

wrong answer for input "racexyzart"

- mrsurajpoudel.wordpress.com November 20, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Naive approach :( O(n^2)

public class PalindromeAddFront{
	
	public static void main(String[] args){
		String str = "racexyzart";
		int length = lengthToMakePalindrome(str);
		StringBuilder sbr = new StringBuilder(str.substring(str.length() - length));
		sbr.reverse().append(str);

		System.out.println(sbr);
	}	

	public static int lengthToMakePalindrome(String str){
		int i = 0, j = str.length() - 1;
		int count = 0;

		while(i < j){
			if(str.charAt(i) == str.charAt(j)){
				i++;
				j--;
			}else{
				j += (i - 1);
				i = 0;
				count++;
			}
		}

		return count;

	}

}

- mrsurajpoudel.wordpress.com November 20, 2014 | 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