谷歌 Custom Sorter 题

Job Hunting Interview
,
1

You run a service that sort words. instead of using the normal alphabet(a, b, c, …, x, y, z),
we have “ch” that goes between “h” and “i” in the sort order. so that the alphabet becomes (a, b, … h, ch, i, … x, y, z)
[‘indigo’, ‘charisma’, ‘hotel’] => [‘hotel’, ‘charisma’, ‘indigo’]

2

试着写了一下代码

public class CustomSorter {

	private static final int border = 'h' - 'a';
	
	private static class Result {
		int val;
		int index;
		public Result(int val, int index) {
			this.val = val;
			this.index = index;
		}
	}
	private static Result getValue(String s, int begIndex) {
		char c = s.charAt(begIndex);
		int offset = c - 'a';
		if (c == 'c' && begIndex + 1 < s.length() && s.charAt(begIndex + 1) == 'h') {
			return new Result(border + 1, begIndex + 2);
		}
		
		if (offset <= border) {
			return new Result(offset, begIndex + 1);
		}
		
		return new Result(offset + 1, begIndex + 1);
	}
	
	public static int compare(String a, String b) {
		int i = 0, j = 0;
		while (i < a.length() && j < b.length()) {
			Result aR = getValue(a, i);
			Result bR = getValue(b, i);
			if (aR.val != bR.val) {
				return Integer.compare(aR.val, bR.val);
			}
			i = aR.index;
			j = bR.index;
		}

		if (i < a.length()) {
			return 1;
		}
		if (j < b.length()) {
			return -1;
		}
		return 0;
	}

	public static void sort(List<String> words) {
		Collections.sort(words, (a, b) -> compare(a, b));
	}

	public static void main(String[] args) {
		List<String> l = new ArrayList<>();
		l.add("indigo");
		l.add("charisma");
		l.add("hotel");
		sort(l);
		System.out.println(l);
	}

}
3

在compare这个方法中，为什么getValue中，第二个attribute是i而不是j？ 谢谢

4

好像是个 Bug， 应该是 j