Google Interview Question for Software Engineer in Tests


Country: United States
Interview Type: Phone Interview




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

This complexity is O(n) for this program.
I use a hashmap for storing the characters of the firstString. The hashmap has all the characters of firstString as key and its occurrence as value. As you iterate over the firstString, find if the character is already present in the map. If yes, then add plus one to its value. else make an entry with value as 1.
After constructing the map, iterate over the secondString and do a lookup against the hashmap to find the key.Decrement the value by 1 once an occurence is found. When the value of occurence becomes 0, remove the entry from hashmap.

Once the iteration is over, if the hashmap is empty, then secondString is an anagram of the firstString. else not an anagram.

The following is the code.

private boolean isAnagram(String firstString, String secondString) {
if(firstString.equals(secondString))
return true;
Map<Character,Integer> mapOfLettersWithOccurence = new HashMap<Character,Integer>();
for(int i = 0; i < firstString.length(); i++) {
char ch = firstString.charAt(i);
if(mapOfLettersWithOccurence.get(ch) != null) {
int occur = mapOfLettersWithOccurence.get(ch);
++occur;
mapOfLettersWithOccurence.put(ch, occur);
} else {
mapOfLettersWithOccurence.put(ch, 1);

}
}
for(int i = 0; i < secondString.length(); i++) {
char ch = secondString.charAt(i);
if(ch == ' ')
continue;
if(mapOfLettersWithOccurence.get(ch) == null)
return false;
else {
int occur = mapOfLettersWithOccurence.get(ch);
--occur;
if(occur == 0)
mapOfLettersWithOccurence.remove(ch);

}
}
if(mapOfLettersWithOccurence.isEmpty())
return true;

return false;
}

- Anand August 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

There is a small coding error is the above pgm. I have corrected it.



import java.util.HashMap;
import java.util.Map;

/*
* Write a method to determine if two strings are anagrams of each other.
e.g. isAnagram(“secure”, “rescue”) false
e.g. isAnagram(“conifers”, “fir cones”) true
e.g. isAnagram(“google”, “facebook”) false

*/
public class Anagram {

public static void main(String[] args) {
Anagram anag = new Anagram();
boolean isAnag = anag.isAnagram("secure","rescue");
System.out.println(isAnag);
}

private boolean isAnagram(String firstString, String secondString) {
if(firstString.equals(secondString))
return true;
Map<Character,Integer> mapOfLettersWithOccurence = new HashMap<Character,Integer>();
for(int i = 0; i < firstString.length(); i++) {
char ch = firstString.charAt(i);
if(mapOfLettersWithOccurence.get(ch) != null) {
int occur = mapOfLettersWithOccurence.get(ch);
++occur;
mapOfLettersWithOccurence.put(ch, occur);
} else {
mapOfLettersWithOccurence.put(ch, 1);

}
}
for(int i = 0; i < secondString.length(); i++) {
char ch = secondString.charAt(i);
if(ch == ' ')
continue;
if(mapOfLettersWithOccurence.get(ch) == null)
return false;
else {
int occur = mapOfLettersWithOccurence.get(ch);
--occur;
if(occur == 0)
mapOfLettersWithOccurence.remove(ch);
else
mapOfLettersWithOccurence.put(ch, occur);

}
}
if(mapOfLettersWithOccurence.isEmpty())
return true;

return false;
}
}

- Anand August 15, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

public static boolean begoAnagram(String a, String b){

if(a.length() != b.length()){
return false;
}

else if(a.length()%2 == 1){
if(a.charAt(a.length()/2 + 1) != (b.charAt(a.length()/2 + 1))){
return false;
}

}

else{

for(int i = 0; i < a.length() ; i++){
int j = (a.length() - 1) - i;
if(a.charAt(i) != b.charAt(j)){
System.out.println(i + "a char is : " + a.charAt(i));
System.out.println(j + "b char is: " + b.charAt(j));
System.out.println();
return false;
}


}
}




return true;

}

- Idaho August 15, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

In the scan of the second string, when the current occur is 0, for a character, one can return false, otherwise decrease occur. No need to remove the entry from hash table. Instead of checking if hash table is empty at the end, do a check to ensure all occurs are zero.

- sabz August 17, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Shouldn't you also convert the strings to lowercase before checking?

- code_maniac January 15, 2015 | Flag
Comment hidden because of low score. Click to expand.
3
of 3 vote

Based wikipedia description.
It seems the first case should return true. Is that right?

Then, a quick way to check will be use a hash of character to number.
Then compare the hash.
The hash can be implemented by array index if the string is ascii only.

- Jie August 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Here's a simple code using C#:

private static void Main(string[] args)
{
const string one = "secure";
const string two = "rescue";
bool result = IsAnagram(one, two);
Console.WriteLine("Strings \"{0}\" and \"{1}\" are {2} Anagrams!", one, two, result ? "" : "not");
}

private static bool IsAnagram(string one, string two)
{
if (one.Length != two.Length)
return false;

int hashOne = 0;
foreach (char c in one)
{
hashOne += c;
}

int hasTwo = 0;
foreach (char c in two)
{
hashTwo += c;
}

return hashOne == hashTwo;
}

- RBmain September 20, 2013 | Flag
Comment hidden because of low score. Click to expand.
3
of 3 vote

Keep an ascii char array.

Code :

boolean isAnagram(String str1, String str2) {
	char[] map = new char[256];

	int length1 = str1.length();
	int length2 = str2.length;

	for(int i = 0; i < length1; ++i) {
		char ch = str1.charAt(i);
		map[ch-0]++;
	}
	for(int i = 0; i < length2; ++i) {
		char ch = str2.length();
		map[ch-0]--;
	}

	boolean anagram = true;
	for(int i = 0; i < 256; ++i) {
		if(map[i] != 0) {
			anagram = false;
			break;
		}
	}

	return isAnagram;
}

- Srikant Aggarwal August 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 votes

Check the two strings can be done in one loop.

- Daniel Yin September 08, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

U should consider the " ",

if(ch==' ') continue;

- Anonymous September 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Yeah, @Jie has a valid question. Why isAnagram(“secure”, “rescue”) → false ??

- Anonymous August 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Simple typo.

- bunnybare August 15, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

#include <string>
#include <iostream>

int charCounts[26];

void changeCharCount(const char value, int amount) {

    int valueIndex = tolower(value) - 'a';

    if (valueIndex < 0 || valueIndex > 25)
        return;

    charCounts[valueIndex] += amount;
}

bool isAnagram(const std::string& a, const std::string& b) {
    // Count character occurances in a
    for (int i=0; i<a.size(); i++) {
        changeCharCount(a.at(i), 1);
    }

    // Decrement character occurances in b
    for (int i=0; i<b.size(); i++) {
        changeCharCount(b.at(i), -1);
    }

    // Check that all characters from a were used
    // and that b required no extras
    for (int i=0; i<26; i++) {
        if (charCounts[i] != 0)
            return false;
    }

    return true;
}

int main(int argc, char *argv[])
{
    std::cout << "secure, rescue: " << isAnagram("secure", "rescue") << std::endl;
    std::cout << "conifers, fir cones: " << isAnagram("conifers", "fir cones") << std::endl;
    std::cout << "google facebook: " << isAnagram("google", "facebook") << std::endl;
}

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

//Determine if two strings are anagrams of each other
import java.util.HashMap;
class AnagramApp
{
	public static void	main(String args[])
	{
		boolean is = isAnagram("stressed","desserts");
		System.out.println(is);
	}

	public static boolean isAnagram(String first, String second)
	{
		//both strings are null
		if(first == null && second == null){
			return true; //debatable whether or not it should return true or false
		}
		//one of the strings is null, but the other is not 
		if((first == null && second != null) || (first != null && second == null)){
			return false;
		}
		//if they are equal then they are anagrams
		if(first.equals(second)){
			return true;
		}
		//if the length doesn't match, they are not anagrams
		if(first.length() != second.length())
			return false;

		//as this point we have 2 non-null strings with matching lengths
		HashMap<Character,Integer> charMap = new HashMap<Character,Integer>();

		int i;
		Integer current;

		for(i = 0; i < first.length(); i++){

			current = charMap.get(first.charAt(i));
			if(current == null)
				current = 0;
			charMap.put(first.charAt(i), ++current);
		}

		Character k;
		Integer v;
		
		for(i = 0; i < first.length(); i++){
			k = second.charAt(i);
			v = charMap.get(k);
			if(v == null || ( v != null && --v < 0)){
				return false;
			} else {
				charMap.put(k,v);
			}				
		}
		return true;
	}

}

- mckeejm August 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hello Mother fucker guys,

Sopping posting codes without discussing algo.

--
Hello World

- Hello world August 15, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

first input rescue and secure should return true... na

- vara August 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

