Home > database >  Why is remove() for TreeSet<String> not working?
Why is remove() for TreeSet<String> not working?

Time:07-25

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 :-

  1. Remove the food from the sortedSet.
  2. Update the rating.
  3. 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));
        }
    }
  • Related