Group Strings By Anagram Signature
Company: Okx
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given a list of strings, group the strings so that each group contains words that are anagrams of each other. Discuss both a sorting-based signature and a frequency-vector signature. Return the groups in any order.
Function signature:
```python
def group_anagrams(words: list[str]) -> list[list[str]]:
pass
```
Constraints:
- All strings contain lowercase English letters unless the interviewer adds a broader character set.
- Words may repeat.
- The order of groups and words within a group does not matter.
- Analyze the cost of sorting each word versus building a frequency signature.
Examples:
```text
words = ['eat', 'tea', 'tan', 'ate', 'nat', 'bat']
Output may be [['eat','tea','ate'], ['tan','nat'], ['bat']]
```
Quick Answer: Practice grouping strings by anagram signature in a coding interview, including sorting-based and frequency-vector approaches. The problem is useful for reviewing hash maps, deterministic grouping, duplicate words, and time-complexity trade-offs.
Group strings that are anagrams. Return each group sorted lexicographically, and return the list of groups sorted by the first word in each group.
Constraints
- Words contain lowercase English letters.
- Duplicate words should be preserved.
Examples
Input: (['eat','tea','tan','ate','nat','bat'])
Expected Output: [['ate','eat','tea'],['bat'],['nat','tan']]
Input: ([''])
Expected Output: [['']]
Hints
- A frequency tuple can improve the per-word signature cost for fixed alphabets.
- Normalize the output order for deterministic tests.