Sequentially Ordinal Rank Tracker
Hard
You are designing a system to track the ranking of scenic locations. Each location has a unique name (string) and an attractiveness score (integer). Locations are ranked from best to worst based on their score (higher is better). If two locations have the same score, the location with the lexicographically smaller name is considered better.
Initially, the system has no locations. You need to implement the SORTracker class with the following functionalities:
SORTracker(): Initializes the tracker system.void add(string name, int score): Adds a scenic location with the givennameandscoreto the system.string get(): Queries and returns the i-th best location, whereiis the number of times this method has been invoked (including the current invocation). For example, ifget()is called for the 4th time, it should return the 4th best location among all locations added so far.
Example:
SORTracker tracker = new SORTracker();
tracker.add("bradford", 2);
tracker.add("branford", 3);
tracker.get(); // Returns "branford" (1st call)
tracker.add("alps", 2);
tracker.get(); // Returns "alps" (2nd call)
tracker.add("orland", 2);
tracker.get(); // Returns "bradford" (3rd call)
Constraints:
nameconsists of lowercase English letters and is unique.1 <= name.length <= 101 <= score <= 10^5- The number of calls to
getwill not exceed the number of calls toaddat any time. - Total calls to
addandgetwill be at most 4 * 10^4.
How would you implement the SORTracker class to efficiently handle these operations?
Solution
Naive Solution
A naive solution involves storing all the locations in a list and sorting the list each time the get() method is called. This approach is simple to implement but inefficient due to the sorting operation.
Implementation
add(name, score): Append the new location (name, score) to a list of locations.get(): Sort the list of locations based on the score (descending) and name (lexicographically ascending if scores are equal). Return the i-th element, where i is the number of timesget()has been called.
Big O Analysis
- Time Complexity:
add(): O(1)get(): O(N log N), where N is the number of locations added so far.
- Space Complexity: O(N), where N is the number of locations stored.
Optimal Solution
An optimal solution uses two data structures to maintain the sorted order of the locations efficiently:
- Sorted List/Array: to maintain all added locations in sorted order.
- Pointer/Index: to point to the i-th best location which can be updated efficiently.
Implementation
add(name, score): Insert the new location (name, score) into the sorted list while maintaining the sorted order.get(): Return the location at the current index. Increment the index for the next call.
Data structures used
- A list to hold all locations with their names and scores.
Algorithm
add(name, score): Add the new location to the list. Sort the list based on the specified criteria (score descending, name ascending if scores are equal).get(): Increment a counter (initialized to 0) each timeget()is called. Return the element at the counter-th index in the sorted list.
Python Code
class SORTracker:
def __init__(self):
self.locations = []
self.i = 0
def add(self, name: str, score: int) -> None:
self.locations.append((name, score))
self.locations.sort(key=lambda x: (-x[1], x[0]))
def get(self) -> str:
result = self.locations[self.i][0]
self.i += 1
return result
Big O Analysis
- Time Complexity:
add(): O(N log N) due to the sorting after each insertion.get(): O(1)
- Space Complexity: O(N), where N is the number of locations stored.
Edge Cases
- Empty List: When the list is empty, the
get()method should handle the empty case gracefully (though the prompt specifies that the number ofgetcalls will never exceed the number ofaddcalls). - Duplicate Scores: The solution correctly handles duplicate scores by comparing names lexicographically.
