Amazon Interview Question Software Engineers
Country: United States
Interview Type: Written Test
import sys
def make_palindrome(word):
orig_word = word
len_orig = len(orig_word)
index = 0
while index<len(orig_word):
palindrome = check_palindrome(word)
if not palindrome:
word = word[0:len(word)-index] + orig_word[index] + word[len(word)-index::]
palindrome = check_palindrome(word)
index = index + 1
else:
print word
return word
def check_palindrome(word):
if word == word[-1::-1]:
return True
else:
return False
if __name__ == "__main__":
make_palindrome(sys.argv[1])
Java Solution
public static String createPalindrome(String str){
if(isPalindrome(str)) return str;
StringBuilder sb = new StringBuilder();
for (char ch : str.toCharArray()) {
sb.append(ch);
sb.reverse();
if(isPalindrome(str+sb)) break;
sb.reverse();
}
return str+sb;
}
public static boolean isPalindrome(String s){
StringBuilder sb = new StringBuilder(s);
return s.equals(sb.reverse().toString());
}
We can do it in O(n).
Basically, having s and reverse(s), we need to find to find reverse(s) in s.
Example:
offset=0
tests
stset - no match
offset=1
tests
stset - no match
offset=1
tests
stset - match of size 3
So we take reverse(s[:-3]) and append it to the resulting string.
Here is code, matching is done using KMP
def get_prefix_string(s):
result = [0] * len(s)
for i, c in enumerate(s):
if i == 0:
continue
k = result[i - 1]
while True:
if s[i] == s[k]:
result[i] = k + 1
break
if not k:
break
k = result[k - 1]
return result
def shortest_palindrome(self, s):
seek_in = s[::-1]
prefix_string = get_prefix_string(s)
matched_length = 0
for compare_with in seek_in:
while True:
if s[matched_length] == compare_with:
matched_length += 1
break
if not matched_length:
break
matched_length = prefix_string[matched_length - 1]
return s[matched_length:][::-1] + s
c# implementation.
static private string MakePalindrome( string str ) {
var sb = new StringBuilder();
for ( int i = str.Length - 1; i >= 0; i-- ) {
sb.Append( str[ i ] );
}
var reverse = sb.ToString();
int maxCnt = 0;
// use KMP instead, I use simple brute force not to blow up the code
for ( int i = 0; i < str.Length; i++ ) {
if ( str[ i ] != reverse[ 0 ] ) { continue; }
int tmpI = i;
Func<int> f = () => tmpI - i;
while ( tmpI < str.Length && str[ tmpI ] == reverse[ f.Invoke() ] ) {
tmpI++;
}
if ( f.Invoke() > maxCnt ) { maxCnt = f.Invoke(); }
}
return str + reverse.Substring( maxCnt, reverse.Length - maxCnt );
}
Any string s can be made into a palindrome by reversing s and appending it to the end. It seems they don't want double ending letters though, so the last letter of s should be removed before (or after) reversing it. In haskell:
createPalindrome = ap (++) (tail . reverse)
I think you are missing the casses when you have something like 12343 and you only need to append 21 or 123432 and need to append 1.
What if you are trying to find the middle and keep checking values to the left and right if they match until there is a missmatch and concatenate what's left unchecked to the end of the string?
I think you're missing the cases when you have 12343 and you have to append 21 or
123432 and have to append only 1.
My solution would be to find the middle and try to check left and right until there's a missmatch. If I find a missmatch, it means the middle is incorrect so I increment it with 1 till I find the correct middle (both to the left and right I have the same values) or I hit the end (when none of the values match).
public class PalindromeMinString {
private static boolean isPalindrome(char[] s1, int newCharIndex) {
for (int i = 0; i < newCharIndex; i++) {
if (i == newCharIndex) {
break;
}
if (s1[i] == s1[newCharIndex--]) {
continue;
}
return false;
}
return true;
}
private static char[] shiftChar(char[] c1, char[] c2, int idx) {
int len = c1.length;
for (int i = idx; i >= 0; i--) {
c2[len++] = c1[i];
}
return c2;
}
private static int addCharsToStr(String s) {
char[] c1 = s.toCharArray();
char[] c2 = new char[c1.length * 2];
int len = c1.length;
for (int j = 0; j < s.length(); j++) {
c2[j] = c1[j];
}
if (isPalindrome(s.toCharArray(), s.length() - 1)) {
return -1;
}
int i = 0;
while (i < len) {
char[] c = shiftChar(c1, c2, i);
if (isPalindrome(c, len + (i))) {
return (len + i);
}
i++;
}
return -1;
}
public static void main(String[] args) {
String str = "test";
int i = addCharsToStr(str);
for (int j = i - str.length(); j >= 0; j--) {
System.out.print(str.toCharArray()[j]);
}
}
}
Java
public static String makePalindrome(String str) {
// test
// tset
// java
// avaj
// scala
// alacs
// dvd
// dvd
StringBuilder origin = new StringBuilder(str);
StringBuilder reversed = new StringBuilder(str).reverse();
if (reversed.toString().equals(str)) {
return str;
}
for (int i = 1; i < origin.length() - 1; i++) {
if (origin.substring(i).equals(reversed.substring(0, reversed.length() - i))) {
return origin.append(reversed.substring(reversed.length() - i)).toString();
}
}
return origin.append(reversed.substring(1)).toString();
}
//string s = "test";
string s = "abccdcc";
Console.WriteLine(string.Format("Palindrome of {0} is {1}", s, CompletePalindrome(s)));
public string CompletePalindrome(string s)
{
int minIndex = s.Length - 1;
for (int i = s.Length - 1; i > 0; i--)
{
int index = GetPalindrome(s, i, i);
if (index != -1 && index < minIndex)
minIndex = index;
index = GetPalindrome(s, i-1, i);
if (index != -1 && index < minIndex)
minIndex = index;
}
var sb = new StringBuilder();
sb.Append(s);
for (int i = minIndex - 1; i >= 0; i--)
sb.Append(s[i]);
return sb.ToString();
}
private int GetPalindrome(string s, int left, int right)
{
int n = 0;
while (left - n > 0 && right + n < s.Length && s[left - n] == s[right + n])
n++;
return (right + n == s.Length) ? left - n + 1 : -1;
}
Time complexity o(n) and space complexity max o(2) . Used extra for loops for display logic which may be avoided..
public class Palindrome {
char[] a={'r','a','b','c','p','p','q','x','q','p'};
public static void main(String[] args){
Palindrome pl = new Palindrome();
pl.getPalindrom();
}
public void getPalindrom(){
int pivot =searchPalindrome(a.length-1, 0, 0);
for(char c : a){
System.out.print(" "+c);
}
for(int i=pivot-1;i>=0;i--)
System.out.print(" "+a[i]);
}
public int searchPalindrome(int endLoc, int startLoc,int startPivot){
if(a[endLoc]==a[startLoc]){
if(endLoc==startLoc)
return startPivot;
else
return searchPalindrome(endLoc-1,startLoc+1,startPivot);
}
else{
if(startLoc!=(a.length-1))
return searchPalindrome(a.length-1,startPivot+1,startPivot+1);
else
return a.length-1;
}
}
}
public class Palindrome {
char[] a={'r','a','b','c','p','p','q','x','q','p'};
public static void main(String[] args){
Palindrome pl = new Palindrome();
pl.getPalindrom();
}
public void getPalindrom(){
int pivot =searchPalindrome(a.length-1, 0, 0);
for(char c : a){
System.out.print(" "+c);
}
for(int i=pivot-1;i>=0;i--)
System.out.print(" "+a[i]);
}
public int searchPalindrome(int endLoc, int startLoc,int startPivot){
if(a[endLoc]==a[startLoc]){
if(endLoc==startLoc)
return startPivot;
else
return searchPalindrome(endLoc-1,startLoc+1,startPivot);
}
else{
if(startLoc!=(a.length-1))
return searchPalindrome(a.length-1,startPivot+1,startPivot+1);
else
return a.length-1;
}
}
}
public class Palindrome {
char[] a={'r','a','b','c','p','p','q','x','q','p'};
public static void main(String[] args){
Palindrome pl = new Palindrome();
pl.getPalindrom();
}
public void getPalindrom(){
int pivot =searchPalindrome(a.length-1, 0, 0);
for(char c : a){
System.out.print(" "+c);
}
for(int i=pivot-1;i>=0;i--)
System.out.print(" "+a[i]);
}
public int searchPalindrome(int endLoc, int startLoc,int startPivot){
if(a[endLoc]==a[startLoc]){
if(endLoc==startLoc)
return startPivot;
else
return searchPalindrome(endLoc-1,startLoc+1,startPivot);
}
else{
if(startLoc!=(a.length-1))
return searchPalindrome(a.length-1,startPivot+1,startPivot+1);
else
return a.length-1;
}
}
}
space complexity -- O(2) max in case no palindrome
timecomplexity -- O(2n) maz in case no palindrome
correct me if m wrong above...
public class Palindrome {
//char[] a={'r','a','b','c','p','p','q','x','q','p'};
StringBuffer sb = new StringBuffer("harry");
public static void main(String[] args){
Palindrome pl = new Palindrome();
pl.getPalindrom();
}
public void getPalindrom(){
int pivot =searchPalindrome(sb.length()-1, 0, 0);
for(int i=pivot-1;i>=0;i--)
sb.append(sb.charAt(i));
System.out.println(sb);
}
public int searchPalindrome(int endLoc, int startLoc,int startPivot){
if(sb.charAt(endLoc)==sb.charAt(startLoc)){
if(endLoc==startLoc)
return startPivot;
else
return searchPalindrome(endLoc-1,startLoc+1,startPivot);
}
else{
if(startLoc!=(sb.length()-1))
return searchPalindrome(sb.length()-1,startPivot+1,startPivot+1);
else
return sb.length()-1;
}
}
}
O(n) Python
def checkPalindrome(string):
if string == string[::-1]:
return True
else:
return False
def makeMinimumPalindrome(string):
stack = []
index = 0
print string
while(index<len(string)):
if string[index] !=string[-1]:
stack.append(string[index])
else:
if checkPalindrome(string[index+1:-1]):
break
else:
stack.append(string[index])
index = index +1
pal = string
while(True):
if stack == []:
break
pal = pal + stack.pop()
print pal
if __name__ == '__main__':
makeMinimumPalindrome('satas')
{{
static String createPalindrome(String word){
String newWord = word;
//not the last char because it is same in palindrome
int index = word.length()-2;
while( !checkPalindrome(newWord) ){
newWord = newWord + word.charAt(index);
System.out.println("word: "+newWord);
index--;
}
return newWord;
}
private static boolean checkPalindrome(String word){
//reverse the word
//check if they are equal
StringBuilder str = new StringBuilder(word);
String reversedWord = str.reverse().toString();
if(reversedWord.equals(word)){
return true;
}
else{
return false;
}
}
}}
public class Solution
{
// arguments are passed using the text field below this editor
public static void main(String[] args)
{
System.out.println(createPalindrome("test"));
}
public static String createPalindrome(String str){
if(isPalindrome(str)) return str;
for(int i=1; i<str.length(); i++){
if(isPalindrome(str.substring(i))) {
StringBuilder sb = new StringBuilder(str.substring(0,i));
return str + sb.reverse().toString();
}
}
return "";
}
private static boolean isPalindrome(String str) {
if(str==null) return true;
int left = 0;
int right = str.length() - 1;
while (left <= right) {
if (str.charAt(left++) != str.charAt(right--)) return false;
}
return true;
}
}
Python
- Sharad Tulsyan December 19, 2015