Microsoft Interview Question
Software Engineer in TestsCountry: United States
Interview Type: In-Person
Just to add to this, we wouldn't need a suffix array at all, if the interviewer didn't add the extension to the question.
If its simply checking if a word is a palindrome, you can put two pointers in the middle of the word (special case, if word length is even) and then check characters on left and right side of the pointer. While doing this, increment one pointer till pointer>=word.length and decrement other pointer, till pointer < 0.
If characters are different, word is not a palindrome.
Brilliant! I think in Step 5, you will have to scan each element with every element, making this O(k^2). But this is an acceptable solution nonetheless. It will find all palindromes!
O(n^2) simple solution for all palindromes. Take matrix( (len(s)+1)*(len(s1)+1)) arrange s on the first row, reverse s(call it rs) arrange it in the first column. Populate matrix with 0 or 1 accordingly. Count all diagonals whose length is more than 1 ,this gives all possible palindromes.
If its just about checking for palindromes then the following code works for me:
public class anagram {
public static void main(String[] args) {
String s1 = "nitin";
String s2 = "MALAYALAM";
String s3 = "abba";
String s4 = "aa";
String s5 = "haha";
System.out.println("Result for s1 is: " +anagramtest(s1));
System.out.println("Result for s2 is: " +anagramtest(s2));
System.out.println("Result for s3 is: " +anagramtest(s3));
System.out.println("Result for s4 is: " +anagramtest(s4));
System.out.println("Result for s5 is: " +anagramtest(s5));
}
public static boolean anagramtest(String s) {
boolean flag = false;
char[] c = s.toCharArray();
if(s.length() == 2) {
if(c[0] == c[1]) { flag = true; }
}
else if(s.length() > 2) {
for (int start = 0, finish = s.length()-1; start < finish; start++,finish--) {
if(c[start] == c[finish]) {
flag = true;
}
}
}
return flag;
}
}
But i think the question is asking for palindromes within palindromes essentially asking us to count the total palindromes within a given word. Please clarify.
I will post the code for this shortly, but here is the explanation in English:
1. You will need a suffix array (you can use a suffix tree, but suffix array takes up less space and is easier to build, especially on a board during the interview).
2. You will need to build two suffix arrays - one for your string: S and one for the reverse of S'. O(n) time
3. Sort the suffixes in the suffix array O(n lg n) time
4. Now run a simple loop comparing the first, second, third.... n elements of your suffix array. Remember, you are not comparing each element to every element. You are just incrementing a single index - 'i' and comparing the element at 'i' in the first suffix array, with that of the second suffix array - O(n) time
5. When you compare, you are actually trying to find the Longest Common Prefix. Suffix arrays naturally lets you perform this operation - O(k) time, where k is the length of the longest common prefix. Since you run this for every compare (in Step 4), total time is O(nk)
6. If the length of the LCP at each compare is greater than 2, then you have a palindrome :)
{{
8. Go back to Step 4 and repeat till you have scanned all elements of both the suffix arrays.
9. Simply output whatever you stored in Step 7 and you have a list of palindromes :)
I am not going to explain how or why suffix arrays/trees are able to do this. I suggest you go through a good suffix array article online (especially once Wikipedia stops protesting against SOPA :P)
I will post the code for this shortly - maybe tomorrow.
- Anonymous January 19, 2012