# Best Python solution. O(n)

from collections import Counter
anagrams = lambda s1, s2: Counter(s1) == Counter(s2)

- Ali August 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

iterate on each char of the first string, keep a count, and look into the second string for the char, if match is found remove it from the second string, at the end check if count and the length of the second string is 0.

private bool IsAnagram(string x, string y)
        {
            bool bResult = false;
            string a = x.Replace(" ", "");
            string b = y.Replace(" ", "");
            int count = a.Length;
            bool bMatch;
            foreach (char c in a)
            {
                count--;
                bMatch = false;
                for (int i = 0; i < b.Length; i++)
                {
                    if (c == b[i])
                    {
                        b = b.Remove(i, 1);
                        bMatch = true;
                        break;
                    }
                }
                if (!bMatch || b.Length==0)
                    break;
                
            }
            if (count == 0 && b.Length == 0)
                bResult = true;

            return bResult;
        }

- Pooja Singh August 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool isAnagram( char *s1, char *s2 )
{
	int map[255] = {0};

	if( ( s1 == NULL ) && ( s2 == NULL ) )
		return true;

	if( ( s1 == NULL ) || ( s2 == NULL ) )
		return false;

	while( *s1 != '\0' )
	{
		map[*s1]++;
		s1++;
	}

	while( *s2 != '\0' )
	{
		map[*s2]--;
		s2++;
	}

	for( int i = 0; i < 255; i++ )
	{
		if( map[i] != 0 )
			return false;
	}

	return true;
}

- Mukesh August 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

* i did this in O(n).
* i did this by maintaining a map of characters in a numerical array. since possible values of alphabets relative to 'a' is only from 0-25. so maintained a numerical array of 26 length and initialize each element to 0.
* next to do was traverse the given string and increase each index of the current characcter by one on occurence. [I ASSUMED THAT THE INPUT WAS NOT IN CAPS OR I WOULD HAD ADDED A SMALL stlwr TO FORMAT STRINGS TO LOWER CASE].
* also i ignored occurences of space and eliminated its processing. after mapping the first, i traversed the second and checcked of the index of that character was >0.
* also at the end i made a check for the residue if any related to corner cases. rest comments in the code

/***************************************
	* great codes are not starstruck
		- you have to bear pain, lots of pain
	*code_jazz, anagram
******************************************/

#include<stdio.h>
#include<string.h>

int mapping[26] = {0};

void mapFirst(char *initial)
{
    while(*initial != '\0')
    {
        if(*initial != ' ') //space has not to be processed
        {
            mapping[*initial-'a']++;    //hence record it
        }
        initial++; //increment it
    }//while ends

    return;
}//end of mapfirst

int traverseAndCheck(char *ref)
{
    int i;
    while(*ref != '\0')
    {
        if(*ref != ' ')
        {
            if(mapping[*ref-'a'] > 0)
            mapping[*ref-'a']--;
        else
            return 0;
        }
        ref++;
    }

    for(i=0;i<26;i++)   //checking residue
    {
        if(mapping[i]!=0)
            return 0;
    }


    return 1;
}//end of trav&chk

int main()
{
    char string1[15] = {'\0'};
    char string2[15] = {'\0'};

    gets(string1); fflush(stdin);
    gets(string2); fflush(stdin);

    mapFirst(&string1[0]);
    if(!traverseAndCheck(&string2[0]))
        printf("False");
    else
        printf("True");
    return 0;
}

- jaiwardhan.live August 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

if __name__=='__main__':
	string1="".replace(' ','')	#string1_Value
	string2="".replace(' ','')	#string2_Value
	
	dict={}
	for i in string1:
		if (dict.has_key(i)):
			dict[i]+=1
		else:
			dict[i]=1
	
        zeroValue=0
	isAnagram=True
	for j in string2:
		if dict.has_key(j):
			dict[j]-=1
			if dict[j]<zeroValue:
				isAnagram=False
				break
		else:
			isAnagram=False
			break
	print isAnagram

- Roopal Garg August 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

ALGO:
---------

Check if both the words belong in some dictionary. There can be a hash map of the dictionary. If there are multiple words, then a split operation might have to be performed on a predefined set of separators (e.g. ' ', ',', ':', ';' etc.)

Use an array of 256 for ascii characters.
1. Go through the first string and add 1 to the array[ascii index] for every character.
2. Go through the second string and add 1 to the array[ascii index] for every character.
If at the end, if all the values of the ascii array are even or 0 then we have an anagram. Else not.

