Frontend School

Dynamic Restaurant Ratings

DSA
medium

Dynamic Restaurant Ratings

Medium
Segment Tree
Data Structures
Range Query

Overview

At Zomato, real-time insights into restaurant performance, especially customer ratings, are crucial for operational decisions, marketing strategies, and improving customer satisfaction. This problem simulates a core system responsible for tracking and analyzing restaurant ratings dynamically. You will implement a data structure that efficiently handles updates to individual restaurant ratings and queries for the average rating across a range of restaurants.

What you need to do / Task

Your task is to implement the RestaurantRatings class with the following methods:

  1. constructor(initialRatings: number[]):

    • Initializes the data structure with an array of initial ratings for restaurants.
    • The i-th element in initialRatings corresponds to the rating of the restaurant at index i.
  2. updateRating(restaurantIndex: number, newRating: number): void:

    • Updates the rating of the restaurant at restaurantIndex to newRating.
  3. getAverageRating(startIndex: number, endIndex: number): number:

    • Returns the average rating of all restaurants within the inclusive range [startIndex, endIndex].

Input & output

constructor(initialRatings: number[])

  • initialRatings: An array of number representing the initial ratings of restaurants. Each rating is a floating-point value.
  • Returns: void (constructor returns null in test cases).

updateRating(restaurantIndex: number, newRating: number): void

  • restaurantIndex: An number representing the 0-based index of the restaurant whose rating is to be updated.
  • newRating: A number representing the new rating for the specified restaurant.
  • Returns: void.

getAverageRating(startIndex: number, endIndex: number): number

  • startIndex: An number representing the 0-based starting index of the range (inclusive).
  • endIndex: An number representing the 0-based ending index of the range (inclusive).
  • Returns: A number (floating-point) representing the average rating of restaurants in the given range. The result should be accurate to at least 5 decimal places.

Clarifications

  • All restaurant indices are 0-based.
  • The startIndex and endIndex for getAverageRating are inclusive.
  • You can assume that startIndex <= endIndex for all queries.

Examples

1

Example 1

Input:

operations = ["RestaurantRatings","getAverageRating","updateRating","getAverageRating","getAverageRating"], params = [[[3.5, 4.0, 2.5, 5.0]], [0, 3], [1, 4.5], [0, 1], [2, 3]]

Output:

[null,3.75,null,4.0,3.75]

Note:

  1. Initialize with ratings [3.5, 4.0, 2.5, 5.0].
  2. Get average for [0, 3]: (3.5 + 4.0 + 2.5 + 5.0) / 4 = 15.0 / 4 = 3.75.
  3. Update rating at index 1 to 4.5. Ratings become [3.5, 4.5, 2.5, 5.0].
  4. Get average for [0, 1]: (3.5 + 4.5) / 2 = 8.0 / 2 = 4.0.
  5. Get average for [2, 3]: (2.5 + 5.0) / 2 = 7.5 / 2 = 3.75.
2

Example 2

Input:

operations = ["RestaurantRatings","getAverageRating","updateRating","getAverageRating"], params = [[[1.0]], [0, 0], [0, 5.0], [0, 0]]

Output:

[null,1.0,null,5.0]

Note:

  1. Initialize with ratings [1.0].
  2. Get average for [0, 0]: 1.0 / 1 = 1.0.
  3. Update rating at index 0 to 5.0. Ratings become [5.0].
  4. Get average for [0, 0]: 5.0 / 1 = 5.0.

Constraints

Constraints & assumptions

  • 1 <= initialRatings.length <= 10^5
  • 0.0 <= initialRatings[i] <= 5.0
  • 0 <= restaurantIndex < initialRatings.length
  • 0.0 <= newRating <= 5.0
  • 0 <= startIndex <= endIndex < initialRatings.length
  • The total number of calls to updateRating and getAverageRating will not exceed 10^5.
  • The average rating should be calculated with high precision (e.g., using standard floating-point types).

What interviewers evaluate

  • Correctness: The Segment Tree implementation correctly computes range sums and handles point updates.
  • Efficiency: Operations updateRating and getAverageRating run in O(log N) time complexity, and the constructor in O(N).
  • Edge Cases: Proper handling of single-element ranges, full-array ranges, and floating-point arithmetic.
  • Code Quality: Clear, well-structured, and maintainable code with appropriate use of data structures.

Loading editor...