-2

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.

Abascus
  • 127
  • 2
  • 10
  • I don't think I am using == anywhere for comparing the strings. – Abascus Jul 24 '22 at 17:39
  • Please update your question with a main method so it can be run with test code. – WJS Jul 24 '22 at 17:44
  • 1
    Actuall, the problem is still comparing objects. Use equals for the map values. too. Try this to see the problem. `System.out.println(Integer.valueOf(29292) == Integer.valueOf(29292));` – WJS Jul 24 '22 at 17:48
  • Is there anyway to do that in a TreeSet ? It is very weird that we can't even do such basic operations on data types such as strings. – Abascus Jul 24 '22 at 17:51
  • Any example ? I am not sure I really quite follow how to do that. – Abascus Jul 24 '22 at 17:55
  • That didn't work. – Abascus Jul 24 '22 at 18:03
  • Also, foodRatingMap.get(A) returns an Integer not string. – Abascus Jul 24 '22 at 18:04
  • change the rating, which is used by the `Comparator`, AFTER removing the food form the Set - by changing the rating but not the order, the Set is unable to correctly find the entry – user16320675 Jul 24 '22 at 18:23
  • You were right. It is the order that matters here. I would update the answer to include that. – Abascus Jul 24 '22 at 18:43
  • The problem is with the implementation of your compare method. If you were to do a simple a.compareTo(b) you would get the results you wanted. Could you explain the logic you are trying to implement in the compare method? It looks to me it may be violating the compareTo contract. – YokedSinger8062 Jul 24 '22 at 19:13
  • If you change the comparison position of an element that's already in a TreeSet, what you get is a corrupt data structure that will give you many mysterious bugs. Don't do that. – Louis Wasserman Jul 24 '22 at 21:14

2 Answers2

1

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.

WJS
  • 36,363
  • 4
  • 24
  • 39
0

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));
        }
    }
Abascus
  • 127
  • 2
  • 10