Interview Question
Country: India
Interview Type: In-Person
We can use constant space for hash implementation, using as much space as the domain of character of Strings. If they are represented using only 1 byte, we can use 2 ^ 8 size array, which is constant. Even if the character domain changes, we can allocate 2 ^ (8 * sizeof( character type)) and use general hash procedure, with hash function H(key) = key.
@suryaamsh: you are correct. btw. can't we use XOR operator. My idea is as below.
I'll do the XOR of both the strings. Next i'll select one of the strings to pick the characters one by one. each time i pick a character i'll do a XOR of character with both strings if both results are equal then i can say i pick a character that is common in both strings. I'll continue this approach and if i pick all the characters then i'll say they are anagrams else they are not.
Example :
string 1 : abcdabc = a+b+c+d+a+b+c
string 2 : acbdcba = a+c+b+d+c+b+a
Now i'll pick characters from string 2 and do XOR with both the strings.
result 1 : a+b+c+d+a+b+c XOR a
and
result 2 : a+c+b+d+c+b+a XOR a
if the result 1 and result 2 are equal then i'll continue with result 1 and result 2 as new strings and pick next character from string 2. if the result 1 and result 2 are not equal then i'll stop and say they are not anagrams.
Please provide me the counter-example if my approach is wrong in anyway.
XOR approach may give false positives. Here is a counter example for XOR approach:
aaaabb
aabbbb
xor will give zero and will say that these are anagrams because a's within a string cancel each other.
Assign every alphabet a prime number. For eg- a=2, b=3, c=5 and so on. For both the strings calculate the product of the prime representation of every number. If the product is equal, they are anagrams.
string1 = abc=2*3*5=30
string2 = bca=3*5*2=30
so they are anagrams.
Prime nos can be calculated using seive method.
Time- O(n)
Space- O(1)
Hope that'll do.
I am sure that it will work. I was talking about the space complexity. Take any example to check that. Product is associative is the whole idea behind it!
Thats a nice and unique approach and this will work too. Only gap I see here is you probably have to calculate atleast 26 first prime number of if number are allowed in the string then 36 and if its case sensitive then 62. Now we must have these prime number already populated. Or if we try to generate at run time, that going to be overhead in the algo.
@neo Is O(nlog log n) very high, where n=62? Sieve method can find primes in a good time. If tim is an issue, we can use Sieve of Atkins. Please let me know if I am wrong.
@neo, theoretically, the rime numbers should be already populated. Since number of numerics are fixed and independent on length of string, theoretically, its O(1). The runtime of algorithm, theoretically is O(n). But yeah, practically infeasible.
@alex suppose the length of string is above 1000+ ,
Then how will you store its value ?? Storing those values cannot be done in O(1) space complexity.
The idea you gave is very good.
This approach is different from conventional one, Thanks for it.
There is another limitation imposed on this approach.Assuming the prime numbers are generated before hand, the algorithm's reach is limited by the capacity of the datatype to store the multiplication. If there is an overflow during multiplication, surely the results are prone to error. I am not sure of the exact String-length that it can support if we use long long but I suppose it will not be very large, as the prime numbers grow at nearly exponential rate.
Take a variable int a=0; now for each character of string1 set the correponding bit position of a (i.e. if string1[0] = 'b' then set second bit of a to 1) .
Now for each character of the second string check if corresponding bit position is set in a; if not then return false.
The short not going to accommodate 26 bits and in worst case it may need upto 62 bits or more.
@abyrupus got it...i think we have to take an arr[26] and for each character of string1 do as : arr[(string1[i]-'a')%26]++....and for string2 do as :arr[(string1[i]-'a')%26]-- in a sinle loop.. if the final arr[26] have all zero the return TRUE else FALSE..
*assuming both strings have only a-z character
- sort both strings
- compare character by character, if all characters are same return true, otherwise return false
You are upvoting yourself. Votes need to be based on the content, not the person. Surely you are BIOSed? ;-)
yes it is nlogn in time complexity.. but I think you can use counting or bucket sort if you know the range of alphabets.
The alphabet size is usually considered a constant.
Since you want Theta(n) with constant space, you can loop through all characters of the alphabet and count the number of occurrences in each string. The running time is Theta(n*alphabet_size) = Theta(n), under the above assumption, and this uses constant space.
We can use XOR to solve this
1st Remove all the 0's from both the array O(n)
Take XOR of first and then second array.
Compare if their XOR's are equal.
Form a hash map using the first string and try and match the second string with it.
- alex January 29, 2013