Find best pin given time window

"""Create a user class that insert pin by increasing timestamp and get best pin in a given time window"""

"""NOT PREFERRED"""

def binary_search(start_i, end_i, want_first_true: "bool",
    *, predicate, **kwargs): # -> index | None
    """ Find a predicate s.t:
        1) if pred(mid_i) == True, pred(start_i) == False, pred(end_i) == True
        2) pred(i) tries to find i satisfying problem.
    """

    is_reverse = (start_i > end_i)
    step = -1 if is_reverse else 1

    left_i = start_i; right_i = end_i
    while left_i * step <= right_i * step:

        # [a, b] -> a; [a, b, c] -> b
        mid_i = left_i + (right_i - left_i) // 2

        is_mid_satisfy = predicate(mid_i, **kwargs)
        can_move_left = (not is_mid_satisfy)

        if can_move_left:
            left_i = mid_i + step
        else:
            right_i = mid_i - step

    final_i = left_i if want_first_true else right_i
    return final_i if min(start_i, end_i) <= final_i <= max(start_i, end_i) else None

class User:
    def __init__(self):
        self.data = []

    def insert_data(self, pin: str, time: int, score: int):
        """ O(n) but amortized O(1)"""
        # You can assume that the time will always be increasing in the data stream
        while self.data and self.data[-1][1] < score:
            self.data.pop()
        self.data.append([time, score, pin])

    def get_best_pin(self, current_time: int, window: int) -> str:
        """O(log len(self.data))"""
        # (i) return the pin with maximum score in the window (current_time - window, current_time)
        # (ii) you can assume that current_time will always increase in the future calls
        # (iii) the window size can increase in the future calls, so you can't throw away old data
        # (iv) you don't have to worry about space complexity

        target_time = current_time - window
        answer_i = binary_search(0, len(self.data) - 1, True, predicate = lambda i: self.data[i][0] >= target_time)

        # please find my solution below
        # return self.data[bisect.bisect(self.data, [current_time - window - 1, 0, ""])][2]
        return self.data[answer_i][2] if answer_i is not None else ""

"""PREFERRED"""
import heapq
from collections import deque

class User:
    def __init__(self):
        # Deque to store pins in the order of their timestamps
        self.deque = deque()  # Each element is (time, score, pin)

        # Max heap to store (-score, time, pin) for quick access to the highest score
        self.heap = []  # Each element is (-score, time, pin)

    def insert_data(self, pin: str, time: int, score: int):
        """
        Insert a new pin with its timestamp and score.
        Time Complexity: O(log n) due to heap push
        """
        # Append to the deque
        self.deque.append((time, score, pin))
        # Push onto the heap. Negate the score to simulate a max heap.
        heapq.heappush(self.heap, (-score, time, pin))

    def get_best_pin(self, current_time: int, window: int) -> str:
        """
        Retrieve the pin with the highest score within the time window.

        Time Complexity: O(log n) in the worst case due to heap operations
        """
        target_time = current_time - window

        # Remove outdated pins from the deque
        while self.deque and self.deque[0][0] < target_time:
            outdated_pin = self.deque.popleft()
            # Marking the pin as outdated is not necessary since we'll handle it in the heap
            # during retrieval by checking the timestamp

        # Clean up the heap by removing pins that are no longer in the deque (outdated)
        while self.heap:
            neg_score, time, pin = self.heap[0]
            if time >= target_time:
                # The top of the heap is within the time window
                return pin
            else:
                # The top pin is outdated, remove it from the heap
                heapq.heappop(self.heap)

        # If no valid pins are found
        return ""

# Example:
xyz = User()
data = [("A", 0, 10), ("B", 1, 40), ("C", 2, 30), ("D", 7, 5)]
for pin, time, score in data:
    xyz.insert_data(pin, time, score)

print(xyz.get_best_pin(current_time = 7, window = 5)) # you should get C
print(xyz.get_best_pin(current_time = 7, window = 1)) # you should get D
print(xyz.get_best_pin(current_time = 7, window = 7)) # you should get B