Sunday, January 22, 2012

Swap words in text w/o additional memory

Yesterday I saw an interview-problem from our C-team:

Revert words-order in text no using additional memory

For example, string
"Fedora Project promotes internet freedom" should be translated to
"freedom internet promotes Project Fedora" [nice semantic palindrome, isn't it? :-)].

Doesn't looks hard, but the only solution I found is to inverse all text, and then inverse each word.

#include <stdio.h>
#include <string.h>

/* invert characters in range [beg; end) */
inline void inv(char *beg, char *end)
{
    end--;
    while(beg < end) {
        char c = *beg;
        *beg++ = *end;
        *end-- = c;
    }
}

int main(int argc, char *argv[])
{
    char *s = argv[1], *beg = s, *end = strchr(s, '\0');

    inv(beg, end);

    beg = s;
    while(*beg)
    {
        end = strchr(beg, ' ') ? : strchr(beg, '\0');
        inv(beg, end);
        beg = end + 1;
    }

    printf("%s\n", s);
    return 0;
}
The problem is we have to scan string twice. Maybe there is a better (by-algo, not especially by-speed) solution?
BTW, nice construction which is used everywhere in Linux kernel
x = y ? : z; // equals to "if(y) x = y; else x = z;"

No comments:

Post a Comment