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.