Anagram Group Tracker with Add, Remove, and Largest-Group Queries: Read vs Write Trade-offs

Design a data structure that tracks words grouped by anagram class. Two words belong to the same group when one is a rearrangement of the other's letters (for example, `listen` and `silent`). The structure supports three operations: ```python class AnagramGroups: def add(self, word: str) -> None: ... def remove(self, word: str) -> None: ... def largest_group(self) -> list[str]: ... # the words in the current largest anagram group ``` Words are added and removed over time, so the largest group can change after any operation. ### Constraints and Clarifications - Assume only the language's standard library is available. In Python, third-party packages such as a sorted-container library cannot be imported, so any ordered structure you need must be built from standard tools. - Let $n$ be the number of words currently stored and $L$ the maximum word length. ### Clarifying Questions - Can the same word be added more than once, and if so, does each copy count toward the group size? - What should `remove` do for a word that is not present? - When several groups tie for the largest size, which one should `largest_group` return, and in what order should its words appear? - What should `largest_group` return when the structure is empty? - Are words case-sensitive, and can they contain characters other than lowercase letters? ### Part 1 — Implement the Structure Implement `add`, `remove`, and `largest_group`. Start with a straightforward version, then produce a version in which all three operations run in logarithmic time in the number of groups (excluding the cost of computing a word's group key). ```hint Name the group Decide on a key that is identical for all words in one anagram group, and consider how cheaply you can compute it for a word of length L. ``` ```hint Keep sizes ordered For the faster version, think about what must stay ordered so the largest group is found without looking at every group, and how that order is updated when a size changes by one. ``` #### What This Part Should Cover - A canonical group key and a mapping from key to the group's words. - A correct straightforward version and a version where the largest group is maintained incrementally. - Correct behavior for removals that empty a group and for the tie and duplicate rules you agreed on. ### Part 2 — Complexity State the time and space complexity of each operation for both versions. ```hint Separate the costs Count the cost of computing the key separately from the cost of updating the grouping and the ordering structure. ``` #### What This Part Should Cover - Per-operation time for both versions, including key computation. - Total space and the extra space used by the ordering structure. ### Part 3 — Choosing Between the Two Versions When would you use your first version, and when the second? What would you measure to decide? ```hint Look at the workload Compare how often words change with how often the largest group is requested. ``` #### What This Part Should Cover - The write-optimized versus read-optimized trade-off, stated in terms of the operation mix. - Concrete metrics you would collect and how they map to a decision. - Practical factors beyond asymptotics, such as the number of distinct groups and implementation complexity. ### What a Strong Answer Covers - A correct canonical key and grouping, with clear handling of duplicates, missing words, empty groups, and ties. - An incremental ordering of group sizes that stays consistent under both additions and removals, built without third-party libraries. - Accurate complexity analysis for every operation in both versions. - A workload-driven recommendation with measurable criteria rather than a blanket preference for the faster-looking version. ### Follow-up Questions 1. How would you change the design if `largest_group` only needed to return the size, not the words? 2. If words arrive from many threads at once, what would you lock, and where would contention appear? 3. How would you support `top_k_groups(k)` efficiently?