Monday, 11 June 2012

find all anagrams of a word in a file, Java Code : Amazon Interview

Find all anagrams of a word in a file 

Amazon Interview (Dec 2011)


Problem Statement

Find all anagrams of a word in a file. Input -  only file name and word. Output - all set of word in file that are anagrams of word. Write production quality code.

Algorithm

1) Use a hashmap with string as key and list<string> as value where list of strings contain all anagrams of a key string.
2) For each word in the file, find beta string which is its sorted version ex abd is sorted version of bad, adb and dba. Put this word to that list whose key is this beta string. If it does not exist then create a new list with the beta string as key in map.
3) Finally print all strings from the list whose key is the input word(sorted/beta string).

If you have a different approach in mind, please share it in comments section for our readers.

Solution

import java.util.*;
import java.io.*;

public class Anagram {
    public static void main(String[] args) {
    String beta = args[1];

        try {

            Map<String, List<String>> m = 
                   new HashMap<String, List<String>>();

            Scanner s = new Scanner(new File(args[0]));
            while (s.hasNext()) {
                String word = s.next();
                String alpha = sorting(word);
                List<String> l = m.get(alpha);
                if (l == null)
                    m.put(alpha, l=new ArrayList<String>());
                l.add(word);
            }

         List<String> l = m.get(sorting(beta));
       Object[] arr = l.toArray();
           for (int i=0; i < arr.length; i++)
                System.out.println(arr[i]);

        }
    catch (Exception e) {
            System.out.println(e);
            System.exit(1);
        }

    }

    private static String sorting(String s) {
        char[] a = s.toCharArray();
        Arrays.sort(a);
        return new String(a);
    }
}

Time Complexity

O(n) for visiting each word in file once. You can't do it actually in O(n) if you consider the time complexity involved in sorting each word.
If you consider that time complexity involve with sorting also, then you should know that java uses quicksort algorithm to sort char array for which time complexity is O(mlogm) and I have applied sorting function in my code to each word of file .Therefore the time complexity would be O(n*mlogm), where longest word has length m.




12 comments:

  1. Hi Sachin,
    Please note that the sorting of each word cannot be O(nlogn). Here 'n' is the no. of items in the input. It could instead be n(klogk) where the longest word has the length 'k'.
    Jag'
    http://www.linkedin.com/in/jagadishvenkat

    ReplyDelete
    Replies
    1. In fact, for sorting, you can do better than klogk, assuming the words are characters (a-z), counting sort can be an option too!

      Delete
    2. Noted Jagadish. Thanks for pointing it out. Let me quickly update it.

      Delete
    3. Hi Sachin,

      Great post. Well thought out. This piece reminds me when I was starting out Amazon Interviewafter graduating from college.


      This is Erin from Amazon Web Services. I took a look at the support case you provided, I see that one of our agents was able to assist and resolve the case. When individually these thresholds are met, a completely new occasion of a person’s selection will most likely be spun up, configured, and folded into the load balancer pool. Voila, you have scaled horizontally without any operator intervention!

      Please let us know if there is anything else we can help with!

      Awesome! Thanks for putting this all in one place. Very useful!

      Kind Regards,
      Kevin

      Delete
  2. Hi Sachin, the solution is very well described. I have a quick question though, If my input word doesn't have any anagrams in the file, then in this(see below) part of code, the array arr would be empty and we will be trying to print out elements which will cause NullPointerException which would be caught though. I want to know that is this part of your design as well ? Like I thought if you don't have any anagrams for the input word then why don't we just print the message saying the same. Let me know your thoughts on this. :)

    List l = m.get(sorting(beta));
    Object[] arr = l.toArray();
    for (int i=0; i < arr.length; i++)
    System.out.println(arr[i]);

    ReplyDelete
    Replies
    1. Also, I would like to add one more point. I think the sort method needs to truncate "blank space". The reason being, if for example, my word is stipend and in my file I have "spend it" (both are anagrams), the output will be wrong isn't it ?

      Delete
  3. could you please tell me java program to print anagram of a string?

    ReplyDelete
  4. You could also try, instead of creating a Map for the whole File, for each word your read from FIle, sort it, and compare it to the sorted version of beta, if it matches you add it to your list of anagrams of beta.

    That way you will be saving up a lot of space(no need for Map)... and maybe time you spent searching in your Map.

    ReplyDelete
  5. if that input of a particular word is not given and we have to find anagrams of all words then the solution is???

    ReplyDelete
  6. Hey Brother,

    Brilliant article, glad I slogged through the find all anagrams of a word in a file, Java Code : Amazon Interview it seems that a whole lot of the details really come back to from my past project.

    I'm using CloudFormation and really enjoy it, but there are a couple of things which are lacking here.

    Maybe there are some reasons why they weren't implemented here, but. AWS Training

    So, the first thing is variables which can be populated during stack creation.
    Here is an example of similar service from another cloud provider:

    Thanks a lot. This was a perfect step-by-step guide. Don’t think it could have been done better.

    Shukran,
    Irene Hynes

    ReplyDelete
  7. Greetings Mate,


    I’ve often thought about this find all anagrams of a word in a file, Java Code : Amazon Interview. Nice to have it laid out so clearly. Great eye opener.

    I am using I EC2 instance, but after several trials I can't get more that 2~3Mbits/sec of the internet connection, is there any limits? AWS Tutorial


    I did the tests in different hours of the last two days.





    THANK YOU!! This saved my butt today, I’m immensely grateful.


    Gracias
    Ajeeth

    ReplyDelete