Recent search history with a size limit

Build the recent-searches list behind a search box. When the user focuses the box, it shows their most recent distinct searches, newest first. Every search the user runs is recorded. A term that is searched again moves to the top; it is never listed twice. The history holds at most capacity distinct terms; when a new term would exceed that, the term searched least recently is dropped.

Implement the SearchHistory class:

• SearchHistory(capacity: int) creates an empty history. capacity is a positive integer.
• add(term: str) -> None records a search for term.
• get_top_k(k: int) -> list[str] returns up to k stored terms, most recent first. If fewer than k terms are stored, return all of them. k = 0 returns an empty list.

Terms are compared exactly (no case folding). Aim for O(1) per add and O(k) per get_top_k, with capacity up to 10^6 and up to 10^6 calls.

Example 1

h = SearchHistory(3)
h.add("llama")
h.add("tpu")
h.add("rlhf")
h.get_top_k(2)    # ["rlhf", "tpu"]
h.add("llama")    # already stored: moves to the front, nothing is dropped
h.get_top_k(3)    # ["llama", "rlhf", "tpu"]
h.add("moe")      # 4 distinct terms > capacity 3: "tpu" is dropped
h.get_top_k(10)   # ["moe", "llama", "rlhf"]

Example 2

h = SearchHistory(1)
h.add("a")
h.add("a")
h.add("b")
h.get_top_k(5)    # ["b"]

Reconstructed from the reported question; details may differ from what interviewers ask.