LeetCode Entry

2353. Design a Food Rating System

17.12.2023 medium 2023 kotlin

Given foods, cuisines and ratings implement efficient methods changeRating(food, newRating) and highestRated(cuisine)

2353. Design a Food Rating System medium blog post substack image.png

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 method

  • Space 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()]
}