eBay Interview Question: Assuming a preexisting list o... | Glassdoor

Interview Question

Software Engineer Intern Interview San Jose, CA

Assuming a preexisting list of 100 words, how would you

  efficiently see if a word received from input is an anagram of any of the 100 words?
Answer

Interview Answer

4 Answers

0

First Sort 100 words and keep the hash of sorted words.. Now when you recieve a word, SOrt it and check if Hash contains that key. O(nlogn) Where n is length of String.

MW on Jul 20, 2012
0

Hi
I think you can take a look at the most efficient algorithm for this question in this link

www.crackeasily.com/2012/01/find-whether-2-strings-are-anagrams.html

crackeasily dot com on Sep 11, 2012
2

To say what MW said more clearly:

If you sort words that are the same anagram they will always look the same. Example: "god" and "dog" both look like "dgo".

So you sort the input word, then you iterate through the list of 100 words, and while looking at each word sort that word. compare if the input and that word are the same. If they are then you have found an anagram. if you made it to the end of the list and you haven't found an anagram then an anagram does not exist in the list.

JZ on Mar 11, 2013
6

Sorting takes O(nLogn) average time. This can be further improved by counting characters in the strings.
So, for the given string calculate count of each character in an array [256]. For each word in the list, check if it contains the same count for its characters and return that word. Complexity O(n)

Vishal on Jan 4, 2014

Add Answers or Comments

To comment on this, Sign In or Sign Up.