One of the conditions might be, do not increment for special characters like space. This can be defined apriori.

- kepler-47 August 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Scanner;


public class Anagram {

	public static void main(String[] args) throws IOException {
		//Scanner a = new Scanner(System.in);
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String s1 = br.readLine();
		String s2 = br.readLine();
		
		if(s1.equals(s2))
			System.out.println("true");
		else{
			s1 = s1.replace(" ", "");
			s2 = s2.replace(" ", "");
			char c1[] = s1.toCharArray();
			char c2[] = s2.toCharArray();
			Arrays.sort(c1);
			Arrays.sort(c2);			
			if(new String(c1).equals(new String(c2)))
				System.out.println("true");
		}
		
		
	}

}

- Bala August 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package test;

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

/**
* @author p80025131
*
*/
public class Anagram {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner kb = new Scanner(System.in);
String firstString=kb.next();
String secondString=kb.next();
/* String firstString="vdlpeeeor";
String secondString="developer";*/
Boolean isSame = checkIdenticle(firstString,secondString);
if(isSame)
{
System.out.println("Yes, Both "+firstString+" and "+secondString+" are identicle");
}
else
{
System.out.println("No, Both "+firstString+" and "+secondString+" are not identicle");
}
}

public static boolean checkIdenticle(String firstString,String secondString)
{
Map <Character, Integer> collect= new HashMap<Character, Integer>();
for(int i=0;i<firstString.length();i++)
{
char ch= firstString.charAt(i);
if(collect.get(ch)!= null)
{
int counter = collect.get(ch);
++counter;
collect.put(ch,counter);

}
else
{
collect.put(ch,1);
}
}
for(int i=0;i<secondString.length();i++)
{
char ch= secondString.charAt(i);
if(ch == ' ')
continue;
if(collect.get(ch)== null)
{
return false;
}
else
{
int counter = collect.get(ch);
--counter;
if(counter==0)
{
collect.remove(ch);
}
else
{
collect.put(ch,counter);
}
}

}
if(collect.isEmpty())
return true;
return false;
}
}

- prashantdubey194 August 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static bool IsAnagram(string source, string target)
        {
            if (source == null || target == null)
                return false;
            Hashtable listOfChars = new Hashtable();

            foreach (char ch in source)
            {
                if (ch == ' ')
                    continue;
                
                if (listOfChars[ch] == null)
                   listOfChars.Add(ch,1);
                else
                {
                    int _cnt = (int)listOfChars[ch];
                    _cnt++;
                    listOfChars[ch] = _cnt;
                }
            }
            foreach (char ch in target)
            {
                if (ch == ' ')
                    continue;
                if (listOfChars[ch] == null)
                    return false;
                
                int _cnt = (int)listOfChars[ch];
                _cnt--;
                listOfChars[ch] = _cnt;
            }

            foreach (DictionaryEntry de in listOfChars)
            {
                if ((int)de.Value != 0)
                    return false;
            }

            return true;
        }

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

Guys its so simple. concatenate and XOR, Below is the code:
complexity O(n) time

public class GoogleAnagram {
public static void main(String args[])  {
	String S1= "conifers";//input strings
	String S2 = "fir cones";	
	System.out.println(strComapareAnagram(S1, S2));
}
public static boolean strComapareAnagram(String S1, String S2){
	String[] sArray = S1.replaceAll(" ", "").concat(S2.replaceAll(" ", "")).split("");
	int result =0;
	for (int i = 1; i < sArray.length; i++) {
		result ^= (int)sArray[i].codePointAt(0); 
	}	
	return (result ==0)?true:false;
}
}

}

- harsha August 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Modifying above code lil bit, we can avoid String array and concat operation. let me know if there is something wrong.

public class GoogleAnagram {

	public static void main(String args[]) {
		String S1 = "conifers";// input strings
		String S2 = "fir cones";
		System.out.println(strComapareAnagram1(S1, S2));
	}

	public static boolean strComapareAnagram1(String S1, String S2) {
		S1 = S1.replaceAll(" ", "");
		S2 = S2.replaceAll(" ", "");
		int result = 0;
		for (int i = 0; i < S1.length(); i++) {
			result = result ^ S1.charAt(i);
		}
		for (int i = 0; i < S2.length(); i++) {
			result = result ^ S2.charAt(i);
		}
		return (result == 0) ? true : false;
	}
}

- nIx September 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

What is your code doing?

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

