Super Secret Interview Question

Jeez, thats an easy one, write the stuff down on a sheet of paper.

Ball the paper up and hand it to Mars, then inform him where and how deep to insert it.

Next.

I truely can't wait to see the answer :-)

indeed an interesting question

That's actually pretty easy. Here's my solutions:

int StringVal(const char * buf) {

    int result = 0;

    

    while(*buf != 0) {

        result = result * 10 + (*buf - 48);

        

        buf = buf + 1;

    }

    

    return result;

}

and for parts 2 and 3:

int StringVal2(const char * buf) {

    int result = 0;

    int seenEnd = 0;

    

    seenEnd = seenEnd || *buf == 0;

    result = seenEnd ? result : *buf - 48;

    buf = buf + 1;

        

    seenEnd = seenEnd || *buf == 0;

    result = seenEnd ? result : result * 10 + (*buf - 48);

    buf = buf + 1;

    

    seenEnd = seenEnd || *buf == 0;

    result = seenEnd ? result : result * 10 + (*buf - 48);

    buf = buf + 1;

    

    seenEnd = seenEnd || *buf == 0;

    result = seenEnd ? result : result * 10 + (*buf - 48);

    buf = buf + 1;

    

    seenEnd = seenEnd || *buf == 0;

    result = seenEnd ? result : result * 10 + (*buf - 48);

    buf = buf + 1;

    

    seenEnd = seenEnd || *buf == 0;

    result = seenEnd ? result : result * 10 + (*buf - 48);

    buf = buf + 1;

    

    seenEnd = seenEnd || *buf == 0;

    result = seenEnd ? result : result * 10 + (*buf - 48);

    buf = buf + 1;

    

    seenEnd = seenEnd || *buf == 0;

    result = seenEnd ? result : result * 10 + (*buf - 48);

    buf = buf + 1;

    

    seenEnd = seenEnd || *buf == 0;

    result = seenEnd ? result : result * 10 + (*buf - 48);

    buf = buf + 1;

    

    seenEnd = seenEnd || *buf == 0;

    result = seenEnd ? result : result * 10 + (*buf - 48);

    

    return result;

}

StringVal2 is based on the return type being a signed integer -- the max number of digits for a signed integer is 10, so it occurs 10 times.

I'm very curious if there's a better solution, which I imagine there must be.

Your solution won't work for #3 -- remember, you're not allowed to use flow control constructs. So ?: tertiary operator is out. Also, it's a very inefficient solution for #2.

Here's a #2 that only solves what's required for #2:

void InternalStringVal(const char * buf, int * result) {

	if(*buf == 0)

		return;

	

	*result = *result * 10 + (*buf - 48);

	InternalStringVal(buf + 1, result);

}

int StringVal2(const char * buf) {
int result = 0;
InternalStringVal(buf, &result);

return result;
}

and #3, this time without the tertiary operator:

int StringVal3(const char * buf) {

    int result = 0;

    int seenEnd = 0;

	

    seenEnd = seenEnd || *buf == 0;

	result = result * seenEnd + !seenEnd * (*buf - 48);

    buf = buf + 1;

		

    seenEnd = seenEnd || *buf == 0;

	result = result * seenEnd + !seenEnd * (10 * result + *buf - 48);

    buf = buf + 1;

seenEnd = seenEnd || *buf == 0;
result = result * seenEnd + !seenEnd * (10 * result + *buf - 48);
buf = buf + 1;

seenEnd = seenEnd || *buf == 0;
result = result * seenEnd + !seenEnd * (10 * result + *buf - 48);
buf = buf + 1;

seenEnd = seenEnd || *buf == 0;
result = result * seenEnd + !seenEnd * (10 * result + *buf - 48);
buf = buf + 1;

seenEnd = seenEnd || *buf == 0;
result = result * seenEnd + !seenEnd * (10 * result + *buf - 48);
buf = buf + 1;

seenEnd = seenEnd || *buf == 0;
result = result * seenEnd + !seenEnd * (10 * result + *buf - 48);
buf = buf + 1;

seenEnd = seenEnd || *buf == 0;
result = result * seenEnd + !seenEnd * (10 * result + *buf - 48);
buf = buf + 1;

seenEnd = seenEnd || *buf == 0;
result = result * seenEnd + !seenEnd * (10 * result + *buf - 48);
buf = buf + 1;

seenEnd = seenEnd || *buf == 0;
result = result * seenEnd + !seenEnd * (10 * result + *buf - 48);

return result;
}

It's faster to bit-wise OR an ASCII numeric character with 0x0F to get it's numeric value than it is to subtract 48. Also, the use of the pow function saves you from multiplying the same number by 10 more than once.

In regards to question 2, looping is out, but recursion isn't mentioned. Or is recursion considered looping? I would think it is.

Too bad on the no-assembly rule - that excludes some really cool BCD instructions. However, converting BCD to binary can be done with a lookup table - quick adds versus costly multiplies.

Not sure what got me on the BCD tangent, so please ignore the BCD tangent.

I presume for #2 and #3 you are allowed to my favorite: 'goto' :-)

@talk2sk -- nope, goto is considered a looping mechanism (as far as a compiler is concerned). It's the same way the compiler implements things like a while/wend loop.

@Anon #1 -- that's a creative solution, but not the one I had in mind (it doesn't scale well, and if we were to add error checking back in, becomes rather hard).

@Anon #2 -- recursion isn't considered a looping construct because it's merely method calling. From the compiler's perspective, it can't tell the difference between a recursive call and a non-recursive one.

Thanks for revealing the question :)
Would be tough enough on paper, but put on the spot...I definitely wouldn't do well with that kind of stuff.

Anon1 was me.

@Anon2: I think you meant bitwise AND against the value instead of OR...

@Chad -- #1 and #2 weren't hard because I was expecting something like that. And I really was just required to talk my ideas through. #3 was what really threw me for a loop because I was only anticipating the first two (an iterative function and a recursive function).

Oh, right - that question. It is awfully clever, but I can't take the credit; it was one of the questions I got when I interviewed at Real Networks.

It's a good question and does force you to think laterally on the spot IF you've not been forwarned.

#1 and #2 were pretty straight forward with #1 a simple loop and some simple operations

#2 I figured for a head recursive function.

#3 I spent a bit of time pondering but not too much