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
Answer

Interview Answer

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.

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>(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 29 Nov 2014
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 3 Dec 2014
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 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 >= 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

Add Answers or Comments

To comment on this, Sign In or Sign Up.