Yahoo Interview Question for Software Development Managers


Team: Y! Suite
Country: United States
Interview Type: In-Person




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

There is much better way to check if two strings are anagrams without using any maps in O(n) time and O(1) space where n is the length of the longest string.

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 a word will have the same UNIQUE product. For example: prod(TEA) = prod(ATE) = prod(ETA) = prod(TAE) = prod(AET) = prod(EAT) = 71*11*2 = 154

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

public boolean isAnagram (String word1, String word2)
{
	word1 = word1.toLower();
	word2 = word2.toLower();

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

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

	return word1Key == word2Key;
}

- zahidbuet106 May 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

sort them compare them
or
use map to 256 letters

- Anonymous October 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 votes

There is much better way to check if two strings are anagrams without using any maps in O(n) time and O(1) space where n is the length of the longest string.

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 a word will have the same UNIQUE product. For example: prod(TEA) = prod(ATE) = prod(ETA) = prod(TAE) = prod(AET) = prod(EAT) = 71*11*2 = 154

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

public boolean isAnagram (String word1, String word2)
{
    if(word1.length() != word2.length())
        return false;

	word1 = word1.toLower();
	word2 = word2.toLower();

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

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

	return word1Key == word2Key;
}

- zahidbuet106 May 12, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

We are comparing the character of str2 with the str1. so increment the count on the character when encounter the character in str1 and decrement in str1.

if the length of the two string is different return false and if any of the element in the count array is non zero then return false .

bool areAnagram(char *str1, char *str2)
{
    // Create two count arrays and initialize all values as 0
    int count[NO_OF_CHARS] = {0};
    int i;


    for (i = 0; str1[i] && str2[i];  i++)
    {
        count[str1[i]]++;
        count[str2[i]]--;
    }



    if (str1[i] || str2[i])
      return false;


    for (i = 0; i < NO_OF_CHARS; i++)
        if (count[i])
            return false;
     return true;
}

complexity O(n).
space complexity : 265*sizeof(int)

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

But it's O(n+m) where m is NO_OF_CHARS. e.g. if your strings only have 5 chars each (areAnagram ("hello","elolh")), it is inefficient because it still loops through all possible chars.

I think better would be:

int lenstr1=0;
int lenstr2=0;

for (i=0; str1[i]; i++) {
	count[str1[i]]++;            //increment letter element same as your program
	lenstr1++;
}
for (i=0; str2[i]; i++) {
	if (--count[str2[i]] <0) {return false;}   //decrement letter - if <0 then we had too many of this letter, so they're anagrams.
	lenstr2++;
}
if (lenstr1!=lenstr2) {return false;}       //if lengths are unequal, they're not anagrams
return true;           //if lengths are the same and str2 didn't have too many of any particular letter, then it's an anagram

- rng October 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 votes

There is much better way to check if two strings are anagrams without using any maps in O(n) time and O(1) space where n is the length of the longest string.

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 a word will have the same UNIQUE product. For example: prod(TEA) = prod(ATE) = prod(ETA) = prod(TAE) = prod(AET) = prod(EAT) = 71*11*2 = 154

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

public boolean isAnagram (String word1, String word2)
{
    if(word1.length() != word2.length())
        return false;

	word1 = word1.toLower();
	word2 = word2.toLower();

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

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

	return word1Key == word2Key;
}

- zahidbuet106 May 26, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

Time: O(n)
Space: 265*size of (int)
Disclaimer : Not sure it this works for alphabets other than English.

public static boolean areAnagrams(String first, String second){
		if(first.length() != second.length())
			return false;
		int[] char_values = new int[256];
		char charAt;
		int uniqueCharsInFirstString = 0;
		int completedCharsSecondString = 0;
		for (int i = 0; i < first.length(); i++) {
			charAt = first.charAt(i);
			if(char_values[charAt] == 0){
				uniqueCharsInFirstString++;
			}
			char_values[charAt]++;
		}
		for (int i = 0; i < second.length(); i++) {
			charAt = second.charAt(i);
			if(char_values[charAt] == 0)
				return false;
			--char_values[charAt];
			if(char_values[charAt] == 0){
				completedCharsSecondString++;
				if(uniqueCharsInFirstString == completedCharsSecondString){
					return (i == second.length()-1);
				}
			}
		}		
		return false;
	}

- Rakesh Roy October 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

Generate the hash code for both the strings, then check the hash value. O(n) time complexity.

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

This will only work if you make the hashCode method yourself.

- nothing special here October 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

1.O(n) time. Space complexity depends on the type of character-set involved. For instance, ASCII requires 128, ANSI 256, and unicode demands 2^16 -1.

if(n1==0 && n2==0)
  return 1;
if(n1==0 || n2==0)
  return 0;
if(n1!=n2)
  return 0;
for(i=0;i<n1;i++)
   t[s[i]]++;
