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:
• Higher occurrence count first.
• If counts tie, smaller earliest timestamp first.
• If both still tie, lexicographically smaller query first. Return one ranked list per prefix. If a prefix has no matching query, return an empty list for that prefix. This is a batch version of the classic search autocomplete system design question. In an interview, clarify whether the output should include all matching queries or only the top k suggestions.

roblox and roblox studio each appear twice, so the earlier first timestamp puts roblox first. roblox game appears once.

Both queries appear twice. alpha has earliest timestamp 2, while alpine has earliest timestamp 3.

The count and earliest timestamp both tie, so lexicographic order breaks the tie.