• Each page has 12 listings
  • Try to avoid listings with the same host ID in the same page
  • If the number of remaining listings is less than 12, allow duplicated host ID in the same page
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
package airbnb;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;


public class PageDisplay {
	
	public static List<List<String>> displayPages(List<String> input) {
		LinkedList<List<String>> result = new LinkedList<>();
		if (input == null || input.size() == 0) return result;
		
		HashSet<String> visited = new HashSet<>();
		LinkedList<String> page = new LinkedList<>();
		Iterator<String> iter = input.iterator();
		
		while (iter.hasNext()) {
			String entry = iter.next();
			String host = entry.split(",")[0];
			if (visited.add(host)) {
				page.add(entry);
				iter.remove();
			}
			if (page.size() == 12 || !iter.hasNext()) {
				visited.clear();
				iter = input.iterator();
				if (page.size() == 12) {
					// sort the list
					result.add(new LinkedList<>(page));
					page = new LinkedList<>();
				}
			}
		}
		if (page.size() != 0) {
			result.add(page);
		}
		return result;
	}
	
	public static List<List<String>> displayFast(List<String> input) {
		List<List<String>> result = new LinkedList<>();
		if (input == null || input.size() == 0) return result;
		
		int notFullPageNumber = 0;
		HashMap<String, Integer> map = new HashMap<>(); // <host id, last inserted page index>
		for (int i = 0; i < input.size(); i++) {
			String entry = input.get(i);
			String host = entry.split(",")[0];
			int page = map.getOrDefault(host, -1);
			// never seen host id, insert into the first page that is not full
			if (page == -1) {
				if (result.size() <= notFullPageNumber) {
					result.add(new LinkedList<>());
				}
				result.get(notFullPageNumber).add(entry);
				map.put(host, notFullPageNumber);
				if (result.get(notFullPageNumber).size() == 12) {
					notFullPageNumber = findNextNotFullPage(notFullPageNumber, result);
				}
			} else {
				// duplicate id, insert into the first not-full page after the last inserted index
				int nextInsertPageNumber = findNextNotFullPage(page, result);
				if (nextInsertPageNumber == result.size() && 
						result.get(nextInsertPageNumber - 1).size() + input.size() - i > 12) {
					result.add(new LinkedList<>());
				} else if (nextInsertPageNumber == result.size()){
					nextInsertPageNumber--;
				}
				result.get(nextInsertPageNumber).add(entry);
				map.put(host, nextInsertPageNumber);
			}
		}
		return result;
	}
	
	public static int findNextNotFullPage(int currentPageNumber, List<List<String>> result) {
		int res = currentPageNumber + 1;
		while (res < result.size() && result.get(res).size() == 12) {
			res++;
		}
		return res;
	}

	public static void main(String[] args) {
		String[] strs = new String[]{
			      "1,28,300.1,SanFrancisco",
			      "4,5,209.1,SanFrancisco",
			      "20,7,208.1,SanFrancisco",
			      "23,8,207.1,SanFrancisco",
			      "16,10,206.1,Oakland",
			      "1,16,205.1,SanFrancisco",
			      "6,29,204.1,SanFrancisco",
			      "7,20,203.1,SanFrancisco",
			      "8,21,202.1,SanFrancisco",
			      "2,18,201.1,SanFrancisco",
			      "2,30,200.1,SanFrancisco",
			      "15,27,109.1,Oakland",
			      "10,13,108.1,Oakland",
			      "11,26,107.1,Oakland",
			      "12,9,106.1,Oakland",
			      "13,1,105.1,Oakland",
			      "22,17,104.1,Oakland",
			      "1,2,103.1,Oakland",
			      "28,24,102.1,Oakland",
			      "18,14,11.1,SanJose",
			      "6,25,10.1,Oakland",
			      "19,15,9.1,SanJose",
			      "3,19,8.1,SanJose",
			      "3,11,7.1,Oakland",
			      "27,12,6.1,Oakland",
			      "1,3,5.1,Oakland",
			      "25,4,4.1,SanJose",
			      "5,6,3.1,SanJose",
			      "29,22,2.1,SanJose",
			      "30,23,1.1,SanJose"
			    };
		List<List<String>> pages = displayPages(new ArrayList<>(Arrays.asList(strs)));
		List<List<String>> pages2 = displayFast(new ArrayList<>(Arrays.asList(strs)));
		for (int i = 0; i < pages.size(); i++) {
			System.out.println("Page " + i);
			System.out.println("left page size " + pages.get(i).size());
			System.out.println("right page size " + pages2.get(i).size());
			for (int j = 0; j < pages.get(i).size(); j++) {
				
				System.out.println(pages.get(i).get(j) + " " + (j < pages2.get(i).size() ? pages2.get(i).get(j) : " "));
//				assert pages.get(i).get(j) == pages2.get(i).get(j);
			}
		}
		System.out.println("Success");
	}

}