Interview Question

Software Engineer Interview

-

Find the minimum number required to insert into a word to make it a palindrome.

Tags:google, string, word, palindrome, brute force, algoirthm

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,end-1); } int b= 1 + findMin(str,start+1,end); int c= 1 + findMin(str,start,end-1); 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