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
Below is an inplace code:
#include<iostream>
#include<conio.h>
using namespace std;
void remDup(int a[],int n,int m){
int i=0,j=0,k=0;
while(i<n){
k=0;
if(i+1<n&&a[i]!=a[i+1]) a[j++]=a[i++]; //if it is not duplicated at all
while(i<n-1&&a[i]==a[i+1]&&k<m){ //copy all duplicates till k<m
a[j++]=a[i++];
k++;
}
if(k<m) a[j++]=a[i]; //copy the last element if k<m
while(i+1<n&&a[i]==a[i+1]) i++; //skip all the othr same elements
i++;
}
if(k<m&&a[i-1]!=a[i-2]) a[j++]=a[i-1]; //last element is copied if it can be taken
for(int i=0;i<j;i++) cout<<a[i]<<" ";
}
int main(){
int a[]={2,1,1,1,3,4,4,4,4,5,5,5,6,6,7,8};
int n=16,m=2;
remDup(a,n,m);
getch();
}
I don' t think this takes into encounter whether it forms an increasing sequence It just ensures hat the values taken are consequent. Ex:
5 6 7 4
1 7 6 2
will probably give 6 7 6 7 as ans, if I am interpreting your algorithm correctly. Kindly correct me if I am wrong.
I just read the definition of inplace. I always thought that no extra memory (except for small variables) can be used!
This seems valid except that in an inplace algorithm, input is replaced by output (ref Wikipedia). You are using O(n) memory for output. The original string needs to be modified into output.
Thanks anyways! :)
You need to check only for primes in 2 to k..You can use sieve method for that.
So space O(k) time O(kloglogk)..
However, if you check for every k, space=O(1), time is O(k). I don't undderstand which one of the two is better? Is mod operation costly so that we should use the first way, or should we go with the basic intuition of the second method?
string addBitStrings( string first, string second )
{
string result; // To store the sum bits
// make the lengths same before adding
int length = makeEqualLength(first, second);
int carry = 0; // Initialize carry
// Add all bits one by one
for (int i = length-1 ; i >= 0 ; i--)
{
int firstBit = first.at(i) - '0';
int secondBit = second.at(i) - '0';
// boolean expression for sum of 3 bits
int sum = (firstBit ^ secondBit ^ carry)+'0';
result = (char)sum + result;
// boolean expression for 3-bit addition
carry = (firstBit&secondBit) | (secondBit&carry) | (firstBit&carry);
}
// if overflow, then add a leading 1
if (carry) result = '1' + result;
return result;
}
//source geeksforgeeks
have used recursion here..can be improved by using dp.
#include<iostream>
#include<conio.h>
using namespace std;
int count(int n){
if(n<0) return 0;
if(n==0) return 1;
if(n==1) return 1;
if(n>25){
if(n==50) return count(25)+1;
return count(n-25)+count(25);
}
if(n>10){
if(n==25) return 1+count(n-10)+count(10);
if(n==20) return 1+count(10);
return count(n-10)+count(10);
}
if(n>5){
if(n==10) return 1+count(5);
return count(n-5)+count(5);
}
if(n>1){
if(n==5) return 1+count(n-1);
return count(n-1);
}
}
int main(){
int n;
cout<<"enter the value"<<endl;
cin>>n;
int c=count(n);
cout<<c;
getch();
return 0;
}
There is something wrong with the ques..
lets say u form some string which contains all the strings as its subsequences, bcdf
then abcdf is lexicographically smaller than bcdf...aabcdf is smaller than abcdf..and so on..
hence we can keep on adding number of a's to form smaller and smaller(lexicographically) strings.
Expand along every possible center n-1 spaces and n-2 characters and traverse along both directions to see if characters on both the sides are equal. Total time is O(n2).
Example a|b|c|b|a|d
space centers are given by | symbol and character centers will be b,c,b,a..
Another algorithm is also possible in O(n) time, called manacher's algorithm. It is available on leetcode.com
If the range is a to b, then generate a random no as
r=rand(b)%a+rand(b-a)
maintain a hash table to check that the no of times the value has been returned is less than n. Maintain the no as key and count as value.
So, if(count(r)<=arr[r]){
count(r)++;
return r;
}
Quick sort: When you don't need a stable sort and average case performance matters more than worst case performance. A quick sort is O(N log N) on average, O(N^2) in the worst case. A good implementation uses O(log N) auxiliary storage in the form of stack space for recursion.
Merge sort: When you need a stable, O(N log N) sort, this is about your only option. The only downsides to it are that it uses O(N) auxiliary space and has a slightly larger constant than a quick sort. There are some in-place merge sorts, but AFAIK they are all either not stable or worse than O(N log N). Even the O(N log N) in place sorts have so much larger a constant than the plain old merge sort that they're more theoretical curiosities than useful algorithms.
Heap sort: When you don't need a stable sort and you care more about worst case performance than average case performance. It's guaranteed to be O(N log N), and uses O(1) auxiliary space, meaning that you won't unexpectedly run out of heap or stack space on very large inputs.
Insertion sort: When N is guaranteed to be small, including as the base case of a quick sort or merge sort. While this is O(N^2), it has a very small constant and is a stable sort.
Bubble sort, selection sort: When you're doing something quick and dirty and for some reason you can't just use the standard library's sorting algorithm. The only advantage these have over insertion sort is being slightly easier to implement.
for i=0...n/2-1
tmp=array[i]
if tmp is a letter
continue // nothing to do, we have a letter already!
index=i
do
// we have the wrong think at index! Where is it supposed to be?
if (index is even) // the wrong thing is a letter
index=index/2
else // the wrong thing is a number
index=n/2+index/2
// we found where temp should go! Lets put it there!
// But we keep what was already there and look for its place next iteration
tmp2=array[index]
array[index]=tmp
tmp=tmp2
while index!=i
this looks like o(n2) but every element is moved only onnce. So, it is o(n).
for i=0...n/2-1
tmp=array[i]
if tmp is a letter
continue // nothing to do, we have a letter already!
index=i
do
// we have the wrong think at index! Where is it supposed to be?
if (index is even) // the wrong thing is a letter
index=index/2
else // the wrong thing is a number
index=n/2+index/2
// we found where temp should go! Lets put it there!
// But we keep what was already there and look for its place next iteration
tmp2=array[index]
array[index]=tmp
tmp=tmp2
while index!=i
It might look like O(n2) but it isnt..Each element is being moved only once..
Here is a code for the same.
- alex October 11, 2014