Amazon Online Assessment (OA) 2021 - Top K Frequently Mentioned Keywords | SHL

Practice on leetcode here: https://leetcode.com/problems/top-k-frequent-words/

1from heapq import heappop, heappush
2import re
3from typing import Counter, List
4
5class Down:
6    def __init__(self, value):
7        self.value = value
8
9    def __lt__(self, other):
10        return self.value > other.value
11
12def top_mentioned(k: int, keywords: List[str], reviews: List[str]) -> List[str]:
13    patt = re.compile(r'\b(:?{})\b'.format('|'.join(keywords)), flags=re.IGNORECASE)
14    counts = Counter(
15        word
16        for review in reviews
17        for word in set(match[0].lower() for match in patt.finditer(review))
18    )
19    queue = []
20    for word, count in counts.items():
21        heappush(queue, (count, Down(word)))
22        if len(queue) > k:
23            heappop(queue)
24    res = []
25    while len(queue) > 0:
26        res.append(heappop(queue)[1].value)
27    return res[::-1]
28
29if __name__ == '__main__':
30    k = int(input())
31    keywords = [input() for _ in range(int(input()))]
32    reviews = [input() for _ in range(int(input()))]
33    res = top_mentioned(k, keywords, reviews)
34    print(' '.join(res))
35
1import java.util.ArrayList;
2import java.util.Collections;
3import java.util.HashMap;
4import java.util.HashSet;
5import java.util.List;
6import java.util.Map;
7import java.util.PriorityQueue;
8import java.util.Scanner;
9import java.util.regex.Matcher;
10import java.util.regex.Pattern;
11
12class Solution {
13    public static List<String> topMentioned(int k, List<String> keywords, List<String> reviews) {
14        Pattern patt = Pattern.compile("\\b(:?" + String.join("|", keywords) + ")\\b", Pattern.CASE_INSENSITIVE);
15        HashMap<String, Integer> counts = new HashMap<>();
16        for (String review : reviews) {
17            Matcher m = patt.matcher(review);
18            HashSet<String> words = new HashSet<>();
19            while (m.find())
20                words.add(m.group(0).toLowerCase());
21            for (String word : words)
22                counts.merge(word, 1, Integer::sum);
23        }
24        PriorityQueue<Map.Entry<Integer, String>> queue = new PriorityQueue<>((a, b) -> {
25            if (a.getKey() != b.getKey())
26                return Integer.compare(a.getKey(), b.getKey());
27            return -a.getValue().compareTo(b.getValue());
28        });
29        for (Map.Entry<String, Integer> entry : counts.entrySet()) {
30            queue.offer(Map.entry(entry.getValue(), entry.getKey()));
31            if (queue.size() > k)
32                queue.poll();
33        }
34        ArrayList<String> res = new ArrayList<>();
35        while (!queue.isEmpty())
36            res.add(queue.poll().getValue());
37        Collections.reverse(res);
38        return res;
39    }
40
41    public static void main(String[] args) {
42        Scanner scanner = new Scanner(System.in);
43        int k = Integer.parseInt(scanner.nextLine());
44        int keywordsLength = Integer.parseInt(scanner.nextLine());
45        List<String> keywords = new ArrayList<>();
46        for (int i = 0; i < keywordsLength; i++) {
47            keywords.add(scanner.nextLine());
48        }
49        int reviewsLength = Integer.parseInt(scanner.nextLine());
50        List<String> reviews = new ArrayList<>();
51        for (int i = 0; i < reviewsLength; i++) {
52            reviews.add(scanner.nextLine());
53        }
54        scanner.close();
55        List<String> res = topMentioned(k, keywords, reviews);
56        System.out.println(String.join(" ", res));
57    }
58}
59

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