Amazon Interview Question
Software Engineer / DevelopersTeam: Kindle-Periodicals
Country: India
Interview Type: In-Person
i think hashing will require O(n^2) because we will have to compare each non unique item from str1 with all the items in str2...
i think the optimal solution is to:
1- sort the string with the larger length
2- search for all the non unique items in str1 using binary search in str2
this will be O(nlogn) solution
assuming the strings are not too huge.. we represent each character by a prime number.
then multiple each primeOf(char) of str1 and store it in str1_long
mulitply each primeOf(char) of str2 and store it in str2_long
then str2_long should be divisible by str1_long
Use two boolean flag1[256], flag2[256]. Firstly, set the character of str2 to true in flag2. Then traverse str1, if flag1[i] == false, then set it true. else find it in flag2, if flag2 is not true, means this duplicate character is not in str2, so return false. at last of the function, return true. O(n)
This problem can be divided into 2 sub problems.
1) Finding out unique elements in str1
2) For each unique element in str1, find out if it is there in str2
Assuming the chars in string are in ascii set.
int uniqueChars(char str1[],char str2[]){
static int a[256],b[256];
int i=0,j=0;
int ret = 1;
while(str1[i] != '\0'){
a[str1[i]]++;
i++;
}
while(str2[j] != '\0'){
b[str2[j]]++;
j++;
}
i = 0;
while(str1[i] != '\0'){
if(a[str1[i]] == 1){
if(b[str1[i]] == 0){
ret = 0;
break;
}
}
i++;
}
return ret;
}
Just a small tweak, in the last while loop it should be if(a[str1[i]] >1) as we are finding non unique chars and not unique ones. Except for that the code seems good
Just a small tweak, in the last while loop it should be if(a[str1[i]] >1) as we are finding non unique chars and not unique ones. Except for that the code seems good
- Anonymous July 24, 2013