I think this code is wrong.

Try:
s1=aa
s2=bb

You will get 0 even when they aren't anagrams

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

Java solution for ASCII characters, including a parameter to know if we accept space between words (e.g. isAnagram(“conifers”, “fir cones”) → true ) or not.

private static boolean isAnagramWithSpaceSaver(String text1, String text2, boolean acceptSpace) 
	{	
		if (!acceptSpace && text1.length() != text2.length()) {
			return false;
		} else if(acceptSpace && text1.length() > text2.length()) {
			// Count the letters of the smallest word first
			String temp = text1;
			text1 = text2;
			text2 = temp;
		}

		int[] lettersCount = new int[256]; // if ASCII

		for (int i = 0; i < text1.length(); i++) {
			lettersCount[text1.charAt(i)]++;
		}

		for (int i = 0; i < text2.length(); i++) {
			char c = text2.charAt(i);
			if (acceptSpace && c != ' ') {
				if (--lettersCount[c] < 0) {
					return false;
				}
			}
		}

		return true;
	}

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

Can do it in O(n), with no extra space used

bool IsAnagram(string s1, string s2)
        {
            if (s1.Length != s2.Length)
                return false;

            int sum = 0;
            for (int i = 0; i < s1.Length; i++)
            {
                sum = sum + s1[i] - s2[i];
            }
            if (sum == 0)
                return true;
            else
                return false;
        }

- vamsi September 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi, above code will fail since it will return 0 for following 2 strings although they are not anagrams:
string1 = abc
string2 = ada

- Coderbhaai November 27, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

EXPLAIN your ideas so the original poster gets some general technique from it.

Here is my line of thinking (not necessarily the best).
strings are just arrays of integers

If you want to compare two arrays of integers, how would you do it?
1) Brute force O(n^2).
Now you think of your brute force method and realize if the arrays were sorted you can linear check on both and see if each position matches.

What is the complexity of sorting?
Comparison sorts: O(n*lg(n))
Integer based sorts O(n+k) for k=max(int)
AHAAAA. At this point my lightbulb goes off, here k=fixed (it is 26 or however many characters in your alphabet).
Since each character is guaranteed to have a small range of integers, we can use a linear integer sorting algorithm!!

So let's do that:
Sort the first one using bucket/counting sort O(n)
Sort the second one using bucket/counting sort O(n)

Now linear scan from left to right checking each position O(n).
This takes O(n+k) extra space.

----- I can also think of a way to save A BIT MORE time doing the above, but who cares. ----

Hash table can be used IF you treat them with care (think about it, what if you have two strings "sssssssssssssssa" "assssssssssssss" .... usually Hash tables will perform badly in these cases and give O(n) lookup).

- bigphatkdawg September 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

No. Hash table stores the counts of each character. In the case of "sssssssssssssssa" "assssssssssssss" hash tables has only two entries (s, 14) and (a, 1). It will give O(1) lookup.

- sabz August 17, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

static bool IsAnagrams(string first, string second)
        {
            bool result = false;
            IDictionary<char, int> temp = new Dictionary<char, int>();

            foreach (char c in first)
            {
                if (temp.ContainsKey(c))
                    temp[c] = temp[c] + 1;
                else
                    temp.Add(c, 1);
            }

            foreach (char c in second)
            {
                if (temp.ContainsKey(c))
                {
                    temp[c] = temp[c] - 1;
                    if (temp[c] == 0)
                        temp.Remove(c);
                }
            }

            if (temp.Count == 0)
                result = true;

            return result;
        }

- sam September 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#!/usr/bin/env python

from collections import Counter
import string

def isAnagram(s1, s2):
    """
    > Counter("abc")
    Counter({'a': 1, 'c': 1, 'b': 1}

    >>> isAnagram("secure", "rescue")
    True

    >>> isAnagram("conifers", "fir cones")
    True

    >>> isAnagram("google", "facebook")
    False

    """

    allowed = set(string.ascii_letters + string.digits)

    clean_s1 = "".join([c for c in s1 if c in allowed]).lower()
    clean_s2 = "".join([c for c in s2 if c in allowed]).lower()

    return Counter(clean_s1) == Counter(clean_s2)

- anon October 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private static int GetCharSum(string str)
        {
            int sum = 0;
            foreach (var ch in str)
            {
                if (ch == ' ')
                    continue;
                sum += ch;
            }
            return sum;
        }

        public static bool IsAnagram(string one, string two)
        {          
            int oneSum = GetCharSum(one);
            int twoSum = GetCharSum(two);        
         
            if (oneSum == twoSum)
                return true;

            return false;
        }

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

