## Sunday, November 29, 2015

### Facebook interview - Suffix Array Order - 我的博客 - ITeye技术网站

Facebook interview - Suffix Array Order - 我的博客 - ITeye技术网站

suffix[1] = {20, 30, 25}
suffix[2] = {30, 25}
suffix[3] = {25}

suffix[0] < suffix[1] < suffix[3] < suffix[2]

input: int[] text
output: int[] suffix_array_order
e.g.
input: int[] text = {10, 20, 30, 25}
output: int[] suffix_array_order = {0, 1, 3, 2}

Solution:

1. public Integer[] suffixArrayOrder(int[] A) {
2.     int n = A.length;
3.     Integer[] order = new Integer[n];
4.     for(int i=0; i<n; i++) {
5.         order[i] = i;
6.     }
7.
8.     Arrays.sort(order, new Comparator<Integer>(){
9.         @Override
10.         public int compare(Integer o1, Integer o2) {
11.             int res = A[o1] - A[o2];
12.             while(res == 0 && o1 < n && o2 < n) {
13.                 res = A[o1++] - A[o2++];
14.             }
15.             return res;
16.         }
17.     });
18.
19.     System.out.println(Arrays.toString(order));
20.     return order;
21. }

output: boolean isExist;

(做法是binary search)

http://www.geeksforgeeks.org/suffix-array-set-1-introduction/

You don't need to create an LIst<List> for all the suffix arrays since that will take extra space and time to create. What I did is to create an wrapper class:
Class Index{
public int index;
public int[] array;
}
Just pass the reference of whole input array to the wrapper class object.
I answered O(n log n), n is the length of the array at the interview and passed.

After that, I think if we consider the worse case of comparing two string, the worst case time should be O(n^2 log n).
1. public class Index {
2.     int[] suff;
3.     int idx;
4.     Index(int[] _suff, int _idx) {
5.         suff = _suff;
6.         idx = _idx;
7.     }
8. }

9. //Sort
10. int[] suffixOrder(int[] text, int n) {
11.     int[] res = new int[n];
12.     Index[] indices = new Index[n];
13.     for (int i=0; i < n; i++) {
14.         int[] suffix = Arrays.copyOfRange(text, i, text.length);
15.         indices[i] = new Index(suffix, i);
16.     }

17.     Arrays.sort(indices, new Comparator<Index>() {
18.         public int compare(Index i1, Index i2) {
19.             int p1 = 0;
20.             int p2 = 0;
21.             while (p1 < i1.suff.length && p2 < i2.suff.length) {
22.                 if(i1.suff[p1] != i2.suff[p2]) {
23.                     return i1.suff[p1] - i2.suff[p2];
24.                 } else {
25.                     p1 ++;
26.                     p2 ++;
27.                 }
28.             }
29.             if (p2 == i2.suff.length) {
30.                 return 1;
31.             }
32.             return -1;
33.         }
34.     });

35.     for (int i = 0; i < n; i++) {
36.         res[i] = indices[i].idx;
37.     }
38.     return res;
39. }

40. // Search
41. boolean search(int[] text, int n, int[] sub_text, int m) {
42.     int[] suffix_order = suffixOrder(text, n);
43.     Comparator<Index> textCompare = new Comparator<Index>(){
44.         @Override
45.         public int compare(Index i1, Index i2){
46.             while (a < text.length && b < sub_text.length) {
47.                 if (text[a] != sub_text[b]) {
48.                     return text[a] - sub_text[b];
49.                 } else {
50.                     a ++;
51.                     b ++;.
52.                 }
53.             }
54.             if(a == text.length) return -1;
55.             return 0;.
56.         }
57.     };

58.     int lo = 0;
59.     int hi = n - 1;
60.     while (lo <= hi) {
61.     int mid = (lo + hi) / 2;
62.     int[] suffix = Arrays.copyOfRange(text, suffix_order[mid], text.length);
63.     int cmp = textCompare(suffix, sub_text);
64.     if (cmp == 0) {
65.         return true;
66.     } else if(cmp < 0) {
67.         lo = mid + 1;
68.     } else {}
69.         hi = mid - 1;
70.     }
71.     return false;
72. }