Return Top Department Suggestions

Problem Statement

In an enterprise search platform, users frequently search for internal departments (e.g., "Engineering - Infrastructure", "Enterprise Sales"). To improve discoverability, implement an autocomplete suggestion system that returns the top k department names matching a given prefix.

Implement the DepartmentSearch class:

• DepartmentSearch(departments: list[tuple[str, int]]): Initializes the search system with a list of pairs (name, score), where name is a unique department name and score is its search popularity score.
• suggest(prefix: str, k: int) -> list[str]: Returns up to k department names that start with prefix, ordered by:
  1. Highest score first.
  2. Lexicographically smaller name in case of a score tie.

If fewer than k departments match the prefix, return all matching departments in the specified order. If no departments match, return an empty list.

Example

search = DepartmentSearch([
    ("engineering", 100),
    ("enterprise sales", 80),
    ("engineering operations", 100),
    ("energy", 50),
    ("executive", 90)
])

# "en" matches "engineering", "enterprise sales", "engineering operations", "energy"
search.suggest("en", 3)
# Output: ["engineering", "engineering operations", "enterprise sales"]
# Explanation: "engineering" and "engineering operations" both have score 100, but "engineering" is lexicographically smaller.

search.suggest("exec", 2)
# Output: ["executive"]

search.suggest("finance", 3)
# Output: []

Constraints

• 1 <= len(departments) <= 20,000
• 1 <= len(name) <= 100 for each department name
• 0 <= score <= 10^6
• 1 <= len(prefix) <= 100
• 1 <= k <= 100
• Department names and prefixes consist of lowercase English letters and spaces.
• suggest will be called up to 10,000 times.

Edge Cases

• k is larger than the number of matching departments.
• prefix matches zero departments.
• prefix matches the exact full name of a department.