Massive Algorithms: Page Display

Given an array of CSV strings representing search results, output results sorted by a score initially. A given host may have several listings that show up in these results. Suppose we want to show 12 results per page, but we don’t want the same host to dominate the results.

Write a function that will reorder the list so that a host shows up at most once on a page if possible, but otherwise preserves the ordering. Your program should return the new array and print out the results in blocks representing the pages.

Given an array of csv strings, output results separated by a blank line.

4. Display page : Iterator, hashset and reachEnd. reachEnd为true时，添加重复元素，为false时不添加，counter满足时，reset hashset。iterator.hasNext为false时，reset iterator.

https://github.com/allaboutjst/airbnb/blob/master/src/main/java/display_page/DisplayPage.java

        Display Page - LinkedList + HashSet
    public class Solution {
        public List<String> displayPages(List<String> input, int pageSize) {
            List<String> res = new ArrayList<>();
            if (input == null || input.size() == 0) {
                return res;
            }

            List<String> visited = new ArrayList<>();
            Iterator<String> iter = input.iterator();
            boolean reachEnd = false;
            while (iter.hasNext()) {
                String curr = iter.next();
                String hostId = curr.split(",")[0];
                if (!visited.contains(hostId) || reachEnd) {
                    res.add(curr);
                    visited.add(hostId);
                    iter.remove();
                }

                if (visited.size() == pageSize) {
                    visited.clear();
                    reachEnd = false;
                    if (!input.isEmpty()) {
                        res.add(" ");
                    }
                    iter = input.iterator();
                }

                if (!iter.hasNext()) {
                    iter = input.iterator();
                    reachEnd = true;
                }
            }

            return res;
        }

        public List<String> displayPages(List<String> input, int pageSize) {
            List<String> res = new ArrayList<>();
            Iterator<String> iter = input.iterator();
            Set<String> set = new HashSet<>();
            boolean reachEnd = false;
            int counter = 0;
            while (iter.hasNext()) {
                String cur = iter.next();
                String id = (cur.split(","))[0];
                if (!set.contains(id) || reachEnd) {
                    res.add(cur);
                    set.add(id);
                    iter.remove();
                    counter++;
                }

                if (counter == pageSize) {
                    if (!input.isEmpty())
                        res.add(" ");
                    set.clear();
                    counter = 0;
                    reachEnd = false;
                    iter = input.iterator();
                }

                if (!iter.hasNext()) {
                    reachEnd = true;
                    iter = input.iterator();
                }
            }

            return res;
        }

Buttercola: Airbnb: Page Display

实现分页显示。给了以下一些输入数据，要求将以下行分页显示，每页12行，其中每行已经按score排好序，分页显示的时候如果有相同host id的行，则将后面同host id的行移到下一页。

[

"host_id,listing_id,score,city",

"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"

]

Code (Java):

There is a trick in this question. When do we need to get to a new page? There are two cases need to consider:
1. When the current page has 12 entries.
2. When the current page has less than 12 but the iterator has reached to the end. IN this case, we need wrap back and iterator the list again.

  public static void displayPages(List<String> input) {

    if (input == null || input.size() == 0) {

      return;

}

    Set<String> visited = new HashSet<>();

    Iterator<String> iterator = input.iterator();

    int pageNum = 1;

    System.out.println("Page " + pageNum);

    while (iterator.hasNext()) {

      String curr = iterator.next();

      String hostId = curr.split(",")[0];

      if (!visited.contains(hostId)) {

        System.out.println(curr);

        visited.add(hostId);

        iterator.remove();

}

      // New page

      if (visited.size() == 12 || (!iterator.hasNext())) {

        visited.clear();

        iterator = input.iterator();

        if (!input.isEmpty()) {

          pageNum++;

          System.out.println("Page " + pageNum);

}

}

}

}

https://github.com/gabhi/leetcode-1/blob/master/b/DividePage.java
private static final int CAPACITY = 12;
public static void displayPages(List<String> input) {
if(input == null || input.size() == 0) return;
Iterator<String> iter = input.iterator();
Set<String> set = new HashSet<>();
StringBuilder sb = new StringBuilder();
int pageNum = 1;
sb.append("page " + pageNum + "\n\n");
while(iter.hasNext()) {
String s = iter.next();
String pageId = s.split(",")[0];
if(!set.contains(pageId)) {
sb.append(s).append("\n");
set.add(pageId);
iter.remove();
}

if(set.size() == CAPACITY || !iter.hasNext()) {
set.clear();
iter = input.iterator();
if(iter.hasNext()) {
pageNum++;
sb.append("\npage " + pageNum + "\n\n");
}
}
}
System.out.println(sb.toString());
}
https://github.com/jxr041100/system_design/blob/master/Airbnb:%20Page%20Display
airbnb面试题汇总

用一个set来保存是否出现，加入以后删除原有元素，不够的话顺序补充

vector<vector<string> > paging(vector<string> items, int size) {
    vector<vector<string> > ans;
    const int n = items.size();
    for (int i = 0; i <= (n - 1) / size; ++i) {
        vector<string> tmp;
        unordered_set<string> st;
        for (auto it = items.begin(); it != items.end() && tmp.size() < size;) {
            if (st.count(*it)) {
                ++it;
                continue;
            }
            st.insert(*it);
            tmp.push_back(*it);
            items.erase(it);
        }
        for (auto it = items.begin(); it != items.end() && tmp.size() < size;) {
            tmp.push_back(*it);
            items.erase(it);
        }
        ans.push_back(tmp);
    }
    return ans;
}

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

给你一组数据，和每页的容量，要求每页上力求没有重复的ID例子:
input：1,2,3,4,1,5,1,2,3,1,3 ; page size : 5
output:
1,2,3,4,5 / 1,2,3,1,1 / 3

我的思路是max heap 统计freq 分配
我没想的那么复杂，就是用Hashset看有没有重复的ID，没有重复放进页面，然后删除这行数据，重复了读下一行，到新页面了，hashset reset，在从头开始读
读到底了，hashset reset, 再从头开始，这时不再使用hashset(比较trick的地方，题目要求读到底后就把重复的依次放进去就可以了 )

比方说input是 1231111222，每页5个
那么第一页是12311而不是12312
第二页是12122
Read full article from Buttercola: Airbnb: Page Display

Page Display - Airbnb

Labels

Popular Posts