Google Interview Question: Find the minimum number requi... | Glassdoor.com.au

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

Interview Candidate on 23 Nov 2014
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&gt;(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 &lt;&lt; result[str1.size()][str2.size()] &lt;&lt; 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 &lt;&lt; "input: " &lt;&lt; input &lt;&lt; " reverse: " &lt;&lt; reverse &lt;&lt; endl;
return input.size() - lcs(input, reverse);
}

int main() {
cout &lt;&lt; palinInsertions("mhretaberra") &lt;&lt; endl;
return 0;
}

Mhret on 29 Nov 2014
0

public static int findMin(String str, int start, int end) {
if(end &lt;= 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 3 Dec 2014
0

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 &lt; s.length(); i++)
{
if (!hs.contains(s.charAt(i)))
else
hs.remove(s.charAt(i));
}
return hs.size() == 0 ? 0 : hs.size() - 1;

}

}

Shirley on 9 Dec 2014
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 20 Dec 2014
0

Yes... Shirley... it wont help know a palindorme.. works for an anagram

Prajakta on 20 Dec 2014
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 19 Jan 2015
0

this is DP program Complexity: O(n^2), Memory: O(n^2);

int dp(int l, int r) {
if (l &gt;= 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 11 Jun 2015