Thursday, April 21, 2011

Generate Palindrome by Appending Characters

I was recently asked this programming puzzle at an interview:
Given a string as input, construct the smallest length palindrome from that string by adding 0 or more characters at  the end of the string.
So for input "abb" it would be "abba" with only one character added at end; for "abcdaad" it would be "abcdaadcba" with three characters added to the end. Of course in the worst case all n-1 characters have to be added as in "abbc" and the best case is if the string is already a palindrome like "abcba".
This is what I wrote: (note that the first question was about checking a string for palindrome, so I kind of thought it would be cool to reuse that piece of isPalin() function that I had already written)

Coming back home it occurred to me that I could have made the code smaller by writing an strrev() function to reverse a string and checking for palindrome with a combination of strcmp() and strrev(). This would furthermore allow me to reverse the beginning non-palindrome part of the input string, which I could directly copy to the end of the newly created palindrome string using strcpy(). Then I came up with this:

Unfortunately it seems that the length of the code did not change much. Or in other words, my innovative idea was no so cool after all.

PS: it seems that there is some issue with the terminating NULL charracter ('\0') of C and PasteBin. Please go through the RAW source code.

No comments:

Post a Comment

I'd love to hear from you !