Re: Microsoft Interview Questions

stdazi@xxxxxxxxx wrote:
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?


It is a permutation. The point is that I got the same return value,
zero, from isperm for both a permutation pair and a non-permutation
pair, demonstrating failure to distinguish them.

Remember there was no comment or specification to indicate how to map
the integer result to a true/false answer to the "are they
permutations of each other?" question. Zero might have implied "false".
Just obtaining the answer for a non-permutation would not have proved
much.

Patricia
.

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: 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)
  • Re: AES 256 key and anti-key
    ... So there are much more permutations than keys. ... mapping of the character set of 128 bit characters to a permutation of ... permutation, then the probability that a two ... ZERO chance of two keys producing the same permutation. ...
    (sci.crypt)