Dolphin Programming Challenge - Most Number of Anagrams
Have you got what it takes to work as a Software Development Engineer at Dolphin?
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 <LF> character between each word.
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.
We are looking for 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.
- Your application should be written in C/C++.
- You can use any standard run-time library functions, STL or win32 API that you like. Do not use the .NET runtime.
- 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, however we recommend that you create a standard win32 console application.
Download our Sample dictionary file.
Please submit your source code file(s), along with your CV to the Human Resources Department. This will be passed onto our Software Engineers to compile and test your application.