Page Display - Airbnb


https://github.com/allaboutjst/airbnb
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.
        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

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts