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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Sequentially Ordinal Rank Tracker

Number: 2207

Difficulty: Hard

Paid? No

Companies: Amazon

Problem Description

Design a ranking tracker for scenic locations that supports two operations. The first operation adds a location (with a unique name and an integer score) to the system. The second operation returns the iᵗʰ best location among those added – where “best” is defined first by a higher score and then (in case of ties) by lexicographically smaller name. Note that each call to the get method increases the query count i; that is, the first get returns the best location, the second get returns the 2ⁿᵈ best, and so on.

Key Insights

  • The ranking order is defined by score (higher is better) and, when scores are equal, by name (lexicographically smaller is better).
  • The get() operation is sequential: the first call returns the best, the second the 2ⁿᵈ best, etc.
  • It is inefficient to sort all locations on every query.
  • A two‐heap approach can “lazy‐maintain” the tree of top candidates:
    • One heap (“selected”) will always hold the top k locations (k = number of get calls so far) such that its root is the kᵗʰ best (i.e. the worst among the selected top ones).
    • The other heap (“buffer”) holds the remaining locations.
  • When adding a new location, decide whether it belongs among the current top k (selected) or should be kept in the buffer.
  • When a get() call is made, if the size of the “selected” heap is less than the current query count, move the best candidate from the “buffer” over.
  • Trick: Because the ranking order is “reverse” of natural numerical order for score and requires a custom tie–breaker for name, we “encode” each location with a key tuple. In the “selected” (min–heap) we want the worst among the top candidates (lowest score; if tied, lexicographically largest name) to be at the root. We achieve this by storing a tuple key = (score, tuple(-ord(c) for c in name)) so that a lower score is “smaller” and among equal scores a name that is lexicographically larger (worse) produces a lower key.
  • In the “buffer” we simulate a max–heap using a min–heap by storing key = (-score, tuple(ord(c) for c in name)); then the candidate with the smallest key is actually the best among the remaining locations.

Space and Time Complexity

Time Complexity:
• add(): O(log n) per call since inserting into one of the heaps and sometimes rebalancing takes logarithmic time.
• get(): O(log n) per call due to possible heap extraction and insertion.

Space Complexity:
• O(n) where n is the total number of locations added (since all locations are stored in one of the two heaps).

Solution

We use two heaps to maintain the ranking dynamically. Let “selected” be a min–heap that contains exactly k elements (where k is the number of times get() has been called so far) – these are the top k locations. We design the key for “selected” as a tuple: (score, nameKey, name) where score is stored normally (since a lower score is worse) and nameKey is computed as tuple(-ord(c) for each character c in the name). This way, if two locations have the same score, the one with a lexicographically larger name (i.e. “worse”) will have a lower nameKey and will be at the top (root) of the min–heap.

All other locations are stored in the “buffer” heap. To efficiently pick the best candidate from the buffer when needed, we store each location with key: (-score, tuple(ord(c) for c in name), name). With this encoding, a location with a higher score (or, if tied, a lexicographically smaller name) will have a smaller key and will be popped first from the buffer.

For add(name, score):
• If the “selected” heap is non–empty and the new location is “better” than the current kth best (i.e. its key for selected is greater than the root’s key), then the new location deserves to be among the top k. We push it into “selected” and then pop the smallest (worst among top k) from “selected” (this element is now “demoted”) and push it into the “buffer.”
• Otherwise, we simply push the new location into “buffer.”

For get():
• Increment the query count k. If “selected” has fewer than k locations, we pop one candidate from “buffer” (which is the best candidate among the remaining) and push it into “selected.”
• Then, return the name from the root of “selected” (which represents the kᵗʰ best location).

Code Solutions

import heapq

class SORTracker:
    def __init__(self):
        # Count of get() calls; this determines the number k of best locations required.
        self.k_count = 0
        # "selected" holds the top k locations.
        # Each element is a tuple: (score, name_key, name)
        # where name_key = tuple(-ord(c) for c in name)
        self.selected = []
        # "buffer" holds the rest of the locations.
        # Each element is a tuple: (-score, name_buf_key, name)
        # where name_buf_key = tuple(ord(c) for c in name)
        self.buffer = []
    
    def add(self, name: str, score: int) -> None:
        # Build keys for the selected and buffer heaps.
        selected_key = (score, tuple(-ord(c) for c in name), name)
        buffer_key = (-score, tuple(ord(c) for c in name), name)
        
        # If there is at least one element in selected and the new location is better than
        # the worst in the selected group, then add it to selected.
        if self.selected and selected_key > self.selected[0]:
            # Push the new location into selected.
            heapq.heappush(self.selected, selected_key)
            # Pop the smallest (i.e. the worst among the top group) and demote it to buffer.
            demoted = heapq.heappop(self.selected)
            # Convert the demoted entry into buffer format.
            demoted_buffer_key = (-demoted[0], tuple(ord(c) for c in demoted[2]), demoted[2])
            heapq.heappush(self.buffer, demoted_buffer_key)
        else:
            # Otherwise, the new location goes straight into buffer.
            heapq.heappush(self.buffer, buffer_key)
        
    def get(self) -> str:
        # Increase the count of get() calls.
        self.k_count += 1
        # Ensure that selected heap has exactly k_count elements.
        if len(self.selected) < self.k_count:
            # Promote the best candidate from buffer.
            best_from_buffer = heapq.heappop(self.buffer)
            # Convert to selected format.
            promoted = ( -best_from_buffer[0], 
                         tuple(-ord(c) for c in best_from_buffer[2]), 
                         best_from_buffer[2] )
            heapq.heappush(self.selected, promoted)
        # The kth best location is the root of the selected heap.
        return self.selected[0][2]
        
# Example usage:
# tracker = SORTracker()
# tracker.add("bradford", 2)
# tracker.add("branford", 3)
# print(tracker.get())  # Expected "branford"
← Back to All Questions