Interview Question

Interview New York, NY

You're given a set of strings. You want to test if any two

  strings in the set are anagrams.
data structures, algorithm

Interview Answer

2 Answers


I gave a solution that involved sorting the strings and using that as elements of a new set to check for anagrams. They asked me to reduce the memory footprint of my solution without sacrificing the O(N) time (N = number of strings, we assumed that string lengths were O(1)). I suggested that if the strings represent words in a natural language, we might be able to apply the same Huffman encoding to everything in the set, which maybe could reduce space by, say, 50%. They seemed satisfied with that solution.

Interview Candidate on Nov 3, 2011

You could also check to see if the words have the same number of characters and same characters using a hash map. Only anagrams can satisfy that.

Rio on Nov 14, 2011

Add Answers or Comments

To comment on this, Sign In or Sign Up.