Design Search Autocomplete System

You are given three arrays:

• queries[i] is a search query issued by a user.
• timestamps[i] is the time when queries[i] was issued.
• prefixes[j] is a prefix typed into an autocomplete box.

For each prefix, return every distinct query that starts with that prefix, ordered by:

1. Higher occurrence count first.
2. If counts tie, smaller earliest timestamp first (the earliest time that query was ever issued).
3. If both still tie, lexicographically smaller query first.

Return one ranked list per prefix, in the same order as prefixes. If a prefix has no matching query, return an empty list for that prefix. The empty prefix matches every distinct query.

This is the batch version of the classic search-autocomplete design question. A Trie keyed on query strings (each terminal node carrying the query's count and earliest timestamp) lets each prefix lookup collect its subtree's queries, which are then ranked by the comparator above. In a live interview, clarify whether the output should include all matching queries or only the top k suggestions.