Yahoo Interview Question for Applications Developers


Country: United States
Interview Type: Written Test




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

I have an elegant solution in my mind which only takes O(n) time and O(1) space:

1) Assign each of the 26 letters a unique prime number i.e. {'a'=>2, 'b'=>3, 'c'=>5, 'd'=>7, 'e'=>11, ..., 'l' = 37, ..., 's' => 67, .... ,'t' => 71,.... 'z' => 101}
2) All the anagrams of the first word will have the same UNIQUE product. For example: prod(TEA) = 71*11*2 = 154
3) Now, go through each position of the 2nd word and find cumulative product at each position and keep the index of a cum-prod in a hashmap.
4) while passing through the letters of 2nd word check if the current cum-prod is divisible by the prod(2nd word). If it is the voila! we got our answer and the anagram starts at the position where cum-prod is equal to the quotient of the devision.

public static final int primes[] = {2, 3, 5, 7, 11, 13, ......, 101} ;

public String findAnagramicSubString (String haystack, String needle)
{
	haystack = haystack.toLower();
	needle = needle.toLower();

	int needleKey = 1;	
	for(int i=0; i<needle.length; i++)
		needleKey*=primes[needle[i]-'a'];

	Map<Integer, Integer> cumprods = Maps.newHashMap();

	int cumprod = 1;
	for(int i=0; i<haystack.length; i++)
	{
		cumprod*=primes[haystack[i]-'a'];
		if(cumprod%needleKey==0 && cumprods.containsKey(cumprod/needleKey))
		{
			return haystack.substring(cumprods.get(umprod/needleKey), needle.length);
		}
	

		cumprods.put(cumprod, i);
	}

	return "";
}

- zahidbuet106 May 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

trash

- people July 11, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@people : I wonder if u had grasp the concept behind the solution. Although the solution is not efficient in case of non-english dictionary words...in which case the production calculation will be little expensive... do u have a solution of o(n) without generating permutations?

- zahidbuet106 July 11, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes, trash. Overflow issues abound, things won't fit in the registers (for large enough strings, like supercalifra...) and then you cannot rely on O(1) divisibility check.


So O(n) time and O(1) space claims are BS.

