Microsoft Interview Question
Software Engineer in TestsCountry: United States
I'm assuming that upper are different than lower cases. But It would be a good thing to point out to the interviewer.
Here is my algorithm:
public static void removeCommon(char str1[], char str2[]){
int letters[] = new int[256];
for(int i = 0; i < str1.length; i++)
letters[str1[i]]++;
for(int i = 0; i < str2.length; i++)
if(letters[str2[i]]>0)
letters[str2[i]]= -1;
int index = 0;
for(int i = 0; i < str1.length; i++)
{
if(letters[str1[i]] != -1){
str1[index++] = str1[i];
}
}
while(index < str1.length)
str1[index++] = 0;
index = 0;
for(int i = 0; i < str2.length; i++)
{
if(letters[str2[i]] != -1){
str2[index++] = str2[i];
}
}
while(index < str2.length)
str2[index++] = 0;
System.out.println(str1);
System.out.println(str2);
System.out.println("Common");
for(int i = 0; i < letters.length; i ++){
if(letters[i] == -1){
char c = (char)i;
System.out.print(c);
}
}
System.out.println();
}
public static void main(String [] args){
removeCommon("abcdefghijklmnopqrstuvwxyz".toCharArray(),"AEIOUaeiou123".toCharArray());
}
mafafito@mafafito-Aspire-4752:~/programming$ javac Amazon.java
mafafito@mafafito-Aspire-4752:~/programming$ java Amazon
bcdfghjklmnpqrstvwxyz
AEIOU123
Common
aeiou
public class RemoveAndPrintCommonChar {
/*Remove common characters from two strings and print the common characters and test cases*/
public static void main(String[] args) {
String string1 = "ahob6n";
String string2 = "javbrho";
// char[] arrayofChar = string1.toCharArray();
Set<Character> setOfCharString1 = new HashSet<Character>();
for (int i=0; i<string1.length(); i++){
setOfCharString1.add(string1.charAt(i));
}
StringBuilder duplicatebuilder = new StringBuilder();
StringBuilder string2builder = new StringBuilder();
for (int j=0; j<string2.length(); j++){
char a = string2.charAt(j);
if (setOfCharString1.contains(a)){
setOfCharString1.remove(a);
duplicatebuilder.append(a);
}
else{
string2builder.append(a);
}
}
System.out.println("String 1 without duplicates: "+setOfCharString1.toString());
System.out.println("String 2 without duplicates: "+string2builder.toString());
System.out.println("Duplicates among both strings: "+duplicatebuilder.toString());
}
public class RemoveAndPrintCommonChar {
/*Remove common characters from two strings and print the common characters and test cases*/
public static void main(String[] args) {
String string1 = "ahob6n";
String string2 = "javbrho";
// char[] arrayofChar = string1.toCharArray();
Set<Character> setOfCharString1 = new HashSet<Character>();
for (int i=0; i<string1.length(); i++){
setOfCharString1.add(string1.charAt(i));
}
StringBuilder duplicatebuilder = new StringBuilder();
StringBuilder string2builder = new StringBuilder();
for (int j=0; j<string2.length(); j++){
char a = string2.charAt(j);
if (setOfCharString1.contains(a)){
setOfCharString1.remove(a);
duplicatebuilder.append(a);
}
else{
string2builder.append(a);
}
}
System.out.println("String 1 without duplicates: "+setOfCharString1.toString());
System.out.println("String 2 without duplicates: "+string2builder.toString());
System.out.println("Duplicates among both strings: "+duplicatebuilder.toString());
}
check_duplicate( char * S1, char * S2)
{
//Hash both strings S1 and S2 with a Key = tolower(S[i]) - 'a'; Key is int
// length of String S1 : S1len = strlen(S1); S2len = strlen(S2);
if ( S1 || S2 == NULL) return;
for (i = 0; i < S1len; i++) {
key = tolower(S1[i]) - 'a' ;
A[ key ] = A[key] + 1;
}
for (i = 0; i < S2len; i++) {
key = tolower(S2[i]) - 'a' ;
A[ key ] = A[key] - 1;
}
// Now check the hash value for S1, find out duplicates and copy the not duplicates to target array
for (i = 0; i < S1len ; i++) {
key = tolower(S1[i]) - 'a';
if ( A[ key ] != 0) target1[i] = S1[i];
}
// Now check the hash value and find out duplicates in S2 and copy not duplicates to target2
for (i = 0; i < S2len ; i++) {
key = tolower(S2[i]) - 'a';
if ( A[ key ] != 0) target2[i] = S2[i];
}
}
Testcases
1) Pass Null pointers
2) Pass one Null another valid character string.
3) Pass valid characters
4) Pass numbers and special characters
5) Pass huge characters with space separated
6) Record the time taken for the entire program
Assuming all characters in a string are ASCII, declare array of 128 boolean elements.
boolean notcommon[128];
/* memset to contain all 0s */
process first string, and forevery character in first string, set corresponding element in notcommon to true
for(i=0; firststr[i]!='\0'; i++)
notcommon[ firststr[i] - 'a'] = ~notcommon[ firststr[i] - 'a'];
Now process second string in a same manner
for(i=0; secondstr[i]!='\0'; i++)
notcommon[ secondstr[i] - 'a'] = ~notcommon[ secondstr[i] - 'a'];
So all elements which are 1 in notcommon are appearing only in 1 of two strings. Now for each string, peform following
char *rp = str;
char *wp = str;
while( *rp != '\0' )
{
if( notcommon[ *rp ] == 1 )
*wp++ = *rp;
*rp++;
}
*wp='\0';
Eliminated all common characters. Time Complexity O( l1 + l2 ) space complexity is O(1) or O(128)
For non-ASCII characters, for variable length encoding, we'll need to maintain multiple tables for each length.
- Anonymous November 17, 2013