Sequentially Ordinal Rank Tracker

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

from sortedcontainers import SortedList

class SORTracker:
    def __init__(self):
        self.sortedList = SortedList()
        self.i = 0

    def add(self, name: str, score: int) -> None:
        self.sortedList.add([-score, name])

    def get(self) -> str:
        answer = self.sortedList[self.i][1]
        self.i += 1
        return answer

Identifying Problem Isomorphism

“Sequentially Ordinal Rank Tracker” can be approximately mapped to “Top K Frequent Elements”.

“Sequentially Ordinal Rank Tracker” deals with maintaining a sorted list of objects (here, scenic locations) based on certain attributes (score and name) and then being able to return the ith best location based on the number of queries made so far.

“Top K Frequent Elements” involves maintaining a list of elements and their frequencies, and being able to return the K most frequent elements.

The reason is that both problems involve maintaining a dynamic list and providing specific elements from the list based on the operation performed (either a query or adding an element). However, the criteria for ordering the elements and the elements themselves are different in the two problems. In “Top K Frequent Elements”, the elements are integers and the criteria for order is the frequency of the integers, while in “Sequentially Ordinal Rank Tracker”, the elements are objects (scenic locations) with properties and the order is determined by these properties.

This is an approximate mapping because the nature of elements and the order criteria are different. “Sequentially Ordinal Rank Tracker” is more complex due to the nature of elements (objects with properties) and the order criteria (multiple properties).

10 Prerequisite LeetCode Problems

“2102. Sequentially Ordinal Rank Tracker” involves maps, sets, heaps, and dealing with real-time data input, possibly with queries. Here are 10 problems as good preparation:

  1. 295. Find Median from Data Stream: This problem requires handling real-time data input and maintaining a data structure that allows for efficient retrieval of the median value.

  2. 460. LFU Cache: This problem requires designing and implementing a data structure that satisfies certain constraints related to frequency of access.

  3. 355. Design Twitter: This problem requires designing a simple version of Twitter with functionalities like posting tweets, following/unfollowing a user and retrieving the 10 most recent tweets.

  4. 380. Insert Delete GetRandom O(1): This problem involves designing a data structure that supports insert, remove and getrandom operations in average O(1) time complexity.

  5. 716. Max Stack: In this problem, you need to design a max stack that supports push, pop, top, peekMax and popMax operations.

  6. 232. Implement Queue using Stacks: This problem requires you to design a queue using stacks, helping you understand how to use one data structure to implement another.

  7. 341. Flatten Nested List Iterator: This problem involves dealing with a nested data structure and provides practice for using iterators.

  8. 146. LRU Cache: This problem requires designing a data structure with specific constraints related to access recency.

  9. 703. Kth Largest Element in a Stream: This problem requires handling real-time data input and maintaining a data structure that allows for efficient retrieval of the kth largest value.

  10. 170. Two Sum III - Data structure design: This problem asks you to design a TwoSum class that efficiently supports add and find operations.

These cover designing data structures to handle real-time data input and satisfy various constraints, which are crucial for tackling “2102. 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.