{x}
blog image

Sequentially Ordinal Rank Tracker

A scenic location is represented by its name and attractiveness score, where name is a unique string among all locations and score is an integer. Locations can be ranked from the best to the worst. The higher the score, the better the location. If the scores of two locations are equal, then the location with the lexicographically smaller name is better.

You are building a system that tracks the ranking of locations with the system initially starting with no locations. It supports:

  • Adding scenic locations, one at a time.
  • Querying the ith best location of all locations already added, where i is the number of times the system has been queried (including the current query).
    • For example, when the system is queried for the 4th time, it returns the 4th best location of all locations already added.

Note that the test data are generated so that at any time, the number of queries does not exceed the number of locations added to the system.

Implement the SORTracker class:

  • SORTracker() Initializes the tracker system.
  • void add(string name, int score) Adds a scenic location with name and score to the system.
  • string get() Queries and returns the ith best location, where i is the number of times this method has been invoked (including this invocation).

 

Example 1:

Input
["SORTracker", "add", "add", "get", "add", "get", "add", "get", "add", "get", "add", "get", "get"]
[[], ["bradford", 2], ["branford", 3], [], ["alps", 2], [], ["orland", 2], [], ["orlando", 3], [], ["alpine", 2], [], []]
Output
[null, null, null, "branford", null, "alps", null, "bradford", null, "bradford", null, "bradford", "orland"]

Explanation
SORTracker tracker = new SORTracker(); // Initialize the tracker system.
tracker.add("bradford", 2); // Add location with name="bradford" and score=2 to the system.
tracker.add("branford", 3); // Add location with name="branford" and score=3 to the system.
tracker.get();              // The sorted locations, from best to worst, are: branford, bradford.
                            // Note that branford precedes bradford due to its higher score (3 > 2).
                            // This is the 1st time get() is called, so return the best location: "branford".
tracker.add("alps", 2);     // Add location with name="alps" and score=2 to the system.
tracker.get();              // Sorted locations: branford, alps, bradford.
                            // Note that alps precedes bradford even though they have the same score (2).
                            // This is because "alps" is lexicographically smaller than "bradford".
                            // Return the 2nd best location "alps", as it is the 2nd time get() is called.
tracker.add("orland", 2);   // Add location with name="orland" and score=2 to the system.
tracker.get();              // Sorted locations: branford, alps, bradford, orland.
                            // Return "bradford", as it is the 3rd time get() is called.
tracker.add("orlando", 3);  // Add location with name="orlando" and score=3 to the system.
tracker.get();              // Sorted locations: branford, orlando, alps, bradford, orland.
                            // Return "bradford".
tracker.add("alpine", 2);   // Add location with name="alpine" and score=2 to the system.
tracker.get();              // Sorted locations: branford, orlando, alpine, alps, bradford, orland.
                            // Return "bradford".
tracker.get();              // Sorted locations: branford, orlando, alpine, alps, bradford, orland.
                            // Return "orland".

 

Constraints:

  • name consists of lowercase English letters, and is unique among all locations.
  • 1 <= name.length <= 10
  • 1 <= score <= 105
  • At any time, the number of calls to get does not exceed the number of calls to add.
  • At most 4 * 104 calls in total will be made to add and get.

Solution Explanation for Sequentially Ordinal Rank Tracker

This problem requires designing a system that tracks the ranking of scenic locations based on their attractiveness scores and names. The system needs to efficiently handle adding new locations and querying the i-th best location (where i is the query number).

Two efficient solutions are presented: using an Ordered Set and using a pair of Priority Queues (Min-Max Heaps).

Solution 1: Ordered Set

This approach leverages the power of an ordered set (like SortedList in Python or tree in C++ with the tree_order_statistics_node_update tag) to maintain the locations in sorted order. The key is to cleverly use the ordering criteria:

  1. Sorting Criteria: Locations are sorted primarily by score in descending order (higher score is better). If scores are equal, they're sorted lexicographically in ascending order (smaller name is better). To achieve this, we store locations as pairs (-score, name) in the ordered set. The negative score ensures descending order for scores.

  2. Adding Locations (add method): Simply insert the (-score, name) pair into the ordered set. The ordered set automatically maintains the sorted order.

  3. Querying Locations (get method): A counter i tracks the query number. The i-th best location is directly accessible using the find_by_order(i) method of the ordered set (Python's SortedList uses indexing similarly).

Time Complexity: Both add and get operations have a time complexity of O(log n), where n is the number of locations. This is because insertion and retrieval in a balanced binary search tree (underlying data structure of ordered sets) takes logarithmic time.

Space Complexity: O(n) to store the locations in the ordered set.

Solution 2: Double Priority Queue (Min-Max Heaps)

This solution employs two priority queues:

  1. good (Min-Heap): Stores the top-ranked locations encountered so far. It's a min-heap, so the smallest element (worst location) is at the top.

  2. bad (Max-Heap): Stores locations that are worse than the current top i locations. It's a max-heap, so the largest element (best among the 'worse' locations) is at the top.

The logic is as follows:

  1. Adding Locations (add method): A new location is initially added to good. Then, the worst location from good (the top element) is moved to bad. This ensures good always contains the top i locations.

  2. Querying Locations (get method): The best location from bad (top element) is moved to good, and the worst location from good (top element) is returned.

Time Complexity: Similar to the ordered set approach, both add and get operations have a time complexity of O(log n). Heap operations (insertion, deletion, retrieval) take logarithmic time.

Space Complexity: O(n), as we store locations in both heaps.

Code Examples

The code examples in Python, Java, and C++ are provided above in the solution section. They implement both the Ordered Set and the Double Priority Queue solutions. Note that the C++ solution uses the GNU extension __gnu_pbds for the ordered set. In Java, we use PriorityQueue for heaps and Map.Entry to conveniently store score-name pairs. Python uses its built-in heapq module and SortedList from the sortedcontainers library. Remember to install sortedcontainers if you use the Python Ordered Set solution (pip install sortedcontainers).