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 n1. 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.

technoapurva
September 23, 2015 @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[i1][j1],a[i][j1],a[i+1][j1]} +a[i][j] for j=0 to n1
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[i1][j1],a[i][j1],a[i+1][j1]} for j=1 to n1
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;
}

technoapurva
September 20, 2015 Open Chat in New Window
It will be O(n!).
 technoapurva September 24, 2015