LeetCode 642 - Design Search Autocomplete System


Design a search autocomplete system for a search engine. Users may input a sentence (at least one word and end with a special character '#'). For each character they type except '#', you need to return the top 3 historical hot sentences that have prefix the same as the part of sentence already typed. Here are the specific rules:
  1. The hot degree for a sentence is defined as the number of times a user typed the exactly same sentence before.
  2. The returned top 3 hot sentences should be sorted by hot degree (The first is the hottest one). If several sentences have the same degree of hot, you need to use ASCII-code order (smaller one appears first).
  3. If less than 3 hot sentences exist, then just return as many as you can.
  4. When the input is a special character, it means the sentence ends, and in this case, you need to return an empty list.
Your job is to implement the following functions:
The constructor function:
AutocompleteSystem(String[] sentences, int[] times): This is the constructor. The input is historical dataSentences is a string array consists of previously typed sentences. Times is the corresponding times a sentence has been typed. Your system should record these historical data.
Now, the user wants to input a new sentence. The following function will provide the next character the user types:
List<String> input(char c): The input c is the next character typed by the user. The character will only be lower-case letters ('a' to 'z'), blank space (' ') or a special character ('#'). Also, the previously typed sentence should be recorded in your system. The output will be the top 3 historical hot sentences that have prefix the same as the part of sentence already typed.
Example:
Operation: AutocompleteSystem(["i love you", "island","ironman", "i love leetcode"], [5,3,2,2])
The system have already tracked down the following sentences and their corresponding times:
"i love you" : 5 times
"island" : 3 times
"ironman" : 2 times
"i love leetcode" : 2 times
Now, the user begins another search:

Operation: input('i')
Output: ["i love you", "island","i love leetcode"]
Explanation:
There are four sentences that have prefix "i". Among them, "ironman" and "i love leetcode" have same hot degree. Since ' ' has ASCII code 32 and 'r' has ASCII code 114, "i love leetcode" should be in front of "ironman". Also we only need to output top 3 hot sentences, so "ironman" will be ignored.

Operation: input(' ')
Output: ["i love you","i love leetcode"]
Explanation:
There are only two sentences that have prefix "i ".

Operation: input('a')
Output: []
Explanation:
There are no sentences that have prefix "i a".

Operation: input('#')
Output: []
Explanation:
The user finished the input, the sentence "i a" should be saved as a historical sentence in system. And the following input will be counted as a new search.
Note:
  1. The input sentence will always start with a letter and end with '#', and only one blank space will exist between two words.
  2. The number of complete sentences that to be searched won't exceed 100. The length of each sentence including those in the historical data won't exceed 100.
  3. Please use double-quote instead of single-quote when you write test cases even for a character input.
  4. Please remember to RESET your class variables declared in class AutocompleteSystem, as static/class variables are persisted across multiple test cases. Please see here for more details.

题目大意:

设计搜索自动完成系统
包含如下两个方法:
构造方法:
AutocompleteSystem(String[] sentences, int[] times): 输入句子sentences,及其出现次数times
输入方法:
List<String> input(char c): 输入字符c可以是26个小写英文字母,也可以是空格,以'#'结尾。返回输入字符前缀对应频率最高的至多3个句子,频率相等时按字典序排列。

解题思路:

Trie(字典树)
利用字典树记录所有出现过的句子集合,利用字典保存每个句子出现的次数。
https://www.jiuzhang.com/qa/6999/
http://hehejun.blogspot.com/2018/12/leetcodedesign-search-autocomplete.html
https://www.jianshu.com/p/6a78f73a57be
题目很长,但不太难,用Trie即可解决,不过需要注意:
  • 在input中,需要边读边写,但注意一定是先读再写,否则会查出刚插进去的sentence
  • 遇到'#'时,要返回empty list
  • 由于要返回Trie中存储的sentences,一种做法是给Trie添加一个成员变量str用来存储root到curr路径上形成的str,另外一种做法是在查询时将str作为参数传入child。本题目采用的是后面的思路。
  • 在dfs trie时,一定要现将root添加到结果集,再遍历children!否则会漏掉栈底的root。这点很重要,Trie的查询都要这么写。
  • 在getKHot时,可以用PriorityQueue来做,也可以用List来做然后排序。

class AutocompleteSystem {
    private Trie root;
    private Trie curr;
    private String str; // store currently visiting str
    
    public AutocompleteSystem(String[] sentences, int[] times) {
        root = new Trie();
        
        for (int i = 0; i < sentences.length; ++i) {
            insert(root, sentences[i], times[i]);
        }
        
        this.curr = root;
        this.str = "";
    }
    
