This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| """ | |
| BBB #51. Kth Most Frequent String | |
| Given a list of strings, | |
| write a function to get the kth most frequently occurring string. | |
| Eg. kthMostFrequent(["a","b","c","a","b","a"], 0) = "a" | |
| Eg. kthMostFrequent(["a","b","c","a","b","a"], 1) = "b" | |
| Eg. kthMostFrequent(["a","b","c","a","b","a"], 2) = "c" | |
| Eg. kthMostFrequent(["a","b","c","a","b","a"], 3) = None | |
| Possible prelim quesitons: | |
| Q1) what if # of element set in an array > k value? what to print out? | |
| Q2) what if there are more than one elements having same frequency? what to print out? | |
| """ | |
| def kthMostFrequent(A, kth): | |
| # 1st pass: construct D1 dict: (k, v) = (char, count) | |
| D1 = dict() | |
| for a in A: | |
| if not D1.get(a): D1[a] = 1 | |
| else: D1[a] += 1 | |
| # 2nd pass: construct D2 dict: (k, v) = (v, k) | |
| D2 = dict() | |
| for k, v in D1.items(): | |
| if not D2.get(v): D2[v] = [k] | |
| else: D2[v].append(k) | |
| # 3rd pass: from sorted D2.keys(), print kth char | |
| sortedKeys = sorted(D2.keys(), reverse=True) # descending order | |
| for i, k in enumerate(sortedKeys): | |
| if kth == i: | |
| kthFreq = ','.join([v for v in D2[k]]) | |
| print(kthFreq) | |
| return | |
| print(None) | |
| """ | |
| # 2nd/3rd passes combined | |
| sortedD1 = sorted(D1.items(), key=lambda x:x[1], reverse=True) | |
| print(sortedD1) | |
| for i, (k,v) in enumerate(sortedD1): # descending order | |
| if kth == i: | |
| print(k) | |
| """ | |
| ### | |
| A=["a","b","c","a","b","a","b"] | |
| kth = 0 | |
| kthMostFrequent(A, kth) |