Design a data structure to store anagrams
Company: Millennium
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Problem
You are building a small in-memory service that stores words and can return all stored words that are anagrams of a query.
Design and implement a data structure **AnagramStore** supporting the following operations:
1. `add(word: string) -> void`: Add a word to the store (duplicates may exist).
2. `getAnagrams(query: string) -> list<string>`: Return **all** words previously added that are anagrams of `query` (including the word itself if it was added). The order of the returned list does not matter.
Two words are anagrams if they contain the same letters with the same frequencies (case-insensitive; assume input is lowercase `a-z` unless you state otherwise).
### Example
- Add: `"eat"`, `"tea"`, `"tan"`, `"ate"`, `"nat"`, `"bat"`
- `getAnagrams("ate")` can return: `["eat", "tea", "ate"]`
- `getAnagrams("ant")` can return: `["tan", "nat"]`
- `getAnagrams("tab")` can return: `["bat"]`
### Constraints (you may assume)
- Up to `10^5` total `add` operations
- Word length up to `100`
### Requirements
- Explain the time and space complexity of your approach.
- Discuss how you would handle duplicates (e.g., adding the same word multiple times).
Quick Answer: This question evaluates proficiency in data structures and algorithms for string grouping and lookup, testing skills in string manipulation, canonicalization/hashing concepts, memory-time trade-offs, and handling duplicates.
Process operations ["add", word] and ["get", query]. Return all previously added words that are anagrams of query, preserving insertion order and duplicates for deterministic output.
Constraints
- Words are lowercase a-z unless normalized
- Duplicates are preserved
Examples
Input: ([['add', 'eat'], ['add', 'tea'], ['add', 'tan'], ['add', 'ate'], ['add', 'nat'], ['add', 'bat'], ['get', 'ate'], ['get', 'ant'], ['get', 'tab']],)
Expected Output: [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]
Input: ([['get', 'abc'], ['add', 'abc'], ['add', 'abc'], ['get', 'bca']],)
Expected Output: [[], ['abc', 'abc']]
Hints
- Canonicalize each word by sorted letters or character counts.