Interview Question
Software Engineer Interview

GoogleFind the minimum number required to insert into a word to make it a palindrome.
Tags:google, string, word, palindrome, brute force, algoirthm
AnswerAdd Tags
Interview Answers
8 Answers
▲
0
▼
This one was my last question and my hardest :( I was exhausted by this time and I probably had the hardest interviewer at the time too.
Anonymous on
▲
0
▼
This is basically a longest common subsequence problem. 1. Find the longest common subsequence between the string and its inverse using dynamic programming. O(n^2) 2. The answer is length of string minus the length of the longest common subsequence. Below is a C++ solution: #include #include #include using namespace std; int lcs(string str1, string str2) { auto matrix = vector>(str1.size() + 1, vector(str2.size() + 1, 0)); for(int i = 1; i matrix[i][j  1]) { matrix[i][j] = matrix[i  1][j]; result[i][j] = result[i  1][j]; } else { matrix[i][j] = matrix[i][j  1]; result[i][j] = result[i][j  1]; } } } cout << result[str1.size()][str2.size()] << endl; return matrix[str1.size()][str2.size()]; } int palinInsertions(string input) { string reverse; for(auto it = input.rbegin(); it != input.rend(); ++it) reverse += *it; cout << "input: " << input << " reverse: " << reverse << endl; return input.size()  lcs(input, reverse); } int main() { cout << palinInsertions("mhretaberra") << endl; // your code goes here return 0; }
Mhret on
▲
0
▼
public static int findMin(String str, int start, int end) { if(end <= start) { return 0; } if(str==null  str.length()==0) { return 0; } int a = Integer.MAX_VALUE; if(str.charAt(start)==str.charAt(end)) { a=findMin(str,start+1,end1); } int b= 1 + findMin(str,start+1,end); int c= 1 + findMin(str,start,end1); return Math.min(c, Math.min(a, b)); }
GReeky on
▲
0
▼
what about using hashset? public class Solution { public int minNumber (String s) { if (s == null  s.length() == 0) return 0; HashSet hs = new HashSet(); for (int i = 0; i < s.length(); i++) { if (!hs.contains(s.charAt(i))) hs.add(s.charAt(i)); else hs.remove(s.charAt(i)); } return hs.size() == 0 ? 0 : hs.size()  1; } }
Shirley on
▲
0
▼
Shirley.. for a Palindrome, occurencce of charachters at mirrored positions are required, pure saving of count is not helpful.. eg.. aabbcc... not a palindrome
Anonymous on
▲
0
▼
Yes... Shirley... it wont help know a palindorme.. works for an anagram
Prajakta on
▲
0
▼
" longest common subsequence" is not right. Str: abcdxfdcba So the shortest insert is just one character, either 'x' or 'f' in the middle. But if look for longest common sub sequence between 'Str1: abcdxfdcba' and 'Str2: abcdfxdcba', it is just 4 (abcd or dcba)
abc on
▲
0
▼
this is DP program Complexity: O(n^2), Memory: O(n^2); int dp(int l, int r) { if (l >= r) return 0; if (dp[l][r] != 1) return dp[l][r]; int ret = s.length(); if (s.charAt(l) == s.charAt(r)) ret = dp(l + 1, r  1); ret = Math.min(ret, dp(l + 1, r) + 1); ret = Math.min(ret, dp(l, r  1) + 1); return dp[l][r] = ret; }
Anonymous on
Add Answers or Comments
To comment on this, Sign In or Sign Up.