Progress Interview Question for Software Engineer / Developers


Country: India
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
1
of 1 vote

I will utilize hash collision to implement this. And i will use an array of prime numbers to avoid false collision.

 HashTable<Integer, List<String>> dictionary;
1. Create an array of prime numbers. It can be easily generated by any random function.
//The size of this array will depend on the avilable number of character for words. 
   int primes[] = {2, 3, 5, 7, ...};
2. Get hascode for each word like this
     int getHashCode(String str){	     
	     int hash = 31;
	     for(i =0 to length of str){
		    hash = hash*primes['a' - str.charAt[i]];
		 }
		 return hash;
	 }
3. Now we can create a dictionary with all given words:
   //This hash table or map will maintain, integer as a key and a list of strings as a value.
   //This is a standard approach to implement hash map. You can find it in any api so i am  not mentioning its details here.
   // You can look in to java.util.HashMap   
   void loadDictionary(String[] words){
      for( word from words ; i = 0 to length of words)   {
         int hash  = getHashCode(word);
		 List<String> anagrams = dictionary.get(hash);
         if(anagrams ! = null){
             anagrams.add(word);
         } else 
		    List<String> newAnagrams = new ArrayList<String>();
			newAnagrams.add(word);
		    dictionary.put(hash, newAnagrams);
		 }
	}
   }
4. Now here is the approach to find anagrams:
   int findNumberOfAnagrams(String str){
   List<String> anagrams = dictionary.get(getHashCode(str));
      return anagrams.size();
   }

- Ajeet October 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

A hashmap such as
HashMap<String, LinkedList<String>> anagramHaspMap
such that the key is the string which is alphabet sorting of the input strings and the linkedlist is the list of the anagrams for the String.

For example for "eat" the data will be stored as:
"aet" : "eat" -> "tea" -> "ate" -> null

so for a given input word sort it in alphabetic order and then perform a hash look up.

- subahjit October 20, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I like your approach

- allanchanly October 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@allanchaly Thanks

- subahjit October 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Based on the observation that all words with the same anagrams shared the same histogram (counting of each individual letter), if the only query that we need is counting query (count the number of words in the same anagrams) then we should use hash map.
The mapping processing is following

word -> histogram -> count

Complexity
- word -> histogram : O(l) with l is the length of the words
- histogram -> count : O(1) as we can pre-compute the value of each entry (count)

The overall complexity is O(l), the solution require additional space O(m) with m is number of anagrams in the lists.

Now if we tight of space, then the best approach is to use a sorted list of words. We ordered all words based on its representative anagrams for example: 'abc', 'bac', 'cab' all be presented by 'abc'. We now can use a binary search to find the first element in the anagram (lower_bound() function in C++) and find the first element of the next anagram (upper_bound() function in C++) the number of words with same anagram is the difference of these two number.

The complexity of the approach is O(l) * O(log N) with N = 10000 and l is the length of the words however this approach require no additional space, the list of the same anagram is available immediately. Note that for the hashmap approach it takes O(N) to build this list.

- LinhHA05 October 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

If we have to count\return only number of anagrams for a string than why should we maintain words .. ?
We can use a HashMap, that will store key as a hash code (with hash collision for all anagrams - similar to my answer) and count as a value.
Each time a words occurs we will check in hashMap and just increase the count .. :)

Complexity will be O(1) to find all anagrams and space will be O(N), n = number of different anagram sets.

- Ajeet October 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

You have unique hash code because all anagrams share the same histogram. Using your hash code is one way to map between the histogram and the count but that is not the only hash function we can use. Basically any good hash function computed from the histogram would work. The reason that I don't think your hash function is a good choice due to the potential to overflow.

I will discuss to interviewer about what are the queries that application will support. if counting is the only query then we don't need to maintain the whole list.

- LinhHA05 October 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

yea agree.

- Ajeet October 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.*;

public class Anagrams
{

    private static Map<Character, Integer> charHashValuemap = new HashMap<Character, Integer>(26);

    public static void main(String[] args)
    {
	populateCharHashValuemap();
	generateAnagrams();

    }

