Programming Challenge

Your task is to write a program that can find out which word in a provided dictionary has the most number of anagrams from the same dictionary and display the set of anagrams for that word.

Two words are anagrams of each other if they are the same length and contain the same set of letters.

Example dictionary: fred two tow show whos wot one red

The answer here is "two, wot, tow" as these 3 words are all anagrams of each other. "show" and "whos" are also anagrams but there are only 2 matching words in the dictionary. "fred", "one", and "red" do not have any anagrams.

A sample dictionary file is provided. This contains one word per line. Many of the words in the dictionary will not have any anagrams, but some of them will and some will have a number of possible anagrams.

The dictionary file may not be in alphabetic order, however you can assume that it only consists of words containing the letters a-z, is consistently formatted, has no punctuation characters or duplicated lines. The dictionary file will contain a character between each word.

Method

The brute force approach would be to load the dictionary file into memory, and then for each word in the dictionary check if it's an anagram of every other word in the dictionary. You will also need to keep a tally of which word has the most anagrams and have some way to display your results. This would have a run-time of O(n2) and for large dictionaries is likely to take a long time.

Your task is to produce an efficient algorithm that can solve the problem on a large dictionary (>250000 words) within a reasonable time. We will be testing your application on a number of dictionary files.

There is no right answer to this problem. There are a number of possible algorithms that you could use for both limiting the amount of processing you need to do and for testing whether two given words are an anagram of each other.

Note: There may be more than one answer if the dictionary contains several words which all have the same number of anagrams.

Rules

  • Your application may be written in any common programming language, for example C/C++, C#, Java or Python.
  • You can use any standard library functions that are part of the language or normal development environment.
  • You may not copy code from the internet.
  • You can base your project on any of the standard project templates provided by the development environment.

Sample Dictionary

Download the sample dictionary file

Submission

Please package your source code files in a .zip file and upload using the form below, your zip file must be smaller than 10 megabytes: