Katkat
Back

Find the Best Word for a Query Suffix

ByteDanceSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to efficiently query a dictionary for the longest word ending with a specific suffix, requiring optimal data structure usage for prefix/suffix operations.

Problem Description

You are building an auto-complete system that suggests words from a provided dictionary based on a given suffix. Given a list of words, implement a class SuffixMatcher that supports the following methods:

  1. __init__(words: List[str]): Preprocesses the list of words.
  2. find_best_word(suffix: str) -> str: Returns the longest word in the dictionary that ends with the given suffix. If multiple words have the same maximum length, return the lexicographically smallest one among them. If no word matches, return an empty string.

Constraints

  • The dictionary contains up to 50,000 words.
  • Total characters across all words will not exceed 1,000,000.
  • Suffix length will be between 1 and 100 characters.
  • Assume only lowercase English letters are used.

Examples

# Example 1
dict = ["apple", "maple", "le", "banana", "tale"]
matcher = SuffixMatcher(dict)
matcher.find_best_word("le") 
# Output: "apple" (length 5, "apple" and "maple" are tied, "apple" is lexicographically smaller)

matcher.find_best_word("ana")
# Output: "banana"

Edge Cases

  • The suffix is longer than the words in the dictionary.
  • The suffix does not exist in any word.
  • Multiple words share the same length and suffix.
  • The dictionary is empty.

Hints

Hint 1

Consider reversing all the words in the dictionary and inserting them into a Trie.

Hint 2

Each node in your Trie can store the index or the best-fitting word that passes through that branch to avoid full traversal during queries.

Hint 3

When storing words in the Trie nodes, ensure you maintain the lexicographical order and length criteria during the insertion phase.

Follow-up questions

  • How would your approach change if the dictionary is dynamic (words can be added or removed after initialization)?
  • Can you optimize the space complexity if many words share the same suffixes?
  • What is the time complexity of the `find_best_word` query relative to the length of the suffix and the depth of the Trie?