Coding questions · Uber
Check anagrams under real-world constraints
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.
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.
Anagram and k-Off Anagram Check
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
Example 1
Input: ('abc', 'cab', 0, False)
Output: True
Explanation: Same multiset.
Example 2
Input: ('aab', 'ab', 0, False)
Output: False
Explanation: Different counts.
Hints
- A character frequency difference gives the number of insertions/deletions needed.