Check Whether Two Strings Are Anagrams
Company: Databricks
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
## Problem
Implement `are_anagrams(a, b)`. Return `true` exactly when `a` and `b` contain the same lowercase English letters with the same multiplicities, possibly in a different order.
## Constraints
- `0 <= len(a), len(b) <= 1,000,000`
- Both strings contain only characters `a` through `z`.
- The empty string is an anagram of the empty string.
## Examples
- `a = "listen"`, `b = "silent"` returns `true`.
- `a = "rat"`, `b = "car"` returns `false`.
- `a = "aab"`, `b = "abb"` returns `false`.
## Clarifications
Do not ignore whitespace, punctuation, or case because those characters are excluded by the input contract. Aim for linear time and constant auxiliary space relative to input length.
## Hint
Sorting works but does more work than necessary. A fixed-size frequency difference tracks exactly what must balance.
## Interview Follow-ups
- Support arbitrary Unicode text.
- Process inputs that do not fit in memory.
- Group a large list of words into anagram classes.
Quick Answer: Check whether two strings contain the same lowercase English letters with identical multiplicities, including empty and million-character inputs. Discuss case-sensitive contract boundaries, time and auxiliary-space expectations, Unicode generalization, inputs larger than memory, and grouping many words by anagram class.
Implement are_anagrams(a, b). Return true exactly when a and b contain the same lowercase English letters with the same multiplicities, possibly arranged in a different order. Both inputs contain only letters a through z, and two empty strings are anagrams.
Constraints
- 0 <= len(a), len(b) <= 1,000,000.
- Both strings contain only lowercase English letters a through z.
- The empty string is an anagram of the empty string.
Examples
Input: ('', '')
Expected Output: True
Explanation: Two empty strings have identical letter multiplicities.
Input: ('', 'a')
Expected Output: False
Explanation: Different lengths cannot have the same multiplicities.
Hints
- Track the difference between the two strings' frequencies in one fixed-size array.