    public List<String> input(char c) {
        if (c == '#') {
            insert(root, str, 1);
            curr = root;
            str = "";
            return Collections.EMPTY_LIST;  // return empty as designed
        }
        
        int i = getIndex(c);
        if (curr.children[i] == null) {
            curr.children[i] = new Trie();
        }

        str += c;
        curr = curr.children[i];
        return getKHot(curr, str, 3);
    }
    
    private void insert(Trie root, String s, int plusTimes) {
        for (int i = 0; i < s.length(); ++i) {
            int j = getIndex(s.charAt(i));
            if (root.children[j] == null) {
                root.children[j] = new Trie();
            }

            root = root.children[j];
        }

        root.times += plusTimes; // accumulate in case duplicate sentences
    }
    
    private List<String> getKHot(Trie root, String s, int k) {
        List<Pair> list = new ArrayList<>();
        dfs(root, s, list);
        Collections.sort(list, (a, b) 
                         -> (b.times != a.times 
                             ? b.times - a.times : a.str.compareTo(b.str)));
        List<String> res = new ArrayList<>();
        
        for (int i = 0; i < Math.min(k, list.size()); ++i) {
            res.add(list.get(i).str);
        }
        
        return res;
    }
    
    private void dfs(Trie root, String s, List<Pair> list) {
        if (root.times > 0) {   // add root first
            list.add(new Pair(s, root.times));
        }
        
        for (char c = 'a'; c <= 'z'; ++c) {
            int i = getIndex(c);
            if (root.children[i] != null) {
                dfs(root.children[i], s + c, list);
            }
        }
        
        if (root.children[26] != null) {
            dfs(root.children[26], s + ' ', list);
        }
    }
    
    private int getIndex(char c) {
        return c == ' ' ? 26 : c - 'a';
    }
    
    class Pair {
        String str;
        int times;
        
        public Pair(String s, int t) {
            str = s;
            times = t;
        }
    }
    
    class Trie {
        Trie[] children;
        int times;
        
        public Trie() {
            children = new Trie[27];
        }
    }
}
https://www.codetd.com/article/2255285
可以用trie树来解决这个问题。
由于要返回前3个搜索次数最多的句子,我们可以用priority_queue来存储所返回的所有的句子和它的次数的键值对。
首先构造trie tree,主要为trieNode的结构以及insert 方法。
构造完trieNode类后, 这个系统实际上主要为一个巨大的trietree,我们需要一个树的根节点。
由于我们每次都要输入一个字符,我们可以用一个私有的Node:curNode来追踪当前我们节点。
curNode初始化为root,在每次输入完一个句子时,即输入的字符为‘#’时,我们需要将其置为root
同时需要一个string类型stn来表示当前的搜索的句子。

需要注意的是我们priority_queue中存储的为pair<string,int>我们需要给它重写比较器。
所以我们每输入一个字符,首先检查是不是结尾标识“#”,如果是的话,将当前句子加入trie树,重置相关变量,返回空数组。
如不是,检查当前TrieNode对应的child是否含有c的对应节点。如果没有,将curNode置为NULL并且返回空数组。

若存在,将curNode 更新为c对应的节点,并且对curNode进行dfs。
dfs时,我们首先检查当前是不是一个完整的句子,如果是,将句子与其次数同时加入priority_queue中,然后对其child中可能存在的子节点进行dfs。

进行完dfs后,我们需要取出前三个,需要注意的是,可能可选择的结果不满3个,所以要在while中多加入检测q为空的条件语句。
最后要将q中的所有元素都弹出。

https://github.com/awangdev/LintCode/blob/master/Java/Design%20Search%20Autocomplete%20System.java
tags: Design, Trie, Hash Table, MinHeap, PriorityQueue
time: input: O(x), where x = possible words, constructor: O(mn) m = max length, n = # of words
space: O(n^2), n = # of possible words, n = # of trie levels; mainlay saving the `Map<S, freq>`

Description is long, but in short: 做 search auto complete.

Best problem to review Trie (prefix search), Top K frequent elements (Hash Map), and MinHeap (PriorityQueue)

Easier to revisit https://leetcode.com/problems/design-search-autocomplete-system/description/

#### 思考方向
- 做text的search, 毋庸置疑要用Prefix tree, trie.

