Facebook interview - Suffix Array Order

首先定义了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之类的原始值数组！

public Integer[] suffixArrayOrder(int[] A) {
	int n = A.length;
	Integer[] order = new Integer[n];
	for(int i=0; i<n; i++) {
		order[i] = i;
	}
	
	Arrays.sort(order, new Comparator<Integer>(){
		@Override
		public int compare(Integer o1, Integer o2) {
			int res = A[o1] - A[o2];
			while(res == 0 && o1 < n && o2 < n) {
				res = A[o1++] - A[o2++];
			}
			return res;
		}
	});
	
	System.out.println(Arrays.toString(order));
	return order;
}

 

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

 

这个没看懂，不知道怎么写。

原文见：

http://www.1point3acres.com/bbs/thread-125284-1-1.html