Check anagrams under real-world constraints
Company: Uber
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given two strings s and t, determine whether they contain exactly the same multiset of characters (e.g., 'abc' and 'cab' → true; 'aab' and 'ab' → false). Provide: (a) an O(n) solution and its time/space complexity; (b) an approach when the character set is large or unknown (Unicode) and inputs may require normalization/case‑folding; (c) a streaming variant where s and t arrive as streams and memory is limited (sublinear in n); and (d) a solution when sorting is disallowed and only O(1) extra space is permitted (explain assumptions needed). Then extend to decide if s and t are "k‑off" anagrams (they become anagrams after at most k single‑character insertions/deletions). Discuss trade‑offs of each approach.
Overview: This question evaluates expertise in string algorithms, multiset equality, algorithmic time/space complexity analysis, memory- and streaming-aware algorithm design, Unicode normalization and case folding, and approximate string matching for k‑off anagrams.
Read the full Uber Data Scientist interview experience this question came from
Return whether two strings are anagrams. If k > 0, allow at most k insertions or deletions to make them anagrams.
Constraints
- Inputs are strings
- k counts single-character insertions/deletions
Examples
Input: ('abc', 'cab', 0, False)
Expected Output: True
Explanation: Same multiset.
Input: ('aab', 'ab', 0, False)
Expected Output: False
Explanation: Different counts.
Hints
- A character frequency difference gives the number of insertions/deletions needed.