Clash Royale CLAN TAG

Top K Frequent Words (Map Reduce) on lintcode online judge

I have met a problem when trying to solve 549. Top K Frequent Words (Map Reduce) on Lintcode. I tried my best to debug but still don't understand why my code cannot be 100% accepted.

class Node{
String key;
Integer count;
Node(String k, Integer c){
key = k; count = c;
}
}
public class TopKFrequentWords {
public static class Map {
public void map(String tmp_, Document value,
OutputCollector<String, Integer> output) {
String words = value.content.split(" ");
for(String word: words){
if(word.length() > 0) output.collect(word, 1);
}
}
}

public static class Reduce {
private Queue<Node> min_heap;
private int K;
private Comparator<Node> nodeComparator = new Comparator<Node>(){
public int compare(Node a, Node b){
return (a.count != b.count) ? a.count - b.count : b.key.compareTo(a.key);
}
};
public void setup(int k) {
min_heap = new PriorityQueue<Node>(k, nodeComparator);
K = k;
}

public void reduce(String key, Iterator<Integer> values) {
Integer sum = 0;
while(values.hasNext()) sum += values.next();
Node res = new Node(key, sum);
if(min_heap.size() < K) min_heap.offer(res);
else{
if(nodeComparator.compare(res, min_heap.peek()) > 0){
min_heap.poll();
min_heap.offer(res);
}
}
}

public void cleanup(OutputCollector<String, Integer> output) {
Stack<Node> stack = new Stack<>();
while(!min_heap.isEmpty()) stack.push(min_heap.poll());
while(!stack.isEmpty()){
Node cur = stack.pop();
output.collect(cur.key, cur.count);
}
}
}
}


This is my first time posting a question. Can anyone help me? Thanks!
In one test case, my output is:

"e", 984
"g", 972
"d", 953
"h", 952
"a", 933
"f", 928
"b", 925
"c", 873
"fg", 168
"hf", 164
"ha", 159
"ec", 152
"fa", 151
"da", 151
"gf", 150
"bd", 149
"ah", 146
"eh", 146
"bc", 145
"hc", 143


but the answer is:

"e", 984
"g", 972
"d", 953
"h", 952
"a", 933
"f", 928
"b", 925
"c", 873
"fg", 168
"hf", 164
"ha", 159
"ec", 152
"da", 151
"fa", 151
"gf", 150
"bd", 149
"ah", 146
"eh", 146
"bc", 145
"ba", 143


Seems that problem occurs in "fa", "da" and last line when having same count and sorting by alpha order. But how can I modify my comparator code?

1 Answer
1

Minor tweak to your comparator. In their solution, they compare by count first and then alphabetically. In your solution though you compare by count first which is good and then you compare alphabetically but in reverse order:

count

alphabetically

count

alphabetically

reverse

public int compare(Node a, Node b){
// Change
// return (a.count != b.count) ? a.count - b.count : b.key.compareTo(a.key);
// To
return (a.count != b.count) ? a.count - b.count : a.key.compareTo(b.key);
}


By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.