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

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

首先定义了suffix string 或者说suffix arrary
如果有个数组是 int[] text = {10, 20, 30, 25}
那么 suffix[0] = {10, 20, 30, 25}
           suffix[1] = {20, 30, 25}
           suffix[2] = {30, 25}
           suffix[3] = {25}
如果对这些数组进行lexical order 的排序，我们可以得到
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:

注意： Arrays.sort(T[], Comparator)只能用于排序对象数组，不能用于排序int, long之类的原始值数组！

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. }

第二题： input:  int[] text, int[] subText
              output: boolean isExist;
检查text数组中有没有一个subarray 是subText。要求时间小于O(N^2)， N == text.length;
这里假设我们有了第一题的 suffix_array_order.
(做法是binary search)

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

就是相当于把所有的substring 排序，然后binary search
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. 
   
10. //Sort
11. int[] suffixOrder(int[] text, int n) {
12.     int[] res = new int[n];
13.     Index[] indices = new Index[n];
14.     for (int i=0; i < n; i++) {
15.         int[] suffix = Arrays.copyOfRange(text, i, text.length);
16.         indices[i] = new Index(suffix, i);
17.     }
18. 
    
19.     Arrays.sort(indices, new Comparator<Index>() {
20.         public int compare(Index i1, Index i2) {
21.             int p1 = 0;
22.             int p2 = 0;
23.             while (p1 < i1.suff.length && p2 < i2.suff.length) {
24.                 if(i1.suff[p1] != i2.suff[p2]) {
25.                     return i1.suff[p1] - i2.suff[p2];
26.                 } else {
27.                     p1 ++;
28.                     p2 ++;
29.                 }
30.             }
31.             if (p2 == i2.suff.length) {
32.                 return 1;
33.             }
34.             return -1;
35.         }
36.     });
37. 
    
38.     for (int i = 0; i < n; i++) {
39.         res[i] = indices[i].idx;
40.     }
41.     return res;
42. }
43. 
    
44. // Search
45. boolean search(int[] text, int n, int[] sub_text, int m) {
46.     int[] suffix_order = suffixOrder(text, n);
47.     Comparator<Index> textCompare = new Comparator<Index>(){
48.         @Override
49.         public int compare(Index i1, Index i2){
50.             while (a < text.length && b < sub_text.length) {
51.                 if (text[a] != sub_text[b]) {
52.                     return text[a] - sub_text[b];
53.                 } else {. 
54.                     a ++;
55.                     b ++;.
56.                 }
57.             }
58.             if(a == text.length) return -1;
59.             return 0;.
60.         }
61.     };
62. 
    
63.     int lo = 0;
64.     int hi = n - 1;
65.     while (lo <= hi) {
66.     int mid = (lo + hi) / 2;
67.     int[] suffix = Arrays.copyOfRange(text, suffix_order[mid], text.length);
68.     int cmp = textCompare(suffix, sub_text); 
69.     if (cmp == 0) {
70.         return true;
71.     } else if(cmp < 0) {
72.         lo = mid + 1;
73.     } else {}
74.         hi = mid - 1;
75.     }
76.     return false;
77. }

Read full article from Facebook interview - Suffix Array Order - 我的博客 - ITeye技术网站