- Anonymous July 11, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The technique is like hashing but prod(TEA) = prod(TAE) in which TAE is not an anagram of TEA. So we need to take care of this situation and in worst case you need to do this check with each position and then the complexity becomes O(mn). As far as I know, we can use Robin-Karp or KMP algorithm with "n" permutations of the pattern to be matched. Then complexity will be O(mn2) (it's mn square) where m= length of the given string, n=length of the pattern to be matched

- Sreekar October 31, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

package take2;
import java.util.*;
class v
{
	static void anagram(String x, String y)
	{
		HashMap<Character, Integer> h = new HashMap<Character, Integer>();
		for(int i = 0; i < y.length(); i++)
		{
			if(h.containsKey(y.charAt(i)))
			{
				h.put(y.charAt(i), h.get(y.charAt(i)) + 1);
			}
			else
				h.put(y.charAt(i),1);
		}
		//System.out.println(h.toString());
		for(int i = 0; i <= x.length() - y.length() ; i++)
		{
			@SuppressWarnings("unchecked")
			HashMap<Character, Integer> h1 = (HashMap<Character, Integer>) h. clone();
 			int j = i;
			for( j = i; j < i + y.length(); j++)
			{
				char g = x.charAt(j);
				if(h1.containsKey(g))
				{
					if(h1.get(g) > 0)
						h1.put(g, h1.get(g)-1);
					else
						break;
				}
				else
					break;
				//.out.println(i + "  " +h1.toString());
			}
			if(j == i + y.length())
				System.out.println(x.substring(i,i+y.length()));
		}
	}
	
	public static void main(String[] args) {
		anagram("teaetate", "tea");
	}
}
//47

- Anonymous April 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

#include <string>
#include <iostream>
#include <algorithm>

int main(int argc, char** argv) // <appName> word1 word2, where word1 is tested to see if it's in word2
{
	if (argc < 3)
		return 0; // failed, not enough arguments

	string word1 = argv[1];
	string word2 = argv[2];

	if (word2.length() < word1.length())
	{
		cout << "Word2 must be at least word1 length" << endl;
		return 0;
	}
	int len = word1.length();
	std::sort(word1.begin(), word1.begin() + len);
	// check for match in the moving window
	for(int i = 0; i <= word2.length() - len; i++)
	{
		string sub = word2.substring(i, i+len);
		std::sort(sub.begin(), sub.begin()+len);
		if (sub == word1)
		{
			cout << "Word1:" << argv[1] << ", was found in " << word2 << endl;
			return 1;
		}
	}
	cout << "anagram not found." << endl;
	return 0;
}

- TomT April 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

input string1 (tea)
input string2 (slate)

for each char x in string2
check if x found in string1
if no continue
if yes
get substring astr of index of x + length string1 from string2
check if it is anagram or not.
end.

- Anonymous April 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

package com.test;

public class AnagramTest {

	public static void main(String args[])
	{
		String word1="tea";
		String word2="slwerateeat";
		// Sort Word1
		String sortedWord1=sortWord(word1.toCharArray());
		// Create substring of word1 lengh from word 2 and compare if words are same. if its same print the word from word 2 starting with that index.

		boolean found=false;
		int wordIndex=0;
		while(!found)
		{
			if(wordIndex+word1.length()<=word2.length())
			{
				String subWord=word2.substring(wordIndex, wordIndex+word1.length());
				// Sort subword
				String sortedWord2=sortWord(subWord.toCharArray());
				if(sortedWord1.equals(sortedWord2))
				{
					found=true;
				}else{
					wordIndex++;
				}
			}else{
				break;
			}
		}
		if(found)
		{
			String anagramWord=word2.substring(wordIndex, wordIndex+word1.length());
			System.out.println(anagramWord);
		}else{
			System.out.println("No Match");
		}

	}

	// Simple method to sort characters of a Word
	private static String sortWord(char[] string)
	{

		for(int i=0;i<string.length;i++)
		{
			for(int j=i+1;j<string.length;j++)
			{
				// Swap the charcters
				if(string[i]>string[j])
				{
					char temp=string[j];
					string[j]=string[i];
					string[i]=temp;
				}
			}
		}
		return new String(string);
	}

}

- Brijesh Singh April 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

Calculate the weight of 1st string then calculate the weight of 2nd string.
Compare the two if both are same then True else False.
Ex:
Input 1:
eat
Input 2:
plate
wt1 = e + a + t;
wt2 = a + t + e; // Last three letters of Input2
if(wt1 == wt2)
True;
else
false;

- Rajani Kanta Acharya April 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The above will not work for all the cases, this will fail in lots of cases.

wt1 = e + a + t;
wt2 = d + b + t;

then also it will be same and it will give us wrong result.
We need extra care for case sensitivity.

- Rajani Kanta Acharya April 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Anagram {

	public static void findWord(String part, String full) {
		char c, ch;
		int k = 0;
		int count = 0;
	
		mainloop: for (int i = 0; i < full.length(); i++) {
			for (int j = 0; j < part.length(); j++) {
				c = full.charAt(i);
				if (c == part.charAt(j)) {
					k = i;
					break mainloop;
				}
			}
		}
		StringBuffer sb = new StringBuffer();
		secondloop: for (int v = k; v < full.length(); v++) {
			int count2 = 0;
			for (int p = 0; p < part.length(); p++) {
				ch = full.charAt(v);
				if (ch == part.charAt(p)) {
					sb.append(part.charAt(p));
					count++;
				} else {
					count2++;
					if (count2 == part.length() && count < part.length()) {
						System.out.println("no anagram found");
						break secondloop;
					}

				}

			}
		}
		if (count == part.length()) {
			System.out.println("String   " + sb.toString());
		}

	}

	public static void main(String[] args) {
		findWord("eat", "slate");
	}

}

- Anonymous July 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Anagram {

	public static void findWord(String part, String full) {
		char c, ch;
		int k = 0;
		int count = 0;
	
		mainloop: for (int i = 0; i < full.length(); i++) {
			for (int j = 0; j < part.length(); j++) {
				c = full.charAt(i);
				if (c == part.charAt(j)) {
					k = i;
					break mainloop;
				}
			}
		}
		StringBuffer sb = new StringBuffer();
		secondloop: for (int v = k; v < full.length(); v++) {
			int count2 = 0;
			for (int p = 0; p < part.length(); p++) {
				ch = full.charAt(v);
				if (ch == part.charAt(p)) {
					sb.append(part.charAt(p));
					count++;
				} else {
					count2++;
					if (count2 == part.length() && count < part.length()) {
						System.out.println("no anagram found");
						break secondloop;
					}

				}

			}
		}
		if (count == part.length()) {
			System.out.println("String   " + sb.toString());
		}

	}

	public static void main(String[] args) {
		findWord("eat", "slate");
	}

}

- Anonymous July 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Anagram {

	public static void findWord(String part, String full) {
		char c, ch;
		int k = 0;
		int count = 0;
	
		mainloop: for (int i = 0; i < full.length(); i++) {
			for (int j = 0; j < part.length(); j++) {
				c = full.charAt(i);
				if (c == part.charAt(j)) {
					k = i;
					break mainloop;
				}
			}
		}
		StringBuffer sb = new StringBuffer();
		secondloop: for (int v = k; v < full.length(); v++) {
			int count2 = 0;
			for (int p = 0; p < part.length(); p++) {
				ch = full.charAt(v);
				if (ch == part.charAt(p)) {
					sb.append(part.charAt(p));
					count++;
				} else {
					count2++;
					if (count2 == part.length() && count < part.length()) {
						System.out.println("no anagram found");
						break secondloop;
					}

				}

			}
		}
		if (count == part.length()) {
			System.out.println("String   " + sb.toString());
		}

	}

	public static void main(String[] args) {
		findWord("act", "aitcon");
	}

}

- grep_code July 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Anagram {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String s = "burstein", sub = "turs";
		System.out.println(containsAnagram(sub, s));
	}
	
	public static String containsAnagram(String sub, String s){
		
		String sortSub = sort(sub);
		
		for(int i = 0; i < s.length(); i++){
			if(sort(s.substring(i, sub.length() + i)).equals(sortSub)){
				return s.substring(i, sub.length() + i);
			}
		}
		return "NONE";
	}
	
	public static String sort(String s){
		char[] a = new char[s.length()];
		for(int i = 0; i < s.length(); i++){
			a[i] = s.charAt(i); 
		}
		
		sort(a, 0, a.length);
		s = "";
		for(int i = 0; i < a.length; i++){
			s += a[i] + "";
		}
		return s;
	}
	
	public static void sort(char[] a, int lo, int hi){
		int N = hi - lo;
		if(N <= 1){
			return;
		}
		int mid = lo + N/2;
		sort(a, lo, mid);
		sort(a, mid, hi);
		
		int i = lo, j = mid;
		char[] aux = new char[N];
		for(int k = 0; k < N; k++){
			if( j == hi){
				aux[k] = a[i++];
			}
			else if(i == mid){
				aux[k] = a[j++];
			}
			else if( (int)a[j] < (int)a[i]){
				aux[k] = a[j++];
			}
			else{
				aux[k] = a[i++];
			}
		}
		for(int k = 0; k < N; k++){
			a[lo + k] = aux[k];
		}
	}

}