##### Find all possible word/leaf, 两种方案:
- Trie造好之后, 做prefix search, 然后DFS/BFS return all leaf items. [high runtime complexity]
- 在TrieNode里面存所有的possible words. [high space usage]
- in memory space 应该不是 大问题, 所以我们可以选择 store all possible words

##### Given k words, find top k frequent items. 肯定用MinHeap, 但也有两种方案:
- Store MinHeap with TrieNode: 因为会不断搜索新此条, 同样的prefix (尤其是在higher level), 会被多次搜索.
- [ complexity: need to update heaps across all visited TrieNodes once new sentence is completed]
- Compute MinHeap on the fly: 当然我们不能每次都来一个DFS 不然会很慢, 所以就必须要store list of possible candidates in TrieNode.
- 这里就用到了`Top K Frequent Words` 里面的 `Map<String, freq>`, 这样O(m) 构建 min-heap其实很方便.

##### Train the system
- 每次 `#` 后 标记一个词条被add进search history. 那么就要 `insert it into trie`.
- 这一条在最后遇到`#`再做就可以了, 非常简洁

#### Trie, PriorityQueue, HashMap
- Trie Prefix Search + maintain top k frequent items

    class TrieNode {
        public boolean isEnd;
        public Map<String, Integer> freq;
        public Map<Character, TrieNode> children; // Map is more applicable to all chars, not
                                                  // limited to 256 ASCII

        public TrieNode() {
            this.freq = new HashMap<>();
            this.children = new HashMap<>();
        }
    }
    class Pair {
        String s;
        int count;

        public Pair(String s, int count) {
            this.s = s;
            this.count = count;
        }
    }

    TrieNode root, curr;
    StringBuffer sb;

    public AutocompleteSystem(String[] sentences, int[] times) {
        if (sentences == null || times == null || sentences.length != times.length)
            return;
        reset();
        root = new TrieNode();
        for (int i = 0; i < times.length; i++) {
            insert(sentences[i], times[i]);
        }
    }

    public List<String> input(char c) {
        List<String> rst = new ArrayList<>();
        if (curr == null)
            curr = root;
        if (c == '#') { // save sentence and reset state
            insert(sb.toString(), 1);
            reset();
            return rst;
        }

        // Update global variable (curr TrieNode and string buffer); or append new character if not
        // exist.
        sb.append(c);
        curr.children.putIfAbsent(c, new TrieNode());
        curr = curr.children.get(c);

        // MinHeap to find top 3.
        rst.addAll(findTopK(curr, 3));

        return rst;
    }

    private List<String> findTopK(TrieNode node, int k) {
        List<String> rst = new ArrayList<>();
        if (node.freq.isEmpty())
            return rst;
        PriorityQueue<Pair> queue = new PriorityQueue<>(
                (a, b) -> a.count == b.count ? b.s.compareTo(a.s) : a.count - b.count);
        for (Map.Entry<String, Integer> entry : node.freq.entrySet()) {
            if (queue.size() < 3 || entry.getValue() >= queue.peek().count) {
                queue.offer(new Pair(entry.getKey(), entry.getValue()));
            }
            if (queue.size() > 3)
                queue.poll();
        }

        while (!queue.isEmpty()) {
            rst.add(0, queue.poll().s);
        }

        return rst;
    }

    private void reset() {
        curr = null;
        sb = new StringBuffer();
    }

    private void insert(String sentence, int count) {
        if (sentence == null || sentence.length() == 0)
            return;
        TrieNode node = root;
        for (char c : sentence.toCharArray()) {
            node.children.putIfAbsent(c, new TrieNode());
            node = node.children.get(c);
            node.freq.put(sentence, node.freq.getOrDefault(sentence, 0) + count);
        }
        node.isEnd = true; // can set word to node as well, if needed

    }
