CareerCup

Easy. Append one of those strings with itself;
so if I am given to check if vindar and darvin are rotational equivalents, just append vindar to itself. Now i have vindarvindar and ANY rotational equivalent of the string will be a substring of this string!

bool rotation(char *str1 , char *str2)
{
if(str1 == NULL || str2 == NULL)
return 0;
if(strlen(str1) != strlen(str2))
return 0;

char *temp = new char[sizeof(str1) * 2 + 1];

strcat(temp,str1);
strcat(temp,str1);

char *ptr =strstr(temp,str2);

delete temp;

if(ptr == NULL)
return 0;
else
return 1;
}

Can be done in O(nlgn)

I doubt if it was ever asked by an Amazon Interviewer. The OP probably wants to solve it, and formulate the problem as his wish. Then why do people care to pay heed to such questions.

@arindam.mitra2: Isn't it better if you post such problems on Stackoverflow?

bool isSubstring(string s1, string s2) {
int j=0;
for (int i=0; i < s1.size(); ++i) {
if (s1[i] == s2[j])
++j;
else
j=0;

if(j==s2.size()) {return true;}
}
return false;
}

bool isRotationallyEquivalent(string &s1, string &s2) {
return isSubstring(s1+s1, s2);
}

can be done in O(1).

char * move1char(char *str)
{
char temp=*str;
static char *strtemp=new char[strlen(str)];
int i=0,len=strlen(str);
while(i<len)
{
strtemp[i]=str[i+1];
i++;
}
strtemp[len-1]=temp;
return(strtemp);
}

bool cyclic(char *str1,char *str2)
{

int m=0,len=strlen(str1);
char *strtemp=new char[strlen(str1)];
if(strlen(str1) != strlen(str2))
return false;
strtemp=str2;
for(int i=0;i<len;i++)
{
if(!strncmp(str1,strtemp,len))
return true;
else
strtemp=move1char(strtemp);
}
return(false);
}

bool cyclic(char *str1,char *str2)
{

int m=0,len=strlen(str1);
char *strtemp=new char[2*strlen(str1)];
if(strlen(str1) != strlen(str2))
return false;
strcpy(strtemp,str2);
strcat(strtemp,str2);
for(int i=0;i<len;i++)
{
if(!strncmp(str1,strtemp+i,len))
return true;
}
return(false);
}

void rotationalequi(){
	char *A="Helluo";
	char *B="elloH";
	char *tmp=B;
	char *CC=(char*)malloc(sizeof(char)*strlen(B)*2+1);
	char *C=CC;
	int counter=0;
	while(1){
		while(*tmp){
			*C++=*tmp++;
		}
		counter++;
		if(counter==2){
			*C='\0';
			break;
		}
		tmp=B;
	}
	
	
	C=CC;
	tmp=A;
	cout << " " << C;
	while(*C){
		while((*C==*tmp)&&(*tmp)){
			C++;
			tmp++;
		}
		if(!*tmp){
			cout << " found ";
			break;
		}
		else{
			tmp=A;
		}
		C++;
	}
	
	
	
	free (CC);
};

Testcase:

assert (RotationalCheck("Stupid Interviewer", "Friggin A***ole") == false);