- Will B August 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int code[26];

int32_t calculate_hash(string s) {
int len = s.size();
int32_t hash_value = 1;
int32_t modulo = 2147483647;
for(int i = 0; i < len; ++i) {
int value = s[i] - 'a';
hash_value = (hash_value * code[value])
% modulo;
}
return hash_value;
}

int32_t calculate_hash_substring(string s, int start, int end) {
int32_t hash_value = 1;
int32_t modulo = 2147483647;
for(int i = start; i <= end; ++i) {
int value = s[i] - 'a';
hash_value = (hash_value * code[value])
% modulo;
}
return hash_value;
}

string find_anagram_in_second(string &first, string &second) {
string result;

int first_hash = calculate_hash(first);
int flen = first.size();
int slen = second.size();

for(int i = 0; i <= slen - flen; ++i) {
int end = i + flen - 1;
int shash = calculate_hash_substring(second,
i,
end);
if(shash == first_hash) {
result = second.substr(i, flen);
return result;
}
}
return "None";
}

int main() {

for(int i = 0; i < 26; ++i) {
code[i] = nth_prime(i+1);
}

string first = "let";
string second = "slate";

cout<<find_anagram_in_second(first, second);

first = "tea";
second = "slate";

cout<<find_anagram_in_second(first, second);

}