    private static void generateAnagrams()
    {
	Map<Integer, Map<Integer, List<String>>> anagramMap = new HashMap<Integer, Map<Integer, List<String>>>();
	Scanner sc = new Scanner(System.in);
	System.out.println("Please enter the count of list:");
	int count = sc.nextInt();
	System.out.println("Please insert strings(press enter after each insert):");

	int hashValue = 0;
	for (int i = 0; i < count; i++)
	{
	    String string = sc.next().toLowerCase();
	    hashValue = getStringHashValue(string);
	    if (anagramMap.containsKey(string.length()))
	    {
		if (anagramMap.get(string.length()).containsKey(hashValue))
		{
		    anagramMap.get(string.length()).get(hashValue).add(string);
		}
		else
		{
		    List<String> innerList = new ArrayList<String>();
		    innerList.add(string);
		    anagramMap.get(string.length()).put(hashValue, innerList);
		}
	    }
	    else
	    {
		Map<Integer, List<String>> innerHashMap = new HashMap<Integer, List<String>>();
		List<String> innerList = new ArrayList<String>();
		innerList.add(string);
		innerHashMap.put(hashValue, innerList);
		anagramMap.put(string.length(), innerHashMap);
	    }

	}

	while (true)
	{
	    System.out.println("Please insert string you want to check anagrams:");
	    String outputString = sc.next().toLowerCase();
	    int hashCode = getStringHashValue(outputString);
	    if (anagramMap.containsKey(outputString.length()))
	    {
		if (anagramMap.get(outputString.length()).containsKey(hashCode))
		{
		    for (String anagram : anagramMap.get(outputString.length()).get(hashCode))
		    {
			System.out.println(anagram);
		    }
		}
		else
		{
		    System.out.println("Anagrams doesnt exist for string :" + outputString);
		}
	    }
	    else
	    {
		System.out.println("Anagrams doesnt exist for string :" + outputString);
	    }
	    System.out.println("You want to continue(Y/N):");
	    if (sc.next().equalsIgnoreCase("N"))
	    {
		break;
	    }
	}

    }

    private static int getStringHashValue(String string)
    {
	char[] charArray = string.toCharArray();
	int hashValue = 0;
	for (char character : charArray)
	{
	    hashValue += charHashValuemap.get(character);
	}
	return hashValue;

    }

    private static void populateCharHashValuemap()
    {
	charHashValuemap.put('a', 1);
	charHashValuemap.put('b', 2);
	charHashValuemap.put('c', 3);
	charHashValuemap.put('d', 4);
	charHashValuemap.put('e', 5);
	charHashValuemap.put('f', 6);
	charHashValuemap.put('g', 7);
	charHashValuemap.put('h', 8);
	charHashValuemap.put('i', 9);
	charHashValuemap.put('j', 10);
	charHashValuemap.put('k', 11);
	charHashValuemap.put('l', 12);
	charHashValuemap.put('m', 13);
	charHashValuemap.put('n', 14);
	charHashValuemap.put('o', 15);
	charHashValuemap.put('p', 16);
	charHashValuemap.put('q', 17);
	charHashValuemap.put('r', 18);
	charHashValuemap.put('s', 19);
	charHashValuemap.put('t', 20);
	charHashValuemap.put('u', 21);
	charHashValuemap.put('v', 22);
	charHashValuemap.put('w', 23);
	charHashValuemap.put('x', 24);
	charHashValuemap.put('y', 25);
	charHashValuemap.put('z', 26);
    }

}

- Ankit Garg October 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Roughly (you can optimize, tweak this in obvious ways).

A string-key based hash table that "keeps" duplicates (doesn't overwrite).
One can think of how to design this, but since anagram equivalence classes are rarely large... who cares.

Simply hash these: < key=linearsort(string), data=string> into the hash table.

Then you are basically done.
How you design the details is boring....

- S O U N D W A V E October 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

"Letter counts" on a string is roughly equal to linear sort == bucket sort (bucket size = 1)

So in the abstract, any linear sort on strings works.

I think the key idea is we hash on the key== anylinearsort(string) and keep the original string as data.

- S O U N D W A V E October 19, 2013 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More