I've done it on my computer. Clearly it works, but without a computer at hand, I am pretty sure I would have made many errors. For example initialize strsize to 1 instead of 0 (in order to add the '\0' at the end of the string).

I believe it is far harder than one could imagine, even more if you are nervous during the interview.

Why not just a binary search. I remember an article claiming 90% of engineer can't write it without bug.

I personnaly asked simply to write a function foo(c,string) (in any language) such that if the string contain the character c, then it returns true. And even with a question as simple as that I had more error I could have imagined.

char itoa(int i) { int strsize; int tmp; char res; int j;

    if (i==0) return "0";

    // allocate the right size
    strsize=0;
    if (i<0) strsize++;
    tmp=i>0?i:-i;
    while (tmp > 0) {
        strsize++;
        tmp /= 10;
    }
    res=(char *)malloc(strsize);

    // write the values
    j=strsize;
    res[j]='\0';
    if (i<0) {
        i=-i;
        res[0]= '-';
    }
    while (i != 0) {
        // printf(".%d(%c)", j, '0'+i%10);
        res[--j] = '0' + i%10;
        i/=10;
    }
    return res;
}