alex
BAN USER- 0of 0 votes
AnswersRemove duplicates from a string inplace. The algorithm should be as efficient as possible.
- alex in India
I gave two approaches. First, the simple comparison O(n2) and second, sorting O(nlgon). But the interviewer did not seem satisfied.
Can someone please suggest a better algorithm?| Report Duplicate | Flag | PURGE
Microsoft Intern Algorithm
Reach to the middle element and reverse the linked list from the mid to the last element. Now compare the first half and second half (which was reversed earlier). If at any point the two elements don't match return false. Else return true. I have not considered the case for odd and even distinctly. A little modification might do.
- alex August 11, 2013Manache's algorithm is the best for it after certain modification. You can read it on leetcode.com Its an O(n) time algorithm.
However, a method that strikes easily is DP.It take O(n2) time and space.
let l[i][j] denote the length of palindrome from ith index to jth index.
using dynamic programming, we can easily solve this.
if x1[i]==x1[i+1], then l[i][i+1]=1
for j<=i, l[i][j]=0 since we are looking for even length palindrome.
otherwise, if x1[i]==x1[j] then l[i][j]=l[i+1][j-1]+2 if the inner substring i.e. x1[i+1][j-1] is a palindrome i.e. l[i][j]!=l[i+1][j-1]
if x1[i]!=x1[j] then l[i][j]=l[i+1][j-1]
int calculatePalindrome(){
int max=0;
for(int i=0;i<16;i++)
for(int j=0;j<16;j++)
if(j<=i)
l[i][j]=0;
for(int i=0;i<16;i++)
if(x1[i]==x1[i+1]){
l[i][i+1]=2;
max=2;
}
for(int j=1;j<16;j++)
for(int i=0;i<j;i++){
if(x1[i]==x1[j]&&l[i][j]!=l[i+1][j-1]){
l[i][j]=l[i+1][j-1]+2;
if(max<l[i][j]){
max=l[i][j];
cout<<"ij"<<i<<j<<endl; }
}
else l[i][j]=l[i+1][j-1];
}
return max;
}
Weigh 5 balls at a time. Select the faulty batch. Divide the 5 balls from the faulty batch into 2 group of two balls each. If none of them is faulty, the left out ball is faulty else, if one of the batches of 2 is faulty, compare the two balls again to find the faulty one!
So, its 3 comparisons at the most.
You will also need a hashset to keep a track of the values that you have already entered in the heap.
- alex September 14, 2013