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.
Tags:
data structures, algorithm
Answer

Interview Answer

2 Answers

0

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
0

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.