Interview Question
Country: -
Have a pointer at the start of the string and one at the end of the string.
Check if chars at the start and end pointer are same, increment start pointer, decrement end pointer, if they are not same, insert char which is at start pointer at (end pointer + 1), and increment start pointer
Repeat the above, till both pointers meet.
find_min_insert(string)
if (length of string is zero or one)
return 0;
if (first char==last char)
return find_min_insert(string after removing first and last character)
return 1+min(find_min_insert(string after removing first character),find_min_insert(string after removing last character))
Here's a hint to compute min # of insertions to convert string S to palindrome:
find LCS of S and Reverse(S)
S = c a b c b a y c
T = Rev(S) = c y a b c b a c
LCS (S,T) = c a b c b a c
min # of insertions = |S| - LCS
Well, I was bit hectic last time. Hence, the example is kinda misleading. My solution finds longest palindromic subsequence, which is indeed min # of char deletion that make a string palindrome.
As the given problem is to insert, it'd be finding edit distance of S and reverse(S), considering only insertion is allowed.
I'm not here as mentor to guide some smart ass. So, I don't pay heed to someone who even doesn't have courage to have a nick... lurking here to seeking for READY-MADE solution, rather giving counter-example and challenging someone in constructive manner. Stop.
LOL. It was for your benefit (and mine, I was hoping to learn something from you). You might well be right, but it is not obvious that an LCS of S and Reverse(S) must be palindromic.
Here is one which seems to be a counter-example:
1 5 2 4 3 3 2 4 5 1
1 5 4 2 3 3 4 2 5 1
LCS = 1 5 2 3 3 4 5 1
Of course it might so happen that there is at least one subsequence with the same length as LCS which is palindromic, but a burden of proof of that is on you (and this is what I was hoping you will convince me of, but alas...).
BTW, LCS algorithm is Theta(n^2) I believe. There are O(n^2) algorithms to find the largest palindromic subsequence (quite similar to LCS, I grant you that), so we could use that instead of LCS which has this potential gotcha.
If all I wanted was the solution, I would not start with "You might want to revisit that hint"...
It might be a bit late, but, apologies to lol for any distress I might have caused you. You caught me in a bad mood, which was only made worse by your unwarranted comment about spoon feeding etc and the accusation of hiding behind anonymity was quite ridiculous.
Which company?
- Anonymous September 11, 2011