I am trying to solve the problem at https://leetcode.com/problems/design-a-food-rating-system and this is my solution.
class FoodRatings {
class SortedSetComparator implements Comparator<String> {
public int compare(String A, String B) {
if (foodRatingMap.get(A) == foodRatingMap.get(B)) {
return A.compareTo(B);
}
return foodRatingMap.get(B).compareTo(foodRatingMap.get(A));
}
}
Map<String, SortedSet<String>> foodTypeMap;
Map<String, String> foodMap;
Map<String, Integer> foodRatingMap;
public FoodRatings(String[] foods, String[] cuisines, int[] ratings) {
foodTypeMap = new HashMap<>();
foodMap = new HashMap<>();
foodRatingMap = new HashMap<>();
for (int i = 0; i<foods.length; i ) {
foodTypeMap.putIfAbsent(cuisines[i], new TreeSet<String> (new SortedSetComparator()));
foodMap.put(foods[i], cuisines[i]);
foodRatingMap.put(foods[i], ratings[i]);
foodTypeMap.get(cuisines[i]).add(foods[i]);
}
}
public void changeRating(String food, int newRating) {
foodRatingMap.put(food, newRating);
SortedSet<String> set = foodTypeMap.get(foodMap.get(food));
if (!set.remove(food)) {
System.out.println("Unable to find " food);
}
foodTypeMap.get(foodMap.get(food)).add(food);
}
public String highestRated(String cuisine) {
return foodTypeMap.get(cuisine).first();
}
}
Could anyone tell me why the TreeSet remove() method is not working ?
Here is the input for the same.
public static void main(String args[]) {
String[] foods = new String[] {
"czopaaeyl", "lxoozsbh", "kbaxapl"
};
String[] cuisines = new String[] {
"dmnuqeatj", "dmnuqeatj", "dmnuqeatj"
};
int[] ratings = new int[] {
11, 2, 15
};
FoodRatings obj = new MyClass().new FoodRatings(foods, cuisines, ratings);
obj.changeRating("czopaaeyl", 12);
String food = obj.highestRated("dmnuqeatj");
System.out.println(food);
obj.changeRating("kbaxapl", 8);
food = obj.highestRated("dmnuqeatj");
System.out.println(food);
obj.changeRating("lxoozsbh", 5);
food = obj.highestRated("dmnuqeatj");
System.out.println(food);
}
I am not sure why the remove function is not working properly here.
CodePudding user response:
Well, it took me a while to find the problem. Besides the Integer compare issue which is only needed to sort equal ratings in lexical order. You were updating the ratings prior to doing a remove. But since your set uses this structure in its comparator, things got out of sync.
public void changeRating(String food, int newRating) {
SortedSet<String> set = foodTypeMap.get(foodMap.get(food));
if (!set.remove(food)) {
System.out.println("Unable to find " food);
}
foodTypeMap.get(foodMap.get(food)).add(food);
foodRatingMap.put(food, newRating);
}
As soon as I moved foodRatingMap.put(food, newRating);
to the bottom, it worked. BTW, I would have written a Food class
hold each foods type, rating, and cuisine. Usually these test sites are only interested in results and efficiency, not how you did it.
CodePudding user response:
Well. That was a very subtle issue to find. First the order in which the ratings were updated are wrong. The correct order was :-
- Remove the food from the sortedSet.
- Update the rating.
- Add the food back to the sorted set.
Changes were done in two places. The first one was to correct the order.
public void changeRating(String food, int newRating) {
foodTypeMap.get(foodMap.get(food)).remove(food);
foodRatingMap.put(food, newRating);
foodTypeMap.get(foodMap.get(food)).add(food);
}
The second one was to use equals() when comparing integer values in the comparator.
class SortedSetComparator implements Comparator<String> {
public int compare(String A, String B) {
if (foodRatingMap.get(A).equals(foodRatingMap.get(B))) {
return A.compareTo(B);
}
return foodRatingMap.get(B).compareTo(foodRatingMap.get(A));
}
}