Sequentially Ordinal Rank Tracker
HardPrompt
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
ithbest location of all locations already added, whereiis the number of times the system has been queried (including the current query).- For example, when the system is queried for the
4thtime, it returns the4thbest location of all locations already added.
- For example, when the system is queried for the
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 withnameandscoreto the system.string get()Queries and returns theithbest location, whereiis 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:
nameconsists of lowercase English letters, and is unique among all locations.1 <= name.length <= 101 <= score <= 105- At any time, the number of calls to
getdoes not exceed the number of calls toadd. - At most
4 * 104calls in total will be made toaddandget.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach uses a simple ArrayList to store the locations. When a new location is added, it's just appended to the list. The main work is done in the get() method. Each time get() is invoked, it sorts the entire list of all locations added so far based on the specified ranking criteria. After sorting, it retrieves the i-th best location, where i corresponds to the number of times get() has been called.
Algorithm
- Define a
Locationclass to hold thenameandscore. - In the
SORTrackerclass, use ajava.util.ArrayListto store all theLocationobjects. - Maintain a counter,
queryCount, initialized to 0, to track the number ofget()calls. add(name, score): Create a newLocationobject and add it to the list. This is an O(1) operation (amortized).get(): a. IncrementqueryCount. b. Sort the entire list of locations. The sorting criteria are: primarily by score in descending order, and secondarily by name in lexicographically ascending order. c. Access the element at indexqueryCount - 1in the sorted list. d. Return the name of this location.
Walkthrough
The brute-force method is the most straightforward way to solve the problem. We use a dynamic array (like ArrayList in Java) to keep all the scenic locations. The add operation is simple: we just append the new location to our list. The get operation is where the inefficiency lies. We maintain a counter for how many times get has been called. For the i-th call to get, we need the i-th best location. To find this, we sort the entire list of N locations, which takes O(N log N) time. Then, we can directly access the i-th element (at index i-1) in O(1) time. While simple to implement, this approach is not scalable as the number of locations and queries grows.
import java.util.ArrayList;import java.util.Collections;import java.util.List; class SORTracker { private static class Location { String name; int score; Location(String name, int score) { this.name = name; this.score = score; } } private List<Location> locations; private int queryCount; public SORTracker() { locations = new ArrayList<>(); queryCount = 0; } public void add(String name, int score) { locations.add(new Location(name, score)); } public String get() { queryCount++; Collections.sort(locations, (a, b) -> { if (a.score != b.score) { return b.score - a.score; // Higher score first } return a.name.compareTo(b.name); // Lexicographically smaller name first }); return locations.get(queryCount - 1).name; }}Complexity
Time
`add`: O(1) amortized time. `get`: O(N log N), where N is the current number of locations. Sorting dominates the complexity.
Space
O(N), where N is the total number of locations added. We need to store all location objects.
Trade-offs
Pros
Simple to understand and implement.
The
addoperation is very fast.
Cons
The
get()operation is very inefficient because it requires sorting the entire list of locations every time it's called.This approach will likely result in a 'Time Limit Exceeded' error for larger inputs due to the high time complexity of
get().
To avoid re-sorting the entire list on every get() call, we can use a data structure that keeps elements sorted at all times. A TreeSet (implemented as a balanced binary search tree) is a good candidate. When a new location is added, it's inserted into the TreeSet in logarithmic time, preserving the sorted order. However, to retrieve the i-th element, we still need to traverse the TreeSet from the start, which takes time proportional to i. This is an improvement over the brute-force approach for the add operation, but get can still be slow.
Algorithm
- Define a
Locationclass. - Use a
java.util.TreeSetto store theLocationobjects. TheTreeSetis initialized with a customComparatorthat enforces the desired ranking order (score descending, name ascending). - Maintain a counter,
queryCount, initialized to 0. add(name, score): Create a newLocationobject and add it to theTreeSet. TheTreeSetautomatically maintains the sorted order, making insertion anO(log N)operation.get(): a. IncrementqueryCount. b. To find thequeryCount-th best location, we must iterate through theTreeSetfrom the beginning. c. Create an iterator for theTreeSetand callnext()queryCounttimes. d. The last element retrieved from the iterator is the desired location. Return its name.
Walkthrough
This approach improves upon the brute-force method by using a data structure that maintains elements in a sorted order, a TreeSet. We provide a custom comparator to the TreeSet to define our specific ranking criteria. The add operation becomes more efficient, as inserting into a balanced binary search tree takes O(log N) time. The get operation, however, remains a performance issue. Since TreeSet does not provide a method to get an element by its rank in O(1) or O(log N), we are forced to iterate. For the i-th call to get, we must start an iterator from the beginning and advance it i times. This results in an O(i) time complexity for the get operation, which can be as bad as O(N) in the worst case.
import java.util.Iterator;import java.util.TreeSet; class SORTracker { private static class Location { String name; int score; Location(String name, int score) { this.name = name; this.score = score; } } private TreeSet<Location> sortedLocations; private int queryCount; public SORTracker() { sortedLocations = new TreeSet<>((a, b) -> { if (a.score != b.score) { return b.score - a.score; } return a.name.compareTo(b.name); }); queryCount = 0; } public void add(String name, int score) { sortedLocations.add(new Location(name, score)); } public String get() { queryCount++; Iterator<Location> it = sortedLocations.iterator(); Location result = null; for (int i = 0; i < queryCount; i++) { result = it.next(); } return result.name; }}Complexity
Time
`add`: O(log N), where N is the current number of locations. `get`: O(K), where K is the number of times `get` has been called. In the worst case, this is O(N).
Space
O(N), where N is the total number of locations added, to store the `TreeSet`.
Trade-offs
Pros
The
addoperation is efficient (O(log N)).The collection of locations is always kept in a sorted state, which is conceptually clean.
Cons
The
get()operation is still slow with a linear time complexity, asTreeSetdoes not support efficient indexed access.For a large number of
get()calls, the repeated iteration from the beginning becomes a bottleneck.
This optimal approach recognizes that the get() operation sequentially asks for the 1st, 2nd, 3rd, ... best location. This moving rank suggests partitioning the locations into two groups around the current rank i. We use two priority queues (heaps) to maintain this partition efficiently.
One heap, a max-heap, stores the i best locations found so far. Its top element is the i-th best location, which is exactly what get() needs to return. The other heap, a min-heap, stores all other locations. Its top element is the (i+1)-th best location, ready to be promoted on the next get() call.
Both add and get operations involve moving at most one element between the heaps, which takes logarithmic time. This makes both operations highly efficient.
Algorithm
- Maintain two priority queues (heaps).
a. A max-heap (
retrievedLocations) to store the topilocations, whereiis the number ofget()calls. The heap is ordered such thatpeek()returns the worst among theseilocations (i.e., thei-th best location). b. A min-heap (candidateLocations) to store the rest of the locations. The heap is ordered such thatpeek()returns the best among the rest (i.e., the(i+1)-th best location). add(name, score): To maintain the partition correctly without changing the number of retrieved locations (i), we use a simple balancing trick: a. Add the new location to theretrievedLocations(max-heap). b. Immediately move the top element fromretrievedLocationstocandidateLocations(min-heap). c. This ensures the new location is correctly placed on either side of thei-th rank boundary, and the size ofretrievedLocationsremainsi.get(): This operation signifies that we are now interested in the(i+1)-th rank. a. Move the top element fromcandidateLocations(the(i+1)-th best) toretrievedLocations. b. The size ofretrievedLocationsis nowi+1. c. The top ofretrievedLocationsis now the newi-th best location. Return its name.
Walkthrough
The most efficient solution uses two priority queues to maintain a dynamic partition of the locations. Let's call them retrievedLocations and candidateLocations.
-
retrievedLocations: This will be a max-heap according to our ranking criteria (higher score/smaller name is better). It will store theilocations that have been 'retrieved' by thegetmethod. The element at the top of this heap will be the worst among theseilocations, which is precisely thei-th best location overall. In Java, aPriorityQueueis a min-heap, so to simulate a max-heap for our custom ranking, we provide a reversed comparator. -
candidateLocations: This will be a min-heap using the natural ranking criteria. It stores all other locations. The element at its top is the best among this group, which is the(i+1)-th best location overall.
The add operation adds a new location and rebalances the heaps to maintain the partition. A clever way to do this is to add the new location to retrievedLocations and then move the top element of retrievedLocations to candidateLocations. This ensures the sizes are maintained and the new location ends up in the correct heap.
The get operation involves moving the top element from candidateLocations to retrievedLocations, effectively increasing the number of 'retrieved' items by one. The new top of retrievedLocations is then the answer.
This design ensures that both add and get operations have a time complexity of O(log N).
import java.util.Comparator;import java.util.PriorityQueue; class SORTracker { private static class Location { String name; int score; Location(String name, int score) { this.name = name; this.score = score; } } // Stores the locations that are candidates for future get() calls. // It's a min-heap, so peek() returns the best location among candidates. private PriorityQueue<Location> candidateLocations; // Stores the top-i locations that have been effectively 'retrieved' by get(). // It's a max-heap, so peek() returns the worst among them (the i-th best location). private PriorityQueue<Location> retrievedLocations; public SORTracker() { // Comparator for ranking: higher score is better, then lexicographically smaller name. Comparator<Location> comp = (a, b) -> { if (a.score != b.score) { return a.score - b.score; // Natural order for score } return b.name.compareTo(a.name); // Reversed order for name }; // Min-heap based on the reversed comparator (effectively a max-heap on our ranking) this.retrievedLocations = new PriorityQueue<>(comp); // Max-heap based on the reversed comparator (effectively a min-heap on our ranking) this.candidateLocations = new PriorityQueue<>(comp.reversed()); } public void add(String name, int score) { Location loc = new Location(name, score); retrievedLocations.add(loc); candidateLocations.add(retrievedLocations.poll()); } public String get() { retrievedLocations.add(candidateLocations.poll()); return retrievedLocations.peek().name; }}Note: The comparator logic in the code snippet is adjusted to create the desired min/max heap behavior with Java's default PriorityQueue implementation.
Complexity
Time
`add`: O(log N) `get`: O(log N) where N is the current number of locations.
Space
O(N), where N is the total number of locations added. We need to store all location objects across two heaps.
Trade-offs
Pros
Highly efficient, with logarithmic time complexity for both
addandgetoperations.Scales well for a large number of locations and queries.
Cons
The implementation is more complex than the previous approaches.
Requires careful handling of comparators for the two heaps.
Solutions
Solution
#include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/hash_policy.hpp> using namespace __gnu_pbds ; template < class T > using ordered_set = tree < T , null_type , less < T > , rb_tree_tag , tree_order_statistics_node_update > ; class SORTracker { public: SORTracker () { } void add ( string name , int score ) { st . insert ({ - score , name }); } string get () { return st . find_by_order ( ++ i ) -> second ; } private: ordered_set < pair < int , string >> st ; int i = - 1 ; }; /** * Your SORTracker object will be instantiated and called as such: * SORTracker* obj = new SORTracker(); * obj->add(name,score); * string param_2 = obj->get(); */from sortedcontainers import SortedList class SORTracker : def __init__ ( self ): self . sl = SortedList () self . i = - 1 def add ( self , name : str , score : int ) -> None : self . sl . add (( - score , name )) def get ( self ) -> str : self . i += 1 return self . sl [ self . i ][ 1 ] # Your SORTracker object will be instantiated and called as such: # obj = SORTracker() # obj.add(name,score) # param_2 = obj.get()Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.