Lab126 Interview Question
SDE1sCountry: United States
Interview Type: Phone Interview
Sorry for not clarifying the other conditions...
a) No requirement that the strings have to be unique... so if an input is OOO, then the total strings can be "OOO", "OOO" & "OOO".
b) That's a valid solution to check if one string is a rotation of the other, however the interviewer has openly said I should actually code the given requirements from scratch and not to use this solution...
Here is a sample code.But it will print all three rotation for the input "ooo".
package com.test;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class AllRotation {
public static void main(String[] args) throws IOException {
BufferedReader obj = new BufferedReader(new InputStreamReader(System.in));
System.out.println("Enter the String whose Rotation is to be found");
String input = obj.readLine();
System.out.println("Enter the String to check whether it's rotation of first String");
String input2 = obj.readLine();
boolean isRotated = false;
for (int index = 0; index < input.length(); index++) {
String rotatedString = input.substring(index)+ input.substring(0, index);
System.out.println(rotatedString);
if (rotatedString.equals(input2)) {
isRotated = true;
}
}
System.out.println("The Second input is Rotation of first " + isRotated);
}
}
void print_all_rotations(char* pstr)
{
int n = strlen(pstr);
char *temp =(char*) malloc(1 + 2*n);
memcpy(temp, pstr, sizeof(char)*n);
memcpy(temp+n, pstr, sizeof(char)*n);
for (int i = 1; i <= n; i++)
{
char save = *(temp + i + n);
*(temp + i + n) = '\0';
printf("%s\n", temp + i);
*(temp + i + n) = save;
}
delete[] temp;
}
public boolean isRotation(String a,String b)
{
String c=b+b;
int trueOrFalse=c.indexOf(a);
if (trueOrFalse == -1) return false;
else return true;
}
I think your solution will not work for "aaaa" and "aaa". You should also have length check for both the strings a and b.
static List<string> find_rotations(string original)
{
List<string> tempList = new List<string>();
for(int i = 0; i < original.Length; ++i)
{
char[] tempChars = original.ToCharArray();
for(int j = 0; j < original.Length; ++j)
{
tempChars[j] = original[(i + j) % original.Length];
}
tempList.Add(new string(tempChars));
}
return tempList;
}
static bool is_rotation(string string1, string string2)
{
if (string1.Length != string2.Length)
return false;
if (find_rotations(string1).Contains(string2))
return true;
return false;
}
Here is the solution I have implemented in the interview, from scratch, given the above conditions...
static void Main(string[] args)
{
Program pg = new Program();
string str1 = "TIME";
string str2 = "ETIM";
bool is_rotate = false;
is_rotate = pg.is_rotation(str1, str2);
if(is_rotate==true)
Console.WriteLine("Str2 is a rotation of Str1");
else
Console.WriteLine("Str2 is not a rotation of Str1");
}
public bool is_rotation(string str1, string str2)
{
string[] sarr = new string[str1.Length];
bool is_rotation = false;
sarr = rotate_str(str1);
for (int k = 0; k < sarr.Length; k++)
{
Console.WriteLine(sarr[k]);
}
int i = 0;
for (i = 0; i < str1.Length;i++)
{
if(sarr[i] == str2)
{
is_rotation = true;
return is_rotation;
}
}
return is_rotation;
}
public string[] rotate_str(string str)
{
char[] ca = str.ToCharArray();
int j = 0, len = ca.Length - 1, k = 0, m=0;
char temp=' ';
string[] sa = new string[str.Length];
for (k = 0; k < str.Length; k++)
{
temp = ca[m];
for(j=0; j<len; j++)
{
ca[j] = ca[j + 1];
}
ca[j] = temp;
sa[k] = new string(ca);
if(k==sa.Length-1)
{
return sa;
}
else
{
ca = sa[k].ToCharArray();
continue;
}
}
return sa;
}
Solution for second problem: concatenate the string with itself and search for the given string in the concatenated string.
def find(string, l_s):
if l_s in string:
return 1
else:
return 0
def main(string, l_s):
t_string = string + string
check = find(t_string, l_s)
print check
if __name__ == "__main__":
main(sys.argv[1], sys.argv[2])
Solution for first problem:
consider array of size 5 , and i want to shift each element n times then:
(5+n+ i) %5 where i is the actual position of a value in the array. This equation will give the new location to the array.
def rotate(string, shift):
i = 0
if shift == len(string):
return
for i in range(0, len(string)):
print string[(len(string)+shift+i)%len(string)]
rotate(string, shift+1)
def main(string, l_s):
rotate(string, 0)
if __name__ == "__main__":
main(sys.argv[1])
void allRotationOfString(string str) {
if (str.size() == 0) {
cout<<endl<<"Invalid input for allRotationOfString";
return;
}
cout<<endl;
for (int i=0; i<str.size(); i++) {
str = str.substr(1, str.size()) + str[0];
cout<<str<<" ";
}
}
bool includedInAllRotationOfString(string str1, string str2) {
if (str1.size() == 0) {
return false;
}
for (int i=0; i<str1.size(); i++) {
str1 = str1.substr(1, str1.size()) + str1[0];
if (str1 == str2)
return true;
}
return false;
}
#include <stdio.h>
#define True 1
#define False 0
unsigned char compare_string_length(unsigned char *, unsigned char*);
unsigned char compare_strings(unsigned char *, unsigned char*, unsigned char);
int main()
{
unsigned char Str1[10], Str2[10];
unsigned char i=0, Result=False, String_count= False;
printf("Input String 1\n");
fgets(Str1, sizeof(Str1), stdin);
printf("Input String 2\n");
fgets(Str2, sizeof(Str2), stdin);
String_count = compare_string_length(Str1, Str2);
if(String_count == False)
{
printf("Strings length not same\n");
}
else
{
Result = compare_strings(Str1, Str2,String_count);
if(Result == False)
{
printf("Strings is not a rotation\n");
}
else
{
printf("Strings is a rotation\n");
}
}
return 0;
}
unsigned char compare_string_length(unsigned char *Str_El_Com1, unsigned char*Str_El_Com2)
{
unsigned char Temp1=0, Temp2=0, Com_Return;
while(Str_El_Com1[Temp1]!='\n')
{
Temp1++;
}
while(Str_El_Com2[Temp2]!='\n')
{
Temp2++;
}
if(Temp1 !=Temp2)
{
Com_Return = 0;
}
else
{
Com_Return = Temp1;
}
return Com_Return;
}
unsigned char compare_strings(unsigned char *Str_Com1, unsigned char*Str_Com2, unsigned char compare_count)
{
unsigned char Temp1=0, Temp2=0, Com_Return, Failure = False, match_found = 0, match_found_flag=0;
while((Str_Com1[Temp1]!='\n' ) && Failure == False)
{
while(Str_Com2[Temp2]!='\n')
{
if(Str_Com1[Temp1] == Str_Com2[Temp2])
{
//Some dummy character
Str_Com2[Temp2] = '#';
match_found++;
match_found_flag = 1;
Temp2=0;
break;
}
Temp2++;
}
if(match_found_flag == 0)
{
Failure = True;
}
Temp1++;
}
if(match_found == compare_count)
{
Com_Return = True;
}
else
{
Com_Return = False;
}
return Com_Return;
}
int checkRotation(char *str1, char *str2) // checks if str2 is a rotation of str1
{
int i, j, k;
int len = strlen(str1);
if(strlen(str2) != len)
return 0;
for(j=0; j<len; j++) // This loop is to take care of multiple occurrence of first character of str1 in str2
{
while(j<len && str2[j++] != *str1); // find the occurrence of the first letter of str1 in str2
if(j == len) // first char is not there in the second string or no match found in subsequent loops also.
return 0;
for(i=0, k=j-1; i<len; i++)
{
if(str1[i] != str2[k])
break;
k = (k+1)%len;
}
if(i==len)
return 1;
}
return 0;
}
I presume you mean unique rotations? So if String is "OOO", only print a single "OOO"?
- Subbu. February 10, 2014We can use a trie to keep track in that case (not sure if you disallow that).
Follow up is a classic: Append Str1 to itself and check if Str2 is a substring ( using KMP, Boyer-Moore etc) and of the appropriate length.