public static boolean isAnagram (String str1,String str2){
		int [] dp = new int [26];
		for (int i =0 ; i < str1.length() ; ++i){
			if (Character.isAlphabetic(str1.charAt(i))){
				dp[str1.charAt(i)-'a']++;
			}
		}
		
		for (int i =0 ; i < str2.length() ; ++i){
			if (Character.isAlphabetic(str2.charAt(i))){
				dp[str2.charAt(i)-'a']--;
			}
		}
		
		for (int i =0 ;i<dp.length ;++i){
			if (dp[i]!=0) return false;
		}
		
		return true;

}

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

Here is my Ruby solution.

#!/usr/bin/env ruby

class String
  def anagram?(s)
    s1 = self.split("").sort.join.strip
    s2 = s.split("").sort.join.strip
    s1 == s2
  end
end
tests = [["secure", "rescue"],["conifers","fir cones"],["google","facebook"]]
tests.each do |test|
  s1,s2 = test
  puts "\"#{s1}\" <=> \"#{s2}\" are anagrams? #{s1.anagram?(s2)}"
end

- Byron Formwalt April 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Simple ruby solution:

# O(n)
def anagram? str1, str2
  str1, str2 = str1.gsub(' ', '').split('').sort.join, str2.gsub(' ', '').split('').sort.join
  str1 == str2 ? true : false
end

- VinceBarresi August 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

#Python 2.x code
def sortString(s):
m = list(s)
m.sort()
i = ""
for j in m:
i+=j
return j
str1 = raw_input()
str2 = raw _input()
if sortString(str1)==sortString(str2):
print "Anagram"#or True
else:
print "Not an anagram"

- Drj Reddy August 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

doesn't m.sort() use quicksort (with base cases using insertion sort) ??

The solution is good still, O(n*lg(n)).

Check python API if counting/bucket sort exist (or if they use a linear sort for strings).

- bigphatkdawg September 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

We can also sort the two strings and then see if they are the same. KMP runs in O(n) time and O(n) space.

- Anonymous August 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

If they are sorted, just scan left to right and check
for (i ..)
if A[i]==B[i] return false;

- bigphatkdawg September 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Method 1:
--------------
For O(N) complexity use hashmap or binary search tree

Method 2:
--------------
For O(NLOGN) complexity sort both the strings and traverse both the strings one by one . If at any index if both are not equal then return false else return true

bool CheckWhetherTwoStringsAreAnagramsONLOGN(char *userInput1,char *userInput2){
	if(userInput1 == NULL && userInput2 == NULL){
		return true;
	}
	if(userInput1 == NULL || userInput2 == NULL){
		return false;
	}
	if(strlen(userInput1) != strlen(userInput2)){
		return false;
	}
	sort(userInput1,strlen(userInput1));
	sort(userInput2,strlen(userInput2));

	for(int counter = 0;counter < strlen(userInput1);counter++){
		if(userInput1[counter] != userInput2[counter]){
			return false;
		}
	}
	return true;
}

Method 3:
--------------
For O(N^2) use two loops

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

Method 3 should be the first one tha twe think of in any situation (always good to come up with a solution).

Method 2 is good. But you can use a linear sort if the alphabet size is fixed.

Method 1... Hash map will degrade very fast because strings tend to have a lot of repeat characters relative to the range of characters is low. meaning load ratio might be too high to consider it O(1).

Can you explain the BST method? How is O(n) for using BST? Inserting n items to build a BST is O(n^2) worst case. A redblack tree is O(n*lgn) to build it.

- bigphatkdawg September 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

#Author : A.Nasimunni

#This programme takes O(1) complexity

n=raw_input(" \n\tEnter your string : ");
n2=raw_input(" \n\tEnter your checking word : ");
d=sorted(n2)
c=sorted(n)
if d==c:
print "\n\t True\n\n"
else:
print"\n\t false\n\n"

- A.Nasimunni August 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

#Author : A.Nasimunni

#This programme takes O(1) complexity

n=raw_input(" \n\tEnter your string : ");
n2=raw_input(" \n\tEnter your checking word : ");
d=sorted(n2)
c=sorted(n)
if d==c:

print "\n\t True\n\n"

else:

print"\n\t false\n\n"

- A.Nasimunni August 26, 2013 | 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