Google Interview Question
Software Engineer in TestsCountry: United States
Interview Type: Phone Interview
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;
}
}
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;
}
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.
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.
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;
}
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;
}
#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;
}
//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;
}
}
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;
}
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;
}
* 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;
}
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
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.
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");
}
}
}
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;
}
}
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;
}
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;
}
}
}
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;
}
}
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;
}
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;
}
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).
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;
}
#!/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)
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;
}
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;
}
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
#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"
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.
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
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.
This complexity is O(n) for this program.
- Anand August 15, 2013I 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;
}