Re: Microsoft Interview Questions


Patricia Shanahan wrote:
stdazi@xxxxxxxxx wrote:
Q2) What is an efficient way to determine whether a string is a
permutation of another string? What is your run time?

damn i forgot.. another method would be to use XOR and apply it to some
integer for each char of the two strings (presuming that the char value
can be casted to an integer tipe...) like that :

4 int isperm(char *s1, char *s2) {
5
6 int retval = 0;
7
8 while (*s1 || *s2) {
9 retval ^= *s1 ^ *s2 ;
10 ++s1; ++s2;
11 }
12 return retval || (*s1 != *s2);
13 }

this is a O(n) algorithm where n is the lenght of the "shortest" string.


The code suggests that you are assuming zero-terminated strings. Under
that assumption, it appears to me to test two conditions:

1. Are the two strings the same length?

2. Let X_n be the number of 1 bits in bit position n in s1, and Y_n be
the number of 1 bits in bit position n in s1. For each bit position, is
(X_n - Y_n) even?

Both conditions are true if they are permutations of each other.
However, there are many pairs of strings that are not permutations but
that would pass those tests. For example:

int main(argc,argv) int argc; char *argv[];{
printf("%d\n",isperm("AB","BA"));
printf("%d\n",isperm("AA","BB"));
}
you are completely right! i knew there was some issue with that method
but couldn't find a counter example. So i pasted the code in hope there
is nothing wrong with it :-)

why is the first case (AB, BA) not a permutation?

.

Relevant Pages

  • Re: Compare permutations
    ... \ FORTH> permtest (short strings, ... permutation comparisons returns false. ... During the pass through the second string if any count goes negative ... This also means that summing of the characters is ...
    (comp.lang.forth)
  • Re: Sabermetrics goes mainstream, part 2384
    ... many strings are unique. ... K 'L', handing off each string to the Canonical Permutation Generator, ... put in the extra work on the random distribution to keep it from ... Possibly the worst sorting algorithm around. ...
    (rec.sport.baseball)
  • Re: Microsoft Interview Questions
    ... Are the two strings the same length? ... why is the first case not a permutation? ... Zero might have implied "false". ... Just obtaining the answer for a non-permutation would not have proved ...
    (comp.theory)
  • Re: Which checksums/hashes do not have any internal cycles?
    ... Let's consider the 32-bit CRC as a mapping of all four byte long strings ... calculating a checksum in order to take this value as input for ... (a piece of data, when processed, results in a particular permutation). ...
    (comp.compression)
  • Re: Compare permutations
    ... str1 COUNT str3 COUNT permutation? ... \ FORTH> permtest (short strings, ... Testing permutation? ...
    (comp.lang.forth)