for(i=0;i<n2;i++)
{
  if(t[s2[i]]==0)
     return 0;
}
return 1;

If space is an issue but we can compromise on time: O(n lg n) time and O(1) space where n is the length of the longer string, if they are not anagrams.

if(n1==0 && n2==0)
  return 1;
if(n1==0 || n2==0)
  return 0;
if(n1!=n2)
  return 0;
sort(s1);
sort(s2);
for(i=0;i<n1;i++)
{
   if(s1[i]!=s2[i])
      return 0;
}
return 1;

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

You have a few problems with your code, but the biggest one is your associative array solution has a problem with repeated characters.

aab
abb

This would return true. You want to increment/decrement as needed.

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

typedef unsigned int uint;

#define ALPH_SIZE 26  //for English alphabet 
                                       //so long as lower, upper case parts live in contiguous
                                       //ranges of any underlying encoding (ascii, etc.)

uint count[2*ALPH_SIZE + 1]; //lower, upper case & other junk
uint h( char x )
{
    return (x >= 'a' && x <='z' ? x-'a' :           //lower case
            x >= 'A' && x <='Z' ? x-'A'+ALPH_SIZE : //upper case
            2*ALPH_SIZE)    //all other characters
                                              
}

/* precondition:  you supply it with strings on English alphabet 
                  that is, the rest of the code in your program
                  should not create junk strings/characters  if you want proper results    */

if( s1.length != s2.length ) return false;

for(i=0; i < s1.length ; i++) count[h(s1[i])]++, count[h(s2[i])]--;
for(i=0; i < 2*ALPH_SIZE ; i++) if ( count[i] ) return false;

return true;

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

this is solution in python .It uses dictionary dataype .The solution can be obtained in O(n).Here the sample inputs given are "rescue" and "secure".You can change it as per your need

#!/usr/local/bin/python2.7
    
dic = {}
flag = 0

inp1 = "rescue" 
inp2 = "secure"

for i in range(0,len(inp1)) :
  dic[inp1[i]] = 0

for i in range(0,len(inp1)) :
  dic[inp1[i]] = dic[inp1[i]] + 1

  
for i in range(0,len(inp2)) :
  if dic[inp2[i]] > 0 :
    dic[inp2[i]] = dic[inp2[i]] - 1
  else :
    flag = 1
    break
  
if flag == 0 :
  for key in dic.keys() :
    if dic[key] > 0 :
      flag = 1
      break

if flag == 1 :
  print "not anagram"
else :
  print "anagram"

- jithin November 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Time: O(n)
Space: O(1)

If s2 is an anagram of s1, then s2 will be part of s1s1

eg:
s1 = computer
s2 = tercompu

then s2 will be part of s1s1 = computercomputer

just check is s2 is part of s1s1

- Charles November 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This works only if s1 is a rotation of s2. Anagrams aren't the same as rotations.

For eg. s1 = "world" s2="rwodl"

Your code would fail in this case

- Anonymous December 31, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static boolean anagram(String s1, String s2){
		int [] ca = new int[26];
		for(char c : s1.toCharArray())
			ca[ c - 'a'] += 1;
		for(char c: s2.toCharArray())
			ca[c- 'a' ] -= 1;
		for ( int i : ca)
			if ( i!= 0)
				return false;
		return true;
	}

- Anonymous December 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package edu.sjsu.java.string;

import java.util.Arrays;

public class AnagramTest {

	public static boolean isAnagram(String s1, String s2) {
		if (s1 == null || s2 == null) {
			return false;
		}

		if (s1.length() != s2.length()) {
			return false;
		}

		char[] c1 = s1.toCharArray();
		char[] c2 = s2.toCharArray();

		Arrays.sort(c1);
		Arrays.sort(c2);

		String sc1 = new String(c1);
		String sc2 = new String(c2);

		return sc1.equals(sc2);
	}

}

- pawanKjajara February 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

All we have to do is to tell if the two strings have exact same characters if I'm not misunderstanding from what I read from the wikipedia.

Thus, we can just use a hash table with the key as the hash and the value of number of times it shows up. Once we have this hash table, we traverse through it.

All the values should be divisible by 2 (i.e. value %2 ==0) if not, it is not an anagram.

- J-Techsha February 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is O(n) time and constant space.

public static boolean areAnagrams(String s1, String s2){
		if(s1.length() != s2.length())
			return false;
		
		s1 = s1.toLowerCase();
		s2 = s2.toLowerCase();
		
		int xorResult = 0;
		
		for(int index = 0; index < s1.length(); index ++){
			xorResult ^= s1.charAt(index);
		}
		
		for(int index = 0; index < s2.length(); index++){
			xorResult ^= s2.charAt(index);
		}
		
		return xorResult == 0;
	}

- bari October 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This won't work if s1="aabbcc" and s2="ddeeff". In either case the xorResult will be 0 only.

- Silent May 31, 2015 | 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