Check anagrams under real-world constraints

Q: Check anagrams under real-world constraints

This is a Coding & Algorithms interview question from Uber for Data Scientist roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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.

Check anagrams under real-world constraints

Comments (0)