Page Contents
Top K Frequent Words Solution
Given a non-empty list of words, return the k most frequent elements. Your answer should be sorted by frequency from highest to lowest. If two words have the same frequency, then the word with the lower alphabetical order comes first.
Also See: Amazon OA Online Assessment 2021 Questions and Answers
Example 1:
Input: ["i", "love", "leetcode", "i", "love", "coding"], k = 2 Output: ["i", "love"] Explanation: "i" and "love" are the two most frequent words. Note that "i" comes before "love" due to a lower alphabetical order.
Example 2:
Input: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4 Output: ["the", "is", "sunny", "day"] Explanation: "the", "is", "sunny" and "day" are the four most frequent words, with the number of occurrence being 4, 3, 2 and 1 respectively.
Note:
- You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
- Input words contain only lowercase letters.
Follow up:
- Try to solve it in O(n log k) time and O(n) extra space.
Solution
Program C++
static bool mycmp(pair<string,int> a,pair<string,int>b){ if(a.second==b.second){ return a.first<b.first; } return a.second>b.second; } vector<string> topKFrequent(vector<string>& words, int k) { map<string,int> mp; for(auto x:words){ mp[x]++; } vector<pair<string,int>> ans(mp.begin(),mp.end()); sort(ans.begin(),ans.end(),mycmp); vector<string> res; int i=0; while(k--){ res.push_back(ans[i].first); i++; } return res; }
Program Java
class Solution { public List topKFrequent(String[] words, int k) { if (words == null || words.length == 0) { return Collections.emptyList(); } Map<String, Integer> wordMap = new HashMap<>(); for (String word : words) { int count = wordMap.get(word) == null ? 0 : wordMap.get(word); wordMap.put(word, ++count); } PriorityQueue<PElement> pq = new PriorityQueue<>(new PElementComparator()); for (Map.Entry<String, Integer> entry : wordMap.entrySet()) { PElement p = new PElement(entry.getKey(), entry.getValue()); pq.add(p); } List<String> result = new ArrayList<>(); for (int i = 0; i < k; i++) { PElement element = pq.poll(); result.add(element.word); } return result; } private static class PElement { String word; int count; public PElement(String word, int count) { this.word = word; this.count = count; } public String getWord() { return word; } public int getCount() { return count; } } private static class PElementComparator implements Comparator<PElement> { public int compare(PElement p1, PElement p2) { if (p1 == p2) { return 0; } if (p1.getCount() > p2.getCount()) { return -1; } if (p2.getCount() > p1.getCount()) { return 1; } return p1.getWord().compareTo(p2.getWord()); } } }
Program Python
import heapq class OppositeString: def __init__(self, word): self.word = word def __lt__(self, other): return self.word > other.word def __eq__(self, other): return self.word == other.word class Solution: def topKFrequent(self, words: List[str], k: int) -> List[str]: wordsDict = Counter(words) heap = [] heapify(heap) for w in wordsDict: heappush(heap, (wordsDict[w], OppositeString(w))) if len(heap) > k: heappop(heap) ans = ['']*k for i in range(k-1, -1, -1): ans[i] = heappop(heap)[1].word return ans
Also See: AMCAT Study Materials, Preparation Guide
Also See: Microsoft Online Assessment Questions and Solution
Amazon Online Assessment Questions:
- Robot Bounded in Box
- Number Game
- Find All Combination of Numbers Sum to Target / Shopping Options
- Fill the Truck
- Music Pairs
- Slowest key
- Five Star Seller
- Split String Into Unique Primes
- Storage Optimization
- Minimum Difficulty of a Job Schedule
- Autoscale Policy, Utilization Check
- Optimal Utilization
- Merge Two Sorted Lists
- Two Sum Unique Pairs
- Shopping Patterns
- Reorder Data in Log Files
- Top K Frequent Words
- Trees Height
- Counting Binary Substrings Amazon OA Solution
- Grid Connections Amazon OA Solution
- Shipment Imbalance Amazon OA Solution
- Max Profit Amazon OA Solution
- Find Lowest Price Amazon OA Solution
- Simple Cipher Amazon OA Solution
- Decode String Frequency Amazon OA Solution
- Valid Discount Coupons Amazon OA Solution
- Count Maximum Teams Amazon OA Solution
- Minimum Coin Flips Amazon OA Solution