Yahoo Interview Question
Applications DevelopersCountry: United States
Interview Type: Written Test
@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?
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.
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
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
#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;
}
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);
}
}
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;
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");
}
}
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");
}
}
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");
}
}
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];
}
}
}
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
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";
}
}
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";
}
}
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
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
# 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
/**
* 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;
}
}
/**
* 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;
}
}
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;
}
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
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;
}
.
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;
}
}
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 "";
}
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"));
}
}
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.
- zahidbuet106 May 03, 2014