Group words into anagram lists
Company: Bloomberg
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Given an array of strings, group the words into lists of anagrams and return the collection of groups in any order. For example, ["abc", "cab", "edf"] -> [["abc", "cab"], ["edf"]]. Aim for near-linear time in the total number of characters. Specify how you handle case sensitivity, non-ASCII characters, and very long strings, and choose an approach that avoids sorting each string if possible.
Quick Answer: This question evaluates string manipulation, data-structure design, and algorithmic complexity analysis, including considerations for case sensitivity, non-ASCII characters, and handling very long strings.
Given an array of lowercase strings, group the words into lists of anagrams and return the collection of groups in any order (and the words within each group in any order).
Two words are anagrams if one can be formed by rearranging the letters of the other (each letter used the same number of times).
Example:
Input: ["abc", "cab", "edf"]
Output: [["abc", "cab"], ["edf"]]
Aim for near-linear time in the total number of characters. Prefer an approach that avoids sorting each string: build a frequency signature instead.
Discussion points the interviewer looks for:
- Case sensitivity: decide whether 'Abc' and 'cab' are anagrams; here treat input as lowercase a-z. For mixed case, normalize (e.g. lowercase) first per the agreed rule.
- Non-ASCII: a fixed 26-slot count array assumes a-z; for Unicode, key on a hashable count map (e.g. a sorted tuple of (char, count)) instead of a 26-array.
- Very long strings: counting is O(length) per string, so total work stays O(total characters); avoid per-string O(L log L) sorting.
Constraints
- 0 <= number of words <= 10^4
- 0 <= length of each word; total characters fit in memory
- Words consist of lowercase English letters a-z (empty strings allowed)
- Return groups in any order; words within a group in any order
Examples
Input: (["abc", "cab", "edf"],)
Expected Output: [["abc", "cab"], ["edf"]]
Explanation: 'abc' and 'cab' share counts {a:1,b:1,c:1}; 'edf' is alone.
Input: (["eat", "tea", "tan", "ate", "nat", "bat"],)
Expected Output: [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]
Explanation: Three anagram groups; 'bat' has no partner.
Hints
- Sorting each string to form a key works but costs O(L log L) per word. Can you build a key in O(L) instead?
- Two words are anagrams iff they have the same letter-frequency vector. Use the 26-length count array as a hashable key (a tuple).
- Use a hash map from frequency-signature to the list of words sharing that signature; the map values are your answer.
- For Unicode input, replace the fixed 26-array with a count dict and key on its sorted (char, count) items.