Output:
None
ate

- neham December 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class anagrams {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		String input1 = scan.next(); // tea
		String input2 = scan.next(); // slate
		
		System.out.println(checkAnagram(input1, input2));
	}
	
	public static String checkAnagram(String input1, String input2) {
		String input1input1 = input1 + input1;
		
		for(int i = 1; i <= input1.length(); i++) {
			String temp = input1input1.substring(i, i+input1.length());
			if(input2.contains(temp)) {
				return temp;
			}
		}
		return "NONE";
	}
}

- Ashwin November 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class anagrams {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		String input1 = scan.next();
		String input2 = scan.next();
		
		System.out.println(checkAnagram(input1, input2));
	}
	
	public static String checkAnagram(String input1, String input2) {
		String input1input1 = input1 + input1;
		
		for(int i = 1; i <= input1.length(); i++) {
			String temp = input1input1.substring(i, i+input1.length());
			if(input2.contains(temp)) {
				return temp;
			}
		}
		return "NONE";
	}
}

- Ashwin November 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

from collections import (
    Counter
)


def find_consecutive(word, char_count, result=None):
    result = result if result else []
    counter = copy.deepcopy(char_count)
    if len(word) == 0:
        return result

    temp_result = ""
    temp_word = ""
    for index, char in enumerate(word):
        if char in counter:
            temp_result = "{}{}".format(temp_result, char)
            counter[char] = counter[char] - 1
            if counter[char] == 0:
                counter.pop(char)
            temp_word = word[index+1: ]
        else:
            temp_word = word[index+1: ]
            break

    del counter
    if len(temp_result) > 1:
        result.append(temp_result)

    return find_consecutive(
        temp_word, char_count, result
    )




def test_if_first_in_consecutive_second(first, second):
    char_count = Counter(list(first))
    result = find_consecutive(second, char_count)
    return result

if __name__ == "__main__":
    result = test_if_first_in_consecutive_second(
        first="tea",
        second="slate"
    )

    print result

- neat_code December 26, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n) solution in python.

