Google Interview Question for Software Engineer / Developers

• 4

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

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

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

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

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

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

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

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

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)

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

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

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

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

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 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;
nonChanges = 0;
endPos--;
}
}
}``````

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

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.

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

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;

}``````

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

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)

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

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)

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

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

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

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

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.

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

}

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

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

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

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.

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

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

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

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.

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

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

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

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

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

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

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

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

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

abcb
abb

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

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

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

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

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

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

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

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

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.

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

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

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

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

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

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

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.

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

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

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.

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

What if the longest substring palindrome is of odd length?

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

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

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

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

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

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

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)]
if cache[start][end] < 0:
if string[start] == string[end]:
cache[start][end] = min(
cache[start][end],
1+min(
)
)
else:
cache[start][end] = 1+min(
return cache[start][end]

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

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)

print minPal(s)``````

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)

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

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

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

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

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{

StringTokenizer str = null;
PrintWriter out;

private String next() throws Exception{
if (str == null || !str.hasMoreElements())
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{
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();
}

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

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

return true;
}

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

tree[size] = new Node(0);

suff = size - 1;
}

class Node {
int next[];
int len;

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

public String toString() {
}
}

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

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

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

``````public void run() throws Exception{
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();
}``````

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

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

}

}
}
}``````

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

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

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

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 }

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 }

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.

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.

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

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;

}``````

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

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

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;

}

}``````

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.