Design a Prefix-Suggestion Search Interface

Problem Statement

You are tasked with building the core search-as-you-type engine for a medical records platform. The service must load a collection of document titles, support fast case-insensitive prefix lookups, rank results based on title popularity, and discard stale results caused by asynchronous or out-of-order network responses.

Implement the PrefixSearchEngine class with the following methods:

1. __init__(self, titles: list[tuple[str, int]]): Initializes the search engine with a list of (title, popularity) tuples. Each title is a non-empty string, and popularity is a positive integer (higher means more relevant).
2. query(self, prefix: str, request_id: int, limit: int = 5) -> list[str] | None: Searches for up to limit titles that start with prefix (case-insensitive). Results should be ranked primarily by descending popularity, and secondarily in lexicographical order (ascending) to break ties. If a query arrives with a request_id that is less than or equal to the highest request_id already processed, the engine should treat it as a stale query and return None.

Matching rules:

• Matching must be case-insensitive, but returned titles must retain their original casing.
• Exact prefix match only: words must start with the given prefix string.
• If multiple identical titles exist, deduplicate them by retaining only the instance with the highest popularity.

Example

records = [
    ("Clinical Notes - Cardiology", 120),
    ("Clinical Summary", 95),
    ("clinical notes - neurology", 150),
    ("CBC Lab Results", 200),
    ("Chest X-Ray", 80),
]

engine = PrefixSearchEngine(records)

# Query 1: prefix "clin", request_id 1
engine.query("clin", request_id=1, limit=3)
# Output: ["clinical notes - neurology", "Clinical Notes - Cardiology", "Clinical Summary"]

# Query 2: prefix "c", request_id 3
engine.query("c", request_id=3, limit=2)
# Output: ["CBC Lab Results", "clinical notes - neurology"]

# Query 3: Stale response arrived late (request_id 2 <= 3)
engine.query("clinical", request_id=2, limit=5)
# Output: None

Constraints

• Total unique titles N <= 50,000
• Average title length <= 80 characters
• Query prefix length <= 50 characters
• request_id is a monotonically increasing integer (1 <= request_id <= 10^9)
• 1 <= limit <= 50
• Lookups should execute efficiently (e.g., Trie-based indexing or sorted prefix arrays).