Amazon Online Assessment (OA) 2021 - Top K Frequently Mentioned Keywords | SHL
Practice on leetcode here: https://leetcode.com/problems/top-k-frequent-words/
1from collections import Counter
2from heapq import heappop, heappush
3import re
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 {match[0].lower() for match in patt.finditer(review)}
18 )
19 queue: list[tuple[int, Down]] = []
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))
351import 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