# 17.12.2023 [2353. Design a Food Rating System]
Given foods, cuisines and ratings implement efficient methods changeRating(food, newRating) and highestRated(cuisine)
17.12.2023
2353. Design a Food Rating System medium
blog post
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/442
Problem TLDR
Given foods, cuisines and ratings implement efficient methods changeRating(food, newRating) and highestRated(cuisine)
Intuition
Given that we must maintain sorted order by rating
and be able to change the rating, the TreeSet
may help, as it provides O(logN) amortized time for remove(obj)
.
Approach
Start with inefficient implementation, like do the linear search in both methods. Then decide what data structures can help to quickly find an item.
keep in mind, that
constructor
should also be efficient
Complexity
Time complexity:
O(log(n)) for either methodSpace complexity:
O(n)
Code
class FoodRatings(val foods: Array<String>, val cuisines: Array<String>, val ratings: IntArray) {
val foodToInd = foods.indices.groupBy { foods[it] }
val cuisineToInds: MutableMap<String, TreeSet<Int>> = mutableMapOf()
init {
for (ind in cuisines.indices)
cuisineToInds.getOrPut(cuisines[ind]) {
TreeSet(compareBy({ -ratings[it] }, { foods[it] }))
} += ind
}
fun changeRating(food: String, newRating: Int) {
val ind = foodToInd[food]!![0]
if (ratings[ind] != newRating) {
val sortedInds = cuisineToInds[cuisines[ind]]!!
sortedInds.remove(ind)
ratings[ind] = newRating
sortedInds.add(ind)
}
}
fun highestRated(cuisine: String): String = foods[cuisineToInds[cuisine]!!.first()]
}