https://discuss.leetcode.com/topic/96150/java-solution-trie-and-priorityqueue
https://flycode.co/archives/70567
    class TrieNode {
        Map<Character, TrieNode> children;
        Map<String, Integer> counts;
        boolean isWord;
        public TrieNode() {
            children = new HashMap<Character, TrieNode>();
            counts = new HashMap<String, Integer>();
            isWord = false;
        }
    }
    
    class Pair {
        String s;
        int c;
        public Pair(String s, int c) {
            this.s = s; this.c = c;
        }
    }
    
    TrieNode root;
    String prefix;
    
    
    public AutocompleteSystem(String[] sentences, int[] times) {
        root = new TrieNode();
        prefix = "";
        
        for (int i = 0; i < sentences.length; i++) {
   add(sentences[i], times[i]);
  }
    }
    
    private void add(String s, int count) {
        TrieNode curr = root;
        for (char c : s.toCharArray()) {
            TrieNode next = curr.children.get(c);
            if (next == null) {
                next = new TrieNode();
                curr.children.put(c, next);
            }
            curr = next;
            curr.counts.put(s, curr.counts.getOrDefault(s, 0) + count);
        }
        curr.isWord = true;
    }
    
    public List<String> input(char c) {
        if (c == '#') {
            add(prefix, 1);
            prefix = "";
            return new ArrayList<String>();
        }
        
        prefix = prefix + c;
        TrieNode curr = root;
  for (char cc : prefix.toCharArray()) {
   TrieNode next = curr.children.get(cc);
   if (next == null) {
    return new ArrayList<String>();
   }
   curr = next;
  }
        
        PriorityQueue<Pair> pq = new PriorityQueue<>((a, b) -> (a.c == b.c ? a.s.compareTo(b.s) : b.c - a.c));
        for (String s : curr.counts.keySet()) {
            pq.add(new Pair(s, curr.counts.get(s)));
        }

        List<String> res = new ArrayList<String>();
        for (int i = 0; i < 3 && !pq.isEmpty(); i++) {
            res.add(pq.poll().s);
        }
        return res;
    }

X. http://www.cnblogs.com/grandyang/p/7897166.html
    AutocompleteSystem(vector<string> sentences, vector<int> times) {
        for (int i = 0; i < sentences.size(); ++i) {
            freq[sentences[i]] += times[i]; 
        }
        data = "";
    }
    
    vector<string> input(char c) {
        if (c == '#') {
            ++freq[data];
            data = "";
            return {};
        }
        data.push_back(c);
        auto cmp = [](pair<string, int>& a, pair<string, int>& b) {
            return a.second > b.second || (a.second == b.second && a.first < b.first);
        };
        priority_queue<pair<string, int>, vector<pair<string, int>>, decltype(cmp) > q(cmp);
        for (auto f : freq) {
            bool matched = true;
            for (int i = 0; i < data.size(); ++i) {
                if (data[i] != f.first[i]) {
                    matched = false;
                    break;
                }
            }
            if (matched) {
                q.push(f);
                if (q.size() > 3) q.pop();
            }
        }
        vector<string> res(q.size());
        for (int i = q.size() - 1; i >= 0; --i) {
            res[i] = q.top().first; q.pop();
        }
        return res;
    }
    
private:
    unordered_map<string, int> freq;
    string data;
思路:直接用能排序的TreeMap,因为可能出现计数值相等的情况(在这个情况下根据String的字典顺序),所以key用一个封装的对象Node,但是对象除非重写equals方法,不然在map里面找不到,所以额外用一个HashMap来存储String到Node的映射,而且因为这里String用的是搜索的内容,所以唯一

public class AutocompleteSystem {

    class Node {
        int cnt;
        String content;

        private Node(int cnt, String content) {
            this.cnt = cnt;
            this.content = content;
        }
    }

    StringBuilder sb = new StringBuilder();

    TreeMap<Node, String> map = new TreeMap<Node, String>(new Comparator<Node>() {
        @Override
        public int compare(Node o1, Node o2) {
            if (o1.cnt == o2.cnt)
                return o1.content.compareTo(o2.content);
            return o2.cnt - o1.cnt;
        }
    });
    Map<String, Node> m = new HashMap<String, Node>();

    public AutocompleteSystem(String[] sentences, int[] times) {
        for (int i = 0; i < sentences.length; i++) {
            Node t = new Node(times[i], sentences[i]);
            map.put(t, sentences[i]);
            m.put(sentences[i], t);
        }
    }

    public List<String> input(char c) {
        if (c == '#') {
            String s = sb.toString();
            if (m.containsKey(s)) {
                Node t = m.get(s);
                map.remove(t);
                t.cnt = t.cnt + 1;
                map.put(t, t.content);
            } else {
                Node t = new Node(1, s);
                m.put(s, t);
                map.put(t, s);
            }

            sb = new StringBuilder();
            return new ArrayList<String>();
        }

        if (c != '#')
            sb.append(c);
        List<String> ret = new ArrayList<String>();
        String prefix = sb.toString();
        for (Node k : map.keySet()) {
            if (k.content.startsWith(prefix)) {
                ret.add(k.content);
                if (ret.size() == 3)
                    break;
            }
        }

        return ret;
    }
}

https://www.jiuzhang.com/qa/6999/
申请空间越大,消耗的时间会越多,你可以在本地的ide中尝试一下

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