class Solution(object):
    def findAnagrams(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        result = []
        
        count = [0] * 26
        
        for c in p:
            count[ord(c)-ord('a')] += 1
            
        left = 0
        right = 0
        
        while right < len(s):
            count[ord(s[right])-ord('a')] -= 1
            
            while left <= right and count[ord(s[right])-ord('a')] < 0:
                count[ord(s[left])-ord('a')] += 1
                left += 1
                
            if right - left + 1 == len(p):
                return True
                
            right += 1
        
        return False

- Prem February 05, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

# Modified Rabin Karp algorithm
# Time complexity: O(n)
# Space complexity: O(26) = O(1)

from collections import defaultdict

class Solution(object):
    def findAnagrams(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: List[int]
        """
        result = []
        hash_map = defaultdict(int)
        
        for c in p:
            hash_map[c] += 1
            
        left = 0
        right = 0
        
        while right < len(s):
            hash_map[s[right]] -= 1
            
            while left <= right and hash_map[s[right]] < 0:
                hash_map[s[left]] += 1
                left += 1
            
            right += 1
            if right - left == len(p):
                return True

        return False

- Prem February 05, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/**
 * Created by MQamri on 17-05-2017.
 */
public class StringAnagrams
{
    public static void main(String[] args)
    {
       System.out.println(getAnagram("slate","let"));
    }

    public static String getAnagram(String source,String test)
    {
       int s =0;

        String returnValue = "NONE";
        for (int i =0;i<source.length();i++)
        {
            if(test.contains(source.subSequence(i,i+1)) )
            {
                s++;
            }
            else
            {
                s =0;
            }
            if(s == test.length())
            {
                returnValue = source.substring(i- s +1,i+1);
                break;
            }
        }
        return returnValue;
    }
}

- Musab May 17, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/**
 * Created by MQamri on 17-05-2017.
 */
public class StringAnagrams
{
    public static void main(String[] args)
    {
       System.out.println(getAnagram("slate","let"));
    }

    public static String getAnagram(String source,String test)
    {
       int s =0;

        String returnValue = "NONE";
        for (int i =0;i<source.length();i++)
        {
            if(test.contains(source.subSequence(i,i+1)) )
            {
                s++;
            }
            else
            {
                s =0;
            }
            if(s == test.length())
            {
                returnValue = source.substring(i- s +1,i+1);
                break;
            }
        }
        return returnValue;
    }
}

- Mu May 17, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

One quick approach could be:
1) Generate all permutation of the input word.
2) Apply substring operation for all of them and return result if any of them matches.

However complexity to generate all permutation is itself in O(2^n).

- Anonymous April 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Assume that all the letters are in lower case. Then we could use the following algorithm. The time complexity is O(26n)

#include<iostream>
#include<string>
using namespace std;

bool check(int* array1, int* array2, int length){
    for(int i = 0; i < length; ++i){
        if(array1[i] != array2[i]){
            return false;
        }
    }
    return true;
}

int isAnagram(char* first, int length1, char* second, int length2){
    if(length2 < length1){
        return false;
    }
    int count[26];
    int currentCount[26];
    memset(count, 0, sizeof(count));
    memset(currentCount, 0, sizeof(currentCount));

    for(int i = 0; i < length1; ++i){
        ++count[first[i] - 'a'];
    }
    for(int i = 0; i < length2; ++i){
        if(i >= length1 - 1){
            ++currentCount[second[i] - 'a'];
            if(check(count, currentCount, 26)){
                return i - length1 + 1;
            }
            --currentCount[second[i - length1 + 1] - 'a'];
        }else{
            ++currentCount[second[i] - 'a'];
        }
    }
    return -1;

}

int main(){
    char* first = "tea";
    char* second = "slate";
    int startIndex = -1;
    if((startIndex = isAnagram(first, strlen(first), second, strlen(second))) >= 0){
        cout<<string(second).substr(startIndex, strlen(first))<<endl;
    }else
        cout<<"none"<<endl;


}

- ravio April 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

This could be done also with a sliding window solution so that you only had to visit each character in the second word once where the window size = Length of word1. Since chars have to be consecutive, you don't need to generate all permutations, but could just compare the sorted value of the sliding window, returning the first match.

1. Sort word 1 (so tea is held as aet)
2. walk through each char of word 2 from 0 to word2.Length - word1.Length, filling window
3. when window (size 3) is full, compare the sorted window string with string from step 1.

1st Window = [S][L][A]. Sorts to ALS. ALS != AET
2nd Window = [L][A][T]. Sorts to ALT. ALT != AET
3rd Window = [A][T][E]. Sorts to AET. AET == AET.

I guess the time complexity is :

* time to walk word2 ( O (n) where n is length of word 2)
* plus time to insert into queue ( O(1) since it is just adding to end )
* plus time to remove from the queue ( O(1) since it is just removing from index 0)
* plus time to sort the window n - m times, when n is length of word 2 and m is length of word 1

- johny418 April 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You have to print the actual anagram word from Word 2.

- Brijesh Thakur April 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Here is C# code for the above

public static string GetSortedString(char[] chars)
    {
        List<char> charList = new List<char>();
        charList.AddRange(chars);
        charList.Sort();
        return new String(charList.ToArray());
    }

    protected static string FindAnagrams2(string word1, string word2)
    {
        string lookupString = GetSortedString(word1.ToCharArray());
        List<char> window = new List<char>();
        for (int idx = 0; idx < word2.Length; idx++)
        {
            window.Add(word2[idx]);
            if (window.Count > word1.Length)
                window.RemoveAt(0);
            if (window.Count == word1.Length && lookupString.Equals(GetSortedString(window.ToArray())))
            {
                return new String(window.ToArray());
            }
                
        }
        return null;
    }

.

- johny418 April 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 3 vote

Optimization of ravio's code that runs in |alphabet| + |needle| + |haystack|.

public static int anagramicSubstringIndex(String haystack, String needle) {
        if (haystack == null || needle == null || haystack.length() < needle.length()) {
            return -1;
        }
        int[] wantedCounts = new int[256];
        int[] diffs = new int[256];
        for (int i = 0; i < needle.length(); ++i) {
            wantedCounts[needle.charAt(i)]++;
            diffs[needle.charAt(i)]++;
        }
        for (int i = 0; i < needle.length(); ++i) {
            diffs[haystack.charAt(i)]--;
        }
        int diffCount = 0;
        for (int i = 0; i < 256; ++i) {
            if (diffs[i] != 0) {
                ++diffCount;
            }
        }
        int curPos = needle.length();
        while (diffCount != 0 && curPos < haystack.length()) {
            diffs[haystack.charAt(curPos)]--;
            if (diffs[haystack.charAt(curPos)] == 0) {
                diffCount--;
            } else if (diffs[haystack.charAt(curPos)] == -1) {
                diffCount++;
            }
            diffs[haystack.charAt(curPos-needle.length())]++;
            if (diffs[haystack.charAt(curPos-needle.length())] == 0) {
                diffCount--;
            } else if (diffs[haystack.charAt(curPos-needle.length())] == 1) {
                diffCount++;
            }
            ++curPos;
        }
        if (diffCount == 0) {
            return curPos - needle.length();
        } else {
            return -1;
        }
    }

- Danstahr April 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 votes

I have an elegant solution in my mind which only takes O(n) time and O(n) space:

1) Assign each of the 26 letters a unique prime number i.e. {'a'=>2, 'b'=>3, 'c'=>5, 'd'=>7, 'e'=>11, ..., 'l' = 37, ..., 's' => 67, .... ,'t' => 71,.... 'z' => 101}
2) All the anagrams of the first word will have the same UNIQUE product. For example: prod(TEA) = 71*11*2 = 154
3) Now, go through each position of the 2nd word and find cumulative product at each position and keep the index of a cum-prod in a hashmap.
4) while passing through the letters of 2nd word check if the current cum-prod is divisible by the prod(2nd word). If it is the voila! we got our answer and the anagram starts at the position where cum-prod is equal to the quotient of the devision.

public static final int primes[] = {2, 3, 5, 7, 11, 13, ......, 101} ;

public String findAnagramicSubString (String haystack, String needle)
{
	haystack = haystack.toLower();
	needle = needle.toLower();

	int needleKey = 1;	
	for(int i=0; i<needle.length; i++)
		needleKey*=primes[needle[i]-'a'];

	Map<Integer, Integer> cumprods = Maps.newHashMap();

	int cumprod = 1;
	for(int i=0; i<haystack.length; i++)
	{
		cumprod*=primes[haystack[i]-'a'];
		if(cumprod%needleKey==0 && cumprods.containsKey(cumprod/needleKey))
		{
			return haystack.substring(cumprods.get(umprod/needleKey), needle.length);
		}
	

		cumprods.put(cumprod, i);
	}

	return "";
}

- zahidbuet106 May 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

This solution will work with Java 1.5+ versions.
import java.util.*;

public class SolutionAnagram
{

static String isanagram(String word1, String word2) {
char[] oneArray = word1.toCharArray();
char[] twoArray = word2.toCharArray();
Arrays.sort(oneArray);
Arrays.sort(twoArray);
if(Arrays.equals(oneArray, twoArray)){
return word2;
}
if(oneArray.length>twoArray.length){
System.out.println("Word2 must be at least word1 length");
return "NONE";
}

int len = word1.length();
// check for match in the moving window
for(int i = 0; i <= word2.length() - len; i++)
{
String sub = word2.substring(i, i+len);
char[] subArray = sub.toCharArray();
Arrays.sort(subArray);

if (Arrays.equals(subArray,oneArray))
{
System.out.println("Word1:"+ word1+ ", was +found in " + word2) ;
return sub;
}
}
System.out.println("anagram not found.");
return "NONE";

}
/**
* @param args
*/
public static void main(String[] args)
{
System.out.println("result="+isanagram("tea","slate"));
System.out.println("result="+isanagram("let","slate"));

}

}

- Vicky May 01, 2014 | Flag Reply


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