Re: Microsoft Interview Questions

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"));
}

int isperm(char *s1, char *s2) {

int retval = 0;

while (*s1 || *s2) {
retval ^= *s1 ^ *s2 ;
++s1; ++s2;
}
return retval || (*s1 != *s2);
}

prints "0" for both tests.

Patricia
.

Relevant Pages

  • Re: print all permutations of string
    ... VAR tmp: CHAR; ... it *does* print all permutations... ... it handles only strings with distinct characters. ... void print_perms(char *s, int n) ...
    (comp.programming)
  • Re: Sets and portability (was) Re: Is ISO Pascal compatible with J&W (original) Pascal ?
    ... strings, the user can control the length by the data they process; ... >> The computer world is more complex than it's ever been (eg Unicode) ... The Pascal `Char' type can be this size (unlike C, ... > Note that ansi->wide conversion is codepage sensitive. ...
    (comp.lang.pascal.misc)
  • Re: socket communication: send & receive doesnt work right
    ... But can I actually send and receive strings? ... I did a test of sending two doubles: ... public void send_doubles(double vals, int len) throws ... char *result; ...
    (microsoft.public.win32.programmer.networks)
  • Re: Efficient strcat implementation.
    ... Programmers using the `strcat' or `wcscat' function (or the ... /* This function concatenates arbitrarily many strings. ... concat (const char *str, ...) ... if (newp == NULL) ...
    (comp.lang.c)
  • Re: Replacing a word in a string
    ... original for large strings with many small replacements. ... * strend and tokend must point to the last char before the terminating nul, ... const char *p, *q; ...
    (comp.lang.c)