technoapurva
BAN USERIt is impossible to solve this problem in O(n) time as the number of solutions is of the exponential order.
- technoapurva September 24, 2015Here is an algorithm that takes O(1) space and O(N) time and meets all these weird requirements.
1. take tow variable: index=-1,value=-1.
2. Imp: Traverse the array from i=0 to n-1. If a[i]==i or a[i]==i+n then move ahead else there will be the following cases:
(i) If a[a[i]] ! =a[i] && a[a[i]]!=a[i]+n : Swap a[i] and a[a[i]].
(ii) else if index==-1 : index=i; value=a[i] and a[a[i]]=value
{iii) else a[a[i]]=value;
3. Now again traverse the array and do the following:
(i) If a[i] == value and i==index: Print i and i+n.
(ii) else If a[i] != value && a[i]==i : Print i+n
(iii) else If a[i] != value && a[i]==i+n : Print i
(iv) else If a[i] !=value : Print i and i+n
(v) else if a[i]==value: continue.
@zortlord: This solution consumes O(1) memory as I am storing the results in the same array. However, if there was a condition that we cannot modify the input array then it can be done in O(m) space as we just need to store the result of the most recent column.
- technoapurva September 23, 2015Dynamic programming O(mn) time.
a[i][j]=max{a[i-1][j-1],a[i][j-1],a[i+1][j-1]} +a[i][j] for j=0 to n-1
and a[i][j]=0 for i<0 or i>=m
Finally the max element in the last column is the solution.
I am sorry but the approach above will not work. It can be solved using dynamic programming in O(mn) time using the equation below:
a[i][j]=max{a[i-1][j-1],a[i][j-1],a[i+1][j-1]} for j=1 to n-1
And a[i][j]=0 if i<0 or i>=m.
Finally the answer will be the max element in the last column.
Here is a solution in C++. Time complexity O(N2)
/*
Given a string which only contains lowercase. You need delete the repeated letters only leave one, and try to make the lexicographical order of new string is smallest.
i.e:
bcabc
You need delete 1 'b' and 1 'c', so you delete the first 'b' and first 'c', the new string will be abc which is smallest.
ps: If you try to use greedy algorithm to solve this problem, you must sure that you could pass this case:
cbacdcbc. answer is acdb not adcb
I can't solve this problem well and the interviewer said that you can scan the string twice. First scan is do some preprocess, and the second is to get the answer, but I really can't come up this idea.
*/
#include<iostream>
using namespace std;
#include<ctype.h>
#include<string.h>
void createDictionary(char *str,int dictionary[26])
{
int i=0;
while(str[i]!='\0')
{
dictionary[str[i]-'a']++;
i++;
}
}
char* removeDuplicates(char *str,int dictionary[26])
{
char *result=new char[strlen(str)];
for(int k=0;str[k]!='\0';k++)
{
for(int i='a';i<='z';i++)
{
int tempDict[26]={0};
int j=k;
while(str[j]!=i && str[j]!='\0')
{
if(isalpha(str[j]))
{
int index=str[j]-'a';
tempDict[index]++;
if(dictionary[index]-tempDict[index]==0)
{
break;
}
}
j++;
}
if(str[j]==i)
{
if(str[j+1]=='\0' && dictionary[str[j]-'a']>1)
{
dictionary[str[j]-'a']--;
str[j]=' ';
}
for(;k<j;k++)
{
dictionary[str[k]-'a']--;
str[k]=' ';
}
break;
}
}
}
int j=0;
for(int i=0;i<strlen(str);i++)
{
if(isalpha(str[i]))
{
result[j]=str[i];
j++;
}
}
result[j]='\0';
return result;
}
int main()
{
char str[]="cbacdcbc";
int dictionary[26]={0};
createDictionary(str,dictionary);
char *result=removeDuplicates(str,dictionary);
cout<<result;
return 0;
}
It will be O(n!).
- technoapurva September 24, 2015