Katkat

Return Words in Repeated Anagram Groups

VoleonQuantitative Researcher · Technical Screen

Last updated

Return all input occurrences belonging to repeated anagram groups, preserving order and duplicates with multiplicity-aware letter-count signatures.

Given a list of words, return every word whose anagram signature occurs more than once in the list. A signature records how many times each letter occurs, regardless of letter order.

Implement repeated_anagram_words(words: string[]) -> string[].

Constraints & Assumptions

  • At most 100000 words and at most 1000000 letters in total. Words contain lowercase ASCII letters only; empty words are allowed.
  • Return qualifying occurrences in their original input order. Do not sort words or deduplicate the output.
  • Identical repeated words count as multiple occurrences of their signature. Two empty words also share a repeated signature.
  • A signature must preserve multiplicity: ab and aab are different.
  • Aim for O(total letters + number of words) time using a fixed-size letter-count signature per word.

Examples

words = ["eat","tea","bat","eat","tan","nat","solo"]
result = ["eat","tea","eat","tan","nat"]
words = ["a","ab","aab",""]
result = []

The output order and duplicate policy are explicit practice conventions where the source leaves them unspecified. Explain why a set of distinct letters is insufficient and how a count-signature avoids sorting every word.

Hints

Hint 1

Count signatures before selecting occurrences: Whether the first word qualifies may depend on a later word. Keep the original ordering separate from the signature frequency table.