Write a function f(a, b) which takes two character string arguments and returns a string containing only the characters found in both strings in the order of a.

Full Question:

Write a function f(a, b) which takes two character string arguments and returns a string containing only the characters found in both strings in the order of a. Write a version which is order N-squared and one which is order N.

With double loop (order N²), it's easy to solve the problem. Just compare one from a and the other from b while looping. Be careful that the solution is required result string in th order of a. So, outer loop should be for string a.

Using boolean array, the problem can be solved in order N time. Since size of char is 256 (char is 1 byte(8 bits) data, so 2⁸ = 256), we just need boolean array whose size is 256. Then first check string b.( note again that result string should be in order of string a). For appearing character in b, set true element of boolean array. (simple use the char as index of array). And then, check string a and print. Done.

public class GoogleQuestion {
public static void main(String args[]) {
String a = "abcdefg";
String b = "afcbedf";

System.out.println(getCommonCharNSquard(a.toCharArray(), b.toCharArray()));
System.out.println(getCommonCharN(a.toCharArray(), b.toCharArray()));

}

public static char[] getCommonCharNSquard(char[] a, char[] b) {
String ret = new String();

for(int i = 0; i < a.length; i++)
for(int j=0; j <b.length; j++) {
if(a[i] == b[j]) {
if(ret.indexOf(a[i]) == -1)
ret += a[i]; // order of a
break; // it may reduce the processing time, but still NSquard
}
}

return ret.toCharArray();
}

public static char[] getCommonCharN(char[] a, char[] b) {
String ret = new String();
boolean[] flags = new boolean[256];  //sizeOf(char)=256

for(int i = 0; i < b.length; i++)
flags[b[i]] = true;

for(int j=0; j <a.length; j++)
if(flags[a[j]] == true) {
ret += a[j];  // order of a
flags[a[j]] = false;
}
return ret.toCharArray();
}

}

Posted in Google Interview Question, Interview Question, MS interview Question, Programmer Interview Question, Software Engineer Interview Question