We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Sequentially Ordinal Rank Tracker

Difficulty: Hard

Problem Description

You need to implement a system that tracks the ranking of scenic locations based on their attractiveness score. Each location has a unique name and a score, and the system should return the best locations in order of their scores and names. You can add locations and query for the ith best location based on the number of queries made.

Key Insights

  • Locations are ranked primarily by their attractiveness score in descending order.
  • In case of ties in scores, locations are ranked lexicographically by their names in ascending order.
  • The get method should return the ith best location based on the number of times it has been called, which increments with each call.
  • Efficient data structures are needed to maintain the order and allow for fast insertions and queries.

Space and Time Complexity

Time Complexity:

  • Adding a location takes O(log n) due to the sorting operation.
  • Querying the ith location takes O(1) since we can directly access the required index after sorting.

Space Complexity:

  • O(n) to store the locations.

Solution

To solve the problem, we will use a list to store the locations and their scores. Each time a location is added, we will insert it into the list in a way that maintains the order (using a binary search for efficient insertion). When querying for the ith best location, we simply return the (i-1) index from the sorted list. We will use the sorted function combined with a custom sort key to handle the ranking conditions efficiently.

Code Solutions

class SORTracker:
    def __init__(self):
        self.locations = []  # To store (score, name) tuples
        self.query_count = 0  # To track the number of queries

    def add(self, name: str, score: int) -> None:
        # Add the location as a tuple (-score, name) to sort by score and name
        self.locations.append((-score, name))
        self.locations.sort()  # Sort by score descending and name ascending

    def get(self) -> str:
        self.query_count += 1  # Increment the query count
        # Return the name of the (query_count-1)'th location (0-based index)
        return self.locations[self.query_count - 1][1]
← Back to All Questions